2022年C语言数据结构线性表的基本操作实验报告 .pdf

《2022年C语言数据结构线性表的基本操作实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年C语言数据结构线性表的基本操作实验报告 .pdf（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 实验一线性表的基本操作一、实验目的与基本要求1掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。2了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。3掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4掌握运用 C 语言上机调试线性表的基本方法。二、实验条件1硬件：一台微机2软件：操作系统和C 语言系统三、实验方法确定存储结构后，上机调试实现线性表的基本运算。四、实验内容1建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i 个元素，定位函数（返回第一个与

2、x 相等的元素位置），插入，删除。2建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i 个元素，定位函数（返回第一个与x 相等的元素位置），插入，删除。3假设有两个按数据元素值非递减有序排列的线性表A 和 B，均以顺序表作为存储结构。编写算法将 A 表和 B 表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将 B 中元素插入 A 中，或新建 C 表）4 假设有两个按数据元素值非递减有序排列的线性表A 和 B，均以单链表作为存储结构。编写算法将A 表和 B 表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。五

3、、附源程序及算法程序流程图1.源程序（1）源程序(实验要求 1 和 3)#include#include#include#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef struct arr 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 34 页 -2 int*elem;int length;int listsize;Sqlist;void menu();/菜单void InitList(Sqlist*p);/创建线性表void ShowList(Sqlist*p);/输出顺序线性表void ListDelet

4、e(Sqlist*p,int i,int&e);/在顺序线性表中删除第i 个元素，并用e返回其值void ListInsert(Sqlist*p);/在顺序线性表中第i 个元素前插入新元素e void ListEmpty(Sqlist*p);/判断 L 是否为空表void GetList(Sqlist*p,int i,int&e);/用 e 返回 L 中第 i 个数据元素的值void ListInsert(Sqlist*p,int i,int e);bool compare(int a,int b);void LocateElem(Sqlist*L,int e);/在顺序线性表L 中查找第1

5、个值与e 满足compare()d 元素的位序void MergeList_L(Sqlist*La,Sqlist*Lb);/归并void main()Sqlist La;Sqlist Lb;int n,m,x;menu();scanf(%d,&n);while(n)switch(n)case 0:;break;case 1:InitList(&La);break;case 2:ListEmpty(&La);break;case 3:printf(请输入插入的位序:n);scanf(%d,&m);printf(请出入要插入的数:n);scanf(%d,&x);ListInsert(&La,m,x

6、);break;case 4:printf(请输入删除元素的位序:n);scanf(%d,&m);名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 34 页 -3 ListDelete(&La,m,x);printf(删除的元素为:%dn,x);break;case 5:printf(请输入要找的与线性表中相等的数:n);scanf(%d,&m);LocateElem(&La,m);break;case 6:printf(请输入查找的位序:n);scanf(%d,&m);GetList(&La,m,x);printf(La 中第%d 个元素的值为%dn,m,x);break;cas

