《数据结构(邹永林版)实验报告2-顺序表与链表》由会员分享，可在线阅读，更多相关《数据结构(邹永林版)实验报告2-顺序表与链表（19页珍藏版）》请在金锄头文库上搜索。
1、实验二顺序表与链表【实验目的】1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点优缺点 。【实验学时】2 学时【实验预习】答复以下问题：1、顺序表的存储表示在顺序表中，任一数据元素的存放位置是从起始位置开始、与该数据元素的位序成正比的对应存储位置，借助 LOC(ai)=LOC(a1)+(i-1)*1确定，则顺序表是一种随机存取的存储结构。2、单链表的存储表示线性链表也称单链表，在每一个结点中只包含一个指针，用于指示该结点的直接后继结点，整个链表通过指针相连， 最后一个结
2、点因为没有后继结点， 其指针置为空 NULL 。这样， 链表中所有数据元素 结点构成一对一的逻辑关系，实现线性表的链式存储。【实验内容和要求】1、按照要求完成程序，实现顺序表的相关操作。以下函数均具有返回值，假设操作完成，返回OK，操作失败返回 ERROR。函数需返回的其他数据，使用函数参数返回。部分代码如下：#include#include#include#define ERROR 0#define MAXSIZE100#define OK 1typedefintElemType; /*定义表元素的类型*/typedef struct slistElemType *list;int list
3、size;int length;Sqlist;Sqlist *L;/*1-补充顺序表的存储分配表示，采用定长和可变长度存储均可*/*函数声明*/int InitList_sq(Sqlist *L);int CreateList_sq(Sqlist *L);1int 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
4、menu_select();/*2-顺序表的初始化*/int InitList_sq(Sqlist *L)L-list=(ElemType *)malloc(MAXSIZE*sizeof(ElemType);if(L-list=NULL)return ERROR;elseL-length=0;L-listsize=MAXSIZE;return 0;/*InitList*/*3-创建具有 n 个元素的顺序表*/int CreateList_sq(Sqlist *L)int a,b,c;printf(请输入输入数据的个数 n:);scanf(%d,&a);printf(请输入输入的数据:);for
5、(b=0;blistb=c;L-length=L-length+a;return 0;/*CreateList*/*4-输出顺序表中的元素*/int PrintList_sq(Sqlist *L)int a;printf(输出数据:);for(a=0;alength;a+)printf(%d,L-lista);return 0;/*PrintList*/*5-在顺序表的第 i 个位置之前插入新元素 e*/int ListInsert_sq(Sqlist *L,int i,ElemType e)2int a=L-length-1;for(;a=i-1;a-)L-lista+1=L-lista;L
6、-listi-1=e;L-length+=1;return OK;/*ListInsert*/*6-在顺序表中删除第 i 个元素，e 返回删除的元素*/int ListDelete_sq(Sqlist *L,int i,ElemType *e)int a=i-1;*e=L-listi-1;for(;alength;a+)L-lista=L-lista+1;L-length-=1;return OK;/* ListDelete_sq */*7-在顺序表中查找指定值元素，pos 为返回其位置序号*/int ListLocate(Sqlist *L,ElemType e,int *pos)int a
7、,b=0;for(a=0;alength;a+)if(e=L-lista)b=0;*pos=a+1;break;elseb=1;if(b=1)return 0;elsereturn OK;/* ListLocate */*定义菜单字符串数组*/int menu_select()char *menu=n*MENU*n, 1. Create Listn,/*创建顺序表*/ 2. Get Elementn,/*查找顺序表中的元素*/ 3. Insert datan,/*插入数据*/ 4. Delete datan,/*删除数据*/3 0. Quitn,/*退出*/n*MENU*n;char s3;/
8、*以字符形式保存选择号*/int c,i;/*定义整形变量*/for (i=0;i7;i+)/*输出主菜单数组*/printf(%s,menui);doprintf(nEnter you choice(04):);/*在菜单窗口外显示提示信息*/scanf(%s,s);/*输入选择项*/c=atoi(s);/*将输入的字符串转化为整形数*/while (c4);/*选择项不在 04 之间重输*/return c;/*返回选择项，主程序根据该数调用相应的函数*/*主函数*/int main()int m,k;int pos;int deldata;Sqlist sl;InitList_sq(&s
9、l);for (;)/*无限循环*/switch (menu_select()/*调用主菜单函数，返回值整数作开关语句的条件*/case 1:printf(n1-Create Sqlist:n);CreateList_sq(&sl);printf(nPrint Sqlist:n);PrintList_sq(&sl);break;case 2:printf(n3-GetElem from Sqlist:n);printf(please input search data:);scanf(%d,&k);if (!ListLocate(&sl,k,&pos)printf(Not found);els
10、eprintf(found the element, position is %dn,pos);printf(nPrint Sqlist:n);PrintList_sq(&sl);4break;case 3:printf(n4-Insert from Sqlist: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);elsepr
11、intf(nERROR!);break;case 4:printf(n5-Delete from Sqlist:n);printf(nplease input delete locationn);scanf(%d,&k);if (ListDelete_sq(&sl,k,&deldata)printf(nOKn);printf(nDelete data is %dn,deldata);printf(nPrintSqlist:n);PrintList_sq(&sl);elseprintf(nERROR!);break;case 0:exit(0);/*如菜单返回值为 0 程序结束*/return
12、0;(1)创建一个顺序表5(2)查找元素位置3插入元素4删除元素62、按照要求完成程序 exp2_2.c，实现单链表的相关操作。exp2_2.c 部分代码如下：#include#include#include#define ERROR 0#define OK 1typedefint ElemType; /*定义表元素的类型*/*1-线性表的单链表存储表示*/typedef struct LNodeElemType date;struct LNode *next;LNode,*LinkList;LNode *InitList(); /*带头结点单链表初始化*/void PrintList(Lin
13、kList L);/*输出带头结点单链表的所有元素*/int GetElem(LinkList L,int i,ElemType *e); /*查找第 i 位置的元素，并由 e 返回其值*/int InsertElem(LinkList L,int i,ElemType e);/*在第 i 个位置插入元素 e*/int DeleteElem(LinkList L,int i,ElemType *e);/*删除第 i 位置的元素，并由 e 返回其值*/void DestroyLinkList(LinkList L);/*释放链表及其空间*/LinkList CreateList(int n);
14、/*创建 n 个结点的单链表*/int menu_select();/*菜单函数*/*带头结点单链表初始化*/LNode *InitList()LinkList L;L=(LNode *)malloc(sizeof(LNode);/*申请一个头结点*/if (!L)return ERROR;/*申请失败*/L-next=NULL;/*头结点的指针域置空*/return L;7/*1-输出带头结点单链表的所有元素*/void PrintList(LinkList L)LNode *p=L-next;int i=0;while(p)i+;printf(n 第%d 个元素%d,i,p-date);p
15、=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)return ERROR;s=(LNode *)malloc(sizeof(LNode);if(!s)return ERROR;s-date=e;s-next=p-next;p-next=s;return OK;/* InsertElem */*3-查找第 i 位置的元素，假设
16、存在返回OK 并由 e 返回其值，假设不存在返回ERROR*/int GetElem(LinkList L,int i,ElemType *e)LNode *p;int j=1;p=L-next;while(p&jnext;j+;if(!p|ji)return ERROR;*e=p-date;return OK;8/*GetElem*/*4-删除第 i 位置的元素，成功返回OK，并由e 返回其值，假设不成功返回ERROR，注意删除的结点必须释放其所占空间*/int DeleteElem(LinkList L,int i,ElemType *e)LNode *p=L,*s;int j=0;whi
17、le(p&jnext;j+;if(!p|ji-1)return ERROR;s=p-next;p-next=s-next;*e=s-date;free(s);return OK;/* DeleteElem */*5-创建具有 n 个结点的单链表，创建成功返回其头指针*/LinkList CreateList(int n)int i=1;LNode *p,*q,*L;L=InitList();p=L;while(idate);q-next=NULL;p-next=q;p=q;return L;/*CreateList*/*释放链表及其空间*/void DestroyLinkList(LinkLi
18、st L)LNode *p=L,*q;while(p)q=p-next;9free(p);p=q;/* DestroyLinkList */int menu_select()char *menu=n*MENU*n, 1. Init LinkListn,/*初始化链表*/ 2. Get Elementn,/*查找元素*/ 3. Insert datan,/*插入元素*/ 4. Delete datan,/*删除元素*/ 5. CreateLinkListn,/*创建具有 n 个元素的链表*/ 0. Destroy LinkList&Quitn, /*释放链表所占空间&退出*/n*MENU*n;c
19、har s3;/*以字符形式保存选择号*/int c,i;/*定义整形变量*/for (i=0;i8;i+)/*输出主菜单数组*/printf(%s,menui);doprintf(nEnter you choice(05):);/*在菜单窗口外显示提示信息*/scanf(%s,s);/*输入选择项*/c=atoi(s);/*将输入的字符串转化为整形数*/while (c5);/*选择项不在 05 之间重输*/return c;/*返回选择项，主程序根据该数调用相应的函数*/int main()int i,n;ElemType e;LinkList L=NULL;/*定义指向单链表的指针*/f
20、or (;)/*无限循环*/switch (menu_select()/*调用主菜单函数，返回值整数作开关语句的条件*/*值不同，执行的函数不同，break 不能省略*/case 1:printf(n1-Init LinkList:n);L=InitList(L);if(L!=NULL)printf(nInitLinkList OK!n);1 0elseprintf(nInitLinkList Error!n);break;case 2:printf(n2-GetElem from LinkList:n);printf(input pos=);scanf(%d,&i);if (L!=NULL&
21、GetElem(L,i,&e)printf(No%i is %d,i,e);printf(nPrintfList:n);PrintList(L);elseprintf(Error&Not exists!);break;case 3:printf(n3-Insert 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);el
22、seprintf(nInsert Error!n);break;case 4:printf(n4-Delete from LinkList:n);printf(input pos=);scanf(%d,&i);if(L!=NULL&DeleteElem(L,i,&e)printf(nOKn);printf(nDelete data is %dn,e);printf(nPrintfList:n);PrintList(L);elseprintf(nDelete Error!n);break;case 5:printf(please input n:);/*输入单链表的元素个数*/scanf(%d,
23、&n);1 1if (n0)printf(ERROR);break;printf(nCreate LinkList.n);L=CreateList(n);if (L=NULL)printf(Error!n);break;printf(nPrintfList:n);PrintList(L);break;case 0:printf(nDestroy linklist and free memory .n);if(L!=NULL)DestroyLinkList(L);L=NULL;exit(0);/*如菜单返回值为 0 程序结束*/return 0;实验结果：1初始化链表：2查找元素：1 23插入数
24、据：4删除数据：1 35创建链表：6销毁和退出链表：3 循环链表的应用约瑟夫回环问题、 用整数序列 1，2，3，n 表示顺序坐在圆桌周围的人，并采用循环链表作为存储结构。任意位置k 开始计数，计到 m 让此位置的人出局，重复上述过程，直至只剩下最后一个人。依次输出每个出局的人的序号。提示：用一个无头结点的循环单链表来实现n 个元素的存储。exp2_3.c 部分代码如下：#include#include#define ERROR 0#define OK 1typedef int ElemType; /*定义表元素的类型*/typedef struct LNode /*线性表的单链表存储*/ El
25、emType data; struct LNode *next; LNode,*LinkList;1 4/*1-创建具有 n 个结点的无头结点的单向循环链表，返回其头指针*/LinkList CreateList(int n) LinkList L; L=(LinkList )malloc(sizeof(LinkList); LNode *q,*p; printf(输入元素:n); scanf(%d,&L-data); q=L; int a; for(a=0;adata); q-next=p; q=p; q-next=L; return L;/*CreateList*/*2-输出无头结点循环单
26、链表的所有元素*/void PrintList(LinkList L) printf(输出表中的元素:); LNode *p; printf(%dn,L-data); p=L-next; while(p!=L) printf(n%dn,p-data); p=p-next; /*PrintList*/*3-约瑟夫问题计算，依次输出出局的元素的序号*/void JOSEPHUS(int n,int k,int m,LinkList L) L=CreateList(n); PrintList(L); int a,length=n; LNode *q; for(a=1;anext; while(len
27、gth!=1) for(a=0;anext; q=L-next;1 5 L-next=q-next; printf(被删除的数字:%dn,q-data); free(q); length-=1; printf(输出最终的一个数字:%d,L-data);/*JOSEPHUS*/int main() int n,m,k; LinkList L=NULL; /*定义指向单链表的指针*/ printf(1.输入元素的个数); printf( 2.输入位置); printf( 3.输入人数); while(scanf(%d%d%d,&n,&k,&m)=3) /*n个元素从 k 位置开始每 m 个报数*/
28、 JOSEPHUS(n,k,m,L); return 0;.输入 10 2 3，表示一共有 10 个数，从第 2 个数之后开始数，数到3 的人出局实验结果：4、选做实验：设有头单链表，设计算法将表中值相同的元素仅保留一个结点。提示：指针 p 从链表的第一个元素开始，利用指针q 从指针 p 位置开始向后搜索整个链表，删除与之值相同的元素；指针 p 继续指向下一个元素，开始下一轮的删除，直至pnull 为至，既完成了对整个链表元素的删除相同值。1 6#include#include#define ERROR 0#define OK 1typedef int ElemType;typedef str
29、uct LNode ElemType data; struct LNode *next;LNode,*LinkList;LinkList L=NULL;LNode *InitList(LinkList L);void PrintList(LinkList L);void DestroyLinkList(LinkList L);LinkList CreateList(int n);/*带头结点单链表初始化*/LNode *InitList(LinkList L) L=(LNode *)malloc(sizeof(LNode); if (!L) return ERROR; L-next=NULL;
30、 return L;/*输出带头结点单链表的所有元素*/void PrintList(LinkList L) LinkList p; p=L-next; int i=1; while(p) printf(nthe %d data is %d,i+,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=head; for(i=0;idata); q-ne
31、xt=NULL; p-next=q; p=q; return head;/*CreateList*/LinkList SelectList(LinkList L) void Delete(LinkList L,int i); LinkList 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 DestroyLinkList(LinkList L) LNode *p=
32、L,*q; while(p) q=p-next; free(p); p=q; /* DestroyLinkList */int main() int n; L=InitList(L);8 1 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;【实验小结】在平时的学习中，主要是老师讲我们听，只有上机的时候才操作一下，对知识的掌握和理解不够。这次课程设计让我认识到自己还有很多的不足， 对知识的掌握及熟练运用不够， 这让我在程序编写中遇到了很多困难。通过查找资料及向老师请教，我终于编写出了程序。这次实验课，让我学会了做任何事都要细心耐心专心。1 9
