线性表数据结构.docx

线性表数据结构.docx

《线性表数据结构.docx》由会员分享，可在线阅读，更多相关《线性表数据结构.docx（22页珍藏版）》请在冰点文库上搜索。

线性表数据结构

淮海工学院计算机科学系

实验报告书

课程名：

《数据结构》

题目：

线性表数据结构试验

班级：

软件081

学号：

110831123

姓名：

XX

线性表实验报告要求

1、目的与要求:

1）掌握线性表数据结构的基本概念和抽象数据类型描述；

2）熟练掌握线性表数据结构的顺序和链式存储存表示；

3）熟练掌握线性表顺序存储结构的基本操作算法实现；

4）熟练掌握线性表的链式存储结构的基本操作算法实现;

5）掌握线性表在实际问题中的应用和基本编程技巧;

6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；

7）认真书写实验报告,并在试验后的第三天提交电子（全部由学委打包提交）和纸质（每班每次5份，学委安排）。

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）在链表中按照有序方式插入一已知字符元素；

6）在线性表中删除第i个结点；

7）计算链表的长度。

3、实验步骤与源程序

一、顺序表的基本操作实现实验

//顺序表的基本操作.cpp

#include"iostream.h"

#defineMaxSize25

typedefintDataType;

classSeqList

{

DataTypelist[MaxSize];

intlength;

public:

SeqList（）{length=0;}

voidSLCreat（intn）;//创建顺序表

voidSLInsert（inti,DataTypex）;//在顺序表L中的第i个位置插入数据元素x

voidSLDelete（inti）;//在顺序表L中的第i个位置删除数据元素

DataTypeSLGet（inti）;//获取第i个位置的元素位置

DataTypeSLSum（）;//求和

intSLIsEmpty（）;//判断顺序表是否为空

voidSLPrint（）;//将顺序表显示在屏幕上

};

//创建顺序表

voidSeqList:

:

SLCreat（intn）

{

DataTypex;

cout<<"请输入数据元素值:

";

for（inti=0;i

{

cin>>x;

list[i]=x;

length++;

}

}

//在顺序表L中的i位置插入数据元素x

voidSeqList:

:

SLInsert（inti,DataTypex）

{

intk;

if（length>=MaxSize）

cout<<"表已满,无法插入!

"<

elseif（i<0||i>length）

cout<<"参数i不合理!

"<

else

{

for（k=length;k>i;k--）

{

list[k]=list[k-1];

}

list[i]=list[i-1];

list[i-1]=x;

length++;

}

}

//删除第i个位置的数据元素

voidSeqList:

:

SLDelete（inti）

{

intk;

if（!

SLIsEmpty（））

cout<<"表已空,无法删除!

"<

elseif（i<0||i>length）

cout<<"参数i不合理!

"<

else

{

for（k=i-1;k

list[k]=list[k+1];

length--;

}

}

//获取第i个位置的元素的数值

DataTypeSeqList:

:

SLGet（inti）

{

if（i<0||i>length）

{

cout<<"参数i不合理!

"<

return0;

}

else

returnlist[i-1];

}

//判断顺序表是否为空

intSeqList:

:

SLIsEmpty（）

{

if（length<=0）return0;

elsereturn1;

}

//将顺序表显示在屏幕上

voidSeqList:

:

SLPrint（）

{

if（!

SLIsEmpty（））

cout<<"空表!

"<

else

for（inti=0;i

cout<

cout<

}

//求和

DataTypeSeqList:

:

SLSum（）

{

intm=0;

for（inti=0;i

{

m=m+list[i];

}

returnm;

}

voidmain（）

