双链表文档格式.docx
- 文档编号:6683844
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:18
- 大小:65.90KB
双链表文档格式.docx
《双链表文档格式.docx》由会员分享,可在线阅读,更多相关《双链表文档格式.docx(18页珍藏版)》请在冰点文库上搜索。
初始化一个空的双链表L,若初始化成功返回1,否则返回0。
●statuscreat_link(intn)
置逆创建双链表。
statusclearlist_link(dulinklist*L)
清空一个双链表L,若清空成功返回1,不成功返回0。
●intempty_link(dulinklist*Ll)
判断双链表L是否为空表,若是空表返回1,若不是空表返回0。
●intlength_link(dulinklist*L)
返回双链表的长度。
●statusgetelem_link(dulinklist*L,inti,elemtype*e)
从双链表L中取第i个元素,并由e带出。
若取元素成功则返回1,取元素不成功返回0。
●statuspriorelem_link(dulinklist*L,elemtypecure,elemtype*pri)
在双链表L中找cure的前驱结点,若有则由pre带出,若没有返回0。
●statusnextelem_link(dulinklist*L,elemtypecure,elemtype*next)
在双链表L中找cure的后继结点,若有则由next带出,若没有返回0。
●statusinsert_link(dulinklist*L,inti,elemtypee)
在双链表L的第i个位置插入一个数据元素e。
插入不成功返回0。
●statusdelete_link(dulinklist*L,inti,elemtype*e)
删除双链表L中的第i个数据元素,并由e带出删除的元素,若删除不成功返回0。
●statusprint_du(dulinklist*L)
打印双链表L。
●statusmergelist_link(dulinklist*La,dulinklist*Lb,dulinklist*Lc)
将非递减的有序双链表La和Lb归并为一个新的非递减的双链表Lc。
(2)双链表的其它常见操作和应用:
●intzhini_link(dulinklist*L)
将双链表L中的元素置逆。
status*ndl_link(intn)
删除双链表中的重复元素。
●statusunion_link(dulinklist*La,dulinklist*Lb)
La和Lb中的元素分别表示两个集合A和B,求一个新的集合A=(A-B)∪(B-A)。
(写思想)。
4.实验程序清单
#include<
stdio.h>
malloc.h>
conio.h>
ctype.h>
#definenull0
#defineok1
typedefintelemtype;
structnode
{
elemtypedata;
structnode*next;
structnode*before;
};
typedefstructnodedulinklist;
dulinklist*initlist_link(intn)
dulinklist*l,*p,*q;
inti;
l=(dulinklist*)malloc(sizeof(dulinklist));
l->
before=l->
next=null;
q=l;
for(i=1;
i<
=n;
i++)
{
p=(dulinklist*)malloc(sizeof(dulinklist));
printf("
\n请输入第%d个结点:
"
i);
scanf("
%d"
&
(p->
data));
p->
next=q->
next;
q->
next=p;
before=q;
q=p;
}
returnl;
}
intprint_du(dulinklist*l)
dulinklist*p;
if(l->
next==null)
此表为空!
);
return0;
p=l->
printf("
\n此表数据域的值依次是:
while(p!
=null)
%d"
p->
data);
p=p->
return1;
dulinklist*creat_link(intn)
dulinklist*l,*p;
next=l->
before=null;
\n请输入%d个结点的值:
scanf("
p->
before=l;
intinsert_link(dulinklist*l,inti,elemtypee)
intj=0;
dulinklist*p,*q;
p=l;
while(p&
&
j<
i-1)
p=p->
j++;
if(!
p||j>
returnnull;
q=(dulinklist*)malloc(sizeof(dulinklist));
q->
data=e;
next=p->
next=q;
returnok;
intdelete_link(dulinklist*l,inti,elemtype*e)
intj=1;
=null&
i)
q=q->
if(p==null||j>
return0;
*e=p->
data;
free(p);
intpriorelem_link(dulinklist*l,elemtypecure,elemtype*pri)
p->
data!
=cure)
if(p==null||p==l->
next)
*pri=p->
before->
intnextelem_link(dulinklist*l,elemtypecure,elemtype*next)
while(p->
next!
if(p->
*next=p->
next->
intlength_link(dulinklist*l)
intcnt=0;
next==null)return0;
while(p)
cnt++;
returncnt;
intgetelem_link(dulinklist*l,inti,elemtype*e)
dulinklist*q;
while(q!
j++;
if(q==null||j>
*e=q->
voidmergelist_link(dulinklist*la,dulinklist*lb,dulinklist*lc)
dulinklist*pa,*pb,*pc;
pb=lb->
pa=la->
lc=pc=pa;
while(pa&
pb)
if(pa->
data>
=pb->
data)
{
pc->
next=pb;
pc=pb;
pb=pb->
}
else
next=pa;
pc=pa;
pa=pa->
pc->
next=pa?
pb:
pa;
free(lb);
voidunion_link(dulinklist*la,dulinklist*lb)
dulinklist*pa,*pb;
while(pb!
pa=la->
while(pa->
data&
pa->
next==null&
pa->
elsepb=pb->
voidclearlist_link(dulinklist*l)
dulinklist*p,*s;
next=NULL;
s=p;
free(s);
dulinklist*ndl_link(intn)
dulinklist*l,*p,*p1,*p2;
elemtypex;
{
\n请输入第%d个元素的值:
x);
p=l->
while(p&
=x)
if(p==null)
{p=(dulinklist*)malloc(sizeof(dulinklist));
data=x;
p->
p1=l;
p2=l->
while(p2&
x>
p2->
{
p1=p2;
p2=p2->
}
next=p2;
p1->
else
i--;
intempty_link(dulinklist*l)
return1;
voidzhini_link(dulinklist*l)
dulinklist*f,*s;
f=l->
while(f!
s=f;
f=f->
s->
next=s;
voidshowmenu()
*******************************\n"
*选择响应的操作*\n"
**\n"
*[0]显示该表[99]退出程序*\n"
*[1]读取元素[2]插入元素[3]删除元素*\n"
*[4]寻找前驱[5]寻找后继[6]返回表长*\n"
*[7]置逆操作[8]双链表合并[9]判断表空*\n"
*[10]逆序创建[11]双链表并集[12]清空链表*\n"
*[13]创建有序无重复元素链表*\n"
******************************\n"
main()
inti,n,c,m,b,d,select,cure,e,pr,nx;
dulinklist*l,*la,*lb,*ld,*le,*lc,*ln,*s;
\n请输入要创建双链表的长度:
n);
l=initlist_link(n);
print_du(l);
while
(1)
showmenu();
select);
switch(select)
{
case99:
exit
(1);
case0:
print_du(l);
break;
case1:
printf("
你想在线性表中取第几个元素:
\n"
i);
b=getelem_link(l,i,&
d);
if(b==1)
printf("
线性表中第%d个元素为%d。
i,d);
else
i的位置不合适!
break;
case2:
请输入要插入的位置:
请输入要插入的元素:
cure);
b=insert_link(l,i,cure);
{
插入操作完成后的线性表是:
}
case3:
你要删除第几个元素:
b=delete_link(l,i,&
e);
你删除的第%d个元素是:
%d\n"
i,e);
删除操作完成后的线性表是:
break;
case4:
请输入一个元素以便寻找其前驱结点结点:
b=priorelem_link(l,cure,&
pr);
该线性表中%d元素的前驱结点是%d\n"
cure,pr);
/
该元素无前驱!
case5:
请输入一个元素以便寻找其后继结点:
b=nextelem_link(l,cure,&
nx);
该线性表中%d元素的后继结点是%d\n"
cure,nx);
该元素无后继结点!
case6:
b=length_link(l);
if(b==0)
\n此表为空"
\n链表的长度为:
%d"
b);
case7:
\n置逆之前的双链表为:
print_du(l);
zhini_link(l);
\n置逆之后的双链表为:
case8:
\n请输入要创建ld链表的长度:
ld=initlist_link(n);
print_du(ld);
\n请输入要创建le链表的长度:
m);
le=initlist_link(m);
print_du(le);
lc=null;
mergelist_link(ld,le,lc);
\n合并为lc:
print_du(lc);
case9:
b=empty_link(l);
if(b==1)
\n此表不为空"
case10:
\n请输入要创建连表的长度:
ln=creat_link(n);
print_du(ln);
case11:
\n请输入要创建la链表的长度:
la=initlist_link(n);
print_du(la);
\n请输入要创建lb链表的长度:
lb=initlist_link(m);
print_du(lb);
union_link(la,lb);
\n并集la为:
case12:
clearlist_link(l);
case13:
\n请输入要创建链表的长度:
c);
s=ndl_link(c);
print_du(s);
default:
请选择菜单中的操作,按0退出程序\n"
5.实验程序执行结果:
6.实验结果分析:
双向链表中的链式存储结构的结点中有两个指针域,其一指向直接后继,另一指向直接前趋。
在双向链表中,有些操作如:
listlength、getelem等仅需涉及一个方向的指针,则它们的算法描述和线性链表的操作相同,但在插入、删除时有很大的不同,在双向链表中需同时修改两个方向上的指针。
教师意见
成绩
批改日期
教师姓名
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 双链表