数据结构实验线性表及其应用.doc

该【数据结构实验线性表及其应用 】是由【知识无限】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【数据结构实验线性表及其应用 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。计算机系数据结构实验报告(1)
实验目的:
帮助学生掌握线性表的基本操作在次序和链表这两种储存结构上的实现,尤以链表的操作和应用作为要点。
问题描绘:
1、结构一个空的线性表L。
2、在线性表L的第i个元素以前插入新的元素e;
3、在线性表L中删除第i个元素,并用e返回其值。
实验要求:
1、分别利用次序和链表储存结构实现线性表的储存,并设计出在不一样的储存结构中线
性表的基本操作算法。
2、在实验过程中,对同样的操作在不一样的储存结构下的时间复杂度和空间复杂度进行
剖析。
算法剖析:
因为两种储存结构都用来创立线性结构的数据表,算法,以下:

可采纳同样的输出模式和整体结构近似的
实验内容和过程:
次序储存结构线性表程序清单:
次序储存结构线性表的插入删除
#include<iostream>
#include<>
usingnamespacestd;
#defineLISTSIZE100#defineCREMENTSIZE

10
typedefcharElemType;

//

定义数据元素种类为字符型
typedefstruct{
ElemType*elem;
intlen;
intlistsize;

//

//
//

数据元素首地点
目前元素个数
目前储存最大容量
}SqList;
结构一个空的线性表LintInitList(SqList&L)
{
=(ElemType*)malloc(LISTSIZE*sizeof(ElemType));
if(!exit(-2);//分派空间失败
=0;
=LISTSIZE;
}
//在次序线性表L中第i个地点以前插入新的元素intListInsert(SqList&L,inti,ElemTypee){

e
if(i<1||i>+1)return-1;//i
if>=
{

值不合法
ElemType*newelem=(ElemType*)realloc,+CREMENTSIZE)*sizeof(ElemType));
储存空间已满,增添分派
if(!newelem)exit(-2);//
=newelem;
+=CREMENTSIZE;

分派失败
}
ElemType*q=&[i-1]);
for(ElemType*p=&[]);p>=q;--p)*(p+1)=*p;//
*q=e;++;
return1;