{

SeqListmylist;

inti,n,flag=1,select;

DataTypex;

cout<<"1.建立顺序表\n";

cout<<"2.求第i个位置上的数值\n";

cout<<"3.在第i个位置前上插入数值元素x\n";

cout<<"4.删除第i个位置上的数值\n";

cout<<"5.该顺序表上各元素之和\n";

cout<<"6.输出显示\n";

cout<<"7.退出\n";

cout<<"特别说明:

第一次请选择1,以后就不要选择1了!

"<

while（flag）

{

cout<<"请选择:

";

cin>>select;

switch（select）

{

case1:

cout<<"请输入顺序表长度:

";

cin>>n;

mylist.SLCreat（n）;

cout<<"顺序表为：

";

mylist.SLPrint（）;

break;

case2:

cout<<"请输入位置i:

";

cin>>i;

cout<<"第"<

"<

break;

case3:

cout<<"请输入要插入元素的位置i和数值x:

";

cin>>i>>x;

mylist.SLInsert（i,x）;

mylist.SLPrint（）;

break;

case4:

cout<<"请输入要删除的数值的位置:

";

cin>>i;

mylist.SLDelete（i）;

cout<<"删除后的顺序表为:

";

mylist.SLPrint（）;

break;

case5:

cout<<"求和的值：

"<

break;

case6:

cout<<"顺序表为:

";

mylist.SLPrint（）;

break;

case7:

flag=0;

break;

}

}

}

二、链表（带头结点）基本操作实验

#include

#include

#include

#include

#defineMaxSize10

#defineTRUE1

#defineFALSE0

typedefcharElemType;

typedefstructnode

{

ElemTypedata;

structnode*next;

}nodetype,*Listlink;

//进行头插法创建链表

voidqcreate（Listlink*head,intn）

{

inti;

Listlinkp;

cout<<"头插法---请输入元素:

"<

*head=（Listlink）malloc（sizeof（structnode））;

（*head）->next=NULL;

for（i=0;i

{

p=（Listlink）malloc（sizeof（structnode））;

cin>>p->data;

p->next=（*head）->next;

（*head）->next=p;

}

}

//按位置查找

intGet1（nodetype*h,inti）

{

intj;

nodetype*p=h;

j=0;

while（（p->next!

=NULL）&&（j

{

p=p->next;

j++;

}

if（i==j）

cout<<"第"<

"<data;

else

cout<<"输入的i值不合法,返回:

0";

returnFALSE;

}

//查找与已知字符e相同的结点

intGet2（nodetype*h,chare）

{

nodetype*p=h;

while（p->data!

=e）

{

if（p->next==NULL）

returnFALSE;

p=p->next;

}

returnTRUE;

}

//对各字符元素进行排序

voidpaixu（nodetype*h）

{

node*r,*q,*small;chartemp;

for（r=h->next;r->next!

=NULL;r=r->next）

{

small=r;

for（q=r->next;q;q=q->next）/*找到链表中最小字符*/

if（q->datadata）

small=q;

if（small!

=r）

{

temp=r->data;

r->data=small->data;/*把最小的数值换到P指针所指的位置数值上（原P指针的next指向不变）*/small->data=temp;/*把原先p指针所指位置的数值填入被置换出的最小字符位置*/

}

}

}

//对表进行插入操作

voidprintf（nodetype*head）

{

node*p;

p=head->next;

while（p!

=NULL）

{

cout<data<<"";

p=p->next;

}

cout<

}

nodetype*find（nodetype*h,inti,intm）

{

nodetype*p=h;

intj=1;

if（i>m||i<0）returnNULL;

else

{

while（p!

=NULL&&j

{

j++;p=p->next;

}

returnp;

}

}

nodetype*cins（nodetype*h,inti,charx,intm）

{

nodetype*p,*s;

s=（nodetype*）malloc（sizeof（nodetype））;

s->data=x;s->next=NULL;

if（i==0）

{

s->next=h;h=s;

}

else

{

p=find（h,i,m）;

if（p!

=NULL）

{

s->next=p->next;

p->next=s;

}

else

cout<<"输入的i值不正确"<

}

returnh;

}

//对链表进行删除操作

nodetype*del（nodetype*h,inti,intm）

{

nodetype*p=h,*s;

intj=1;

if（i==1）

{

h=h->next;free（p）;

}

elseif（i==m）

{

while（p->next->next!

=NULL）

{

p=p->next;

}

s=p->next;

p->next=NULL;

free（s）;

}

elseif（i>m）

{

cout<<"输入的i值不正确"<

cout<<"删除不成功!

"<

}

else

{

p=find（h,i,m）;

if（p!

=NULL&&p->next!

=NULL）

{

s=p->next;p->next=s->next;free（s）;

}

}

returnh;

}

