数据结构c语言版双向链表表示和实现

《数据结构c语言版双向链表表示和实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构C语言版双向链表表示和实现P36-P37编译环境：Dev-C++4.9.9.2日期：2011年2月10日*/#inelude#inelude#ineludetypedefintElemType;//线性表的双向链表存储结构typedefstructDuLNode{ElemTypedata;//数据域structDuLNode*prior,^next://前驱后继指针}DuLNode,*DuLinkList;//产生空的双向循环链表LintInitList(DuLinkList*L){*L=(

2、DuLinkList)malloc(sizeof(DuLNode));//*L指向头结点if(*L){//将头结点的前驱后继都指向头结点，这样构成了一个空表(*L)—>next=(*L)->prior二*L;return1;elsereturn0;}//销毁双向循环链表LintDestroyList(DuLinkList*L){DuLinkListq,p=(*L)->next;//p指向第一个结点while(p!=*L)//p没到表头{q二p->next;free(p);P二q；}free(*L);*L=NULL;return1;}//将L重置为空表int

3、ClearList(DuLinkListL){DuLinkListq,p=L->next;//p指向第一个结点while(p!=L)//p没到表头{q二p-〉next;free(p);P二q；L->next=L->prior=L;//头结点的两个指针域均指向自身,构成空表return1;}//若L为空表(空表就是头结点的前驱后继都指向头结点)，则返回1,否则返回0intListEmpty(DuLinkListL){if(L-〉next二二L&&L-〉prior二二L)return1;elsereturn0;}//返回L中数据元素个数intListLengt

4、h(DuLinkListL){inti二0;DuLinkListp=L->next;//p指向第一个结点while(p!=L)//p没到表头{i++；p=p->next:}returni;}//当笫i个元素存在时，其值赋给e并返回1,否则返回0intGetElem(DuLinkListL,inti,ElemType*e)intj二1;//j为计数器DuLinkListp=L->next;//p指向第一个结点while(p!=L&&j

5、

6、j〉i)//第i

7、个元素不存在return0;^e=p->data;//取第i个元素return1;}//返回L中第1个与e满足关系compare()的数据元素的位序。//若这样的数据元素不存在，则返回值为0intLocateElem(DuLinkListL,ElemTypee,int(^compare)(ElemType,ElemType)){inti二0;DuLinkListp=L->next://p指向第1个元素while(p!=L){i++；if(compare(p->data,e))//找到这样的数据元素returni;p=p->next:}return0;//若

8、cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱intPriorE1em(DuLinkListL,ElemTypecur_e,ElemType*pre_e){DuLinkListp=L->next->next://p指向第2个元素while(p!=L)//p没到表头{if(p->data=cur_e){*pre_e二p-〉prior'-〉data;return1;}p二p->next;}return0;}//若cur_e是L的数据元素，且不是最后一个，则用next_e返凹它的后继intNextElem(DuLinkListL,ElemTy

9、pecur_e,ElemType*next_e){DuLinkListp=L->next->next://p指向第2个元素while(p!=L)//p没到表头{if(p->prior->data=cur_e){*next_e=p->data;return1;}p=p->next;return0;//在双向链表L中返回第i个元素的位置指针(算法2.18.2.19要调用的函数)DuLinkListGetElemP(DuLinkListL,inti)intj;DuLinkListp二L;for(j=l;j〈=i;j++)p二p-〉next;returnp;}//

10、改进算法2.18P36//在带头结点的双链循环线性表L中笫i个位置