7、e 7:ShowList(&La);break;case 8:InitList(&Lb);break;case 9:MergeList_L(&La,&Lb);printf(归并成功!);break;menu();scanf(%d,&n);/*菜单*/void menu()printf(*nn);printf(0.退出 nn);printf(1.创建线性表Lann);printf(2.判断 La 是否为空表 nn);printf(3.插入元素(La)nn);printf(4.删除元素(La)nn);printf(5.定位元素(La)nn);printf(6.取元素(La)nn);printf(7

8、.输出线性表 nn);名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 34 页 -4 printf(8.创建线性表Lbnn);printf(9.归并为一个线性表Lann);printf(*nn);/*创建顺序线性表L*/void InitList(Sqlist*L)int n;int i=0;L-elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(NULL=L-elem)printf(储存分配失败!n);else L-length=0;L-listsize=LIST_INIT_SIZE;printf(输入顺序表a:n);scanf(%d

9、,&n);while(n)L-elemi=n;i+;L-length+;L-listsize=L-listsize-4;scanf(%d,&n);/*输出顺序线性表*/void ShowList(Sqlist*p)int i;if(0=p-length)printf(数组为空!n);else for(i=0;ilength;i+)printf(%d,p-elemi);printf(n);/*判断 L 是否为空表*/void ListEmpty(Sqlist*p)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 34 页 -5 if(0=p-length)printf(L 是空表!n

10、);else printf(L 不是空表!n);/*在顺序线性表中第i 个元素前插入新元素e*/void ListInsert(Sqlist*p,int i,int e)int*newbase;int*q1;int*q2;while(ip-length+1)printf(您输入的i 超出范围!n 请重新输入要插入的位置n:);scanf(%d,&i);if(p-length=p-listsize)newbase=(int*)realloc(p-elem,(p-listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);else p-elem=

11、newbase;p-listsize+=LISTINCREMENT;q1=&(p-elemi-1);for(q2=&(p-elemp-length-1);q2=q1;-q2)*(q2+1)=*q2;*q1=e;+p-length;/*/在顺序线性表中删除第i 个元素，并用e返回其值*/void ListDelete(Sqlist*p,int i,int&e)int*q1,*q2;while(ip-length)printf(您输入的i 超出范围!请重新输入:);scanf(%d,&i);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 34 页 -6 q1=&(p-elemi-1)

12、;e=*q1;q2=p-elem+p-length-1;for(+q1;q1length;/*对比 a 与 b 相等*/bool compare(int a,int b)if(a=b)return 1;else return 0;/*在顺序线性表L 中查找第1 个值与 e 满足 compare()d 元素的位序*/void LocateElem(Sqlist*L,int e)int i=1;int*p;p=L-elem;while(ilength&!compare(*p+,e)+i;if(ilength)printf(第 1 个与 e 相等的元素的位序为%dn,i);else printf(没

13、有该元素!n);/*用 e返回 L 中第 i 个数据元素的值*/void GetList(Sqlist*p,int i,int&e)Sqlist*p1;p1=p;e=p1-elemi-1;/*已知顺序线性表La 和 Lb 是元素按值非递减排列*/*把 La 和 Lb 归并到 La 上,La 的元素也是按值非递减*/void MergeList_L(Sqlist*La,Sqlist*Lb)int i=0,j=0,k,t;int*newbase;Sqlist*pa,*pb;pa=La;pb=Lb;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 34 页 -7 while(ilengt

14、h&jlength)if(pa-elemi=pb-elemj)if(pa-listsize=0)newbase=(int*)realloc(pa-elem,(pa-listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);for(k=pa-length-1;k=i;k-)pa-elemk+1=pa-elemk;pa-length+;pa-elemi=pb-elemj;i+;j+;else i+;while(jlength)if(pa-listsize length-j)newbase=(int*)realloc(pa-elem,(pa-li

15、stsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);for(j;jlength;j+,i+)pa-elemi=pb-elemj;pa-length+;for(i=0;ilength/2;i+)t=pa-elemi;pa-elemi=pa-elempa-length-i-1;pa-elempa-length-i-1=t;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 34 页 -8（2）源程序(实验要求 2 和 4)#include#include#include typedef struct LNode int data;s

16、truct LNode*next;LNode,*LinkList;void menu();LinkList InitList();void ShowList(LinkList L);void ListDelete(LinkList L,int i,int&e);void ListEmpty(LinkList L);void GetList(LinkList L,int i,int&e);void ListInsert(LinkList L,int i,int e);bool compare(int a,int b);void LocateElem(LinkList L,int e);LinkL

17、ist MergeList_L(LinkList La,LinkList Lb);int total=0;void main()LinkList La;LinkList Lb;La=(LinkList)malloc(sizeof(struct LNode);La-next=NULL;Lb=(LinkList)malloc(sizeof(struct LNode);Lb-next=NULL;int n;int m;int x;menu();scanf(%d,&n);while(n)switch(n)case 0:;break;case 1:La-next=InitList();break;cas

18、e 2:ListEmpty(La);break;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 34 页 -9 case 3:printf(请输入要插入到第几个节点前:n);scanf(%d,&m);printf(请输入插入的数据:n);scanf(%d,&x);ListInsert(La,m,x);break;case 4:printf(请输入删除元素的位序:n);scanf(%d,&m);ListDelete(La,m,x);printf(删除的元素为:%dn,x);break;case 5:printf(请输入要找的与线性表中相等的数:n);scanf(%d,&m);Loc

19、ateElem(La,m);break;case 6:printf(请输入查找的位序:n);scanf(%d,&m);GetList(La,m,x);printf(La 中第%d 个元素的值为%dn,m,x);break;case 7:ShowList(La);break;case 8:Lb-next=InitList();break;case 9:La=MergeList_L(La,Lb);printf(归并成功 n);break;menu();scanf(%d,&n);void menu()printf(*nn);printf(0.退出 nn);printf(1.创建线性表Lann);pr

20、intf(2.判断是否为空表nn);printf(3.插入元素 nn);名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 34 页 -10 printf(4.删除元素 nn);printf(5.定位元素 nn);printf(6.取元素 nn);printf(7.输出线性表 nn);printf(8.创建线性表Lbnn);printf(9.归并两线性表nn);printf(*nn);/创建链式线性表L LinkList InitList()int count=0;LinkList pHead=NULL;LinkList pEnd,pNew;pEnd=pNew=(LinkList)m

21、alloc(sizeof(struct LNode);printf(请输入数据:n);scanf(%d,&pNew-data);while(pNew-data)count+;if(count=1)pNew-next=pHead;pEnd=pNew;pHead=pNew;else pNew-next=NULL;pEnd-next=pNew;pEnd=pNew;pNew=(LinkList)malloc(sizeof(struct LNode);printf(请输入数据:n);scanf(%d,&pNew-data);名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 34 页 -11

22、 free(pNew);total=total+count;return pHead;/判断 L 是否为空表void ListEmpty(LinkList L)if(NULL=L-next)printf(此表为空表!n);else printf(此表不为空表!n);/在链式线性表中第i 个元素前插入新元素e void ListInsert(LinkList L,int i,int e)LinkList p;LinkList s;p=L;int j=0;while(p&jnext;+j;if(!p|ji-1)printf(不存在您要找的节点!n);else s=(LinkList)malloc(

23、sizeof(int);s-data=e;s-next=p-next;p-next=s;printf(插入节点成功!n);/输出链式线性表void ShowList(LinkList L)LinkList p;p=L-next;if(p=NULL)printf(此表为空表!n);else 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 34 页 -12 while(p)printf(%d,p-data);p=p-next;printf(n);/在链式线性表中删除第i 个元素，并用e返回其值void ListDelete(LinkList L,int i,int&e)LinkLi

24、st p;LinkList q;p=L;int j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)printf(没有找到要删除的位置!);else q=p-next;p-next=q-next;e=q-data;free(q);/用 e返回 L 中第 i 个数据元素的值void GetList(LinkList L,int i,int&e)LinkList p;p=L-next;int j=0;while(p-next&jnext;+j;if(!(p)|ji-1)printf(没有找到要查找的位置!);else e=p-data;名师资料总结-精品资料欢迎

25、下载-名师精心整理-第 12 页，共 34 页 -13 /对比 a与 b 相等bool compare(int a,int b)if(a=b)return 1;else return 0;/在链式线性表L 中查找第1 个值与 e满足 compare()d 元素的位序void LocateElem(LinkList L,int e)int i=0;LinkList p;p=L;while(p-next&!compare(p-data,e)p=p-next;i+;if(NULL=p-next)if(0=compare(p-data,e)printf(没有该元素!n);else printf(第 1

26、 个与 e 相等的元素的位序为%dn,i);else if(compare(p-data,e)printf(没有该元素!n);LinkList MergeList_L(LinkList La,LinkList Lb)int i,j,k;LinkList pa_1,pb_1,pa_2,pb_2,pc,pd;pa_1=La-next;pc=pa_2=La;pb_1=pb_2=Lb-next;if(pa_1-data pb_1-data)pc=pa_2=Lb;pa_1=Lb-next;pb_1=pb_2=La-next;名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 34 页 -14

27、 while(pa_1&pb_1)if(pa_1-data=pb_1-data)pa_2-next=pb_1;pb_2=pb_1-next;pb_1-next=pa_1;pb_1=pb_2;pa_2=pa_2-next;else pa_1=pa_1-next;pa_2=pa_2-next;if(pb_1)pa_2-next=pb_1;pd=(LinkList)malloc(sizeof(struct LNode);pd-next=NULL;pa_2=pd;k=total;for(i=0;inext;for(j=1;jnext;pb_1=(LinkList)malloc(sizeof(struc

28、t LNode);pa_2-next=pb_1;pa_2=pa_2-next;pa_2-data=pa_1-data;k-;pa_2-next=NULL;return pd;名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 34 页 -15 2.流程图(实验要求 1 和 3)开始判断 L是否为空表插入元素创建线性表La定位元素删除元素创建线性表Lb取元素输出线性表归并为一个线性表 La123457869switch(n)输入 nWhile（n）YNmenu();scanf(%d,&n);开始图 1 主函数流程图开始L-elem=(int*)malloc(LIST_INIT_SIZ

29、E*sizeof(int)NULL=L-elemYNL-length=0;L-listsize=LIST_INIT_SIZE;printf(输入顺序表a:n);scanf(%d,&n)；while（n）L-elemi=n；i+;L-length+;L-listsize=L-listsize-4;scanf(%d,&n);结束NY图 2 创建线性表La 流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 34 页 -16 开始s-top=s-base此栈为空栈此栈不为空栈结束YN图 3 判断 La 是否为空表流程图开始0=p-lengthprintf(L是空表!n);print

30、f(L不是空表!n);结束图 4 插入元素(La)流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 34 页 -17 开始ip-length+1i值不在范围内，重新输入p-length=p-listsize空间不足，接着分配空间p-elem=newbase;p-listsize+=LISTINCREMENT;q1=&(p-elemi-1);q2=&(p-elemp-length-1)q2=q1*(q2+1)=*q2;-q2YN*q1=e;+p-length;结束NYYN图 5 删除元素(La)流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 34 页 -

31、18 开始p=L-elem;ilength&!compare(*p+,e)+i；ilength输出位序没有该元素结束YNYN图 6 定位元素(La)流程图开始p1=p;e=p1-elemi-1;结束图 7 取元素(La)流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 34 页 -19 开始(0=p-length数组为空输出所有元素结束NY图 8 输出线性表流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 34 页 -20 开始pa=La;pb=Lb;ilength&jlength(pa-elemi=pb-elemjpa-listsize=0newbas

32、e=(int*)realloc(pa-elem,(pa-listsize+LISTINCREMENT)*sizeof(int);!newbaseexit(0);Yk=pa-length-1k=iYNNpa-elemk+1=pa-elemk;k-pa-length+;pa-elemi=pb-elemj;i+;j+;NYYNi+;NYjlengthpa-listsize length-jnewbase=(int*)realloc(pa-elem,(pa-listsize+LISTINCREMENT)*sizeof(int);!newbaseexit(0);YjlengthYYNj+i+pa-ele

33、mi=pb-elemj;pa-length+;YNNN11i=0ilength/2t=pa-elemi;pa-elemi=pa-elempa-length-i-1;pa-elempa-length-i-1=t;i+结束YN图 9 输出线性表流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 34 页 -21 流程图(实验要求 2 和 4)开始创建头结点La,Lb并输入 nwhile(n)switch(n)创建线性表La判断是否为空表插入元素删除元素定位元素取元素输出线性表创建线性表Lb归并两线性表123456789结束menu（）menu();scanf(%d,&n);YN图

34、 10 主函数流程图开始LinkList pHead=NULL;LinkList pEnd,pNew;pEnd=pNew=(LinkList)malloc(sizeof(struct LNode);scanf(%d,&pNew-data);pNew-datacount+;count=1pNew-next=pHead;pEnd=pNew;pHead=pNew;pNew-next=NULL;pEnd-next=pNew;pEnd=pNew;YNpNew=(LinkList)malloc(sizeof(struct LNode);scanf(%d,&pNew-data);结束YN图 11 创建线性表

35、La 流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 34 页 -22 开始NULL=L-next输出空表输出不为空表结束YN图 12 判断是否为空表流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 34 页 -23 开始LinkList p;LinkList s;p=L;p&jnext;+j;YN!p|ji-1输出找不到节点s=(LinkList)malloc(sizeof(int);s-data=e;s-next=p-next;p-next=s；YN结束图 13 插入元素流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 34 页

36、 -24 开始LinkList p;LinkList q;p=L;p-next&jnext;+j;Y!(p-next)|ji-1N输出没找到位置q=p-next;p-next=q-next;e=q-data;结束NY图 14 删除元素流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 34 页 -25 开始LinkList p;p=L;p-next&!compare(p-data,e)p=p-next;i+;NULL=p-next0=compare(p-data,e)输出没有该元素输出位序compare(p-data,e)没有该元素结束YNYNYNYN开始LinkList p

37、;p=L-next;p-next&jnext;+j;!(p)|ji-1没有找到要查找的位置e=p-data;结束YNYN图 15 定位元素流程图图图 16 取元素流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 25 页，共 34 页 -26 开始LinkList pHead=NULL;LinkList pEnd,pNew;pEnd=pNew=(LinkList)malloc(sizeof(struct LNode);scanf(%d,&pNew-data);pNew-datacount+;count=1pNew-next=pHead;pEnd=pNew;pHead=pNew;pNew-

38、next=NULL;pEnd-next=pNew;pEnd=pNew;YNpNew=(LinkList)malloc(sizeof(struct LNode);scanf(%d,&pNew-data);结束YN图 17 创建 Lb 流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 26 页，共 34 页 -27 开始pa_1=La-next;pc=pa_2=La;pb_1=pb_2=Lb-next;pa_1-data pb_1-datapc=pa_2=Lb;pa_1=Lb-next;pb_1=pb_2=La-next;pa_1&pb_1pa_1-data=pb_1-datapa_2-ne

39、xt=pb_1;pb_2=pb_1-next;pb_1-next=pa_1;pb_1=pb_2;pa_2=pa_2-next;pa_1=pa_1-next;pa_2=pa_2-next;YNYNYN1名师资料总结-精品资料欢迎下载-名师精心整理-第 27 页，共 34 页 -28 1if(pb_1)pa_2-next=pb_1;pd=(LinkList)malloc(sizeof(struct LNode);pd-next=NULL;pa_2=pd;k=total;i=0;inext;j=1jnext;j+pb_1=(LinkList)malloc(sizeof(struct LNode);p

40、a_2-next=pb_1;pa_2=pa_2-next;pa_2-data=pa_1-data;k-;i+pa_2-next=NULL;return pd;结束NYNYNY图 18 归并两表流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 34 页 -29 六、运行结果1.(实验要求 1 和 3)点击运行，首先出现的是菜单界面，选择菜单选项进行操作，如图所示。按“1”回车后，即可以创建顺序表La，输入“0”结束添加，如图所示。名师资料总结-精品资料欢迎下载-名师精心整理-第 29 页，共 34 页 -30 输入 2，判断 La 是否为空表，如图所示。输入 3，在指定的位序

41、插入元素，如图所示。名师资料总结-精品资料欢迎下载-名师精心整理-第 30 页，共 34 页 -31 输入 4，在指定的位序删除元素，如图所示。输入 5，查找表中与之相等数的位序，如图所示。名师资料总结-精品资料欢迎下载-名师精心整理-第 31 页，共 34 页 -32 输入 6，查找相应位序对应的元素，如图所示。输入 7，输出顺序表中的内容，如图所示。输入 8，创建顺序表 Lb，如图所示。名师资料总结-精品资料欢迎下载-名师精心整理-第 32 页，共 34 页 -33 输入 9，归并两表为递减顺序，如图所示。名师资料总结-精品资料欢迎下载-名师精心整理-第 33 页，共 34 页 -34 2.(实验要求 2 和 4)七、算法效率分析八、实验小结通过这个实验，感受到了指针的重要性，同时也感受到了指针并不是如你所愿的那样去指，稍不留神，就出错了。再有函数定义时*与&及调用结构体成员的方法，课后应该再仔细斟酌斟酌，多多交流，多多练习把。名师资料总结-精品资料欢迎下载-名师精心整理-第 34 页，共 34 页 -