2.2-C中的动态分配与释放函数 2.2一基本操作的实现（宏与Status) C中的动态分配与释放函数 ■基本操作的实现 void *malloc(unsigned int size) P10 生成一大小为s立的站点空间，将被空间的起地 地址赋给p: /体函数结果状春代码 #define TRUE 1 free(void *p) 回收p所指询的结点空间： #define FALSE #define OK 1 void *realloc(void *p,unsigned int size) #define ERROR 0 特p所指向的已分配内存区的大小改为size,size #define INFEASIBLE -1 分配失败示 可以比原分乖的空间大或小。 #define OVERFLOW -2 条温 /体函数结果状态类型，其值为上述的状本代码 typedef int Status; 172 囵 20y3 图 2.2-基本操作的实现(InitList_Sq) 主2.2-基本操作实现(LocateElem-.s)刘 ■基本操作的实现 ■基本操作的实现 ,°化Status InitList_Sq(SqList&L) ,求表长L.length Status InitList_Sq(SqList &L){ ∥构造一个空的线性表L ,取第i个元素L.elem[i-1](0<i<L..length-+1) Lelem=(ElemType") 。按值查找 malloc(LIST_INIT_SIZE'sizeof(ElemType)); int LocateElem_Sq(SqList L,ElemType e, if (L.elem =NULL) exit(OVERFLOW); Ⅱ存储分配失败 Status("compare)(ElemType,ElemType)) L.length=0; Ⅱ空表长度为0 for(i=0;i<Llength &&!(compare)(L.elem[i],e);i++); Llistsize=LIST_INIT_SIZE; ∥初始存偏容量 if (i<L.length)returni+1; return OK; else return 0; }HIni混ist Sq 21/73 图 22/73 图 2.2-插入操作的实现 2.2-插入操作的实现（分析设计） 。基本操作的实现 ,插入操作—算法设计（算法2.4） ■插入操作 ·最：顺序表&L、领入位量、指入元廉： Status ListInsert Sq(SqList &L,int i,ElemType e) 播入分析： 12345678 15234616571064.. 后移的序是从录后一个元震开地，毫个住后移 for(j=Llength;j>=子-L.e4em0]=L.elem-1j/∥盾w 入e L.eemt-1】=ei/算个元常存放在L.elem[i-1]中，胞地下标为0 L.length Llength+1; 48y 123456789 ,法的位置：i1L.length+1 。上滥及处理： 1523464816571064 。上提搜生的条并：LlengthL.lists位e, 22/7万 图19/73 2.2 –C中的动态分配与释放函数 „ C中的动态分配与释放函数 „ void *malloc(unsigned int size) 生成一大小为size的结点空间，将该空间的起始 地址赋给p； „ free(void *p) 回收p所指向的结点空间; „ void *realloc(void *p, unsigned int size) 将p所指向的已分配内存区的大小改为size，size 可以比原分配的空间大或小。 old p 返回 空间不够, NULL 分配失败! 分配失败示例 20/73 2.2 –基本操作的实现(宏与Status) „ 基本操作的实现 P10 /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /* 函数结果状态类型，其值为上述的状态代码 */ typedef int Status; 21/73 2.2 –基本操作的实现(InitList_Sq) „ 基本操作的实现 „ 初始化 Status InitList_Sq(SqList &L) Status InitList_Sq( SqList &L) { // 构造一个空的线性表L L.elem = (ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType)); if ( L.elem == NULL ) exit(OVERFLOW); // 存储分配失败 L.length = 0; // 空表长度为0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq 22/73 2.2 –基本操作实现(LocateElem_Sq) „ 基本操作的实现 „ 求表长 L.length „ 取第i个元素 L.elem[i-1] (0<i<L.length+1) „ 按值查找 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { for(i=0; i<L.length && !(*compare)(L.elem[i],e); i++); if (i<L.length) return i+1; else return 0; } 23/73 2.2 –插入操作的实现 „ 基本操作的实现 „ 插入操作 Status ListInsert_Sq(SqList &L, int i, ElemType e) 15 23 46 16 57 10 64 …… 1 2 3 4 5 6 7 8 48 插入 e 0 1 2 3 4 5 6 7 i 15 23 46 16 57 10 64 …… 1 2 3 4 5 6 7 8 9 48 24/73 2.2 –插入操作的实现(分析设计) „ 插入操作——算法设计(算法2.4) „ 参数：顺序表&L、插入位置i、插入元素e „ 插入分析： „ 第i个位置放e，则原来第i~L.length个数据元素必须先后移，以腾出 第i个位置; „ 后移的顺序是从最后一个元素开始，逐个往后移 for ( j = L.length; j >= i; j--) L.elem[j] = L.elem[j-1]; // 后移 L.elem[i -1] = e; //第i个元素存放在L.elem[i-1]中，起始下标为0 L.length = L.length+1; „ 合法的位置：i:1..L.length+1 „ 上溢及处理： „ 上溢发生的条件：L.length≥L.listsize， „ 处理：先申请一个有一定增量的空间：申请成功则原空间的元素复制 到新空间，修改L.listsize，再进行插入工作；否则报错退出