链表实验报告
数据结构实验报告
姓名; 方钢 学号: 20105567 专业: 电子商务 班 级: 10-1班
指导教师: 实验时间: 实验地点:新区实验楼4楼
(实验题目)单链表实验
1.实验内容和要求
1.1实验要求
① 本次实验中的链表结构均为带头结点的单链表;
② 链表结构定义,算法实现放入库文件“linkList.h”;
运算和变量命名直观易懂,并有相应的注释
1.2实验内容
求链表中第i个结点的指针(函数),若不存在,则返回NULL。
在第i个结点前插入值为x的结点。
删除链表中第i个元素结点。
在一个递增有序的链表L中插入一个值为x的元素,并保持其递增有序特
性。
将单链表L中的奇数项和偶数项结点分解开(元素值为奇数、偶数),申请
2个头结点,把分开的奇数项和偶数项分别链接到这2个头结点上,然后再
将 这两个新链表同时输出在屏幕上,并保留原链表的显示结果,以便对照
求解 结果。 求两个递增有序链表L1和L2中的公共元素,并以同样方式连接成链表L3。
2.实验目的
2.1 理解线性表的链式存储结构。
2.2熟练掌握单链表结构及有关算法的设计。
2.3根据具体问题的需要,设计出合理的表示数据的链表结构,并设计相关
算法。
3.数据结构设计
求链表中第i个结点的指针(函数),若不存在,则返回NULL。
实验代码
node *L,*p;
int i;
createNode(*&L); //尾插法创建一个链表,
cout
p=L->next;
while(p)
{
coutdata
p=p->next;
}
cout
cout
cin>>i;
locateNode (L, i, &p );
if(p!=NULL)
coutdata
else
cout
destroyList(L); //销毁链表,释放heap内存
_CrtDumpMemoryLeaks(); //debug 模式下检测是否内存泄漏
测试截图
在第i个结点前插入值为x的结点。
实验代码
node *L,*p;
int i;
elementType x;
createNode(L); //尾插法创建一个链表,
cout
p=L->next;
while(p)
{
coutdata
p=p->next;
}
cout
cout
cout
cin>>x;
cout
cin>>i;
//调用插入函数,并检查是否插入成功
if(insertNode (L,i,x))
cout
cout
//打印插入元素后的链表
cout
p=L->next;
while(p)
{
coutdata
p=p->next;
}
cout
cout
destroyList(L); //销毁链表,释放heap内存
_CrtDumpMemoryLeaks(); //debug 模式下检测是否内存泄漏
测试截图
删除链表中第i个元素结点。
实验代码
node *L,*p;
int i;
elementType x;
creatNode(L); //尾插法创建一个链表,
cout
p=L->next;
while(p)
{
coutdata
p=p->next;
}
cout
cout
cout
cin>>i;
//调用删除函数,并检查是否删除成功
if(deleteNode (L,i))
cout
else
cout
//删除节点后的链表
cout
cout
p=L->next;
while(p)
{
coutdata
p=p->next;
}
cout
destroyList(L); //销毁链表,释放heap内存
_CrtDumpMemoryLeaks(); //debug 模式下检测是否内存泄漏
测试截图
在一个递增有序的链表L中插入一个值为x的元素,并保持其递增有序特性。 实验代码
node *L,*p;
elementType x;
createNode(L); //尾插法创建一个链表,
cout
p=L->next;
while(p)
{
coutdata
p=p->next;
}
cout
cout
cout
cin>>x;
rankInsert (L,x);
cout
p=L->next;
while(p)
{
coutdata
p=p->next;
}
cout
destroyList(L); //销毁链表,释放heap内存
_CrtDumpMemoryLeaks(); //debug 模式下检测是否内存泄漏
测试截图
将单链表L中的奇数项和偶数项结点分解开(元素值为奇数、偶数),申请2
个头结点,把分开的奇数项和偶数项分别链接到这2个头结点上,然后再将 这两个新链表同时输出在屏幕上,并保留原链表的显示结果,以便对照求解 结果。
实验代码
node *L,*p,*A,*B,*k,*m;
createNode(L); //尾插法创建一个链表,
cout
p=L->next;
while(p)
{
coutdata
p=p->next;
}
cout
cout
seperateNode (L,A,B);
cout
k=A->next;
while(k)
{
coutdata
k=k->next;
}
cout
cout
m=B->next;
while(m)
{
coutdata
m=m->next;
}
cout
destroyList(L); //销毁链表,释放heap内存
_CrtDumpMemoryLeaks(); //debug 模式下检测是否内存泄漏
测试截图
求两个递增有序链表L1和L2中的公共元素,并以同样方式连接成链表L3。 实验代码
node *L,*A,*B,*p,*q,*r;
createNode(A);
createNode(B);
int t;
cout
p=A->next;
while(p)
{
coutdata
p=p->next;
}
cout
cout
q=B->next;
while(q)
{
coutdata
q=q->next;
}
cout
t=getPENode (A,B,L);
switch(t)
{
case 0:
cout
break;
case 1:
cout
}
r=L->next;
while(r)
{
coutdata
r=r->next;
}
cout
destroyList(L); //销毁链表,释放heap内存
_CrtDumpMemoryLeaks(); //debug 模式下检测是否内存泄漏 测试截图
4总结和心得
1>通过对链表上机实验的操作更加了解了可以用链来实现使用计算机零碎内存,并且知道了对使用过的内存使用destoryList来销毁内存的重要性;
2>整合各函数时遇到了线性表一样的问题,解决方法亦类似;
3>尾插法创建链表时,使用了直接用元素个数控制的方法,直接用p=p->next避免了连接链表指针的繁琐过程。