内容发布更新时间 : 2024/11/14 12:46:20星期一 下面是文章的全部内容请认真阅读。
计算机系数据结构实验报告（1）
实验目的：
帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的
操作和应用作为重点。
问题描述：
1、 构造一个空的线性表L。
2、 在线性表L的第i个元素之前插入新的元素e； 3、 在线性表L中删除第i个元素，并用e返回其值。
实验要求：文法是一个四元
1、 分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线
性表的基本操作算法。 2、 在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行
分析。
算法分析：
由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的算法，如下：
实验内容和过程：
顺序存储结构线性表程序清单： //顺序存储结构线性表的插入删除 #include
- 1 -
#include
# define LISTSIZE 100 # define CREMENTSIZE 10
typedef char ElemType; //定义数据元素类型为字符型 typedef struct { ElemType *elem; //数据元素首地址 int len; //当前元素个数 int listsize; //当前存储最大容量 }SqList;
//构造一个空的线性表L
int InitList(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
*)realloc(L.elem,(L.listsize+CREMENTSIZE)*sizeof(ElemType)); //存储空间已满，增加分配 if(!newelem) exit (-2); //分配失败
L.elem=newelem; L.listsize+=CREMENTSIZE; }
ElemType *q=&(L.elem[i-1]) ;
for (ElemType *p=&(L.elem[L.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)
- 2 -
*newelem=(ElemType
//插入位置及其后的元素
{ } int {
if (i<1||i>L.len) return -1; //i值不合法
ElemType *p=&(L.elem[i-1]);
e=*p; ElemType*q=L.elem+L.len-1;
for (++p;p<=q+1;++p) *(p-1)=*p; //被删除元素之后的元素前移 --L.len; return 1;
main ()
SqList L; char e,ch; int i,j,state;
InitList(L); //构造线性表
printf(\请输入原始数据(字符串个数0~99)：L=\ //数据初始化 gets(L.elem);
for ( j=1;L.elem[j-1]!='\\0';j++) L.len=j; //获取表长L.len L.elem[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)\ state=ListInsert (L,i,e); } else if (ch=='D') { cout<<\删除第几个元素：\ //删除操作 cin>>i; cout< printf(\输入数据：L=(%s) DeleteList(L,%d,e)\ state=ListDelete(L,i,e); } else goto AGAIN; //操作指示符输入错误处理 cout< if(state==-1) cout<<\ printf(\\ //输出结果 if(ch=='D'&&state!=-1) cout<<\ - 3 - 链式存储结构线性表程序清单： // - - - - -单链存储结构线性表的插入删除 - - - - - #include #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 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 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返回其值 - 4 - LinkList p,q; int j; p=L;j=0; while(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(\请输入原始数据(字符串个数0~99)：L=\ //数据初始化 gets(ch); for (k=0;ch[k]!='\\0';k++) ListInsert(L,k+1, ch[k]); //将初始化数据插入链表L中 cout<<\ 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;