2023年数据结构实验报告顺序表与链表.pdf

《2023年数据结构实验报告顺序表与链表.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构实验报告顺序表与链表.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.实验二 顺序表与链表【实验目的】1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。【实验学时】4 学时【实验预习】回答以下问题：1、顺序表的存储表示 假设线性表中每一个数据元素的存储空间大小为 1 个字节，并且以其所占存储空间的第一个字节的地址作为该元素的存储位置，则线性表中任一个数据元素的存储位置为：LOC(Ai)=LOC(A1)+(i-1)*1 其中，LOC(A1)为线性表中第一个数据元素 a1 的存储位置，也称为线性表的起始位置（首地址）。typed

2、ef struct Sqlist ElemType*slist;/存储空间的基地址 int length;/表长度 int listsize;/当前分配的存储空间容量 Sqlist;2、单链表的存储表示 线性链表也称单链表，在每一个结点中只包含一个指针，用于指示该结点的直接后继结点，整个链表通过指针相连，最后一个结点因为没有后继结点，其指针置为空（NULL）。这样，链表中所有数据元素（结点）构成一对一的逻辑关系，实现线性表的链式存储。【实验容和要求】1、按照要求完成程序 exp2_1.c，实现顺序表的相关操作。以下函数均具有返回值，若操作完成，返回 OK，操作失败返回 ERROR。函数需返回的

3、其他数据，使用函数参数返回。exp2_1.c 部分代码如下：#include#include#define ERROR 0.#define OK 1#define INIT_SIZE 100#define INCREM 10 typedef int ElemType;/*定义表元素的类型*/*（1）-补充顺序表的存储分配表示，采用定长和可变长度存储均可*/typedef struct Sqlist ElemType*slist;/基地址 int length;/表长度 int listsize;/分配的空间 Sqlist;/*函数声明*/int InitList_sq(Sqlist*L);in

4、t CreateList_sq(Sqlist*L,int n);int ListInsert_sq(Sqlist*L,int i,ElemType e);int PrintList_sq(Sqlist*L);int ListDelete_sq(Sqlist*L,int i,ElemType*e);int ListLocate(Sqlist*L,ElemType e,int*pos);int menu_select();/*（2）-顺序表的初始化*/int InitList_sq(Sqlist*L)L-slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemTy

