实验二链表的基本操作实验报告.docx
《实验二链表的基本操作实验报告.docx》由会员分享，可在线阅读，更多相关《实验二链表的基本操作实验报告.docx（13页珍藏版）》请在冰点文库上搜索。
实验二链表的基本操作实验报告
实验名称
链表的基本操作及应用
实验日期
2019.10.09
实验成绩
1、实验目的：
1．掌握线性表的链式存储结构的表示和实现方法。
2．掌握单链表基本操作的算法实现。
3．了解单链表的应用。
2、实验内容：
1.编写一个程序，实现单链表的各种基本运算（假设单链表的元素类型为char），并在此基础上设计一个主程序完成如下功能：
（1）初始化单链表h；
（2）依次采用尾插法插入a、b、c、d、e元素；
（3）输出单链表h；
（4）输出单链表h的长度；
（5）判断单链表h是否为空；
（6）输出单链表h的第3个元素；
（7）输出元素a的位置
（8）在第4个元素位置上插入f元素
（9）输出单链表h；
（10）删除h的第3个元素；
（11）输出单链表h；
（12）释放单链表h。
3、核心算法或代码片段：
核心算法：
1．链表建立操作的基本步骤：
链表是一个动态的结构，它不需要分配空间，因此建立链表的过程是一个结点“逐个插入”的过程。
先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到链表的头部或尾部，分别称其为“头插法”和“尾插法”。
2．链表查找操作的基本步骤：
因链表是一种"顺序存取"的结构，则要在带头结点的链表中查找到第i个元素，必须从头结点开始沿着后继指针依次"点数"，直到点到第i个结点为止,如果查找成功，则用e返回第i个元素值。
头结点可看成是第0个结点。
3．链表插入操作的基本步骤：
先确定要插入的位置，如果插入位置合法，则再生成新的结点，最后通过修改链将新结点插入到指定的位置上。
4．链表删除操作的基本步骤：
先确定要删除的结点位置，如果位置合法，则再通过修改链使被删结点从链表中“卸下”，最后释放被删结点的空间。
单链表的存储结构描述如下：
typedefstructLNode//定义单链表结点类型
{
ElemTypedata;
structLNode*next;
}LinkList;
初始化链表：
voidInitList（LinkList*&L）
{
L=（LinkList*）malloc（sizeof（LinkList））;//创建头结点
L->next=NULL;
}
销毁线性表：
voidDestroyList（LinkList*&L）//销毁线性表
{
LinkList*p=L,*q=p->next;
while（q!
=NULL）
{
free（p）;
p=q;
q=p->next;
}
free（p）;
}
判断是否为空表：
boolListEmpty（LinkList*L）//判线性表是否为空表
{
return（L->next==NULL）;
}
求线性表长度：
intListLength（LinkList*L）//求线性表的长度
{
LinkList*p=L;inti=0;
while（p->next!
=NULL）
{
i++;
p=p->next;
}
return（i）;
}
输出线性表：
voidDispList（LinkList*L）//输出线性表
{
LinkList*p=L->next;
while（p!
=NULL）
{
printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
}
求线性表某个数据元素值：
boolGetElem（LinkList*L,inti,ElemType&e）//求线性表中某个数据元素值
{
intj=0;
LinkList*p=L;//p指向头节点,j置为0（即头节点的序号为0）
while（j=NULL）//找第i个节点
{j++;
p=p->next;
}
if（p==NULL）//不存在第i个数据节点,返回0
returnfalse;
else//存在第i个数据节点,返回1
{e=p->data;
returntrue;
}
}
按元素值查找：
intLocateElem（LinkList*L,ElemTypee）//按元素值查找
{inti=1;
LinkList*p=L->next;//p指向开始节点,i置为1（即开始节点的序号为1）
while（p!
=NULL&&p->data!
=e）//查找data值为e的节点,其序号为i
{p=p->next;
i++;
}
if（p==NULL）//不存在元素值为e的节点,返回0
return（0）;
else//存在元素值为e的节点,返回其逻辑序号i
return（i）;
}
链表的插入：
boolListInsert（LinkList*&L,inti,ElemTypee）//插入数据元素
{
intj=0;
LinkList*p=L,*s;//p指向头节点,j置为0（即头节点的序号为0）
while（j=NULL）//查找第i-1个节点
{j++;
p=p->next;
}
if（p==NULL）//未找到第i-1个节点,返回false
returnfalse;
else//找到第i-1个节点*p,插入新节点并返回1
{s=（LinkList*）malloc（sizeof（LinkList））;
s->data=e;//创建新节点*s,其data域置为e
s->next=p->next;//将*s插入到*p之后
p->next=s;
returntrue;
}
}
线性表的删除：
boolListDelete（LinkList*&L,inti,ElemType&e）//删除数据元素
{
intj=0;
LinkList*p=L,*q;//p指向头节点,j置为0（即头节点的序号为0）
while（j=NULL）//查找第i-1个节点
{j++;
p=p->next;
}
if（p==NULL）//未找到第i-1个节点,返回false
returnfalse;
else//找到第i-1个节点*p
{q=p->next;//q指向第i个节点
if（q==NULL）//若不存在第i个节点,返回false
returnfalse;
e=q->data;
p->next=q->next;//从单链表中删除*q节点
free（q）;//释放*q节点
returntrue;//返回true表示成功删除第i个节点
}
}
代码：
#include
#include
typedefcharElemType;
#defineMaxsize50
typedefstructLNode//定义单链表结点类型
{
ElemTypedata;
structLNode*next;
}LinkList;
voidInitList（LinkList*&L）//初始化单链表
{
L=（LinkList*）malloc（sizeof（LinkList））;//创建头结点
L->next=NULL;
}
voidDestroyList（LinkList*L）//销毁单链表
{
LinkList*p=L,*q=L->next;
while（q!
=NULL）
{
free（p）;
p=q;
q=p->next;
}
free（p）;
}
boolListEmpty（LinkList*L）//判断单链表是否为空
{
return（L->next==NULL）;
}
intListLength（LinkList*L）//求单链表的长度
{
LinkList*p=L;
inti=0;
while（p->next!
=NULL）
{
i++;
p=p->next;
}
return（i）;
}
voidDispList（LinkList*L）//输出单链表
{
LinkList*p=L->next;
//inti=0;
while（p->next!
=NULL）
{
printf（"%c",p->data）;
p=p->next;
}
printf（"%c",p->data）;
printf（"\n"）;
}
boolGetElem（LinkList*L,inti,ElemType&e）//求单链表中某个元数的值
{
LinkList*p=L;
intj=0;
while（p!
=NULL&&j{
j++;
p=p->next;
}
if（p==NULL）
returnfalse;
else
{
e=p->data;
returntrue;
}
}
intLocateElem（LinkList*L,ElemTypee）//按元素值查找
{
LinkList*p=L;
intj=0;
while（p!
=NULL&&p->data==e）
{
j++;
p=p->next;
}
if（p==NULL）
return0;
else
{
return（j+1）;
}
}
boolListInsert（LinkList*L,inti,ElemTypee）//插入数据元素
{
LinkList*p=L,*s;
intj=0;
while（p!
=NULL&&j{
j++;
p=p->next;
}
if（p==NULL）
returnfalse;
else
{
s=（LinkList*）malloc（sizeof（LinkList））;
s->data=e;
s->next=p->next;
p->next=s;
returntrue;
}
}
boolListDelete（LinkList*L,inti,ElemType&e）
{
LinkList*p=L,*s;
intj=0;
while（p!
=NULL&&j{
j++;
p=p->next;
}
if（p==NULL）
returnfalse;
else
{
s=p->next;
if（s==NULL）
returnfalse;
e=s->data;
p->next=s->next;
free（s）;
returntrue;
}
}
intmain（）
{
LinkList*h;
ElemTypee;
printf（"单链表的基本运算如下：
\n"）;
printf（"
（1）初始化单链表h：
\n"）;
InitList（h）;
printf（"
（2）依此采用尾插法插入a,b,c,d,e元素：
\n"）;
ListInsert（h,1,'a'）;
ListInsert（h,2,'b'）;
ListInsert（h,3,'c'）;
ListInsert（h,4,'d'）;
ListInsert（h,5,'e'）;
printf（"（3）输出单链表h：
\n"）;
DispList（h）;
printf（"（4）单链表h长度为：
\n"）;
printf（"%d\n",ListLength（h））;
printf（"（5）单链表h为%s\n",（ListEmpty（h）?
"空":
"非空"））;
GetElem（h,3,e）;
printf（"（6）单链表h的第3个元素是：
\n"）;
printf（"%c\n",e）;
printf（"（7）元素a的位置：
\n"）;
printf（"%d\n",LocateElem（h,'a'））;
printf（"（8）在第四个元素位置上插入f元素：
\n"）;
ListInsert（h,4,'f'）;
printf（"（9）输出单链表h:
"）;
DispList（h）;
printf（"（10）删除h的第3个元素：
\n"）;
ListDelete（h,3,e）;
printf（"（11）输出单链表h：
\n"）;
DispList（h）;
printf（"（12）释放单链表h：
"）;
DestroyList（h）;
}
4、实验结果分析及总结体会：
实验结果：
对单链表hInitList（）创建头结点并初始化L->next=NULL;利用尾插法ListInsert（）依次插入a,b,c,d,e。
即改变最后一个结点的next域指向新插入的数据。
输出单链表DispList（）和输出单链表的长度ListLength（）,需要对于判断每一个结点的next域直到next域等于NULL，单链表是否为空ListEmpty（）对头结点的（L->next）域判断是否为null。
确定某一个位置的数据GetElem（）时，同样也要考虑结点的next域,在没有达到i值但p->next==null,则返回错误。
在单链表中间的某一个位置插入数据ListInsert（）时对指针的改变要注意,要先将被插入结点的指针指向他后面位置的结点然后将前面的结点的next域指向被插入结点，否则后面的数据会发生丢失。
再删除数据时ListDelete（）只需要对指针进行改变，最后释放内存DestroyList（）;
总结体会：
通过本次实验掌握了线性表的链式存储结构的表示和实现方法，还学会了单链表基本操作的算法实现。
同时还了解单链表的应用，理解了单链表的用途，同时并能通过单链表解决一些简单问题，但同时也发现了自己的不足，基础不足，还需多练习。
升级会员 