链表的基本操作数据结构实验报告.docx
《链表的基本操作数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《链表的基本操作数据结构实验报告.docx（19页珍藏版）》请在冰点文库上搜索。
链表的基本操作数据结构实验报告
大学数据结构实验报告
课程名称数据结构实验第（四）次实验实验名称链表的基本操作
学生姓名于歌专业班级学号
实验成绩指导老师（签名）日期2018年10月01日
一、实验目的
1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。
2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。
二、实验要求
1．预习C语言中结构体的定义与基本操作方法。
2．对单链表的每个基本操作用单独的函数实现。
3．编写完整程序完成下面的实验内容并上机运行。
4．整理并上交实验报告。
三、实验内容：
1．编写程序完成单链表的下列基本操作：
（1）初始化单链表La
（2）在La中插入一个新结点
（3）删除La中的某一个结点
（4）在La中查找某结点并返回其位置
（5）打印输出La中的结点元素值
（6）清空链表
（7）销毁链表
2.构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。
四、思考与提高：
1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？
2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？
五、实验设计
1．编写程序完成单链表的下列基本操作：
（1）初始化单链表La
LinkListInitList（）
{
inti,value,n;
LinkListH=（LinkList）malloc（sizeof（LNode））;
LinkListP=H;
P->next=NULL;
do{
printf（"请输入链表的长度:
"）;
scanf（"%d",&n）;
if（n<=0）
printf（"输入有误请重新输入！
\n"）;
}while（n<=0）;
printf（"请输入各个元素:
\n"）;
for（i=0;i{
scanf（"%d",&value）;
LinkListNEW=（LinkList）malloc（sizeof（LNode））;
NEW->data=value;
P->next=NEW;
NEW->next=NULL;
P=NEW;
}
printf（"链表建立成功！
\n"）;
returnH->next;
}
（2）在La中插入一个新结点
LinkListInsertList（LinkListL,inti,ElemTypevalue）
{
LinkListh,q,t=NewLNode（t,value）;
intx=0;
h=q=L;
if（i==1）
t->next=h,h=t;
else
{
while（x++q=q->next;
t->next=q->next;
q->next=t;
}
printf（"插入成功！
\n"）;
returnh;
}
（3）删除La中的某一个结点
LinkListDeleteList（LinkListL,inti）
{
LinkListh,q,de;
intx=0;
h=q=L;
intt;
if（i==1）
h=h->next;
else
{
while（x++q=q->next;
de=q->next;
if（de->next==NULL）
q->next=NULL;
else
q->next=de->next;
}
printf（"删除成功！
\n"）;
returnh;
}
（4）在La中查找某结点并返回其位置
StatusLocateList（LinkListL,ElemTypevalue）
{
LinkListq=L;
inti=0,t;
while（q!
=NULL）
{
i++;
if（q->data==value）
{
printf（"该结点在链表中的位置为第%d个\n",i）;
returnOK;
}
q=q->next;
}
printf（"该链表中没有该结点！
\n"）;
returnERROR;
}
（5）打印输出La中的结点元素值
StatusPrint（LinkListL）
{
LinkListq=L;
printf（"该链表的每个元素为:
\n"）;
while（q!
=NULL）
{
printf（"%8d",q->data）;
q=q->next;
}
printf（"\n"）;
returnOK;
}
（6）清空链表
LinkListEmptyList（LinkListL）
{
free（L->data）;
L->next=NULL;
printf（"清空成功！
\n"）;
returnL;
}
（7）销毁链表
LinkListFreeList（LinkListL）
{
printf（"释放成功！
\n"）;
free（L）;
}
（8）主函数
intmain（）
{
LinkListL=InitList（）;
intn,i,j;
Pr（）;
scanf（"%d",&n）;
while（n>0&&n<7）
{
switch（n）
{
case1:
printf（"请输入要插入的结点的值和插入的位置:
"）;
scanf（"%d%d",&i,&j）;
InsertList（L,j,i）;
break;
case2:
printf（"请输入要删除的结点的位置:
"）;
scanf（"%d",&i）;
DeleteList（L,i）;
break;
case3:
printf（"请输入要查找的结点的值:
"）;
scanf（"%d",&i）;
LocateList（L,i）;
break;
case4:
Print（L）;
break;
case5:
EmptyList（L）;
break;
case6:
FreeList（L）;
break;
}
Pr（）;
scanf（"%d",&n）;
}
if（n==7）
printf（"退出成功！
"）;
return0;
}
2．构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc
LinkListConnectList（LinkListLa,LinkListLb）
{
LinkListLc,a,b,c;
a=La;
b=Lb;
if（La->datadata）
Lc=La,a=a->next;
else
Lc=Lb,b=b->next;
c=Lc;
while（a!
=NULL||b!
=NULL）
{
if（a==NULL）
c->next=b,break;
if（b==NULL）
c->next=a;break;
if（a->datadata）
c->next=a,a=a->next,c=c->next;
else
c->next=b,b=b->next,c=c->next;
returnLc;
}
3．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作
LinkListConnectList（LinkListLa,LinkListLb）
{
inti=1;
LinkListLc,a,b,c,q,p;
a=La;
b=Lb;
if（La->datadata）
Lc=La;a=a->next;
else
Lc=Lb;b=b->next;
c=Lc;
while（a!
=NULL||b!
=NULL）
{
if（a==NULL）
c->next=b，break;
if（b==NULL）
c->next=a，break;
if（a->datadata）
c->next=a，a=a->next，c=c->next;
else
c->next=b，b=b->next，c=c->next;
}
c=Lc;
q=c->next;
while（q!
=NULL）
{
if（c->data==q->data）
{
c->next=q->next;
}
c=c->next;
q=c->next;
}
returnLc;
}
4．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？
StatusPartList（LinkListLc）
{
intn1=0,n2=0;
LinkListLa,Lb,L;
LinkLista,b;
L=Lc;
while（L!
=NULL）
{
if（L->data%2==0）
{
if（n1==0）
{
a=La=L;
L=L->next;
}
else
{
a->next=L;
L=L->next;
}
}
else
{
if（n2==0）
{
b=Lb=L;
L=L->next;
}
else
{
b->next=L;
L=L->next;
}
}
}
a->next=NULL;
b->next=NULL;
returnOK;
}
六、实验测试
1．编写程序完成单链表的下列基本操作：
七、总结
附录1：
源代码
#include
#include
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintElemType;
typedefintStatus;
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
LinkListNewLNode（LNode*P,ElemTypedata）
{
P=（LNode*）malloc（sizeof（LNode））;
P->data=data;
P->next=NULL;
returnP;
}
LinkListInitList（）
{
inti,value,n;
LinkListH=（LinkList）malloc（sizeof（LNode））;
LinkListP=H;
P->next=NULL;
do
{
printf（"请输入链表的长度:
"）;
scanf（"%d",&n）;
if（n<=0）
printf（"输入有误请重新输入！
\n"）;
}
while（n<=0）;
printf（"请输入各个元素:
\n"）;
for（i=0;i{
scanf（"%d",&value）;
LinkListNEW=（LinkList）malloc（sizeof（LNode））;
NEW->data=value;
P->next=NEW;
NEW->next=NULL;
P=NEW;
}
printf（"链表建立成功！
\n"）;
returnH->next;
}
LinkListInsertList（LinkListL,inti,ElemTypevalue）
{
LinkListh,q,t=NewLNode（t,value）;
intx=0;
h=q=L;
if（i==1）
{
t->next=h;
h=t;
}
else
{
while（x++q=q->next;
t->next=q->next;
q->next=t;
}
printf（"插入成功！
\n"）;
returnh;
}
LinkListDeleteList（LinkListL,inti）
{
LinkListh,q,de;
intx=0;
h=q=L;
intt;
if（i==1）
h=h->next;
else
{
while（x++q=q->next;
de=q->next;
if（de->next==NULL）
q->next=NULL;
else
q->next=de->next;
}
printf（"删除成功！
\n"）;
returnh;
}
StatusLocateList（LinkListL,ElemTypevalue）
{
LinkListq=L;
inti=0,t;
while（q!
=NULL）
{
i++;
if（q->data==value）
{
printf（"该结点在链表中的位置为第%d个\n",i）;
returnOK;
}
q=q->next;
}
printf（"该链表中没有该结点！
\n"）;
returnERROR;
}
StatusPrint（LinkListL）
{
LinkListq=L;
printf（"该链表的每个元素为:
\n"）;
while（q!
=NULL）
{
printf（"%8d",q->data）;
q=q->next;
}
printf（"\n"）;
returnOK;
}
LinkListEmptyList（LinkListL）
{
free（L->data）;
L->next=NULL;
printf（"清空成功！
\n"）;
returnL;
}
LinkListFreeList（LinkListL）
{
printf（"释放成功！
\n"）;
free（L）;
}
voidPr（）
{
printf（"\n1.插入新结点\n"）;
printf（"2.删除链表中的结点\n"）;
printf（"3.查找结点\n"）;
printf（"4.输出链表\n"）;
printf（"5.清空链表\n"）;
printf（"6.销毁链表\n"）;
printf（"7.退出\n"）;
printf（"请输入要使用的功能:
"）;
}
intmain（）
{
LinkListL=InitList（）;
intn,i,j;
Pr（）;
scanf（"%d",&n）;
while（n>0&&n<7）
{
switch（n）
{
case1:
printf（"请输入要插入的结点的值和插入的位置:
"）;
scanf（"%d%d",&i,&j）;
InsertList（L,j,i）;
break;
case2:
printf（"请输入要删除的结点的位置:
"）;
scanf（"%d",&i）;
DeleteList（L,i）;
break;
case3:
printf（"请输入要查找的结点的值:
"）;
scanf（"%d",&i）;
LocateList（L,i）;
break;
case4:
Print（L）;
break;
case5:
EmptyList（L）;
break;
case6:
FreeList（L）;
break;
}
Pr（）;
scanf（"%d",&n）;
}
if（n==7）
printf（"退出成功！
"）;
return0;
}
升级会员 