《顺序表的动态链式存储实现.doc》由会员分享，可在线阅读，更多相关《顺序表的动态链式存储实现.doc（11页珍藏版）》请在金锄头文库上搜索。
1、顺序表的动态链式存储实现/*DynaLnkList.cpp - 动态链表，即顺序表的动态链式存储实现*题目：实验2-2 线性表的动态链式存储实现*班级：6*姓名：王政*学号：2012012001*/#include #include #include #include #include DynaLnkList.h/*-操作目的：初始化链表初始条件：无操作结果：构造一个空的线性表函数参数：LinkList *L待初始化的线性表返回值：bool操作是否成功-*/bool InitList(LinkList *L)/ L(头指针的地址)if(*L = (LinkList)malloc(sizeof(
2、LNode) = NULL)return false;(*L)-next = NULL;return true;/*-操作目的：销毁链表初始条件：线性表L已存在操作结果：销毁线性表L函数参数：LinkList *L待销毁的线性表返回值：无-*/void DestroyList(LinkList *L)LinkList tmp;while(*L != NULL)tmp = (*L)-next;free(*L);*L = tmp;/*-操作目的：判断链表是否为空初始条件：线性表L已存在操作结果：若L为空表，则返回true，否则返回false函数参数：LinkList L待判断的线性表返回值：boo
3、l是否为空-*/bool ListEmpty(LinkList L)assert(L != NULL);return(L-next = NULL);/*-操作目的：得到链表的长度初始条件：线性表L已存在操作结果：返回L中数据元素的个数函数参数：LinkList L线性表L返回值：int数据元素的个数-*/int ListLength(LinkList L)assert(L != NULL);int n = 0;for(; L != NULL; n+, L = L-next);return n-1;/*-操作目的：得到链表的第i个元素初始条件：线性表L已存在，1=i=ListLength(L)操
4、作结果：用e返回L中第i个数据元素的值函数参数：LinkList L线性表Lint i数据元素的位置ElemType *e第i个数据元素的值返回值：bool操作是否成功-*/bool GetElem(LinkList L, int i, ElemType *e)assert(L != NULL);if(iListLength(L)return false;for(int n=0; nnext);*e = L-data;return true;/*-操作目的：得到链表指定元素的位置初始条件：线性表L已存在操作结果：返回L中第一个与e满足关系compare()的数据元素的位序。若这样的元素不存在则
5、返回0。函数参数：LinkList L线性表LElemType e数据元素eint (*fp)()用于比较相等的函数指针返回值：int与e满足关系compare()的数据元素的位序-*/int LocateElem(LinkList L, ElemType e, int (*fp)(ElemType, ElemType)assert(L != NULL);int n = 0;for(; L-next != NULL & (*fp)(e, L-data)!=0; n+, L = L-next);return (L-next = NULL & (*fp)(e, L-data)!=0) ? 0: n
6、;/*-操作目的：得到链表指定元素的前驱初始条件：线性表L已存在操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义函数参数：LinkList L线性表LElemType cur_e数据元素cur_eElemType *pre_e前驱数据元素返回值：bool操作是否成功-*/bool PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e)assert(L != NULL);int pos = LocateElem(L, cur_e, compare);if(posListLength
7、(L)-1)return false;GetElem(L, pos+1, nxt_e);return true;/*-操作目的：遍历链表初始条件：线性表L已存在操作结果：依次对L的每个元素调用函数fp函数参数：LinkList L线性表Lvoid (*fp)()访问每个数据元素的函数指针返回值：无-*/void ListTraverse(LinkList L, void (*fp)(ElemType)assert(L != NULL);for(L=L-next; L != NULL; L = L-next)(*fp)(L-data);/*-操作目的：清空链表初始条件：线性表L已存在操作结果：将
8、L置为空表函数参数：LinkList L线性表L返回值：无-*/void ClearList(LinkList L)assert(L != NULL);LinkList tmp = L-next;while(tmp != NULL)L-next = tmp-next;free(tmp);tmp = L-next;L-next = NULL; /清空操作后，头指针的next域应为空/*-操作目的：在链表的指定位置插入结点，插入位置i表示在第i个元素之前插入初始条件：线性表L已存在，1=i=ListLength(L) + 1操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1函数参数：LinkList L线性表Lint i插入位置ElemType e待插入的数据元素返回值：bool操作是否成功-*/bool ListInsert(LinkList L, int i, ElemType e)assert(L
