存储结构

/* 线性表的动态分配顺序存储结构 */#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */#define LIST_INCREMENT 2 /* 线性表存储空间的分配增量 */typedefstruct{ElemType*elem;/* 存储空间基址 */intlength;/* 当前长度 */intlistsize;/* 当前分配的存储容量(以sizeof(ElemType)为单位) */}SqList;

基本操作

/* 顺序表示的线性表的基本操作(12个) */voidInitList(SqList*L)/* 算法2.3 */{/* 操作结果：构造一个空的顺序线性表L */L->elem=malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L->elem)exit(OVERFLOW);/* 存储分配失败 */L->length=0;/* 空表长度为0 */L->listsize=LIST_INIT_SIZE;/* 初始存储容量 */}voidDestroyList(SqList*L){/* 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L */free(L->elem);L->elem=NULL;L->length=0;L->listsize=0;}voidClearList(SqList*L){/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */L->length=0;}StatusListEmpty(SqListL){/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */if(L.length==0)returnTRUE;elsereturnFALSE;}intListLength(SqListL){/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */returnL.length;}StatusGetElem(SqListL,inti,ElemType*e){/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值 */if(iL.length)returnERROR;*e=*(L.elem+i-1);returnOK;}intLocateElem(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){/* 初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) *//* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 *//* 若这样的数据元素不存在，则返回值为0。 */ElemType*p;inti=1;/* i的初值为第1个元素的位序 */p=L.elem;/* p的初值为第1个元素的存储位置 */while(i<=L.length&&!compare(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}StatusPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e){/* 初始条件：顺序线性表L已存在 *//* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， *//* 否则操作失败，pre_e无定义 */inti=2;ElemType*p=L.elem+1;while(iL.length)returnINFEASIBLE;/* 操作失败 */else{*pre_e=*--p;returnOK;}}StatusNextElem(SqListL,ElemTypecur_e,ElemType*next_e){/* 初始条件：顺序线性表L已存在 *//* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， *//* 否则操作失败，next_e无定义 */inti=1;ElemType*p=L.elem;while(i<L.length&&*p!=cur_e){i++;p++;}if(i==L.length)returnINFEASIBLE;/* 操作失败 */else{*next_e=*++p;returnOK;}}StatusListInsert(SqList*L,inti,ElemTypee){/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1 *//* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ElemType*newbase,*q,*p;if(iL->length+1)/* i值不合法 */returnERROR;if(L->length>=L->listsize)/* 当前存储空间已满,增加分配 */{newbase=realloc(L->elem,(L->listsize+LIST_INCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);/* 存储分配失败 */L->elem=newbase;/* 新基址 */L->listsize+=LIST_INCREMENT;/* 增加存储容量 */}q=L->elem+i-1;/* q为插入位置 */for(p=L->elem+L->length-1;p>=q;--p)/* 插入位置及之后的元素右移 */*(p+1)=*p;*q=e;/* 插入e */++L->length;/* 表长增1 */returnOK;}StatusListDelete(SqList*L,inti,ElemType*e){/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) *//* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */ElemType*p,*q;if(iL->length)/* i值不合法 */returnERROR;p=L->elem+i-1;/* p为元素的位置 */*e=*p;/* 元素的值赋给e */q=L->elem+L->length-1;/* 表尾元素的位置 */for(++p;plength--;/* 表长减1 */returnOK;}voidListTraverse(SqListL,void(*vi)(ElemType*)){/* 初始条件：顺序线性表L已存在 *//* 操作结果：依次对L的每个数据元素调用函数vi() *//* vi()的形参加"&"，表明可通过调用vi()改变元素的值 */ElemType*p;inti;p=L.elem;for(i=1;i<=L.length;i++)vi(p++);printf("\n");}

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。