第二章链表代码.doc

代码1：函数状态码定义头文件func_Status.h/函数状态码定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;代码2：ADT改进的单链表代码LinkList.cpp/库函数头文件包含#include#include#include#includefunc_Status.h/改进的单链表存储结构定义typedef int ElemType; /假设元素类型为int，具体应用中需要改写typedef struct LNode /结点类型ElemType data;struct LNode *next;*Link,*Position;typedef struct /链表类型Link head,tail;/头指针和尾指针int len; /表长LinkList;/链表基本操作的函数原型说明/*如果此处省略则要注意函数的出现顺序，函数使用前必须已经被定义或声明，此处略去*/链表基本操作的实现/结点类操作Status MakeNode(Link &p,ElemType e)/分配由p指向的值为e的结点，并返回OK，若分配失败则返回ERROR；p=(Link)malloc(sizeof(LNode);if(!p)return ERROR;p-data=e;p-next=NULL;return OK;void FreeNode(Link p)/释放p所指结点free(p);p=NULL;/结构初始化和销毁操作Status InitList_L(LinkList &L) /初始化L为一个带头结点的空链表,头尾指针指向头结点，表长赋ElemType e;e=-1;/实际应用中此初始化语句需要修改if(!MakeNode(L.head,e)return ERROR; /开辟头结点L.tail=L.head;L.len=0;return OK;/InitList_LStatus DestroyList_L(LinkList &L)/销毁链表LLink p;while(p=L.head-next) /依次释放有序链表中第一个元素至最后一个元素所占用空间;L.head-next=p-next;FreeNode(p);free(L.head);L.head=NULL;L.tail=NULL;L.len=0;return OK;/DestroyList_L/*将所有元素结点及头结点释放，设表长为n，则共释放n+1个结点，时间复杂度为O(n)*/加工型操作Status ClearList_L(LinkList &L)/链表L置空Link p;while(p=L.head-next) /依次释放有序链表中第一个元素至最后一个元素所占用空间;L.head-next=p-next;FreeNode(p);L.tail=L.head;L.len=0;return OK;Status InsFirst_L(LinkList &L,Link s)/将s所指结点插入到L的第一个元素结点前，头结点后s-next=L.head-next;L.head-next=s;if(L.len=0)L.tail=s; /插入前为空表则尾指针相应改变+L.len;return OK;Status Append_L(LinkList &L,Link s)/在L的末尾追加一串由s指向的一串结点,尾指针与表长均改变L.tail-next=s;while(L.tail-next)L.tail=L.tail-next;L.len+;return OK;Status InsAfter_L(LinkList &L,Link &p,Link s)/已知p指向L中某个结点，将s所指结点插入到p所指结点后，并修改p使之指向新插入的结点，同时表长加s-next=p-next;p-next=s;p=s;+L.len;if(p-next=NULL)L.tail=p;/若插入到表尾则尾指针应改变return OK;Status InsBefore_L(LinkList &L,Link &p,Link s)/已知p指向L中某个结点，将s所指结点插入到p所指结点前，并修改p使之指向新插入的结点，同时表长加/因此操作为线性时间复杂度，且可用InsertAfter及其它操作替代，故不常用，此处略printf(InsBefore_L() is to be implemented.n);return ERROR;Status DeleteFirst_L(LinkList &L,Link &q)/将L的第一个元素结点删除并以q返回，若L为空表则q赋空，返回ERRORif(!L.len)q=NULL;return ERROR;if(L.len=1)L.tail=L.head; /若删除后为空表则尾指针改变q=L.head-next;L.head-next=q-next;q-next=NULL;-L.len;return OK;Status Remove_L(LinkList &L,Link &q)/删除L的尾结点并以q返回，同时改变尾指针/此操作为线性时间复杂度且能被DeleteAfter等操作取代，不常用，故略printf(Remove_L() is to be implemented.n);return ERROR;Status DeleteAfter_L(LinkList &L,Link p,Link &q)/已知p指向L中某个结点，删除p所指结点后的结点并以q返回，同时表长减if(!p-next)q=NULL;return ERROR;if(p=L.head)DeleteFirst_L(L,q);return OK;if(p-next=L.tail)L.tail=p;q=p-next;p-next=q-next;q-next=NULL;-L.len;return OK;Status DeleteBefore_L(LinkList &L,Link p,Link s)/已知p指向L中某个结点，删除p所指结点前的结点以q返回，同时表长减/因此操作为线性时间复杂度，且可用DeleteAfter及其它操作替代，故不常用，此处略printf(DeleteBefore_L() is to be implemented.n);return ERROR;Status SetCurElem_L(Link &p,ElemType e) /用e更新p所指向结点的数据域的值if(!p)return ERROR;p-data=e;return OK;/引用型操作Status ListEmpty_L(LinkList L)/判表空if(L.len)return TRUE;else return FALSE;int ListLength_L(LinkList L)/求表长return(L.len);ElemType GetCurElem_L(Link p)if(!p)exit(OVERFLOW);return p-data;Position GetHead_L(LinkList L)/返回头结点的位置即头指针return L.head;Position GetLast_L(LinkList L)/返回尾指针return L.tail;Status LocatePos_L(LinkList L,int i,Link &p)/用p返回L中第i个元素结点的位置,i不合法时返回iERRORif(iL.len)p=NULL;return ERROR;Link q=L.head; int j=0;while(p&jnext;+j;if(!p)return ERROR; /实际i的取值范围判定已经避免了此种情况的发生else return OK;Position PriorPos_L(LinkList L,Link p)/返回p所指向结点前的结点的位置/线性复杂度，不常用，略printf(PriorPos is to be implemented .n);return NULL;Position NextPos_L(LinkList L,Link p)/返回L中p所指结点后的结点的指针;无后继则返回NULLreturn p-next;/比较函数在此仅作声明，具体应用中如下两个比较函数可能需要改写Status SmallEqual(ElemType ,ElemType );Status Equal(ElemType ,ElemType );/若要测试本文件各基本操作的正确性则将如下两个函数的注释去掉，使得可用/*Status SmallEqual(ElemType e1,ElemType e2)if(e1data)p=p-next;return p;Position LocateElemPrior_L(LinkList L,ElemType e,Status (*cmp)(ElemType,ElemType)/返回L中第一个与元素e满足关系cmp()的元素的前驱的位置，若不存在则返回NULL。Link p=L.head;while(p-next&!(*cmp)(e,p-next-data)p=p-next;if(p-next)return p;else return NULL;void PrintList_L(LinkList L) /依次输出有序顺序表L中的各个元素及表长Link p=L.head-next;printf(共%d个结点n,L.len);while(p)printf(-%d-,*p);p=p-next;printf(nn);/测试用程序/*void main()LinkList L;InitList_L(L); PrintList_L(L);if(!ListEmpty_L(L)printf(NULL);ElemType e1=5,e2=3,e3=6;Link p,q,s;if(MakeNode(p,e1) InsFirst_L(L,p);PrintList_L(L);if(!ListEmpty_L(L)printf(NULL);if(MakeNode(q,e2)Append_L(L,q);PrintList_L(L);if(MakeNode(p,e3)InsAfter_L(L,q,p);PrintList_L(L);if(MakeNode(p,e3)InsAfter_L(L,q,p);PrintList_L(L);e1=GetCurElem_L(L.tail);printf(%dn,e1);s=LocateElem_L(L,e1,Equal);if(s)printf(%d,s-data);DeleteFirst_L(L,q);PrintList_L(L);DeleteAfter_L(L,L.head-next,q);printf(%dn,q-data);PrintList_L(L); q=LocateElem_L(L,4,SmallEqual);printf(%d,q-data);q=LocateElemPrior_L(L,4,SmallEqual); /定位到第一个满足edata的结点q的前驱printf(%d,q-data);q=GetLast_L(L);printf(%d,q-data);ClearList_L(L);PrintList_L(L);DestroyList_L(L);*/代码3：ADT有序单链表代码SortedLinkList.cpp/库函数头文件包含#include#include#include/-文件LinkList.cpp中含有改进的单链表的类型定义及基本操作的函数说明和具体实现，本程序在改进单链表基础上通过改进单链表的定义和基本操作实现有序单链表的类型定义和操作，故将其包含进来#includeLinkList.cpp/-有序单链表的类型定义与基本操作的函数原型声明-typedef LinkList SortedLinkList; /有序链表类型的定义/有序单链表各操作的函数原型说明Status LocateElem_SortedL(SortedLinkList L,ElemType e,Status(*cmp)(ElemType,ElemType),Link &q);/在表L中查找第一个满足cmp(e,x)的x结点，用q返回该结点前驱,找不到则q带回NULL，当cmp为SmallEqual时用于定位到第一个满足SmallEqual(e,x)的x结点之前驱，即定位第一个数据值“大于等于”e的结点的前驱； /当cmp为BigEqual时定位第一个值满足BigEqual(e,x)的元素x，即第一个“小于等于”e的x结点的前驱； cmp为Equal时定位第一个等于e的x结点的前驱。务必注意对应关系Status ListInsert_SortedL(SortedLinkList &L,ElemType e,Status (*cmp)(ElemType,ElemType);/在有序链表L中插入元素e，使得链表仍然满足cmp序,当cmp为SmallEqual时为升序,即将e插入到第第一个大于或等于e的元素之前，当cmp为BigEqual时为降序,将e插入到第一个小于等于e的元素前int ListDelete_SortedL(SortedLinkList &L,ElemType e,Status (*cmp)(ElemType,ElemType);/在有序表中删除“所有”满足cmp(e,x)的元素x,返回删除的元素个数。/当cmp为SmallEqual时删除所有满足SmallEqual(e,x)的元素x，即所有“大于等于e”的元素x；/当cmp为BigEqual时删除所有满足BigEqual(e,x)的元素x，即所有“小于等于e”的元素x；当cmp为Equal时删除所有与e相等的元素xStatus ListMerge_SortedL(SortedLinkList La,SortedLinkList Lb,SortedLinkList &Lc);/将两个有序链表La与Lb归并为有序链表Lc,之后释放La与LbStatus SmallEqual(ElemType e1, ElemType e2); /若元素e1=e2则返回TRUE，否则返回FAlSEStatus Equal(ElemType e1, ElemType e2);/若元素e1=e2则返回TRUE，否则返回FAlSE/-有序单链表中各操作的函数实现-Status SmallEqual(ElemType e1,ElemType e2)if(e1=e2)return TRUE;else return FALSE;Status LocateElem_SortedL(SortedLinkList L,ElemType e,Status(*cmp)(ElemType,ElemType),Link &q)/在表L中查找第一个满足cmp(e,x)的x结点，用q返回该结点前驱,找不到则q带回NULL,同时函数返回FALSE，否则函数返回TRUE，q带回x结点前驱的地址；当cmp为SmallEqual时用于定位到第一个满足SmallEqual(e,x)的x结点之前驱，即定位第一个数据值“大于等于”e的结点的前驱； /当cmp为BigEqual时定位第一个值满足BigEqual(e,x)的元素x，即第一个“小于等于”e的x结点的前驱； cmp为Equal时定位第一个等于e的x结点的前驱。务必注意对应关系 q=L.head; while(q-next!=NULL&!cmp(e,q-next-data)q=q-next; if(q-next=NULL)q=NULL;return FALSE; else return TRUE;Status ListInsert_SortedL(SortedLinkList &L,ElemType e,Status (*cmp)(ElemType,ElemType)/在有序链表L中插入元素e，使得链表仍然满足cmp序,当cmp为SmallEqual时为升序,即将e插入到第第一个大于或等于e的元素之前，当cmp为BigEqual时为降序,将e插入到第一个小于等于e的元素前Link q,s;if(!MakeNode(s,e)exit(OVERFLOW);LocateElem_SortedL(L,e,(*cmp),q);if(q)InsAfter_L(L,q,s);else Append_L(L,s);/未找到时插入到表尾结点之后return OK;int ListDelete_SortedL(SortedLinkList &L,ElemType e,Status (*cmp)(ElemType,ElemType)/在有序表中删除“所有”满足cmp(e,x)的元素x,返回删除的元素个数。/当cmp为SmallEqual时删除所有满足SmallEqual(e,x)的元素x，即所有“大于等于e”的元素x；/当cmp为BigEqual时删除所有满足BigEqual(e,x)的元素x，即所有“小于等于e”的元素x；当cmp为Equal时删除所有与e相等的元素xLink pre_q,q;int count=0;while(LocateElem_SortedL(L,e,(*cmp),pre_q)DeleteAfter_L(L,pre_q,q);count+;printf(共删除%d个元素n,count);return ERROR;Status ListMerge_SortedL(SortedLinkList La,SortedLinkList Lb,SortedLinkList &Lc)/将两个有序链表La与Lb归并为有序链表Lc,之后释放La与Lbif(!InitList_L(Lc)return ERROR; Link ha=GetHead_L(La),hb=GetHead_L(Lb); Link pa=NextPos_L(La,ha), pb=NextPos_L(Lb,hb),q;ElemType a,b; while(pa&pb)a=GetCurElem_L(pa);b=GetCurElem_L(pb);if(SmallEqual(a,b)DeleteFirst_L(La,q);Append_L(Lc,q);pa=La.head-next;elseDeleteFirst_L(Lb,q);Append_L(Lc,q);pb=Lb.head-next; if(pa)Append_L(Lc,pa);if(pb)Append_L(Lc,pb);FreeNode(La.head);FreeNode(Lb.head);return OK;/MergeList_L/-主函数主要用以验证前述操作实现的正确性，注意测试数据要选择合理-void main()SortedLinkList La,Lb,Lc;InitList_L(La); PrintList_L(La);/以下初始化La，依次向其插入元素,3,6,3，如此则既有在表头、表尾的插入操作，也有在表中间的插入，还有插入元素相等情况的出现，只要这几种情况都正确则说明插入操作正确ElemType e1=5,e2=3,e3=6;ListInsert_SortedL(La,e1,SmallEqual);PrintList_L(La);ListInsert_SortedL(La,e2,SmallEqual);PrintList_L(La);ListInsert_SortedL(La,e3,SmallEqual);PrintList_L(La);ListInsert_SortedL(La,e2,SmallEqual);PrintList_L(La);/以下初始化Lb，并向其中插入元素,4,0,3；将来将La与Lb合并为Lc用以验证合并操作的正确性，注意Lb中的数据比La中元素小的、大的、相等的都有，如此方能验证合并操作的正确性InitList_L(Lb);ListInsert_SortedL(Lb,8,SmallEqual);PrintList_L(Lb);ListInsert_SortedL(Lb,4,SmallEqual);PrintList_L(Lb);ListInsert_SortedL(Lb,0,SmallEqual);PrintList_L(Lb);ListInsert_SortedL(Lb,3,SmallEqual);PrintList_L(Lb); /以下合并La与Lb为表LcListMerge_SortedL(La,Lb,Lc);PrintList_L(Lc);/以下从Lc中删除若干数据，既删除与指定值e相等的元素，也删除与指定值e满足SmallEqual(e,x)即“大于等于”e的元素x，还删除与指定值e满足BigEqual(e,x)即“小于等于e”的元素x，删除的元素在表头、表尾、表中间及不存在表中的元素均有，都正确方能保证删除操作的正确性ListDelete_SortedL(Lc,5,Equal);PrintList_L(Lc);ListDelete_SortedL(Lc,3,BigEqual);/删除所有满足BigEqual(3,x)即小于等于的元素xPrintList_L(Lc);ListDelete_SortedL(Lc,8,SmallEqual);/删除所有满足SmallEqual(8,x)即大于等于的元素xPrintList_L(Lc);ListDelete_SortedL(Lc,-1,Equal);/删除与-1相等的元素，实际不存在PrintList_L(Lc);DestroyList_L(Lc);代码4：ADT多项式定义代码/#includeLinkList.cpp /除非修改文件LinkList中ElemType的定义，否则不能将LinkList.cpp，直接包含进来。本文件将LinkList.cpp中的代码复制到下面/-/-以下为LinkList.cpp中的代码，只是将ElemType的定义加以修改，且-/-/库函数头文件包含#include#include#include#includefunc_Status.htypedef structfloat coef;int expn;term,ElemType;/改进的单链表存储结构定义/typedef int ElemType; /假设元素类型为inttypedef struct LNode /结点类型ElemType data;struct LNode *next;*Link,*Position;typedef struct /链表类型Link head,tail;/头指针和尾指针int len; /表长LinkList;/链表基本操作的函数原型说明/*如果此处省略则要注意函数的出现顺序，函数使用前必须已经被定义或声明，此处略去*/链表基本操作的实现/结点类操作Status MakeNode(Link &p,ElemType e)/分配由p指向的值为e的结点，并返回OK，若分配失败则返回ERROR；p=(Link)malloc(sizeof(LNode);if(!p)return ERROR;p-data=e;p-next=NULL;return OK;void FreeNode(Link p)/释放p所指结点free(p);p=NULL;/结构初始化和销毁操作Status InitList_L(LinkList &L) /初始化L为一个带头结点的空链表,头尾指针指向头结点，表长赋ElemType e;e.coef=-1;e.expn=-1;if(!MakeNode(L.head,e)return ERROR; /开辟头结点L.tail=L.head;L.len=0;return OK;/InitList_LStatus DestroyList_L(LinkList &L)/销毁链表LLink p;while(p=L.head-next) /依次释放有序链表中第一个元素至最后一个元素所占用空间;L.head-next=p-next;FreeNode(p);free(L.head);L.head=NULL;L.tail=NULL;L.len=0;return OK;/DestroyList_L/*将所有元素结点及头结点释放，设表长为n，则共释放n+1个结点，时间复杂度为O(n)*/加工型操作Status ClearList_L(LinkList &L)/链表L置空Link p;while(p=L.head-next) /依次释放有序链表中第一个元素至最后一个元素所占用空间;L.head-next=p-next;FreeNode(p);L.tail=L.head;L.len=0;return OK;Status InsFirst_L(LinkList &L,Link s)/将s所指结点插入到L的第一个元素结点前，头结点后s-next=L.head-next;L.head-next=s;if(L.len=0)L.tail=s; /插入前为空表则尾指针相应改变+L.len;return OK;Status Append_L(LinkList &L,Link s)/在L的末尾追加一串由s指向的一串结点,尾指针与表长均改变L.tail-next=s;while(L.tail-next)L.tail=L.tail-next;L.len+;return OK;Status InsAfter_L(LinkList &L,Link &p,Link s)/已知p指向L中某个结点，将s所指结点插入到p所指结点后，并修改p使之指向新插入的结点，同时表长加s-next=p-next;p-next=s;p=s;+L.len;if(p-next=NULL)L.tail=p;/若插入到表尾则尾指针应改变return OK;Status InsBefore_L(LinkList &L,Link &p,Link s)/已知p指向L中某个结点，将s所指结点插入到p所指结点前，并修改p使之指向新插入的结点，同时表长加/因此操作为线性时间复杂度，且可用InsertAfter及其它操作替代，故不常用，此处略printf(InsBefore_L() is to be implemented.n);return ERROR;Status DeleteFirst_L(LinkList &L,Link &q)/将L的第一个元素结点删除并以q返回，若L为空表则q赋空，返回ERRORif(!L.len)q=NULL;return ERROR;if(L.len=1)L.tail=L.head; /若删除后为空表则尾指针改变q=L.head-next;L.head-next=q-next;q-next=NULL;-L.len;return OK;Status Remove_L(LinkList &L,Link &q)/删除L的尾结点并以q返回，同时改变尾指针/此操作为线性时间复杂度且能被DeleteAfter等操作取代，不常用，故略printf(Remove_L() is to be implemented.n);return ERROR;Status DeleteAfter_L(LinkList &L,Link p,Link &q)/已知p指向L中某个结点，删除p所指结点后的结点并以q返回，同时表长减if(!p-next)q=NULL;return ERROR;if(p=L.head)DeleteFirst_L(L,q);return OK;if(p-next=L.tail)L.tail=p;q=p-next;p-next=q-next;q-next=NULL;-L.len;return OK;Status DeleteBefore_L(LinkList &L,Link p,Link s)/已知p指向L中某个结点，删除p所指结点前的结点以q返回，同时表长减/因此操作为线性时间复杂度，且可用DeleteAfter及其它操作替代，故不常用，此处略printf(DeleteBefore_L() is to be implemented.n);return ERROR;Status SetCurElem_L(Link &p,ElemType e) /用e更新p所指向结点的数据域的值if(!p)return ERROR;p-data=e;return OK;/引用型操作Status ListEmpty_L(LinkList L)/判表空if(L.len)return TRUE;else return FALSE;int ListLength_L(LinkList L)/求表长return(L.len);ElemType GetCurElem_L(Link p)if(!p)exit(OVERFLOW);return p-data;Position GetHead_L(LinkList L)/返回头结点的位置即头指针return L.head;Position GetLast_L(LinkList L)/返回尾指针return L.tail;Status LocatePos_L(LinkList L,int i,Link &p)/用p返回L中第i个元素结点的位置,i不合法时返回iERRORif(iL.len)p=NULL;return ERROR;Link q=L.head; int j=0;while(p&jnext;+j;if(!p)return ERROR; /实际i的取值范围判定已经避免了此种情况的发生else return OK;Position PriorPos_L(LinkList L,Link p)/返回p所指向结点前的结点的位置/线性复杂度，不常用，略printf(PriorPos is to be implemented .n);return NULL;Position NextPos_L(LinkList L,Link p)/返回L中p所指结点后的结点的指针;无后继则返回NULLreturn p-next;/*具体应用中可能需要改写Status SmallEqual(ElemType e1,ElemType e2)if(e1data)p=p-next;return p;Position LocateElemPrior_L(LinkList L,ElemType e,Status (*cmp)(ElemType,ElemType)/返回L中第一个与元素e满足关系cmp()的元素的前驱的位置，若不存在则返回NULL。Link p=L.head;while(p-next&!(*cmp)(e,p-next-data)p=p-next;if(p-next)return p;else return NULL;void PrintList_L(LinkList L) /依次输出有序顺序表L中的各个元素及表长Link p=L.head-next;printf(共%d个结点n,L.len);while(p)printf(-%d-,*p);p=p-next;printf(nn);/测试用程序/*void main()LinkList L;InitList_L(L); PrintLis