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

计算机系数据结构实验报告（1）实验目的： 帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。问题描述：1、 构造一个空的线性表L。2、 在线性表L的第i个元素之前插入新的元素e；3、 在线性表L中删除第i个元素，并用e返回其值。实验要求：文法是一个四元1、 分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。2、 在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。算法分析：由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的算法，如下： 实验内容和过程：顺序存储结构线性表程序清单：/顺序存储结构线性表的插入删除 #include #include using namespace std;# define LISTSIZE 100# define CREMENTSIZE 10typedef char ElemType; /定义数据元素类型为字符型 typedef struct ElemType *elem; /数据元素首地址 int len; /当前元素个数int listsize; /当前存储最大容量 SqList;/构造一个空的线性表L intInitList(SqList &L) L.elem=(ElemType *)malloc(LISTSIZE*sizeof(ElemType);if (!L.elem) exit(-2); /分配空间失败L.len=0;L.listsize=LISTSIZE;/在顺序线性表L中第i个位置之前插入新的元素e int ListInsert(SqList &L,int i,ElemType e)if (iL.len+1) return -1; /i值不合法 if (L.len=L.listsize) ElemType *newelem=(ElemType *)realloc(L.elem,(L.listsize+CREMENTSIZE)*sizeof(ElemType); /存储空间已满，增加分配 if(!newelem) exit (-2); /分配失败 L.elem=newelem; L.listsize+=CREMENTSIZE; ElemType *q=&(L.elemi-1) ; for (ElemType *p=&(L.elemL.len-1);p=q;-p) *(p+1)=*p; /插入位置及其后的元素后移 *q=e; +L.len;return 1; /在顺序线性表L中删除第i个元素，并用e返回其值int ListDelete(SqList &L,int i,ElemType&e) if (iL.len) return -1; /i值不合法 ElemType *p=&(L.elemi-1); e=*p; ElemType*q=L.elem+L.len-1; for (+p;pch;if(ch=I) couti; coute; coutendl; printf(输入数据：L=(%s)ListInsert(L,%d,%c),L.elem,i,e); state=ListInsert (L,i,e); else if (ch=D) couti; coutendl; printf(输入数据：L=(%s)DeleteList(L,%d,e),L.elem,i); state=ListDelete(L,i,e); else goto AGAIN; /操作指示符输入错误处理 coutendl正确结果：; if(state=-1) coutERROR,; printf(L=(%s),L.elem); /输出结果 if(ch=D&state!=-1) cout,e=e;链式存储结构线性表程序清单：/ - - - - -单链存储结构线性表的插入删除 - - - - -#include #include using namespace std;#define null 0 typedef char ElemType; /定义数据元素类型为字符型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; int GetElem(LinkList L,int i,ElemType &e) /获取第i个元素的值 LinkList p;int j; p=L-next; j=1; while(p&jnext; +j; /寻找第i个元素 if(!p|ji) return -1; /寻找失败 e=p-data; return 1; int ListInsert(LinkList &L,int i,ElemType e) /在带头结点的单链线性表L中第i个元素之前插入元素e LinkList p,s; int j; p=L;j=0; while(p&jnext;+j; if(!p|ji-1) return -1; s=(LinkList) malloc( sizeof(LNode); s-data=e;s-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&jnext;+j; if(!(p-next)|ji-1) return -1; q=p-next;p-next=q-next; e=q-data;free(q); return 1; 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中 coutOKCH;if(CH=I) couti; coute; coutendl; printf(输入数据：L=(%s)ListInsert(L,%d,%c),ch,i,e); state=ListInsert(L,i,e); (head.data)+; else if (CH=D) couti; coutendl; printf(输入数据：L=(%s)DeleteList(L,%d,e),ch,i); state=ListDelete(L,i,e); (head.data)-; else goto AGAIN; /操作指示符输入错误处理 coutendl正确结果：; if(state=-1) coutERROR,; /输出结果 cout=m;m+) /一一输出数据 GetElem(L,m,f); coutf; cout); if(CH=D&state!=-1) cout,e=next作为基本操作的原操作，并讨论在最坏情况下的时间复杂度，记T(n)=O(n);删除程序段以p=p-next作为基本操作的原操作，并讨论在最坏情况下的时间复杂度，记T(n)=O(n)。总结和感想：改进设想在于减少中间变量，优化数据初始化操作，和增加程序可重复性。具体操作完成估计就该把上述程序全面修改了，还包括算法的修改和增进。从完成该实验的过程中，出现的问题很多，一方面由于对C语言的不够熟悉，在语法和语句执行效率上总是不尽人意，另一方面由于在设计算法时考虑不全面，在后来写入程序时屡屡修改，使程序设计效率大大降低。基于上述两点，今后需全面复习C语言以效后计，并做好在设计算法方面的工作。思考题：实现链表的逆置算法：以上述链式存储结构线性表程序做基础，可省略数据初始化和输入输出等操作，此处只列出实现逆置的用户函数Inversion()，主程序调用该函数并输出即可。int Inversion(LNode head) /形参为链表的头结点LinkList p,q,r; p=head.next; q=r=0; /p中存放第一个节点的地址while(p)q=p-next; /q作为中间变量p-next=r; /逆序替换元素的地址域r=p;p=q; /将q值返还给preturn 1;- 9 -