数据结构实验报告（一）
2刘信息管理与信息系统09-3班
一、实验目的
（1）理解线性表的链式存储结构。
（2）熟练掌握动态链表结构及有关算法的设计。
（3）根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。
二、实验内容
编写算法实现下列问题的求解。
<1>求链表中第i个结点的指针（函数），若不存在，则返回NULL。
实验测试数据基本要求：
第一组数据：链表长度n≥10，i分别为5，n，0，n+1，n+2
第二组数据：链表长度n=0，i分别为0，2
<2>在第i个结点前插入值为_的结点。
实验测试数据基本要求：
第一组数据：链表长度n≥10，_=100,i分别为5,n,n+1,0,1,n+2
第二组数据：链表长度n=0，_=100，i=5
<3>删除链表中第i个元素结点。
实验测试数据基本要求：
第一组数据：链表长度n≥10，i分别为5,n,1,n+1,0
第二组数据：链表长度n=0，i=5
<4>在一个递增有序的链表L中插入一个值为_的元素，并保持其递增有序特性。实验测试数据基本要求：
链表元素为（10,20,30,40,50,60,70,80,90,100）,
_分别为25，85，110和8
<5>将单链表Ｌ中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。实验测试数据基本要求：
第一组数据：链表元素为（1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）第二组数据：链表元素为（10,20,30,40,50,60,70,80,90,100）
<6>求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。实验测试数据基本要求：
第一个链表元素为（1，3，6，10，15，16，17，18，19，20）
第二个链表元素为（1，2，3，4，5，6，7，8，9，10，18，20，30）第二组
第一个链表元素为（1，3，6，10，15，16，17，18，19，20）
第二个链表元素为（2，4，5，7，8，9，12，22）
第一个链表元素为（）
第二个链表元素为（1，2，3，4，5，6，7，8，9，10）
三、算法实现
（一）实验中，各个程序基本上都要实现结点结构体定义、建造链表、主函数实现，故首先将除特定程序所涉及到的具体算法外的公共程序部分（具体操作或有不同）写出如下：
（1）结点结构体定义：
typedefstructLNode
intdata;/定义元素值类型
structLNodene_t;/递归实现ne_t节点结构体的定义
}node;
（2）建造链表：
nodecreatlist()
nodeL;
nodeu;int_;
L=newnode;
L->ne_t=NULL;
puts("Pleaseuse'0'toendtheimput!");/头插法建造链表/
cin>_;
while(_!=0)
u=newnode;
u->data=_;
u->ne_t=L->ne_t;L->ne_t=u;
cin>_;
returnL;
（3）主函数实现：
voidmain()
定义变量；
调用所需函数；/不同实验要求有不同主函数实现
（二）具体算法以及部分运行界面截图
<1>查找：
a.计量长度函数listlen(nodeL)
其具体实现为：
intlistlen(nodeL)
{nodep=L->ne_t;
intnum=0;
while(p!=NULL)/计量链表长度的算法/计量链表长度/{num++;p=p->ne_t;}
returnnum;/返回长度值}
b.查找算法：
nodegetele(nodeL,inti)
{nodep=L->ne_t;intj=1;
while(j!=ip!=NULL)/查找算法
{p=p->ne_t;j++;}/实现查找元素/
if(p==NULL)
returnNULL;
elsereturnp;/返回链表头结点地址
<2>插入算法：
voidlistinsert(nodeL,inti,int_)
{nodeS;
nodeP=L;
nodeQ=P;
intk=0;
while(k!=i-1P!=NULL)/插入操作的实现/{P=P->ne_t;k++;}
if(P==NULL)
printf("序号溢出！");/异常处理
else{S=newnode;S->data=_;S->ne_t=P->ne_t;P->ne_t=S;/插入算法}Q=Q->ne_t;puts("Theresultis:");while(Q!=NULL){printf("%d ",Q->data);Q=Q->ne_t;}/打印puts(" ");
<3>删除算法：
voidlistdelete(nodeL,inti)
{nodeP=L,u;
nodeQ=L;
intk=0;
while(k!=i-1P!=NULL)
{P=P->ne_t;k++;}
if(P==NULL||P->ne_t==NULL)
puts("删除序号出错啦！");/删除算法的实现else
{u=P->ne_t;
P->ne_t=u->ne_t;/删除算法
deleteu;
Q=Q->ne_t;
while(Q!=NULL)
{printf("%d ",Q->data);Q=Q->ne_t;puts(" ");}
<4>顺序插入算法：
voidlistinsert(nodeL,int_)
{nodeu;
nodeP=L;
nodeQ=L;
while(P->ne_t!=NULLP->ne_t->data<_)
P=P->ne_t;/查找插入位置/插入操作的实现
if(P->ne_t==NULL||P->ne_t->data>_)
{u=newnode;
u->data=_;
u->ne_t=P->ne_t;/具体插入算法
P->ne_t=u;
Q=Q->ne_t;
puts("Thefinaloutputisasbelow:");
while(Q!=NULL)
{printf("%d ",Q->data);/打印
Q=Q->ne_t;
puts(" ");
<5>分解链表：
voidpart(nodeL)
{nodeA,B,P=L->ne_t,Q,R;
nodelinshi;
A=newnode;
B=newnode;
Q=A;R=B;
while(L->ne_t!=NULL)
if(L->ne_t->data%2==0)
{linshi=newnode;
linshi->data=L->ne_t->data;/偶数值赋给偶数链表
A->ne_t=linshi;
A=linshi;L=L->ne_t;
else
{linshi=newnode;
linshi->data=L->ne_t->data;/奇数值赋给奇数链表
B->ne_t=linshi;
B=linshi;L=L->ne_t;
A->ne_t=NULL;B->ne_t=NULL;
/以下皆为打印实现
puts("Theoriginalinputis：");/分解链表的实现while(P!=NULL)
{printf("%d ",P->data);P=P->ne_t;}
puts(" ");
puts("Thefirstoutputis(偶数)：");
if(Q->ne_t==NULL)
}{puts("None!(为空！)");}else{while(Q->ne_t!=NULL){printf("%d ",Q->ne_t->data);Q=Q->ne_t;}}puts(" ");puts("Thesecondoutputis(奇数):");if(R->ne_t==NULL){puts("None!(为空！)");}else{while(R->ne_t!=NULL){printf("%d ",R->ne_t->data);R=R->ne_t;}}puts(" ");
<6>两链表求交集：
nodeFindsame(nodeL1,nodeL2)
{nodeP1=L1->ne_t,P2=L2->ne_t,P3,U,T;
P3=newnode;T=P3;
while(P1!=NULLP2!=NULL)
if(P1->datadata)
P1=P1->ne_t;
elseif(P1->data>P2->data)/判断是否同值/求交集的实现P2=P2->ne_t;
}else{U=newnode;U->data=P1->data;P3->ne_t=U;P3=U;/把两链表中的共同元素赋给链表3P1=P1->ne_t;P2=P2->ne_t;}P3->ne_t=NULL;returnT;
四、实验总结
本次实验，重点是链表的构建及构建前提下各种其他操作的实现。链表实验的顺利进行有助于我们更好的掌握链表的使用。在本次实验中，我采用的是表头插入法建造链表，这样的构造方式在本次实验中有其优点，但也有不足：输出时逆序输出，若要获得顺序输出，则输入时应逆序输入。当然，对链表进行就地转置后也可实现顺序输出。
通过这次实验，我增进了对链表的了解与应用，当然，其中还存在很大不足，希望能在日后的学习中不断改进，不断提高！