《数据结构ADT》由会员分享,可在线阅读,更多相关《数据结构ADT(6页珍藏版)》请在金锄头文库上搜索。
1、/*DynaSeqList.cpp - 动态顺序表,即顺序表的动态数组实现*题目:实验-1 线性表的动态顺序存储实现*/#include #include #include #include #include DynaSeqList.hconst int LIST_INIT_SIZE = 100;/ 表初始分配的最大长度const int LISTINCREMENT = 10;/ 分配存的增量/*-操作目的:初始化顺序表初始条件:无操作结果:构造一个空的线性表函数参数:SqList *L待初始化的线性表返回值:bool操作是否成功-*/bool InitList(SqList *L)asser
2、t(L != NULL);L-elem = (ElemType*)malloc(sizeof(ElemType) * LIST_INIT_SIZE);if(L-elem = NULL) return false;L-length = 0;L-listsize = LIST_INIT_SIZE;return true;/*-操作目的:销毁顺序表初始条件:线性表L已存在操作结果:销毁线性表L函数参数:SqList *L待销毁的线性表返回值:无-*/void DestroyList(SqList *L)assert(L != NULL);free(L-elem);L-elem = NULL;/*-操
3、作目的:判断顺序表是否为空初始条件:线性表L已存在操作结果:若L为空表,则返回true,否则返回false函数参数:SqList L待判断的线性表返回值:bool是否为空-*/bool ListEmpty(SqList L)assert(L.elem != NULL);return(L.length = 0);/*-操作目的:得到顺序表的长度初始条件:线性表L已存在操作结果:返回L中数据元素的个数函数参数:SqList L线性表L返回值:int数据元素的个数-*/int ListLength(SqList L)assert(L.elem != NULL);return L.length;/*-
4、操作目的:得到顺序表的第i个元素初始条件:线性表L已存在,=i=ListLength(L)操作结果:用e返回L中第i个数据元素的值函数参数:SqList L线性表L int i数据元素的位置 ElemType *e第i个数据元素的值返回值:bool操作是否成功-*/bool GetElem(SqList L, int i, ElemType *e)assert(L.elem != NULL);if(iL.length) return false;*e = L.elemi-1;return true;/*-操作目的:得到顺序表指定元素的位置初始条件:线性表L已存在操作结果:返回L中第一个与e满足
5、关系compare()的数据元素的位序。若这样的元素不存在则返回。函数参数:SqList L线性表L ElemType e 数据元素eInt (*fp)()用于比较相等的函数指针返回值:int与e满足关系compare()的数据元素的位序-*/int LocateElem(SqList L, ElemType e, int (*fp)(ElemType, ElemType)assert(L.elem != NULL);int i = 0;for(i=0; iL.length & (*fp)(e, L.elemi) != 0); i+);return (i+1)%(L.length+1);/*-
6、操作目的:得到顺序表指定元素的前驱初始条件:线性表L已存在操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义函数参数:SqList L线性表LElemType cur_e数据元素cur_eElemType *pre_e前驱数据元素返回值:bool操作是否成功-*/bool PriorElem(SqList L, ElemType cur_e, ElemType *pre_e)assert(L.elem != NULL);int pos = LocateElem(L, cur_e, compare);if(posL.length-1)r
7、eturn false;*nxt_e = L.elempos;return true;/*-操作目的:遍历顺序表初始条件:线性表L已存在操作结果:依次对L的每个元素调用函数fp函数参数:SqList L线性表Lvoid (*fp)()访问每个数据元素的函数指针返回值:无-*/void ListTraverse(SqList L, void (*fp)(ElemType)assert(L.elem != NULL) & (fp != NULL);for(int i=0; ielem != NULL);L-length = 0;/*-操作目的:在顺序表的指定位置插入结点,插入位置i表示在第i个元素
8、之前插入初始条件:线性表L已存在,=ielem != NULL);if(iL-length+1)return false;if(L-length = L-listsize)int newsize = L-listsize + LISTINCREMENT;ElemType *newbase = (ElemType*)malloc(sizeof(ElemType) * newsize);if(newbase = NULL)return false;memcpy(newbase, L-elem, _msize(L-elem);free(L-elem);L-elem = newbase;L-listsize = newsize;int j = 0;for(j=L-length; j=i; j-)L-elemj = L-elemj-1;L-elemj = e;L-length+;return true;/*-