2022年数据结构C语言版_双向链表表示和实现 .pdf

《2022年数据结构C语言版_双向链表表示和实现 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构C语言版_双向链表表示和实现 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C 语言版#include #include #include typedef int ElemType; / 线性表的双向链表存储结构typedef struct DuLNode ElemType data; /数据域struct DuLNode *prior,*next; /前驱后继指针DuLNode,*DuLinkList; / 产生空的双向循环链表L int InitList(DuLinkList *L) *L=(DuLinkList)malloc(sizeof(DuLNode); / *L指向头结点if(*L) / 将头结点的前驱后继都指向头结点，这样构成了一个空表(*L)-next

2、=(*L)-prior=*L; return 1; else return 0; / 销毁双向循环链表L int DestroyList(DuLinkList *L) DuLinkList q,p=(*L)-next; / p指向第一个结点while(p!=*L) / p没到表头 q=p-next; free(p); p=q; free(*L); *L=NULL; return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - -

3、- / 将 L 重置为空表int ClearList(DuLinkList L) DuLinkList q,p=L-next; / p指向第一个结点while(p!=L) / p没到表头 q=p-next; free(p); p=q; L-next=L-prior=L; / 头结点的两个指针域均指向自身，构成空表return 1; / 若 L 为空表（空表就是头结点的前驱后继都指向头结点），则返回1，否则返回0 int ListEmpty(DuLinkList L) if(L-next=L&L-prior=L) return 1; else return 0; / 返回 L 中数据元素个数in

4、t ListLength(DuLinkList L) int i=0; DuLinkList p=L-next; / p指向第一个结点while(p!=L) / p没到表头 i+; p=p-next; return i; / 当第 i 个元素存在时,其值赋给 e 并返回 1,否则返回0 int GetElem(DuLinkList L,int i,ElemType *e) int j=1; / j 为计数器DuLinkList p=L-next; / p指向第一个结点while(p!=L&jnext; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

5、 - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - j+; if(p=L|ji) / 第 i 个元素不存在return 0; *e=p-data; / 取第 i 个元素return 1; / 返回 L 中第 1 个与 e 满足关系compare()的数据元素的位序。/ 若这样的数据元素不存在，则返回值为0 int LocateElem(DuLinkList L,ElemType e,int(*compare)(ElemType,ElemType) int i=0; DuLinkList p=L-next; / p指向第 1

6、 个元素while(p!=L) i+; if(compare(p-data,e) / 找到这样的数据元素return i; p=p-next; return 0; / 若 cur_e 是 L 的数据元素，且不是第一个，则用pre_e 返回它的前驱int PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e) DuLinkList p=L-next-next; / p指向第 2 个元素while(p!=L) / p没到表头 if(p-data=cur_e) *pre_e=p-prior-data; return 1; p=p-next; re

7、turn 0; / 若 cur_e 是 L 的数据元素，且不是最后一个，则用next_e 返回它的后继int NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e) DuLinkList p=L-next-next; / p指向第 2 个元素while(p!=L) / p没到表头名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - if(p-prior-data=cur_e) *n

8、ext_e=p-data; return 1; p=p-next; return 0; / 在双向链表L 中返回第i 个元素的位置指针(算法 2.18、2.19 要调用的函数 ) DuLinkList GetElemP(DuLinkList L,int i) int j; DuLinkList p=L; for(j=1;jnext; return p; / 改进算法2.18 P36 / 在带头结点的双链循环线性表L 中第 i 个位置之前插入元素e，/ i 的合法值为1 i表长 +1 int ListInsert(DuLinkList L,int i,ElemType e) DuLinkList

9、 p,s; if(iListLength(L)+1) / i值不合法return 0; p=GetElemP(L,i-1); / 在 L 中确定第i-1 个元素的位置指针p if(!p) / p=NULL,即第 i-1 个元素不存在return 0; s=(DuLinkList)malloc(sizeof(DuLNode); if(!s) return 0; s-data=e; / 在第 i-1 个元素之后插入s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; return 1; / 算法 2.19 P37 名师资料总结 - - -精品资料欢

10、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - / 删除带头结点的双链循环线性表L 的第 i 个元素 ,i 的合法值为1i表长 +1 int ListDelete(DuLinkList L,int i,ElemType *e) DuLinkList p; if(iListLength(L) / i值不合法return 0; p=GetElemP(L,i); / 在 L 中确定第i 个元素的位置指针p if(!p) / p=NULL,即第 i 个元素不存在retu

11、rn 0; *e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return 1; / 由双链循环线性表L 的头结点出发 ,正序对每个数据元素调用函数visit() void ListTraverse(DuLinkList L,void(*visit)(ElemType) DuLinkList p=L-next; / p指向头结点while(p!=L) visit(p-data); p=p-next; printf(n); / 由双链循环线性表L 的头结点出发 ,逆序对每个数据元素调用函数visit() void Lis

12、tTraverseBack(DuLinkList L,void(*visit)(ElemType) DuLinkList p=L-prior; / p指向尾结点while(p!=L) visit(p-data); p=p-prior; printf(n); / 数据元素判定函数(判定相等 ) int compare(ElemType c1,ElemType c2) if(c1=c2) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - -

13、- return 1; else return 0; void vd(ElemType c) / ListTraverse() 调用的函数 (类型一致 ) printf(%d ,c); int main() DuLinkList L; int i,n; int j; ElemType e; InitList(&L); for(i=1;i=5;i+) ListInsert(L,i,i); / 在第 i 个结点之前插入i printf( 正序输出链表：); ListTraverse(L,vd); / 正序输出printf( 逆序输出链表：); ListTraverseBack(L,vd); / 逆

14、序输出n=2; ListDelete(L,n,&e); / 删除并释放第n 个结点printf( 删除第 %d 个结点，值为%d，其余结点为：,n,e); ListTraverse(L,vd); / 正序输出printf( 链表的元素个数为%dn,ListLength(L); printf( 链表是否空：%d(1:是 0:否)n,ListEmpty(L); ClearList(L); / 清空链表printf( 清空后，链表是否空：%d(1:是 0:否)n,ListEmpty(L); for(i=1;i=5;i+) ListInsert(L,i,i); / 重新插入5 个结点ListTrave

15、rse(L,vd); / 正序输出n=3; j=GetElem(L,n,&e); / 将链表的第n 个元素赋值给e if(j) printf( 链表的第 %d 个元素值为 %dn,n,e); else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - printf( 不存在第 %d 个元素 n,n); n=4; i=LocateElem(L,n,compare); if(i) printf( 等于 %d 的元素是第 %d 个n,n

16、,i); else printf( 没有等于 %d 的元素 n,n); j=PriorElem(L,n,&e); if(j) printf(%d 的前驱是 %dn,n,e); else printf( 不存在 %d 的前驱 n,n); j=NextElem(L,n,&e); if(j) printf(%d 的后继是 %dn,n,e); else printf( 不存在 %d 的后继 n,n); DestroyList(&L); system(pause); return 0; /* 输出效果：正序输出链表：1 2 3 4 5 逆序输出链表：5 4 3 2 1 删除第 2 个结点，值为2，其余结点为：1 3 4 5 链表的元素个数为4 链表是否空： 0(1:是 0:否) 清空后，链表是否空：1(1:是 0:否) 1 2 3 4 5 链表的第3 个元素值为3 等于 4 的元素是第4 个4 的前驱是3 4 的后继是5 请按任意键继续. . . */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -