数据结构实验1顺序表链表.docx
《数据结构实验1顺序表链表.docx》由会员分享，可在线阅读，更多相关《数据结构实验1顺序表链表.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构实验1顺序表链表
数据结构实验1顺序表-链表
淮海工学院计算机科学系
实验报告书
课程名：
《数据结构》
题目：
线性表数据结构试验
班级：
软件112
学号：
姓名：
评语：
成绩：
指导教师：
批阅时间：
年月日
线性表实验报告要求
1目的与要求:
1）掌握线性表数据结构的基本概念和抽象数据类型描述；
2）熟练掌握线性表数据结构的顺序和链式存储存表示；
3）熟练掌握线性表顺序存储结构的基本操作算法实现；
4）熟练掌握线性表的链式存储结构的基本操作算法实现;
5）掌握线性表在实际问题中的应用和基本编程技巧;
6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；
7）按照报告格式和内容要求，认真书写实验报告，并在试验后的第三天提交电子（全班同学提交到学委，再统一打包提交给老师）和纸质（每班每次5份，学委安排，保证每个同学至少提交一次）；
8）积极开展实验组组内交流和辅导，严禁复制和剽窃他人实验成果，一旦发现严肃处理；
9）上实验课前，要求每个同学基本写好程序，并存储在自己的U盘上，用于实验课堂操作时调试和运行。
凡不做准备，没有提前编写程序者，拒绝上机试验。
2实验内容或题目
一、顺序表的基本操作实现实验
要求：
数据元素类型ElemType取整型int。
按照顺序存储结构实现如下算法：
1）创建任意整数线性表（即线性表的元素值随机在键盘上输入）的顺序存储结构（即顺序表），长度限定在25之内；
2）打印/显示（遍历）该线性表（依次打印/显示出表中元素值）；
3）在顺序表中查找第i个元素，并返回其值；
4）在顺序表第i个元素之前插入一已知元素；
5）在顺序表中删除第i个元素；
6）求顺序表中所有元素值（整数）之和；
二、链表（带头结点）基本操作实验
要求：
数据元素类型ElemType取字符型char。
按照动态单链表结构实现如下算法：
1）按照头插法或尾插法创建一个带头结点的字符型单链表（链表的字符元素从键盘输入），长度限定在10之内；
2）打印（遍历）该链表（依次打印出表中元素值，注意字符的输入顺序与链表的结点顺序）；
3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；
4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；
5）在链表中第i个结点之前插入一个新结点；
6）在线性表中删除第i个结点；
7）计算链表的长度。
3实验步骤与源程序
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineElemTypeint
#defineMAXSIZE25/*此处的宏定义常量表示线性表可能达到的最大长度*/
usingnamespacestd;
typedefstruct
{
ElemTypeelem[MAXSIZE];/*线性表占用的数组空间*/
intlast;/*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1*/
}SeqList;
voidOutputSeqList（SeqList*L）
{
cout<<"顺序表如下：
"<inti;
for（i=0;i<=L->last;i++）
cout<elem[i]<<'\n';
cout<}
intGetDate（SeqList*L）
{
intt;
cout<<"请输入要查找的元素的序数：
"<cin>>t;
if（（t<0）||（t>L->last））
{
cout<<"输入错误！
";
return（ERROR）;
}
elsereturn（L->elem[t-1]）;
}
intInsList（SeqList*L）
{
inti,e;
cout<<"请输入要插入的元素插入位置及要插入的元素"<cin>>i>>e;
intk;
if（（i<1）||（i>L->last+2））/*首先判断插入位置是否合法*/
{
printf（"插入位置i值不合法"）;
return（ERROR）;
}
if（L->last>=MAXSIZE-1）
{
printf（"表已满无法插入"）;
return（ERROR）;
}
for（k=L->last;k>=i-1;k--）/*为插入元素而移动位置*/
L->elem[k+1]=L->elem[k];
L->elem[i-1]=e;/*在C语言数组中，第i个元素的下标为i-1*/
L->last++;
return（OK）;
}
intDelList（SeqList*L,ElemType*m）
{
intw;
cout<<"请输出要删除的元素位置：
"<cin>>w;
intk;
if（（w<1）||（w>L->last+1））
{
cout<<"删除位置不合法!
"<return（ERROR）;
}
*m=L->elem[w-1];/*将删除的元素存放到e所指向的变量中*/
for（k=w;k<=L->last;k++）
L->elem[k-1]=L->elem[k];/*将后面的元素依次前移*/
L->last--;
return（OK）;
}
intsum（SeqList*L）
{
inti,n=0;
for（i=0;ilast+1;i++）
n=n+L->elem[i];
return（n）;
}
voidmain（）
{
int*q,n;
SeqList*L;
L=（SeqList*）malloc（sizeof（SeqList））;
q=（int*）malloc（sizeof（int））;
cout<<"请输入顺序表长度：
";
cin>>n;
L->last=n-1;
cout<<"请输入顺序表：
"<inti;
for（i=0;icin>>L->elem[i];
charc='y';
while（c!
='n'）
{
cout<<"请选择你要进行的操作：
"<cout<<"1.输出顺序表；"<<'\n'<<"2.查找元素；"<<'\n'<<"3.插入元素；"<<'\n'<<"4.删除元素；"<<'\n'<<"5.求和"<intxuanze;
cin>>xuanze;
switch（xuanze）
{
case1:
OutputSeqList（L）;break;
case2:
cout<case3:
InsList（L）;break;
case4:
DelList（L,q）;break;
case5:
cout<}
cout<<"是否要继续进行操作y/n:
"<cin>>c;
}
#include
#include
#defineMAX15
#defineTURE1
#defineFALSE0
typedefcharElemType;
typedefstructNode
{
chardate;
structNode*next;
}Node,*LinkList;
voidInitList（LinkList*L）
{
*L=（LinkList）malloc（sizeof（char））;
（*L）->next=NULL;
}
voidPrintfLink（LinkListL）
{
LinkListp;
p=L->next;
printf（"链表为:
"）;
while（p!
=NULL）
{
printf（"%c",p->date）;
p=p->next;
}
}
voidCreate（LinkListL）
{
LinkLists,r;
charc;
intflag=1;
intn;
r=L;
printf（"元素个数:
"）;
scanf（"%d",&n）;
if（n>MAX）
printf（"超出限定长度!
"）;
else
{
printf（"输入字符（以#键结束）:
"）;
while（flag）
{
scanf（"%c",&c）;
if（c!
='#'）
{
s=（Node*）malloc（sizeof（char））;
s->date=c;
r->next=s;
r=s;
}
else
flag=0;
r->next=NULL;
}
}
}
voidOrder（LinkListL）
{
charc;
Node*r,*q,*p;
for（r=L->next;r->next!
=NULL;r=r->next）
{
p=r;
for（q=r->next;q;q=q->next）
if（（q->date）<（p->date））
p=q;
if（p!
=r）
{
c=r->date;
r->date=p->date;
p->date=c;
}
}PrintfLink（L）;
}
voidGet（LinkListL,inti,ElemType*e）
{
intj;Node*p;
p=L;j=-1;
while（（p->next!
=NULL）&&（j{
p=p->next;
j++;
}
*e=p->date;
if（i==j）
printf（"第%d个元素为:
%c",i,*e）;
else
printf（"FALSE"）;
}
voidLocate（LinkListL,ElemTypee）
{
inti=1;
LinkListp;
p=L->next;
while（p&&p->date!
=e）
{
i=i++;
p=p->next;
}
if（!
p）
printf（"FALSE\n"）;
else
{
printf（"TRUE\n"）;
printf（"该元素在第%d个位置!
",i-1）;
}
}
voidInsList（LinkListL,inti,ElemTypee）
{
Node*p,*s;
intk=0;
p=L;
while（p!
=NULL&&k{
p=p->next;
k=k++;
}
if（!
p）
{
printf（"插入位置不合理!
"）;
}
s=（Node*）malloc（sizeof（char））;
s->date=e;
s->next=p->next;
p->next=s;
Order（L）;
}
voidDelList（LinkListL,inti,ElemType*e）
{
Node*p,*r;
intj;
j=0;
p=L;
while（（p->next!
=NULL）&&（j{
p=p->next;
j++;
}
if（p->next!
=NULL）
{
p->next=p->next->next;
r=p->next;
*e=r->date;
printf（"删除第%d个元素:
%c\n",i,*e）;
}
else
printf（"删除结点的位置i不合理!
"）;
}
voidListLength（LinkListL）
{
Node*p;intj=0;
p=L->next;
while（p!
=NULL）
{
p=p->next;
j++;
}
printf（"单链表的长度:
%d",j）;
}
voidmenu（）
{
printf（"\n************************菜单*********************"）;
printf（"\n1.创建任意字符型单循环链表"）;
printf（"\n2.打印（遍历）该链表"）;
printf（"\n3.查找第i个元素"）;
printf（"\n4.查找与一已知字符相同的元素"）;
printf（"\n5.插入元素"）;
printf（"\n6.删除第i个结点"）;
printf（"\n7.计算链表的长度"）;
printf（"\n8.退出"）;
printf（"\n***********************************************"）;
}
voidmain（）
{
inti;
intflag=0;
ElemTypee;
LinkListL;
L=（LinkList）malloc（sizeof（char））;
InitList（&L）;
menu（）;
while（!
flag）
{
printf（"\n\n请输入你的选择（1~8）:
"）;
scanf（"%d",&i）;
switch（i）
{
case1:
Create（L）;
break;
case2:
Order（L）;
break;
case3:
printf（"输入要查找的第i个元素:
"）;
scanf（"%d",&i）;
Get（L,i,&e）;
break;
case4:
printf（"输入查找的元素:
"）;
rewind（stdin）;
scanf（"%c",&e）;
Locate（L,e）;
break;
case5:
printf（"输入插入的元素:
"）;
rewind（stdin）;
scanf（"%c",&e）;
InsList（L,i,e）;
break;
case6:
printf（"输入要删除第几个结点:
"）;
scanf（"%d",&i）;
DelList（L,i,&e）;
break;
case7:
ListLength（L）;
break;
case8:
flag=1;
break;
}
}
}
}4测试数据与实验结果（可以抓图粘贴）
5结果分析与实验体会
1.编程时，要注意随时写点注释，有利于编译；
2.要先熟悉书本上的内容，否则编译会有困难；
3.不能太过死板，要灵活运用所学知识。
升级会员 