5、pe);if(!L-slist)return ERROR;L-length=0;L-listsize=INIT_SIZE;/初始空间容量 return OK;/*InitList*/*（3）-创建具有 n 个元素的顺序表*/int CreateList_sq(Sqlist*L,int n)ElemType e;int i;for(i=0;in;i+)printf(input data%d:,i+1);scanf(%d,&e);.if(!ListInsert_sq(L,i+1,e)return ERROR;return OK;/*CreateList*/*（4）-输出顺序表中的元素*/int P

6、rintList_sq(Sqlist*L)int i;for(i=1;ilength;i+)printf(%5d,L-slisti-1);return OK;/*PrintList*/*（5）-在顺序表的第 i 个位置之前插入新元素 e*/int ListInsert_sq(Sqlist*L,int i,ElemType e)int k;if(iL-length+1)return ERROR;if(L-length=L-listsize)/当前空间已满，申请新的空间 L-slist=(ElemType*)realloc(L-slist,(L-listsize+INCREM)*sizeof(El

7、emType);if(!L-slist)return ERROR;L-listsize+=INCREM;for(k=L-length-1;k=i-1;k-)L-slistk+1=L-slistk;L-slisti-1=e;L-length+;return OK;/*ListInsert*/./*（6）-在顺序表中删除第 i 个元素，e 返回删除的元素*/int ListDelete_sq(Sqlist*L,int i,ElemType*e)int j;if(iL-length)return ERROR;*e=L-slisti-1;for(j=i;ilength;j+)L-slistj-1=L-

8、slistj;L-length-;return OK;/*ListDelete_sq*/*（7）-在顺序表中查找指定值元素，pos 为返回其位置序号*/int ListLocate(Sqlist*L,ElemType e,int*pos)ElemType*end=L-slist+L-length;ElemType*p=L-slist;int i;for(i=1;p=end)return ERROR;else return OK;/*ListLocate*/*定义菜单字符串数组*/int menu_select().char*menu=n*MENU*n,1.Create Listn,/*创建顺序

9、表*/2.Get Elementn,/*查找顺序表中的元素*/3.Insert datan,/*插入数据*/4.Delete datan,/*删除数据*/0.Quitn,/*退出*/n*MENU*n ;char s3;/*以字符形式保存选择号*/int c,i;/*定义整形变量*/for(i=0;i7;i+)/*输出主菜单数组*/printf(%s,menui);do printf(nEnter you choice(04):);/*在菜单窗口外显示提示信息*/scanf(%s,s);/*输入选择项*/c=atoi(s);/*将输入的字符串转化为整形数*/while(c4);/*选择项不在 0

10、4 之间重输*/return c;/*返回选择项，主程序根据该数调用相应的函数*/*主函数*/int main()Sqlist sl;InitList_sq(&sl);int n;int m,k;printf(please input n:);/*输入顺序表的元素个数*/scanf(%d,&n);if(n=0)printf(ERROR);for(;)/*无限循环*/switch(menu_select()/*调用主菜单函数，返回值整数作开关语句的条件*/case 1:printf(n1-Create Sqlist:n);CreateList_sq(&sl,n);printf(nPrint Sq

11、list:n);PrintList_sq(&sl);break;.case 2:printf(n3-GetElem from Sqlist:n);printf(please input search data:);scanf(%d,&k);int pos;if(!ListLocate(&sl,k,&pos)printf(Not found);else printf(found the element,position is%dn,pos);printf(nPrint Sqlist:n);PrintList_sq(&sl);break;case 3:printf(n4-Insert from S

12、qlist:n);printf(n input insert location and data:(location,data)n);scanf(%d,%d,&m,&k);if(ListInsert_sq(&sl,m,k)printf(nOKn);printf(nPrint Sqlist:n);PrintList_sq(&sl);else printf(nERROR!);break;case 4:printf(n5-Delete from Sqlist:n);printf(nplease input delete locationn);scanf(%d,&k);int deldata;if(L

13、istDelete_sq(&sl,k,&deldata)printf(nOKn);printf(nDelete data is%dn,deldata);printf(nPrintSqlist:n);PrintList_sq(&sl);else printf(nERROR!);break;case 0:exit(0);/*如菜单返回值为 0 程序结束*/.return 0;2、按照要求完成程序 exp2_2.c，实现单链表的相关操作。exp2_2.c 部分代码如下：#include#include#define ERROR 0#define OK 1 typedef int ElemType;/

14、*定义表元素的类型*/*（1）-线性表的单链表存储表示*/typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;LNode*InitList(LinkList L);/*带头结点单链表初始化*/void PrintList(LinkList L);/*输出带头结点单链表的所有元素*/int GetElem(LinkList L,int i,ElemType*e);/*查找第 i 位置的元素，并由 e 返回其值*/int InsertElem(LinkList L,int i,ElemType e);/*在第 i

15、 个位置插入元素 e*/int DeleteElem(LinkList L,int i,ElemType*e);/*删除第 i 位置的元素，并由 e 返回其值*/void DestroyLinkList(LinkList L);/*释放链表及其空间*/LinkList CreateList(int n);/*创建 n 个结点的单链表*/int menu_select();/*菜单函数*/*带头结点单链表初始化*/LNode*InitList(LinkList L)L=(LNode*)malloc(sizeof(LNode);/*申请一个头结点*/if(!L)return ERROR;/*申请失

16、败*/L-next=NULL;/*头结点的指针域置空*/return L;/*（1）-输出带头结点单链表的所有元素*/void PrintList(LinkList L)LNode*p;p=L-next;while(p!=NULL).printf(%5d,p-data);p=p-next;/*PrintList*/*（2）-在单链表的第 i 个位置插入元素 e，若插入成功返回 OK，插入失败返回 ERROR*/int InsertElem(LinkList L,int i,ElemType e)LNode*p=L,*s;int j=0;while(p&jnext;j+;if(!p|ji-1)r

17、eturn ERROR;s=(LNode*)malloc(sizeof(LNode);if(!s)return ERROR;s-data=e;s-next=p-next;p-next=s;return OK;/*InsertElem*/*（3）-查找第 i 位置的元素，若存在返回 OK并由 e 返回其值，若不存在返回 ERROR*/int GetElem(LinkList L,int i,ElemType*e)LNode*p;int j=1;while(p&jnext;j+;if(!p|ji)return ERROR;.*e=p-data;return OK;/*GetElem*/*（4）-删

18、除第 i 位置的元素，成功返回 OK，并由 e 返回其值，若不成功返回 ERROR，注意删除的结点必须释放其所占空间*/int DeleteElem(LinkList L,int i,ElemType*e)LNode*p=L,*s;int j=0;while(p&jnext;j+;if(!p|ji-1)return ERROR;s=p-next;p-next=s-next;*e=s-data;free(s);return OK;/*DeleteElem*/*（5）-创建具有 n 个结点的单链表，创建成功返回其头指针*/LinkList CreateList(int n)LNode*p,*q,*

19、head;int i;head=(LinkList)malloc(sizeof(LNode);head-next=NULL;p=head;for(i=0;idata);q-next=NULL;/节点指针域置空 p-next=q;/新节点连接在表末尾 p=q;return head;/*CreateList*/./*释放链表及其空间*/void DestroyLinkList(LinkList L)LNode*p=L,*q;while(p)q=p-next;free(p);p=q;/*DestroyLinkList*/int menu_select()char*menu=n*MENU*n,1.I

20、nit LinkListn,/*初始化链表*/2.Get Elementn,/*查找元素*/3.Insert datan,/*插入元素*/4.Delete datan,/*删除元素*/5.CreateLinkListn,/*创建具有 n 个元素的链表*/0.Destroy LinkList&Quitn,/*释放链表所占空间&退出*/n*MENU*n ;char s3;/*以字符形式保存选择号*/int c,i;/*定义整形变量*/for(i=0;i8;i+)/*输出主菜单数组*/printf(%s,menui);do printf(nEnter you choice(05):);/*在菜单窗口

21、外显示提示信息*/scanf(%s,s);/*输入选择项*/c=atoi(s);/*将输入的字符串转化为整形数*/while(c5);/*选择项不在 05 之间重输*/return c;/*返回选择项，主程序根据该数调用相应的函数*/int main()int i,n;.ElemType e;LinkList L=NULL;/*定义指向单链表的指针*/for(;)/*无限循环*/switch(menu_select()/*调用主菜单函数，返回值整数作开关语句的条件*/*值不同，执行的函数不同，break 不能省略*/case 1:printf(n1-Init LinkList:n);L=Ini

22、tList(L);if(L!=NULL)printf(nInitLinkList OK!n);else printf(nInitLinkList Error!n);break;case 2:printf(n2-GetElem from LinkList:n);printf(input pos=);scanf(%d,&i);if(L!=NULL&GetElem(L,i,&e)printf(No%i is%d,i,e);printf(nPrintfList:n);PrintList(L);else printf(Error&Not exists!);break;case 3:printf(n3-I

23、nsert e into LinkList:n);printf(input pos=);scanf(%d,&i);printf(input e=);scanf(%d,&e);if(L!=NULL&InsertElem(L,i,e)printf(nInsert OK!n);printf(nPrintfList:n);PrintList(L);else printf(nInsert Error!n);break;.case 4:printf(n4-Delete from LinkList:n);printf(input pos=);scanf(%d,&i);if(L!=NULL&DeleteEle

24、m(L,i,&e)printf(nOKn);printf(nDelete data is%dn,e);printf(nPrintfList:n);PrintList(L);else printf(nDelete Error!n);break;case 5:printf(please input n:);/*输入单链表的元素个数*/scanf(%d,&n);if(n0)printf(ERROR);break;printf(nCreate LinkList.n);L=CreateList(n);if(L=NULL)printf(Error!n);break;printf(nPrintfList:n

25、);PrintList(L);break;case 0:printf(nDestroy linklist and free memory.n);if(L!=NULL)DestroyLinkList(L);L=NULL;exit(0);/*如菜单返回值为 0 程序结束*/return 0;.3、循环链表的应用（约瑟夫回环问题）用整数序列 1，2，3，n 表示顺序坐在圆桌周围的人，并采用循环链表作为存储结构。任意位置 k 开始计数，计到 m让此位置的人出局，重复上述过程，直至只剩下最后一个人。依次输出每个出局的人的序号。提示：用一个无头结点的循环单链表来实现 n 个元素的存储。exp2_3.c 部

26、分代码如下：#include#include#define ERROR 0#define OK 1 typedef int ElemType;/*定义表元素的类型*/typedef struct LNode /*线性表的单链表存储*/ElemType data;struct LNode*next;LNode,*LinkList;/*（1）-创建具有 n 个结点的无头结点的单向循环链表，返回其头指针*/LinkList CreateList(int n)LinkList head=NULL;LNode*s,*r;int i;for(i=1;idata=i;s-next=NULL;if(head=

27、NULL)head=s;else r-next=s;r=s;r-next=head;return head;/*CreateList*/*（2）-输出无头结点循环单链表的所有元素*/void PrintList(LinkList L).LNode*p,*q;/p=L-next;p=L;q=p;while(p!=NULL)printf(%5d,p-data);p=p-next;if(p=q)break;printf(n);/*PrintList*/*（3）-约瑟夫问题计算，依次输出出局的元素的序号*/void JOSEPHUS(int n,int k,int m,LinkList L)LNode

28、*p,*q;int i;p=L;for(i=1;inext;while(p-next!=p)for(i=1;inext;q-next=p-next;printf(%5d,p-data);free(p);p=q-next;printf(%5d,p-data);/*JOSEPHUS*/int main()int n,m,k;LinkList L=NULL;/*定义指向单链表的指针*/./输入 n 个人、从 k 位置开始、报 m出局 while(scanf(%d%d%d,&n,&k,&m)=3)/*n个元素从 k 位置开始每 m个报数*/L=CreateList(n);PrintList(L);JO

29、SEPHUS(n,k,m,L);return 0;4、选做实验：设有头单链表，设计算法将表中值相同的元素仅保留一个结点。提示：指针 p 从链表的第一个元素开始，利用指针 q 从指针 p 位置开始向后搜索整个链表，删除与之值相同的元素；指针 p 继续指向下一个元素，开始下一轮的删除，直至 pnull为至，既完成了对整个链表元素的删除相同值。#include#include#define ERROR 0#define OK 1 typedef int ElemType;/*定义表元素的类型*/*（1）-线性表的单链表存储表示*/typedef struct LNode ElemType data;

30、struct LNode*next;LNode,*LinkList;LinkList L=NULL;LNode*InitList(LinkList L);/*带头结点单链表初始化*/void PrintList(LinkList L);/*输出带头结点单链表的所有元素*/void DestroyLinkList(LinkList L);/*释放链表及其空间*/LinkList CreateList(int n);/*创建 n 个结点的单链表*/*带头结点单链表初始化*/LNode*InitList(LinkList L)L=(LNode*)malloc(sizeof(LNode);/*申请一个

31、头结点*/if(!L)return ERROR;/*申请失败*/L-next=NULL;/*头结点的指针域置空*/return L;/*（1）-输出带头结点单链表的所有元素*/void PrintList(LinkList L)LNode*p;.p=L-next;while(p!=NULL)printf(%5d,p-data);p=p-next;printf(n);/*PrintList*/LinkList CreateList(int n)LNode*p,*q,*head;int i;head=(LinkList)malloc(sizeof(LNode);head-next=NULL;p=h

32、ead;for(i=0;idata);q-next=NULL;/节点指针域置空 p-next=q;/新节点连接在表末尾 p=q;return head;/*CreateList*/LinkList SelectList(LinkList L)void Delete(LinkList L,int i);LNode*p,*q,*a;p=L-next;a=L-next;while(p!=NULL)q=p-next;while(q!=NULL)if(p-data=q-data)a-next=q-next;.a=q;q=q-next;p=p-next;return L;void DestroyLinkL

33、ist(LinkList L)LNode*p=L,*q;while(p)q=p-next;free(p);p=q;/*DestroyLinkList*/int main()int n;L=InitList(L);if(L=NULL)printf(nInitLinkList Error!n);return 0;printf(please input n:);/*输入单链表的元素个数*/scanf(%d,&n);if(n=0)printf(nError!n);return 0;L=CreateList(n);if(L=NULL)printf(nInitLinkList Error!n);return 0;PrintList(L);L=SelectList(L);PrintList(L);.if(L!=NULL)DestroyLinkList(L);L=NULL;return 0;【实验小结】