实验一线性表地基本操作实现及其应用.docx
《实验一线性表地基本操作实现及其应用.docx》由会员分享，可在线阅读，更多相关《实验一线性表地基本操作实现及其应用.docx（25页珍藏版）》请在冰点文库上搜索。
实验一线性表地基本操作实现及其应用
实验一线性表的基本操作实现及其应用
一、实验目的
1、熟练掌握线性表的基本操作在两种存储结构上的实现。
2、会用线性链表解决简单的实际问题。
二、实验内容
题目一链表基本操作
该程序的功能是实现单链表的定义和操作。
该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。
其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。
单链表操作的选择以菜单形式出现，如下所示：
pleaseinputtheoperation：
1.初始化2.清空3.求链表长度4.检查链表是否为空
5.检查链表是否为满6.遍历链表（设为输出元素）7.从链表中查找元素
8.从链表中查找与给定元素值相同的元素在表中的位置
9.向链表中插入元素10.从链表中删除元素
其他键退出。
。
。
。
。
实验一线性表的基本操作实现及其应用
一、实验目的
1、熟练掌握线性表的基本操作在两种存储结构上的实现。
2、会用线性链表解决简单的实际问题。
二、实验内容
题目一链表基本操作
该程序的功能是实现单链表的定义和操作。
该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。
其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。
单链表操作的选择以菜单形式出现，如下所示：
pleaseinputtheoperation：
1.初始化2.清空3.求链表长度4.检查链表是否为空
5.检查链表是否为满6.遍历链表（设为输出元素）7.从链表中查找元素
8.从链表中查找与给定元素值相同的元素在表中的位置
9.向链表中插入元素10.从链表中删除元素
其他键退出。
。
。
。
。
题目一链表基本操作
一、数据结构与核心算法的设计描述
1、单链表的最大长度
#defineMAXSIZE100
2、单链表的结点类型定义
/*定义elemtype为int类型*/
typedefintelemtype;
/*单链表的结点类型*/
typedefstructSTD
{
elemtypeelem;
STD*next;
}list,*linklist;
3、初始化单链表
/*函数功能：
对链表进行初始化
参数：
链表（linklistL）
成功初始化返回1,否则返回0*/
intinit（linklist&L）
{
L=（linklist）malloc（sizeof（list））;//头结点申请内存。
if（!
L）//判断有无申请到空间。
return0;//没有申请到内存,参数失败返回0
L->next=NULL;
L->elem=0;//单链表中有多少元素
return1;//成功参数返回1
}
4、清空单链表
/*函数功能：
把链表清空
参数：
链表（linklistL）
成功清空链表返回1*/
intmakeempty（linklist&L）
{
linklistp,q;
p=L->next;
while（p）//当p非空时，删除p
{
q=p;
p=p->next;
free（q）;
}
L->next=NULL;//只剩头指针，所以L->next=NULL
L->elem=0;//清空后链表中元素为0
return1;//清空后返回1
}
5、求链表长度
/*函数功能:
返回链表的长度
参数;链表（linklistL）
函数返回链表的长度*/
intgetlength（linklistL）
{
linklistp;
p=L->next;
intj=0;
while（p）
{
j++;//统计链表中元素
p=p->next;
}
returnj;//最后返回链表长度.
}
6、判断链表是否为空
/*函数功能:
判断链表是否为空
参数;链表（linklistL）
链表为空时返回0,不为空返回1*/
intisempty（linklistL）
{
if（L->next）//头结点后有元素表示链表不空则返回1
return1;
else
return0;//头结点后没有元素表示链表不空则返回0
}
7、检查链表是否为满
/*函数功能:
判断链表是否为满
参数;链表（linklistL）
链表为满时返回0,不为满返回1*/
intisfull（linklistL）
{
if（L->elem<=MAXSIZE）//头结点的elem储存的为链表的长度。
return1;//其小于MAXSIZE表示链表不满
else
return0;//否则返回0
}
8、遍历链表
/*函数功能:
遍历链表,输出每个节点的elem值
参数;链表（linklistL）
通过循环逐个输出节点的elem值*/
voidshow（linklistL）
{
linklistp;
p=L->next;
if（isempty（L）==0）//当链表为空时则输出链表为空
{
cout<<"链表为空！
";
}
while（p）//当链表为不空时则输出链表每个节点的elem值
{
cout<elem<<"";
p=p->next;
}
cout<}
9、从链表中查找元素
/*函数功能:
从链表中查找有无给定元素
参数;链表（linklistL）,给定元素（inti）
如果链表中有给定元素（i）则返回1,否则返回0*/
intfind（linklistL,inti）
{
linklistp;
p=L->next;
while（p）
{
if（p->elem==i）//判断有无元素I,有返回1
return1;
p=p->next;
}
return0;//没有找到返回0
}
10、从链表中查找与给定元素值相同的元素在表中的位置
/*函数功能:
从链表中查找给定元素的位置
参数;链表（linklistL）,给定元素（inti）
如果链表中有给定元素i则返回元素的位置,没有则返回0*/
intlocation（linklistL,inti）
{
linklistp;
intj=0;
p=L->next;
while（p）
{
j++;
if（p->elem==i）//判断有无元素i,有返回其的位置j
returnj;
p=p->next;
}
return0;//没有则返回0
}
11、向链表中插入元素
/*函数功能:
向链表中的某个位置插入元素
参数;链表（linklistL）,位置（inti）,元素（elemtypee）
成功插入返回1,否则返回0*/
intinsert（linklist&L,inti,elemtypee）
{
linklistp,s;
intj=0;
p=L;
while（p&&j{
p=p->next;
j++;
}
if（j>i-1||!
p）//不符合条件返回0
return0;
s=（linklist）malloc（sizeof（list））;//给节点s分配内存
s->elem=e;
s->next=p->next;//插入操作
p->next=s;
L->elem++;//插入完成后头结点的elem加1
return1;//成功插入返回1
}
12、从链表中删除元素
/*函数功能:
在链表中的某个位置删除元素
参数;链表（linklistL）,位置（inti）,元素（elemtypee）
成功删除返回1,否则返回0*/
intdeleteelem（linklist&L,inti）
{
linklistp,q;
intj=0;
p=L;
while（p->next&&j{
p=p->next;
j++;
}
if（j>i-1||!
（p->next））//不符合条件返回0
return0;
q=p->next;
p->next=q->next;//删除操作
free（q）;
L->elem--;////插入完成后头结点的elem减1
return1;//成功删除返回1
}
13、主界面函数
/*函数功能:
显示所有操作功能
参数;无*/
voidzhujiemian（）
{
cout<cout<<"\t\t\t\t数据结构实验一"<cout<<"\t\t------------------------------------------"<cout<<"\t\t1链表初始化"<cout<<"\t\t2清空链表"<cout<<"\t\t3求链表长度"<cout<<"\t\t4链表是否为空"<cout<<"\t\t5检查链表是否为满"<cout<<"\t\t6遍历链表"<cout<<"\t\t7从链表中查找元素"<cout<<"\t\t8从链表中查找与给定元素值相同的元素在表中的位置"<cout<<"\t\t9向链表中插入元素"<cout<<"\t\t10从链表中删除元素"<cout<<"\t\t其他键退出"<cout<<"\t\t------------------------------------------"<cout<<"\t请选择要进行操作的序号（1--10）:
";
}
二、函数调用及主函数设计
主函数主要设计：
zhujiemian（）;//显示主界面
cin>>a;//输入要进行的操作的序号
cout<do
{
switch（a）//用switch语句进行选择操作
{
case1:
//初始化
if（init（L）==1）
cout<<"初始化成功！
"<else
cout<<"初始化失败！
"<break;
case2:
if（makeempty（L）==1）//链表置空
cout<<"链表已清空！
"<else
cout<<"链表清空失败！
"<break;
case3:
//链表的长度
b=getlength（L）;
cout<<"链表的长度为：
"<break;
case4:
//判断链表是否空
if（isempty（L）==1）
cout<<"链表不空！
"<else
cout<<"链表为空！
"<break;
case5:
//判断链表是否满
if（isfull（L）==1）
cout<<"链表不满！
"<else
cout<<"链表已满！
"<break;
case6:
//遍历链表
show（L）;
break;
case7:
//链表是否有要查找元素
cout<<"您要查找的元素：
";
cin>>b;
if（find（L,b）==1）
cout<<"链表中有元素"<else
cout<<"链表没中有元素"<break;
case8:
//输出链表要查找元素的位置
cout<<"您要查找的元素为：
"<cin>>b;
if（location（L,b）==0）
cout<<"没有您要查找的元素"<else
cout<<"您查找的元素"<"<break;
case9:
do{
cout<<"输入你要插入的位置和元素"<cin>>b>>c;
while（b<=0||b>getlength（L）+1）
/*此处可以对错误的输入进行判断*/
{
cout<<"插入位置错误！
请重新插入！
"<cin>>b>>c;
}
if（insert（L,b,c）==0）
cout<<"您插入的位置不对，插入失败！
"<else
cout<<"插入成功！
"<cout<<"是否继续插入元素（Y/y继续）,其他键停止插入\n";//提示是否继续进行插入操作
cin>>YES;
}while（YES=='Y'||YES=='y'）;
break;
case10:
do{
if（getlength（L）==0）
//判断链表是否为空若是则输出链表为空，并继续
{
cout<<"链表为空无法删除！
"<break;
}
cout<<"输入你要删除元素的位置：
"<cin>>b;
while（b<=0||b>getlength（L））
/*此处可以对错误的输入进行判断*/
{
cout<<"输入错误！
请重新输入！
"<cin>>b;
}
if（deleteelem（L,b）==0）
cout<<"您删除的位置不对，删除失败！
"<else
cout<<"删除成功！
"<cout<<"是否继续删除元素（Y/y继续）,其他键停止删除\n";//提示是否继续进行删除操作
cin>>YES;
}while（YES=='Y'||YES=='y'）;
break;
default:
break;
}
system（"pause"）;////按任意键继续
system（"cls"）;////清理屏幕上的内容
zhujiemian（）;///显示主界面
cin>>a;//输入要进行操作的序号
cout<}while（a>0&&a<=10）;///对进行输入的数进行判断（不在0—9则程序结束）
说明：
通过调用序列号不同的函数进行各种操作。
函数根据每次输入的数进行判断不在1—10内的函数将结束，否则将继续进行。
三、程序调试及运行结果分析
程序第一步必须执行初始化，否则程序不能运行。
在程序第一步必须执行初始化后，程序完美运行，在进行任何函数操作程序都是正常运行，而且本程序对插入和删除时进行错误检测如有的地方不可以插入，有点地方不能删除，如果链表为空时则程序会输出链表为空，并继续进行其他操作，大大减少了程序的bug。
四、实验总结
通过这次试验我熟悉了对链表的基本操作，对基本的链表操作有了很好的掌握，知道自己容易在什么地方出错。
五、程序清单
//实验一.h
#include"iostream"
#include"malloc.h"
#include"stdlib.h"
#include"windows.h"
usingnamespacestd;
#defineMAXSIZE100//链表的最大长度
typedefintelemtype;
typedefstructSTD
{
elemtypeelem;
STD*next;
}list,*linklist;
voidzhujiemian（）
{
cout<cout<<"\t\t\t\t数据结构实验一"<cout<<"\t\t----------------------------------------------"<cout<<"\t\t1链表初始化"<cout<<"\t\t2清空链表"<cout<<"\t\t3求链表长度"<cout<<"\t\t4链表是否为空"<cout<<"\t\t5检查链表是否为满"<cout<<"\t\t6遍历链表"<cout<<"\t\t7从链表中查找元素"<cout<<"\t\t8从链表中查找与给定元素值相同的元素在表中的位置"<cout<<"\t\t9向链表中插入元素"<cout<<"\t\t10从链表中删除元素"<cout<<"\t\t其他键退出"<cout<<"\t\t----------------------------------------------"<cout<<"\t请选择要进行操作的序号（1--10）:
";
}
intinit（linklist&L）
{
L=（linklist）malloc（sizeof（list））;
if（!
L）
return0;
L->next=NULL;
L->elem=0;
return1;
}
intinsert（linklist&L,inti,elemtypee）
{
linklistp,s;
intj=0;
p=L;
while（p&&j{
p=p->next;
j++;
}
if（j>i-1||!
p）
return0;
s=（linklist）malloc（sizeof（list））;
s->elem=e;
s->next=p->next;
p->next=s;
L->elem++;
return1;
}
intdeleteelem（linklist&L,inti）
{
linklistp,q;
intj=0;
p=L;
while（p->next&&j{
p=p->next;
j++;
}
if（j>i-1||!
（p->next））
return0;
q=p->next;
p->next=q->next;
free（q）;
L->elem--;
return1;
}
intisempty（linklistL）
{
if（L->next）
return1;
else
return0;
}
voidshow（linklistL）
{
linklistp;
p=L->next;
if（isempty（L）==0）
{
cout<<"链表为空！
";
}
while（p）
{
cout<elem<<"";
p=p->next;
}
cout<}
intgetlength（linklistL）
{
linklistp;
p=L->next;
intj=0;
while（p）
{
j++;
p=p->next;
}
returnj;
}
intmakeempty（linklist&L）
{
linklistp,q;
p=L->next;
while（p）
{
q=p;
p=p->next;
free（q）;
}
L->next=NULL;
L->elem=0;
return1;
}
intfind（linklistL,inti）
{
linklistp;
p=L->next;
while（p）
{
if（p->elem==i）
return1;
p=p->next;
}
return0;
}
intlocation（linklistL,inti）
{
linklistp;
intj=0;
p=L->next;
while（p）
{
j++;
if（p->elem==i）
returnj;
p=p->next;
}
return0;
}
intisfull（linklistL）
{
if（L->elem<=MAXSIZE）
return1;
else
return0;
}
//main.cpp
#include"iostream"
#include"malloc.h"
#include"stdlib.h"
#include"windows.h"
#include"实验一.h"
usingnamespacestd;
intmain（）
{
charYES;
linklistL;
inta,b,c;
zhujiemian（）;
cin>>a;
cout<do
{
switch（a）
{
case1:
if（init（L）==1）
cout<<"初始化成功！
"<else
cout<<"初始化失败！
"<break;
case2:
if（makeempty（L）==1）
cout<<"链表已清空！
"<else
cout<<"链表清空失败！
"<break;
case3:
升级会员 