数据的结构实验的1线性表及其应用.doc
计算机系数据结构实验报告1实验目的：帮助学生掌握线性表的根本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。问题描述：1、 构造一个空的线性表L。2、 在线性表L的第i个元素之前插入新的元素e；3、 在线性表L中删除第i个元素，并用e返回其值。实验要求：1、 分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的根本操作算法。2、 在实验过程中，对一样的操作在不同的存储结构下的时间复杂度和空间复杂度进展分析。算法分析：由于两种存储结构都用来创建线性结构的数据表，可采用一样的输出模式和整体结构类似的算法，如下：实验内容和过程：顺序存储结构线性表程序清单：/顺序存储结构线性表的插入删除 #include <iostream>#include <stdlib.h>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 (i<1|i>L.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 (i<1|i>L.len) return -1; /i值不合法 ElemType *p=&(L.elemi-1); e=*p; ElemType*q=L.elem+L.len-1; for (+p;p<=q+1;+p) *(p-1)=*p; /被删除元素之后的元素前移 -L.len; return 1;intmain ()SqList L; char e,ch;int i,j,state;InitList(L); /构造线性表 printf("请输入原始数据(字符串个数099)：L="); /数据初始化gets(L.elem); for ( j=1;L.elemj-1!='0'j+) L.len=j; /获取表长L.lenL.elemj='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)",L.elem,i,e); state=ListInsert (L,i,e); else if (ch='D') cout<<"删除第几个元素：" /删除操作 cin>>i; cout<<endl; printf("输入数据：L=(%s)DeleteList(L,%d,e)",L.elem,i); state=ListDelete(L,i,e); else goto AGAIN; /操作指示符输入错误处理 cout<<endl<<"正确结果：" if(state=-1) cout<<"ERROR," printf("L=(%s)",L.elem); /输出结果 if(ch='D'&&state!=-1) cout<<",e="<<e;链式存储结构线性表程序清单：/ - - - - -单链存储结构线性表的插入删除 - - - - -#include <iostream>#include <stdlib.h>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&&j<i) p=p->next; +j; /寻找第i个元素 if(!p|j>i) 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&&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; 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; 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 head; /头结点 L=&head; head.next=null; int i,k,state; char e,CH,f; k=newdata(L,ch); /调用函数使链表数据初始化head.data=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); (head.data)+; else if (CH='D') cout<<"删除第几个元素：" /删除操作 cin>>i; cout<<endl; printf("输入数据：L=(%s)DeleteList(L,%d,e)",ch,i); state=ListDelete(L,i,e); (head.data)-; else goto AGAIN; /操作指示符输入错误处理 cout<<endl<<"正确结果：" if(state=-1) cout<<"ERROR," /输出结果 cout<<"L=(" for(int m=1;(head.data)>=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()，主程序调用该函数并输出即可。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;