//求链表的长度

intleg（nodetype*h）

{

intlength=0;

while（h!

=NULL）

{

length++;

h=h->next;

}

returnlength-1;

}

voidmain（）

{

inti,flag=1,select;

cout<<"1.建立链表\n";

cout<<"2.查找第i个位置上的数值\n";

cout<<"3.查找与一已知字符相同的第一个结点\n";

cout<<"4.按照有序方式插入一已知字符元\n";

cout<<"5.删除第i个结点\n";

cout<<"6.计算链表的长度\n";

cout<<"7.退出\n";

while（flag）

{

cout<<"请选择:

";

cin>>select;

intn,y;

charq,e;

switch（select）

{

case1:

Listlinka;

cout<<"请输要创建的元素个数:

";

cin>>n;

qcreate（&a,n）;

cout<<"创建成功，该链表为:

\n";

printf（a）;

break;

case2:

cout<<"请输入要查找的位置i:

";

cin>>i;

Get1（a,i）;

cout<

break;

case3:

cout<<"输入需查找有相同一已知字符e:

";

cin>>e;

cout<

cout<

break;

case4:

cout<<"请输入要插入的元素值:

";

cin>>q;

a=cins（a,1,q,n）;

paixu（a）;

cout<<"插入成功,链表按有序插入之后值为:

"<

printf（a）;

n=leg（a）;

break;

case5:

cout<<"请输入你要删除的结点:

"<

cin>>y;

a=del（a,y,n）;

cout<<"操作后链表值为:

";

printf（a）;

n=leg（a）;

break;

case6:

cout<<"该链表的长度为:

"<

cout<

break;

case7:

flag=0;

break;

}

}

}

4、测试数据与实验结果（可以抓图粘贴）

一、顺序表的基本操作实现实验

创建一个顺序表，输入数值并将其输出，如下图：

求出第i位置上的数值，并将其输出，如不合理则返回FALSE（0），之后在又一次输入的第i位置前插入数值元素x，如不合理则程序会输出输入的i不合理；随后进行删除操作，同样不合理会显示，实现如下图：

求该顺序表上各元素之和，求好后可选择6将此时的链表再一次输入，最后退出，如下图：

二、链表（带头结点）基本操作实验

头插法创建一个带头结点的字符型单链表，并输出，如下图：

查找合法的位置i，并输出该元素，如不合法则返回FALSE（0），之后查找与已知字符相同的第一个结点，有则返回1（TRUE），没有则返回0（FALSE）,下面的截图已将这两种情况都包含在里面，如下图：

按照有序方式插入一已知字符元，也就是插入后输出按顺序排出，在链表中删除第i个结点，如果删除的结点合理，则输出此时的链表，如删除不合理，则输出删除不成功，执行如下图：

可以计算链表的长度，最后退出，执行如下图：

5、结果分析与实验体会

做到了以上结果，自己确实花了不心思，我最后执行出的两个程序都已选择的形式给出，读者可以选择自己想要执行的一步，当然第一步创建线性表要先定义。

此外，在该两个线性表中我都给出了可以出现的结果，比如说你输入要插入或删除的位置不合法等等，都以return形式返回FALSE（0）。

很明显，链表中简单操作的实现要比顺序表的实现要稍微难一点，比如说在链表中按照有序方式插入一已知字符元素，插入并不难，主要还要对它进行有序插入，就加了一层次，刚开始根本不知道从哪里入手，之后想想，为什么不可以先就插入一元素，最后将它进行排序再输出，可是插入的元素也不能乱插，最后想将它插入第一结点位置，因为不管链表是否为空链表都可将元素插入，最后调用函数将其排序输入。

其实做程序时出现的问题还有很多，可是我都自己慢慢研究克服了，请教别人还不如靠自己，毕竟这程序是自己写的，应该比别人更了解，靠自己找出问题错的出处。

经过这一次的程序研究，我对线性表的认知又更进一层，这几天都在泡机子，自己丰富不少啊！

不过还要努力，下面几次的实验争取做快又做的帮。