数据结构实验(1)线性表及其应用

1、v1.0可编辑可修改计算机系数据结构实验报告（1）实验目的：帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。问题描述：1、构造一个空的线性表 L。2、在线，f表L的第i个元素之前插入新的元素 e；3、在线f表L中删除第i个元素，并用e返回其值。实验要求：1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行 分析。算法分析：由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的算法，如下：1v1.0可编辑可

2、修改实验内容和过程：顺序存储结构线性表程序清单：/顺序存储结构线性表的插入删除#include <iostream>#include <>using namespace std;# define LISTSIZE 100# define CREMENTSIZE 10typedef char ElemType;/typedef struct ElemType *elem;/int len;int listsize;SqList;定义数据元素类型为字符型数据元素首地址/当前元素个数/ 当前存储最大容量/构造一个空的线性表L13 -int InitList(SqList &a

3、mp;L)二(ElemType *)malloc(LISTSIZE*sizeof(ElemType);if (!exit(-2);/分配空间失败=0;=LISTSIZE;/在顺序线性表L中第i个位置之前插入新的元素eint ListInsert(SqList &L,int i,ElemType e)if (i<1|i>+1) return -1; /i值不合法if >=ElemType *newelem=(ElemType *)realloc,+CREMENTSIZE)*sizeof(ElemType);/存储空间已满，增加分配if(!newelem) exit (-

4、2); /分配失败=newelem;+=CREMENTSIZE;ElemType *q=&i-1);for (ElemType *p=&);p>=q;-p) *(p+1)=*p; /插入位置及其后的元素后移*q=e; +;return 1;/在顺序线性表L中删除第i个元素，并用e返回其值int ListDelete(SqList &L,int i,ElemType&e)if (i<1|i> return -1; /i值不合法ElemType *p=&i-1);e=*p; ElemType*q=+;for (+p;p<=q+1;+p

5、) *(p-1)=*p; /被删除元素之后的元素前移return 1;int main ()SqList L; char e,ch;int i,j,state;InitList(L);/构造线性表/数据初始化获取表长判断进行插入还是删除操作printf("请输入原始数据(字符串个数099): L=");gets；for ( j=1;j-1!='0'j+)=j;/j='0'；printf(" 操作：才f入(I)还是删除(D)n");/AGAIN:cin>>ch;if(ch='I')cout<

