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