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