第二章链表代码

《第二章链表代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、代码1：函数状态码定义头文件func_Status.h//函数状态码定义#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;代码2：ADT改进的单链表代码LinkList.cpp//库函数头文件包含#include#include#include#include"func_Status.h"//改进的单链表存储

2、结构定义typedefintElemType;//假设元素类型为int，具体应用中需要改写typedefstructLNode{//结点类型ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{//链表类型Linkhead,tail;//头指针和尾指针intlen;//表长}LinkList;//链表基本操作的函数原型说明/*如果此处省略则要注意函数的出现顺序，函数使用前必须已经被定义或声明，此处略去*///链表基本操作的实现//结点类操作Stat

3、usMakeNode(Link&p,ElemTypee){//分配由p指向的值为e的结点，并返回OK，若分配失败则返回ERROR；p=(Link)malloc(sizeof(LNode));if(!p)returnERROR;p->data=e;p->next=NULL;returnOK;}voidFreeNode(Linkp){//释放p所指结点free(p);p=NULL;}//结构初始化和销毁操作StatusInitList_L(LinkList&L){//初始化L为一个带头结点的空链表,头尾指针指向头结点，

4、表长赋ElemTypee;e=-1;//实际应用中此初始化语句需要修改if(!MakeNode(L.head,e))returnERROR;//开辟头结点L.tail=L.head;L.len=0;returnOK;}//InitList_LStatusDestroyList_L(LinkList&L){//销毁链表LLinkp;while(p=L.head->next){//依次释放有序链表中第一个元素至最后一个元素所占用空间;L.head->next=p->next;FreeNode(p);}free(L.he

5、ad);L.head=NULL;L.tail=NULL;L.len=0;returnOK;}//DestroyList_L/*将所有元素结点及头结点释放，设表长为n，则共释放n+1个结点，时间复杂度为O(n)*///加工型操作StatusClearList_L(LinkList&L){//链表L置空Linkp;while(p=L.head->next){//依次释放有序链表中第一个元素至最后一个元素所占用空间;L.head->next=p->next;FreeNode(p);}L.tail=L.head;L.len

6、=0;returnOK;}StatusInsFirst_L(LinkList&L,Links){//将s所指结点插入到L的第一个元素结点前，头结点后s->next=L.head->next;L.head->next=s;if(L.len==0)L.tail=s;//插入前为空表则尾指针相应改变++L.len;returnOK;}StatusAppend_L(LinkList&L,Links){//在L的末尾追加一串由s指向的一串结点,尾指针与表长均改变L.tail->next=s;while(L.tail->nex

7、t){L.tail=L.tail->next;L.len++;}returnOK;}StatusInsAfter_L(LinkList&L,Link&p,Links){//已知p指向L中某个结点，将s所指结点插入到p所指结点后，并修改p使之指向新插入的结点，同时表长加s->next=p->next;p->next=s;p=s;++L.len;if(p->next==NULL)L.tail=p;//若插入到表尾则尾指针应改变returnOK;}StatusInsBefore_L(LinkList&L,Link&p,L

8、inks){//已知p指向L中某个结点，将s所指结点插入到p所指结点前，并修改p使之指向新插入的结点，同时表长加//因此操作为线性时间复杂度，且可用InsertAfter及其它操作替代，故不常用，此处略printf("InsBefore_L()istobeimplemented...");returnERROR;}StatusDeleteFirst_L(