数据结构实验线性表及其应用.docx
- 文档编号:12900540
- 上传时间:2023-06-09
- 格式:DOCX
- 页数:13
- 大小:228.67KB
数据结构实验线性表及其应用.docx
《数据结构实验线性表及其应用.docx》由会员分享,可在线阅读,更多相关《数据结构实验线性表及其应用.docx(13页珍藏版)》请在冰点文库上搜索。
数据结构实验线性表及其应用
--本页仅作为文档封面,使用时请直接删除即可----内页可以根据需求调整合适字体及大小--
数据结构实验
(1)线性表及其应用(共9页)
计算机系数据结构实验报告
(1)
实验目的:
帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现,尤以链表的操作和应用作为重点。
问题描述:
1、构造一个空的线性表L。
2、在线性表L的第i个元素之前插入新的元素e;
3、在线性表L中删除第i个元素,并用e返回其值。
实验要求:
1、分别利用顺序和链表存储结构实现线性表的存储,并设计出在不同的存储结构中线性表的基本操作算法。
2、在实验过程中,对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。
算法分析:
由于两种存储结构都用来创建线性结构的数据表,可采用相同的输出模式和整体结构类似的算法,如下:
实验内容和过程:
顺序存储结构线性表程序清单:
//顺序存储结构线性表的插入删除
#include
#include<>
usingnamespacestd;
#defineLISTSIZE100
#defineCREMENTSIZE10
typedefcharElemType;//定义数据元素类型为字符型
typedefstruct{
ElemType*elem;//数据元素首地址
intlen;//当前元素个数
intlistsize;//当前存储最大容量
}SqList;
//构造一个空的线性表L
intInitList(SqList&L)
{
=(ElemType*)malloc(LISTSIZE*sizeof(ElemType));
if(!
exit(-2);//分配空间失败
=0;
=LISTSIZE;
}
//在顺序线性表L中第i个位置之前插入新的元素e
intListInsert(SqList&L,inti,ElemTypee)
{
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< printf("输入数据: L=(%s)ListInsert(L,%d,%c)",,i,e); state=ListInsert(L,i,e); } elseif(ch=='D') { cout<<"删除第几个元素: ";//删除操作 cin>>i; cout< printf("输入数据: L=(%s)DeleteList(L,%d,e)",,i); state=ListDelete(L,i,e); } elsegotoAGAIN;//操作指示符输入错误处理 cout< "; if(state==-1)cout<<"ERROR,"; printf("L=(%s)",;//输出结果 if(ch=='D'&&state! =-1)cout<<",e="< } 链式存储结构线性表程序清单: //-----单链存储结构线性表的插入删除----- #include #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 { 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 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 { 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("请输入原始数据(字符串个数0~99): L=");//数据初始化 gets(ch); for(k=0;ch[k]! ='\0';k++)ListInsert(L,k+1,ch[k]);//将初始化数据插入链表L中 cout<<"OK"< 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< printf("输入数据: L=(%s)ListInsert(L,%d,%c)",ch,i,e); state=ListInsert(L,i,e); ++; } elseif(CH=='D') { cout<<"删除第几个元素: ";//删除操作 cin>>i; cout< printf("输入数据: L=(%s)DeleteList(L,%d,e)",ch,i); state=ListDelete(L,i,e); --; } elsegotoAGAIN;//操作指示符输入错误处理 cout< "; if(state==-1)cout<<"ERROR,";//输出结果 cout<<"L=("; for(intm=1;>=m;m++)//一一输出数据 { GetElem(L,m,f); cout< } cout<<")"; if(CH=='D'&&state! =-1)cout<<",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;//q作为中间变量 p->next=r;//逆序替换元素的地址域 r=p; p=q;//将q值返还给p } return1; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 线性 及其 应用
![提示](https://static.bingdoc.com/images/bang_tan.gif)