北京邮电大学计算机学院 数据结构第一次实验报告.docx
《北京邮电大学计算机学院 数据结构第一次实验报告.docx》由会员分享，可在线阅读，更多相关《北京邮电大学计算机学院 数据结构第一次实验报告.docx（12页珍藏版）》请在冰点文库上搜索。
北京邮电大学计算机学院数据结构第一次实验报告
实验报告
（1）
姓名：
学号：
班级：
日期：
实验目的、实验原理和内容：
一、实验目的：
熟悉实验环境，掌握线性表动态存储结构的基本特点。
二、实验原理：
链表运算，完成有关单链表有关运算的程序。
三、实验内容及要求：
1、有一个带头结点的单链表，写出在其值为x的结点之后插入m个结点的算法程序。
2、已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。
试编写—个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法程序。
要求：
请同学把步骤、调试好的程序及存在的问题写在下面。
第一题实验程序代码：
#include
#include
typedefstructLnode{
intdata;
structLnode*next;
}Lnode,*Linklist;//非头结点结构定义
typedefstruct{
intlen;
Linklisthead;
}HeadNode;//头结点结构定义
Linklistcreatlist（HeadNode*L）;//创造含头结点的链表函数
Linklistget（LinklistR,intkey）;//在链表中寻找值为key的结点，并返回该结点
Linklistinvert（HeadNode*L,LinklistS,intnum）;//在链表中的某个结点之后插入num个结点
voidprintlist（HeadNode*L,LinklistS）;//打印链表中数据域的值
voiddeletelist（LinklistR）;//释放链表
intmain（）
{
HeadNode*L;
LinklistS;
intkey,num;
L=（HeadNode*）malloc（sizeof（HeadNode））;
if（L==NULL）
return0;
L->head=creatlist（L）;//含头结点的链表的创建
printlist（L,L->head）;
if（L->head==NULL）//判断链表中是否只有头结点
{
printf（"Thelisthasnodata,can'tbeinverted!
\n"）;
return0;
}
printf（"Pleaseinputthedatayouwanttoresearch:
\n"）;
scanf（"%d",&key）;//提示用户输入需要查找的数值
fflush（stdin）;//清空缓冲区，防止读入用户多输入的数据
S=get（L->head,key）;
if（!
S）
return0;
printf（"PleaseinputthenumberoftheLnodeyouwanttoinvert:
\n"）;//提示用户输入需要插入的结点值
scanf（"%d",&num）;
S=invert（L,S,num）;
printlist（L,L->head）;
deletelist（L->head）;
free（L）;//释放头结点
system（"pause"）;
return0;
}
Linklistcreatlist（HeadNode*L）//创造含头结点的链表函数
{
LinklistS=NULL,R=NULL,H=NULL;
inti;
printf（"Pleaseinputthelengthofthelist:
\n"）;
scanf（"%d",&L->len）;
fflush（stdin）;
if（L->len<=0）
return0;
printf（"Pleaseinputthedata:
\n"）;
for（i=0;i<=L->len-1;i++）
{
S=（Linklist）malloc（sizeof（Lnode））;
if（S!
=NULL）
{
if（R==NULL）
{
R=S;
H=S;
}
scanf（"%d",&S->data）;
R->next=S;
R=S;
}
}
fflush（stdin）;
R->next=NULL;
L->head=H;
returnL->head;
}
Linklistget（LinklistR,intkey）//在链表中寻找值为key的结点，并返回该结点
{
LinklistS;
S=R;
while（S&&S->data!
=key）
S=S->next;
if（!
S）
{
printf（"Can'tfindthedata%d,thelistcan'tbeinverted!
\n",key）;
returnNULL;
}
else
{
printf（"Findthedatasuccessful!
\n"）;
returnS;
}
}
Linklistinvert（HeadNode*L,LinklistS,intnum）//在链表中的某个结点之后插入num个结点
{
LinklistR,K,H;
inti;
R=S;
H=S->next;
if（num>0）
{
printf（"Pleaseinputthedataof%dinvertedLnode:
\n",num）;
L->len+=num;
}
else
printf（"Invertfailed!
\n"）;
for（i=0;i<=num-1;i++）
{
K=（Linklist）malloc（sizeof（Lnode））;
scanf（"%d",&K->data）;
R->next=K;
R=K;
}
R->next=H;
returnS;
}
voidprintlist（HeadNode*L,LinklistS）//打印链表中数据域的值
{
if（S==NULL）
printf（"Thelistisempty.\n"）;
else
{
printf（"Thelisthas%dLnodes.\n",L->len）;
printf（"Thelistis:
\n"）;
while（S!
=NULL）
{
printf（"%d--->",S->data）;
S=S->next;
}
printf（"NULL\n"）;
}
}
voiddeletelist（LinklistR）//释放链表
{
Linklisttemp;
while（R!
=NULL）
{
temp=R;
R=R->next;
free（temp）;
}
}
第一题存在的问题:
1.注意头结点与非头结点结构定义的差别，链表的长度由用户输入，需要排除用户错误输入即L->len小于0时的情况，并注意判断链表中是否只含有头结点；
2.在进行链表的创建与结点的查找操作时，需要读入每个结点的数据值及num的值，这时候需要清空缓存区，防止读入用户输入的多余的数据。
第二题实验程序代码：
#include
#include
typedefstructLnode{
intdata;
structLnode*next;
}Lnode,*Linklist;//非头结点结构定义
typedefstruct{
intlen;
Linklisthead;
}HeadNode;//头结点结构定义
Linklistcreatlist（HeadNode*L）;//创造含头结点的链表函数
Linklistget（HeadNode*L,LinklistH,intnum,intjudge）;//在链表中寻找数值小于num的结点并返回
Linklistdelete（HeadNode*L,LinklistS,LinklistR,intmin）;//释放链表中两个节点之间的所有节点空间
intjudgelist（LinklistS）;//判断链表是否按升序排列
voidprintlist（HeadNode*L,LinklistS）;//打印链表中数据域的值
voiddeletelist（LinklistS）;//释放链表
intmain（）
{
HeadNode*L=NULL;
LinklistS,R;
intmin,max;
L=（HeadNode*）malloc（sizeof（HeadNode））;
if（L==NULL）
return0;
L->head=creatlist（L）;
printlist（L,L->head）;
while（（judgelist（L->head））==0）//判断链表是否按升序排列，若不是，则提示用户重新输入，直至符合要求
{
deletelist（L->head）;
L->head=creatlist（L）;
printlist（L,L->head）;
}
if（L->head==NULL）//判断链表中是否只有头结点
{
printf（"Thelisthasnodata,can'tbedeleted!
\n"）;
return0;
}
printf（"Pleaseinputthemindataandthemaxdatayouwanttofindfordelete:
\n"）;
scanf（"%d%d",&min,&max）;
if（min>=max||max<=L->head->data）//无法进行删除的情况
{
printf（"Deletefailed!
\n"）;
printlist（L,L->head）;
return0;
}
else
{
S=get（L,L->head,min,0）;//0和1为开关，进行设置
R=get（L,S,max,1）;
if（min>=L->head->data）//判断删除的节点中是否包含头结点
S=delete（L,S,R->next,min）;
else
{
L->head=delete（L,L->head,R->next,min）;
}
if（S）
printf（"Deletesuccessful!
\n"）;
else
printf（"Deletefailed!
\n"）;
}
printlist（L,L->head）;
deletelist（L->head）;
free（L）;//释放头结点
system（"pause"）;
return0;
}
Linklistcreatlist（HeadNode*L）//创造含头结点的链表函数
{
LinklistS=NULL,R=NULL,N=NULL;
inti;
printf（"Pleaseinputthelengthofthelist:
\n"）;
scanf（"%d",&L->len）;
fflush（stdin）;//清空缓冲区，防止读入用户多输入的数据
if（L->len<=0）
return0;
printf（"Pleaseinputthedata:
\n"）;
for（i=0;i<=L->len-1;i++）
{
S=（Linklist）malloc（sizeof（Lnode））;
if（S!
=NULL）
{
if（R==NULL）
{
R=S;
N=S;
}
scanf（"%d",&S->data）;
R->next=S;
R=S;
}
}
fflush（stdin）;
R->next=NULL;
L->head=N;
returnL->head;
}
Linklistget（HeadNode*L,LinklistH,intnum,intjudge）//在链表中寻找数值小于num的结点并返回
{
LinklistS;
S=H;
if（judge==0）//设置开关，最小值与最大值寻找结点的差异区分开来
while（S->next&&S->next->data<=num）
S=S->next;
else
while（S->next&&S->next->dataS=S->next;
returnS;
}
Linklistdelete（HeadNode*L,LinklistS,LinklistR,intmin）//释放链表中两个节点之间的所有节点空间
{
LinklistH,K;
if（min==S->data||S!
=L->head）//注意是否为头结点，进行区分
K=S->next;
else
K=S;
if（!
K||K==R）
returnNULL;
while（K&&K!
=R）
{
H=K;
K=K->next;
free（H）;
L->len--;
}
if（min==S->data||S!
=L->head）//注意是否为头结点，进行区分
{
S->next=K;
returnS;
}
else
{
L->head=K;
returnL->head;
}
}
intjudgelist（LinklistS）
{
Linklisttemp;
while（S!
=NULL）
{
temp=S;
S=S->next;
if（S!
=NULL&&temp->data>=S->data）
{
printf（"Thelistisn'tlistedrightfromthesmalldatatobigdata,pleaseinputthedataagain!
\n"）;
return0;
}
}
return1;
}
voidprintlist（HeadNode*L,LinklistS）//打印链表中数据域的值
{
if（S==NULL）
printf（"Thelistisempty,ithas0data.\n"）;
else
{
printf（"Thelisthas%dLnodes.\n",L->len）;
printf（"Thelistis:
\n"）;
while（S!
=NULL）
{
printf（"%d--->",S->data）;
S=S->next;
}
printf（"NULL\n"）;
}
}
voiddeletelist（LinklistS）//释放链表
{
Linklisttemp;
while（S!
=NULL）
{
temp=S;
S=S->next;
free（temp）;
}
}
第二题存在的问题:
1.链表的创建需要用户自己输入每个结点的数值,因而需要在用户创建完链表之后,对链表进行判断，判断是否为升序链表,若不是，则提示用户重新输入每个结点的数值，直至链表为升序链表，再进行相应的结点删除操作。
2.进行相关的删除操作时，应注意区分删除的结点是否包括头指针所指向的结点，以及在链表中查找大于min与小于max所对应的结点的差异，注意排除用户错误输入的情况，即min可能大于等于max的值。
3.在进行链表的创建与结点的查找操作时，需要读入每个结点的数据值及min和max，因而需要清空缓存区，防止读入用户输入的多余的数据。
升级会员 