插入地点及以后的元素后移
}
在次序线性表L中删除第i个元素,并用e返回其值
intListDelete(SqList&L,inti,ElemType&e)
{
if(i<1||i>return-1;//i
ElemType*p=&[i-1]);

值不合法
e=*p;ElemType*q=+;
for(++p;p<=q+1;++p)*(p-1)=*p;

//

被删除元素以后的元素前移
;
return1;
}
intmain()
{
SqListL;chare,ch;
inti,j,state;
InitList(L);//结构线性表
printf("请输入原始数据(字符串个数0~99):L=");//数据初始化
gets;
for(j=1;[j-1]!='\0';j++)=j;//获得表长
[j]='\0';
printf("操作:插入(I)仍是删除(D)\n");//判断进行插入仍是删除操作
AGAIN:
cin>>ch;
if(ch=='I')
{
cout<<"插在第几个元素以前:";//插入操作
cin>>i;cout<<"输入要插入的新元素:";
cin>>e;
cout<<endl;
printf("

输入数据:

L=(%s)

ListInsert(L,%d,%c)",,i,e);
state=ListInsert(L,i,e);
}
elseif(ch=='D')
{
cout<<"删除第几个元素:";//删除操作
cin>>i;
cout<<endl;
printf("输入数据:L=(%s)DeleteList(L,%d,e)",,i);
state=ListDelete(L,i,e);
}
elsegotoAGAIN;//操作指示符输入错误办理
cout<<endl<<"正确结果:";
if(state==-1)cout<<"ERROR,";
printf("L=(%s)",;//输出结果
if(ch=='D'&&state!=-1)cout<<",e="<<e;
}
链式储存结构线性表程序清单:
-----单链储存结构线性表的插入删除-----
#include<iostream>
#include<>
usingnamespacestd;
#definenull0
typedefcharElemType;

//

定义数据元素种类为字符型
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
intGetElem(LinkListL,inti,ElemType&e)

//

获得第

i个元素的值
{
LinkListp;intj;
p=L->next;j=1;
while(p&&j<i)
{
p=p->next;++j;

//

找寻第

i个元素
}
if(!p||j>i)return-1;

//

找寻失败
e=p->data;
return1;
}
intListInsert(LinkList&L,inti,ElemTypee)
{
//在带头结点的单链线性表

L中第

i

个元素以前插入元素

e
LinkListp,s;intj;
p=L;j=0;
while(p&&j<i-1){p=p->next;++j;}
if(!p||j>i-1)return-1;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;s->next=p->next;
p->next=s;
return1;
}
intListDelete(LinkList&L,inti,ElemType&e)
{
//在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
LinkListp,q;intj;
p=L;j=0;
while(p->next&&j<i-1)
{
p=p->next;++j;
}
if(!(p->next)||j>i-1)return-1;
q=p->next;p->next=q->next;
e=q->data;free(q);
return1;
}
intnewdata(LinkList&L,char*ch)
{
intk;
printf("请输入原始数据
gets(ch);
for(k=0;ch[k]!='\0';k++)

(字符串个数0~99):L=");
ListInsert(L,k+1,ch[k]);

//

//

数据初始化

将初始
化数据插入链表

L中
cout<<"OK"<<endl;
returnk;

//

返回链表中的元素个数
}
intmain()
{
char*ch;
ch=(char*)malloc(100*sizeof(char));//定义数组用来协助数据初始化
LinkListL;//头指针
LNodehead;//头结点
L=&head;=null;
inti,k,state;chare,CH,f;
k=newdata(L,ch);//调用函数使链表数据初始化
=k;//将元素个数存入头结点的数据域
printf("操作:插入(I)仍是删除(D)\n");//判断进行插入仍是删除操作
AGAIN:
cin>>CH;
if(CH=='I')
{
cout<<"插在第几个元素以前:";//插入操作
cin>>i;cout<<"输入要插入的新元素:";
cin>>e;
cout<<endl;
printf("

输入数据:

L=(%s)

ListInsert(L,%d,%c)",ch,i,e);
state=ListInsert(L,i,e);
++;
}
elseif(CH=='D')
{
cout<<"删除第几个元素:";//删除操作
cin>>i;
cout<<endl;
printf("输入数据:L=(%s)DeleteList(L,%d,e)",ch,i);
state=ListDelete(L,i,e);
--;
}
elsegotoAGAIN;//操作指示符输入错误办理
cout<<endl<<"正确结果:";
if(state==-1)cout<<"ERROR,";//输出结果
cout<<"L=(";
for(intm=1;>=m;m++)//一一输出数据
{
GetElem(L,m,f);
cout<<f;
}
cout<<")";
if(CH=='D'&&state!=-1)cout<<",e="<<e;//删除操作反应e
}
实验结果:
因为两个程序的输出模式同样,在此只列一组测试数据:
L=()ListInsert(L,1,'k')
L=(EHIKMOP)ListInsert(L,9,'t')
L=(ABCEHKNPQTU)ListInsert(L,4,'u')
L=()ListDelete(L,1,e)
L=(DEFILMNORU)ListDelete_Sq(L,5,e)
L=(CD)ListDelete_Sq(L,1,e)
测试过程中所注意到的问题主要仍是输出与输入界面的问题,经过灵巧使用
cout和cin函
数来精益求精。此外,在用户端看来在设计算法时程序的可重复性未考虑,
显得不够人性化。
时间复杂度剖析:
假设线性表有n个节点,次序储存结构下,插入程序段以*(p+1)=*p
作为基本操作的原操作,
并议论在最坏状况下的时间复杂度,记
T(n)=O(n);删除程序段以
*(p-1)=*(p)作为基本操
作的原操作,并议论在最坏状况下的时间复杂度,记
T’(n)=O(n)
。链式储存结构下,插入
程序段以p=p->next作为基本操作的原操作,并议论在最坏状况下的时间复杂度,记
T(n)=O(n);删除程序段以p=p->next
作为基本操作的原操作,并议论在最坏状况下的时间复
杂度,记T’(n)=O(n)。
总结和感想:
改良假想在于减少中间变量,优化数据初始化操作,和增添程序可重复性。详细操作达成预计就该把上述程序全面改正了,还包含算法的改正和增进。
从达成该实验的过程中,出现的问题好多,一方面因为对C语言的不够熟习,在语法和语句
履行效率上老是不尽人意,另一方面因为在设计算法时考虑不全面,在以后写入程序时每每
改正,使程序设计效率大大降低。鉴于上述两点,此后需全面复习C语言以效后计,并做幸亏设计算法方面的工作。
思虑题:
实现链表的逆置算法:
以上述链式储存结构线性表程序做基础,可省略数据初始化和输入输出等操作,此处只列出实现逆置的用户函数Inversion(),主程序调用该函数并输出即可。
intInversion(LNodehead)

//

形参为链表的头结点
{
LinkListp,q,r;
p=;q=r=0;

//p

中寄存第一个节点的地点
while(p)
{
q=p->next;
p->next=r;

//q
//

作为中间变量
逆序替代元素的地点域
r=p;
p=q;

//

将q值返还给

p
}
return1;
}