数据结构实验报告 线性表的基本操作.docx
《数据结构实验报告 线性表的基本操作.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告 线性表的基本操作.docx（23页珍藏版）》请在冰点文库上搜索。
数据结构实验报告线性表的基本操作
《数据结构》
实
验
报
告
前言
计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。
计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。
数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。
所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。
一、实验目的
二、实验内容和要求
三、源代码
1）顺序表的代码
2）单链表的代码
四、测试结果
1）顺序表的测试结果
2）单链表的测试结果
五、心得体会
实验一线性表的基本操作及其应用
一、实验目的
1、帮助读者复习C++语言程序设计中的知识。
2、熟悉线性表的逻辑结构。
3、熟悉线性表的基本运算在两种存储结构上的实现。
4、掌握顺序表的存储结构形式及其描述和基本运算的实现。
5、熟练掌握动态链表结构及有关算法的设计
二、实验内容
题目一：
顺序表的基本操作
[问题描述]
实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。
[基本要求]
（1）依次从键盘读入数据，建立带头结点的顺序表；
（2）输出顺序表中的数据元素
（3）求顺序表的长度；
（4）根据指定条件能够取元素和修改元素；
（5）实现在指定位置插入和删除元素的功能。
（6）根据算法，将两个有序的顺序表合并成一个有序顺序表。
[测试数据]由学生任意指定。
题目二：
单链表的基本操作
[问题描述]
实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。
[基本要求]
（1）依次从键盘读入数据，建立带头结点的单链表；
（2）输出单链表中的数据元素
（3）求单链表的长度；
（4）根据指定条件能够取元素和修改元素；
（5）实现在指定位置插入和删除元素的功能。
（6）根据算法，将两个有序的单链表合并成一个有序单链表。
[测试数据]
由学生任意指定。
三、源代码
（一）顺序表的基本操作
#include
usingnamespacestd;
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
typedefintElemType;
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
typedefstruct{//结构体
ElemType*elem;
intlength;
intlistsize;
}SqList;
SqListLx;
StatusInitList_Sq（SqList&L）//分配空间
{L.elem=newElemType[LIST_INIT_SIZE];
if（!
L.elem）exit（OVERFLOW）;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
StatusListInsert（SqList&L,inti,ElemTypee）//插入新元素
{int*q,*p;ElemType*newbase;
if（i<1||i>L.length+1）returnERROR;
if（L.length>=L.listsize）
{newbase=newElemType[L.listsize+LISTINCREMENT];
if（!
newbase）exit（OVERFLOW）;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&（L.elem[i-1]）;
for（p=&（L.elem[L.length-1]）;p>=q;--p）
*（p+1）=*p;
*q=e;
++L.length;
returnOK;
}
StatusListlength（SqListL）//长度
{int*p=L.elem;//判断线形表是否存在
while（p）
{return（L.length）;}
}
StatusGetElem（SqListL,inti,ElemType&e）//取元素
{if（i<1||i>L.length）
returnERROR;
else
{e=L.elem[i-1];
returne;
}
}
voidMergeList（SqListLa,SqListLb,SqList&Lc）//合并
{ElemTypeai,bj;
InitList_Sq（Lc）;
inti=1,j=1,k=0;
intLa_len,Lb_len;
La_len=Listlength（La）;
Lb_len=Listlength（Lb）;
while（（i<=La_len）&&（j<=Lb_len））
{GetElem（La,i,ai）;GetElem（Lb,j,bj）;
if（ai<=bj）
{ListInsert（Lc,++k,ai）;++i;}
else
{ListInsert（Lc,++k,bj）;++j;}
}
while（i<=La_len）
{GetElem（La,i++,ai）;
ListInsert（Lc,++k,ai）;
}
while（j<=Lb_len）
{GetElem（Lb,j++,bj）;
ListInsert（Lc,++k,bj）;
}
}
voidshow（SqListL,inti）//显示
{intj;ElemTypek;
cout<<"顺序表显示如下:
"<for（j=0;j{k=L.elem[j];
cout<";}
if（j==i-1&&i>0）
{k=L.elem[j];cout<cout<}
voidcreate（SqList&L,intn）//输入元素
{inte;
for（inti=0;i{cin>>e;
L.elem[i]=e;
L.length=i+1;}
}
StatusListDelete_Sq（SqList&L,inti,ElemType&e）//删除
{ElemType*p,*q;
if（i<1||i>L.length）returnERROR;
p=&（L.elem[i-1]）;
e=*p;
q=L.elem+L.length-1;
for（++p;p<=q;++p）*（p-1）=*p;
--L.length;
returnOK;
}
StatusListxiugei（SqList&L,inti,ElemType&e）//修改
{if（i<1||i>L.length）
returnERROR;
else
{L.elem[i-1]=e;
returnOK;}
}
voidshuru（SqList&L1）//顺序表的创建
{inta;
InitList_Sq（L1）;
cout<<"请输入顺序表的长度：
";
cin>>a;
cout<<"请输入顺序表的元素（共"<create（L1,a）;
show（L1,a）;
}
voidchaxun（SqList&L1）//取第i个位置的元素
{intj;ElemTypee1;
cout<<"请选择所要取出元素的位置:
";
cin>>j;
while（j<0||j>Listlength（L1））
{cout<<"输入有误，请重新输入"<cout<<"请选择所要取出元素的位置:
";
cin>>j;}
GetElem（L1,j,e1）;
cout<<"取出的元素为:
"<voidxiugai（SqList&L1）//修改第i个位置的元素
{inta;
intj;ElemTypee1;
a=L1.length;
cout<<"请选择所要修改元素的位置:
";
cin>>j;
while（j<0||j>Listlength（L1））
{cout<<"输入有误，请重新输入"<cout<<"请选择所要修改元素的位置:
";
cin>>j;}
cout<<"要修改成的元素:
";
cin>>e1;
Listxiugei（L1,j,e1）;
cout<<"修改后的顺序表数据:
"<show（L1,a）;
}
voidshanchu（SqList&L1）//删除顺序表里的元素
{inta;
intj;ElemTypee1;
a=L1.length;
cout<<"请选择所要删除元素的位置:
";
cin>>j;
while（j<0||j>Listlength（L1））
{cout<<"输入有误，请重新输入"<cout<<"请选择所要删除元素的位置:
";
cin>>j;}
ListDelete_Sq（L1,j,e1）;
cout<<"修改后的顺序表数据:
"<show（L1,a-1）;
}
voidcharu（SqList&L1）//插入元素到顺序表里
{inta;intj;ElemTypee1;
a=L1.length;
cout<<"请选择所要插入元素的位置:
";
cin>>j;
while（j<0||j>Listlength（L1））
{cout<<"输入有误，请重新输入"<cout<<"请选择所要插入元素的位置:
";
cin>>j;}
cout<<"要插入的元素:
";
cin>>e1;
ListInsert（L1,j,e1）;
cout<<"修改后的顺序表数据:
"<show（L1,a+1）;
}
voidhebing（SqList&L3）//合并两个顺序表
{SqListL1,L2;
inta,b;
InitList_Sq（L1）;InitList_Sq（L2）;
cout<<"请输入第一个有序表的长度：
";cin>>a;
cout<<"请输入第一个有序表的元素（共"<create（L1,a）;
show（L1,a）;
cout<<"请输入第二个有序表的长度：
";cin>>b;
cout<<"请输入第二个有序表的元素（共"<create（L2,b）;
show（L2,b）;
MergeList（L1,L2,L3）;
cout<<"合并后的有序表如下：
";show（L3,a+b）;
}
voidmain（）//主菜单
{intchoice;
for（;;）
{cout<<"顺序表的基本操作"<cout<<"1.顺序表的创建"<cout<<"2.顺序表的显示"<cout<<"3.顺序表的长度"<cout<<"4.取第i个位置的元素"<cout<<"5.修改第i个位置的元素"<cout<<"6.插入元素到顺序表里"<cout<<"7.删除顺序表里的元素"<cout<<"8.合并两个顺序表"<cout<<"9.退出系统"<cout<<"请选择：
";
cin>>choice;
switch（choice）
{case1:
shuru（Lx）;break;
case2:
show（Lx,Lx.length）;break;
case3:
cout<<"顺序表的长度:
"<case4:
chaxun（Lx）;break;
case5:
xiugai（Lx）;break;
case6:
charu（Lx）;break;
case7:
shanchu（Lx）;break;
case8:
hebing（Lx）;break;
case9:
cout<<"退出系统!
"<default:
cout<<"输入有误，请重新选择"<}
}
（二）单链表的基本操作
#include
usingnamespacestd;
#definetrue1
#definefalse0
#defineok1
#defineerror0
#defineoverflow-2
typedefintStatus;
typedefintElemType;
typedefstructLNode//存储结构
{ElemTypedata;
structLNode*next;
}LNode,*LinkList;
voidCreateList（LinkList&L,intn）//尾插法创建单链表
{LinkListp;
L=newLNode;
L->next=NULL;//建立一个带头结点的单链表
LinkListq=L;//使q指向表尾
for（inti=1;i<=n;i++）
{p=newLNode;
cin>>p->data;
p->next=NULL;
q->next=p;
q=p;}
}
StatusGetElem（LinkListL,inti,ElemType&e）//取第i个元素
{LinkListp=L->next;
intj=1;
while（p&&j{p=p->next;
++j;}
if（!
p||j>i）returnerror;//第i个元素不存在
e=p->data;
returnok;
}
StatusLinkInsert（LinkList&L,inti,ElemTypee）//插入
{LinkListp=L;
intj=0;
while（p&&j{p=p->next;
++j;}//寻找第i-1个结点
if（!
p||j>i-1）
returnerror;//i小于1或者大于表长加1
LinkLists=newLNode;//生成新结点
s->data=e;
s->next=p->next;//插入L中
p->next=s;
returnok;
}
StatusListDelete（LinkList&L,inti,ElemType&e）//删除
{LinkListp=L;
LinkListq;
intj=0;
while（p->next&&j{//寻找第i个结点，并令p指向其前驱
p=p->next;
++j;}
if（!
（p->next）||j>i-1）returnerror;//删除位置不合理
q=p->next;
p->next=q->next;//删除并释放结点
e=q->data;
delete（q）;
returnok;
}
voidMergeList（LinkList&La,LinkList&Lb,LinkList&Lc）
{//合并两个顺序链表
LinkListpa,pc,pb;
pa=La->next;
pb=Lb->next;
Lc=pc=La;
while（pa&&pb）
{if（pa->data<=pb->data）
{pc->next=pa;
pc=pa;
pa=pa->next;}
else
{pc->next=pb;
pc=pb;
pb=pb->next;}
}
pc->next=pa?
pa:
pb;
delete（Lb）;
}
voidshow（LinkListL）//显示
{LinkListp;
p=L->next;
while（p）
{cout<data<<"-->";
p=p->next;}
cout<}
intLength（LinkListL,inti）//表长
{i=0;
LinkListp=L->next;
while（p）
{++i;
p=p->next;}
returni;
}
voidxiugai（LinkListL）//修改
{inti,j=1;
ElemTypek;
ElemTypee,m;
LinkListp=L->next;
cout<<"请输入要修改的元素位置（0";
cin>>i;
GetElem（L,i,e）;
cout<<"该位置的元素:
"<cout<<"修改后的元素值:
";
cin>>k;
while（p&&j{p=p->next;
++j;}
m=p->data;
p->data=k;
cout<<"修改后的单链表显示如下:
"<show（L）;
}
voidhebing（）//合并两个单链表
{inta,b;
LinkListLa,Lb,Lc;
cout<<"请输入第一个有序链表的长度:
"<cin>>a;
cout<<"请输入第一个有序链表的元素共（"<"<CreateList（La,a）;
show（La）;
cout<<"请输入第二个有序链表的长度:
"<cin>>b;
cout<<"请输入第二个有序链表的元素共（"<"<CreateList（Lb,b）;
show（Lb）;
MergeList（La,Lb,Lc）;
cout<<"合并后的有序链表如下：
"<show（Lc）;
}
voidmain（）//主函数
{intselect;
intx;
ElemTypey;
LinkListlist;
for（;;）
{cout<<"单链表的基本操作"<cout<<"1.单链表的创建"<cout<<"2.单链表的显示"<cout<<"3.单链表的长度"<cout<<"4.取第i个位置的元素"<cout<<"5.修改第i个位置的元素"<cout<<"6.插入元素到单链表里"<cout<<"7.删除单链表里的元素"<cout<<"8.合并两个单链表"<cout<<"9.退出系统"<cout<<"请选择:
";
cin>>select;
switch（select）
{case1:
cout<<"请输入单链表的长度:
"<cin>>x;
cout<<"请输入"<CreateList（list,x）;
break;
case2:
cout<<"单链表显示如下:
"<show（list）;
break;
case3:
ints;
cout<<"单链表的长度为:
"<break;
case4:
cout<<"请选择所要取出元素的位置:
";
cin>>x;
while（x<0||x>Length（list,s））
{cout<<"输入有误，请重新输入"<cout<<"请选择所要取出元素的位置:
";
cin>>x;}
GetElem（list,x,y）;
cout<<"该位置的元素为:
"<break;
case5:
xiugai（list）;break;
case6:
cout<<"请选择要插入的位置:
";cin>>x;
while（x<0||x>Length（list,s））
{cout<<"输入有误，请重新输入"<cout<<"请选择所要插入元素的位置:
";
cin>>x;}
cout<<"要插入的元素值:
";
cin>>y;
LinkInsert（list,x,y）;
cout<<"插入后单链表显示如下:
"<show（list）;
break;
case7:
cout<<"请选择要删除的位置:
";cin>>x;
while（x<0||x>Length（list,s））
{cout<<"输入有误，请重新输入"<cout<<"请选择所要删除元素的位置:
";
cin>>x;}
ListDelete（list,x,y）;
cout<<"要删除的元素值:
"<
升级会员 