链表程序设计训练实习报告.docx
《链表程序设计训练实习报告.docx》由会员分享，可在线阅读，更多相关《链表程序设计训练实习报告.docx（19页珍藏版）》请在冰点文库上搜索。
链表程序设计训练实习报告
链表程序设计训练
一实验目的
●使学生掌握VisualC++6.0环境下C++语言程序调试与排错方法；
●使学生掌握单向链表结构并实现插入、删除、建表等基本功能操作；
●使学生掌握应单向循环链表结构并实现插入、删除、建表等基本功能操作；
●使学生掌握双向链表结构并实现插入、删除、建表等基本功能操作；
●使学生熟悉应用链表解决实际问题；
二实验环境
●所需硬件环境为微机；
●所需软件环境为MicrosoftVisualC++6.0或Code:
:
Blocks；
三实验内容
（二）、设计单向循环链表并实现其构建（包括正序及逆序建表）、插入、删除、销毁等基本操作算法
#include
#include
#defineOVERFLOW-2
#defineOK1
#defineFAILURE0
#defineTRUE1
#defineFALSE0
#defineERROR-1
typedefintElemType;
typedefintStatus;
typedefstructNode
{
ElemTypee;
structNode*next;
}ListNode,*list;
StatusDestroyList_Sl（listL）//销毁
{
listp;
if（!
L）returnERROR;/*单向线性链表不存在*/
do{/*释放单向线性链表空间*/
p=L->next;
L->next=p->next;
deletep;
}while（L）;
returnOK;
}
StatusListDelete_Sl（listL）
{
listp;
if（!
L）returnERROR;/*单向线性链表结点L不存在*/
p=L->next;
L->next=p->next;
deletep;
returnOK;
}
listset（intn）/*建立链表*/
{
listL,p,q;
L=newListNode;
L->e=0;
L->next=NULL;
p=L;
cout<<"正序的数字:
";
for（inti=0;i{
if（q=newListNode）
{
ElemTypet;
cin>>t;
q->e=t;
q->next=NULL;
p->next=q;
p=p->next;
}
else
{
while（p）
{
q=p;
p=NULL;
deletep;
p=q->next;
}
}
if（i==n-1）
{
p->next=L->next;
}
}
returnL;
}
listset2（intn）
{
listL2,p,q;
if（L2=newListNode）
{
L2->next=NULL;
L2->e=0;
cout<<"逆序数字:
";
for（inti=0;i{
intt;
cin>>t;
if（q=newListNode）
{
q->e=t;
q->next=NULL;
q->next=L2->next;
L2->next=q;
}
else
{
p=L2;
while（p）
{
L2=p;
deleteL2;
p=p->next;
}
}
}
p=L2->next;
while（p->next）
{
p=p->next;
}
p->next=L2;
}
returnL2;
}
intmain（）
{
listL,p,q,L2;
intn,ListDelete_number;
cout<<"个数：
"<cin>>n;
L=set（n）;
p=L->next;
inti=0;
while（p）
{
cout<e<<'\t';
p=p->next;
i++;
if（i==n）
{
break;
}
}//单链正序测试
cout<L2=set2（n）;
p=L2->next;
while（p!
=L2）
{
cout<e<<'\t';
p=p->next;
}
cout<ListDelete_number=ListDelete_Sl（L）;
cout<<"ListDelete_number="<p=L->next;
i=0;
cout<<"剩下的：
";
while（p）
{
cout<e<<'\t';
p=p->next;
i++;
if（i==n-1）
{
break;
}
}//删除结点及测试
DestroyList_Sl（L）;
return0;
}
（三）、设计双向链表并实现其构建（包括正序及逆序建表）、插入、删除、销毁等基本操作算法
#include
#include
#defineOVERFLOW-2
#defineOK1
#defineFAILURE0
#defineTRUE1
#defineFALSE0
#defineERROR-1
typedefintElemType;
typedefintStatus;
typedefstructNode
{
ElemTypee;
structNode*next;
structNode*last;
}ListNode,*list;
StatusDestroyList_Sl（listL）//销毁
{
listp;
if（!
L）returnERROR;/*单向线性链表不存在*/
do{/*释放单向线性链表空间*/
p=L->next;
L->next=p->next;
deletep;
}while（L）;
returnOK;
}
StatusListDelete_Sl（listL）
{
listp;
if（!
L）returnERROR;/*单向线性链表结点L不存在*/
p=L->next;
L->next=p->next;
deletep;
returnOK;
}
listset（intn）/*建立链表*/
{
listL,p,q;
L=newListNode;
L->e=0;
L->next=NULL;
p=L;
cout<<"正序的数字:
";
for（inti=0;i{
if（q=newListNode）
{
ElemTypet;
cin>>t;
q->e=t;
q->next=NULL;
p->next=q;
q->last=p;
p=p->next;
}
else
{
while（p）
{
q=p;
p=NULL;
deletep;
p=q->next;
}
}
if（i==n-1）
{
q=L->next;
p->next=q;
q->last=p;
}
}
returnL;
}
listset2（intn）
{
listL2,p,q;
if（L2=newListNode）
{
L2->next=NULL;
L2->e=0;
cout<<"逆序数字:
";
for（inti=0;i{
intt;
cin>>t;
if（q=newListNode）
{
q->e=t;
q->next=NULL;
q->next=L2->next;
L2->next=q;
}
else
{
p=L2;
while（p）
{
L2=p;
deleteL2;
p=p->next;
}
}
}
p=L2->next;
while（p->next）
{
p=p->next;
}
p->next=L2;
}
returnL2;
}
intmain（）
{
listL,p,q,L2;
intn,ListDelete_number;
cout<<"个数：
"<cin>>n;
L=set（n）;
p=L->next;
inti=0;
while（p）
{
cout<e<<'\t';
p=p->next;
i++;
if（i==n）
{
break;
}
}//单链正序测试
cout<cout<<"反向:
";
i=0;
p=L->next;
while（p）
{
p=p->last;
cout<e<<'\t';
i++;
if（i==n）
{
break;
}
}
cout<L2=set2（n）;
p=L2->next;
while（p!
=L2）
{
cout<e<<'\t';
p=p->next;
}
cout<ListDelete_number=ListDelete_Sl（L）;
cout<<"ListDelete_number="<p=L->next;
i=0;
cout<<"剩下的：
";
while（p）
{
cout<e<<'\t';
p=p->next;
i++;
if（i==n-1）
{
break;
}
}//删除结点及测试
DestroyList_Sl（L）;
return0;
}
（四）、分析并使用循环链表解决“猴子选大王”问题
#include
typedefstructNode
{
inte;
structNode*next;
structNode*last;
}ListNode,*list;
listset（intn）/*建立链表*/
{
listL,p,q;
L=newListNode;
L->e=0;
L->next=NULL;
p=L;
for（inti=0;i{
if（q=newListNode）
{
q->e=i+1;
q->next=NULL;
p->next=q;
q->last=p;
p=p->next;
}
else
{
while（p）
{
q=p;
p=NULL;
deletep;
p=q->next;
}
}
if（i==n-1）
{
q=L->next;
p->next=q;
}
}
p->next=L;
L->last=p;
returnL;
}
intmain（）
{
listL,p,q,t;
intn,m,i=0;
cout<<"总个数：
"<cin>>n;
cout<<"跳下报的数字:
"<cin>>m;
L=set（n）;
p=L;
/*while（p）
{
p=p->next;
cout<e<<'\t';
i++;
if（i==n+1）
{
break;
}
}*/
while（!
（（L==p->next）&&（p==L->next）））
{
p=p->next;
if（p->e>0）
{
i++;
if（i%m==0）
{
q=p->next;
t=p->last;
t->next=q;
q->last=t;
cout<<"delete"<e<deletep;
p=t;
}
}
}
cout<<"猴王：
"<e;
return0;
}
四实验分析及问题思考
1、分析双向循环链表与单向链表、循环链表、双向链表间的差异；
循环链表是在单向链表的基础上用最后面的指针指向头结点，而双向链表是在单向链表的基础上，定义一个指针，用后面的指向前面的结点。
2、分析数组与线性链表的优缺点；
数组不能删除其中元素，而链表可以删除结点。
链表程序设计训练
实验自评
实验内容
自评结果（在对应格内打）
熟练
比较熟练
一般
不熟练
动态内存分配
线性链表的操作与应用
线性链表结构
正序、逆序构建线性链表
线性链表元素插入
线性链表元素删除
线性链表元素查找
实验体会
通过半年对于链表的学习，对于链表相对熟悉，能够熟练的应用，这与平时的练习是分不开的。
以后也要经常复习。
升级会员 