6、<"插在第几个元素之前："；/插入操作cin>>i; cout<<"输入要插入的新元素："；cin>>e;cout<<endl;printf("输入数据：L=(%s) state=ListInsert (L,i,e);else if (ch='D')cout<<"删除第几个元素："cin>>i;cout<<endl;printf("输入数据：L=(%s)state=ListDelete(L,i,e);else

7、goto AGAIN;/cout<<endl<<"正确结果："if(state=-1) cout<<"ERROR,"printf("L=(%s) ",;/ListInsert(L,%d,%c)",i,e);/删除操作DeleteList(L,%d,e)”,i);操作指示符输入错误处理输出结果if(ch='D'&&state!=-1) cout<<",e="<<e;链式存储结构线性表程序清单：/ 单链存储结构线性表的

8、插入删除 #include <iostream>#include <>using namespace std;#define null 0typedef char ElemType;/typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;int GetElem(LinkList L,int i,ElemType &e)LinkList p;int j;p=L->next; j=1;while(p&&j<i)p=p->next; +j;/if(!p

9、|j>i) return -1;/e=p->data;return 1;int ListInsert(LinkList &L,int i,ElemType e)/在带头结点的单链线性表L中第LinkList p,s; int j;p=L;j=0;定义数据元素类型为字符型/获取第i个元素的值寻找第i个元素寻找失败i个元素之前插入元素ewhile(p&&j<i-1) p=p->next;+j;if(!p|j>i-1) return -1;s=(LinkList) malloc( sizeof(LNode);s->data=e;s->

10、next=p->next;p->next=s;return 1; int ListDelete(LinkList&L,int i,ElemType&e)/在带头结点的单链线性表L中，删除第i个元素，并由e返回其值LinkList p,q; int j;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);return 1

11、;int newdata(LinkList&L,char *ch)int k;printf("请输入原始数据(字符串个数099): L=");/ 数据初始化gets(ch);将初始for (k=0;chk!='0'k+)ListInsert(L,k+1, chk);/化数据插入链表L中cout<<"OK"<<endl;return k;/返回链表中的元素个数int main ()char *ch;ch=(char *)malloc(100*sizeof(char); /LinkList L;/LNode h

12、ead;/L=&head; =null;int i,k,state; char e,CH,f;k=newdata(L,ch);/=k;/printf(" 操作：插入(定义数组用来辅助数据初始化头指针头结点AGAIN:I )还是删除(D)n");/调用函数使链表数据初始化将元素个数存入头结点的数据域判断进行插入还是删除操作cin>>CH;if(CH='I')cout<<"插在第几个元素之前："；/插入操作cin>>i; cout<<"输入要插入的新元素："；cin&

13、gt;>e;cout<<endl;printf("输入数据：L=(%s)state=ListInsert(L,i,e);+;else if (CH='D')cout<<"删除第几个元素："cin>>i;cout<<endl;printf("输入数据：L=(%s)state=ListDelete(L,i,e);-;else goto AGAIN;/cout<<endl<<"正确结果："ListInsert(L,%d,%c)",ch,i

14、,e);/删除操作DeleteList(L,%d,e)",ch,i);操作指示符输入错误处理输出结果if(state=-1) cout<<"ERROR," /cout<<"L=("for(int m=1;>=m;m+)/一一输出数据GetElem(L,m,f);cout<<f;cout<<")"if(CH='D'&&state!=-1) cout<<",e="<<e;/删除操作反馈 e实验结果：由

15、于两个程序的输出模式相同，在此只列一组测试数据：L = () Listinsert (L, 1,'k')L = (EHIKMOP) Listinsert (L, 9, 't')C:Us ers'Ad minist rato rDes kto p；未命名 2.exe .口.| 画L = (ABCEHKNPQTU) ListInsert(L, 4, 'u')CAUs ersAd minist rate rD kt。p:去命名 2.exeL = () ListDelete (L, 1, e)C：lU$g式Administrmt 口 r日

16、7;ktop未命&Zwxs=L = (DEFILMNORU) ListDelete_Sq(L, 5, e)C:Us ersAcl minist rato r D esp；声靠名 2.exeL = (CD) ListDelete_Sq(L, 1, e)v1.0可编辑可修改-15 -测试过程中所注意到的问题主要还是输出与输入界面的问题，通过灵活使用cout 和 cin 函显得不够人性化。数来不断改进。另外，在用户端看来在设计算法时程序的可重复性未考虑, 时间复杂度分析:假定线T表有n个节点，顺序存储结构下，插入程序段以*(p+1)=*p作为基本操作的原操作， 并讨论在最坏情况下的时间复杂度

17、，记T(n)=O(n);删除程序段以*(p-1)=*(p)作为基本操作的原操作，并讨论在最坏情况下的时间复杂度，记(n)=O(n)。链式存储结构下，插入程序段以 p=p->next作为基本操作的原操作，并讨论在最坏情况下的时间复杂度，记 T(n)=O(n);删除程序段以p=p->next作为基本操作的原操作，并讨论在最坏情况下的时间复 杂度，记 丁(n)=O(n)。总结和感想：改进设想在于减少中间变量， 优化数据初始化操作， 和增加程序可重复性。 具体操作完成估 计就该把上述程序全面修改了，还包括算法的修改和增进。从完成该实验的过程中， 出现的问题很多，一方面由于对 C语言的不够熟悉，在语法和语句 执行效率上总是不尽人意，另一方面由于在设计算法时考虑不全面， 在后来写入程序时屡屡 修改，使程序设计效率大大降低。基于