数据结构实验报告

1实验报告年月日目录1实验一基于数组的表实验……………………………………………1实验二链表实验……………………………………………………10实验三基于数轴的栈基本操作实验………………………………17实验四循环队列实验…………………………………………………21实验五二叉树基本操作实验…………………………………………231实验一基于数组的表实验一、实验目的1.学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。2.掌握顺序表的基本操作，实现顺序表在指定位置插入、删除运算以及查找运算。3.掌握函数的调用过程。二、实验要求1．预习C语言中结构体的定义与基本操作方法。2．对顺序表的每个基本操作用单独的函数实现。3．编写完整程序完成下面的实验内容并上机调试,运行。4．按南昌大学教务处要求整理并上交实验报告。三、实验内容：1．编写程序实现顺序表的下列基本操作：(1)初始化顺序表La。(2)在顺序表中插入元素形成表[1020304050]，并输出表。(3)删除表中第3个元素，并输出表(4)删除元素40，并输出表(5)在La中查找某元素，若找到，则返回它在La中第一次出现的位置，否则返回0。(6)打印输出La中的元素值。#includestdio.h#includestdlib.h#definemaxsize9typedefstruct{intdata[maxsize];intlength;}seqlist;/*初始化线性表*/seqlistsqinit(){seqlistL;L.length=0;returnL;2}/*插入元素*/seqlistsqinsert(seqlistl,intx){if(l.length==maxsize){printf(overflow);exit(0);}elsel.length++;l.data[l.length-1]=x;returnl;}/*输出表元素*/voidsqprint(seqlistL){inti;for(i=0;iL.length;i++)printf(%d\n,L.data[i]);}/*删除i位置上元素*/seqlistsqdelete(seqlistL,inti){intj;if(i1||iL.length){printf(notthiselementinthelist.\n);exit(0);}for(j=i;jL.length;j++)L.data[j-1]=L.data[j];L.length--;returnL;}/*删除值为x元素*/seqlistsqde(seqlistL,intx){inti=1,j;while(i=L.length&&L.data[i-1]!=x)i++;if(i=L.length){for(j=i;j=L.length-1;j++)L.data[j-1]=L.data[j];L.length--;3returnL;}else{printf(Thiselemarenotinthelist);}}/*查找元素第一次出现的位置*/intsqlocate(seqlistL,intx){inti=1;while(i=L.length&&L.data[i-1]!=x)i++;if(i=L.length)returni;elsereturn0;}/*主函数*/main(){inti,a;seqlistLa;La=sqinit();La=sqinsert(La,10);La=sqinsert(La,20);La=sqinsert(La,30);La=sqinsert(La,40);La=sqinsert(La,50);sqprint(La);printf(删除第三个元素后的表为：\n);La=sqdelete(La,3);sqprint(La);printf(\n);i=sqlocate(La,40);La=sqdelete(La,i);printf(删除元素40后的表为：\n);sqprint(La);printf(\n);printf(请输入元素:);scanf(%d,&a);i=sqlocate(La,a);printf(所在的位置是%d\n,i);4printf(最终的表为：\n);sqprint(La);}2．编写程序完成下面的操作：(1)构造两个顺序线性表La和Lb，其元素都按值非递减顺序排列。(2)实现归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减顺序排列。#includestdio.h#includestdlib.h#definemaxsize10typedefstruct{intdata[maxsize];intlength;}seqlist;seqlistsqint(){seqlistL;L.length=0;returnL;}seqlistsqinsert(seqlistL,intx){if(L.length==maxsize){printf(overflow);5exit(0);}L.length++;L.data[L.length-1]=x;returnL;}seqlistsqdelete(seqlistL,inti){intj;if(i1||iL.length){printf(notthiselementinthelist.\n);exit(0);}for(j=i;jL.length;j++)L.data[j-1]=L.data[j];L.length--;returnL;}intsqlocate(seqlistL,intx){inti=1;while(i=L.length&&L.data[i-1]!=x)i++;if(i=L.length)returni;elsereturn0;}voidsqprint(seqlistL){inti;for(i=0;iL.length;i++)printf(%d\n,L.data[i]);}main(){inti,j,t;inta0,a1,a2,a3;intb0,b1,b2,b3;seqlistLa,Lb,Lc;printf(请输入La表的四个元素：\n);scanf(%d%d%d%d,&a0,&a1,&a2,&a3);La=sqint();6La=sqinsert(La,a0);La=sqinsert(La,a1);La=sqinsert(La,a2);La=sqinsert(La,a3);for(i=0;i3;i++)for(j=i+1;j4;j++)if(La.data[i]La.data[j]){t=La.data[i];La.data[i]=La.data[j];La.data[j]=t;}printf(La表为：\n);sqprint(La);printf(请输入Lb表的四个元素：\n);scanf(%d%d%d%d,&b0,&b1,&b2,&b3);Lb=sqint();Lb=sqinsert(Lb,b0);Lb=sqinsert(Lb,b1);Lb=sqinsert(Lb,b2);Lb=sqinsert(Lb,b3);for(i=0;i3;i++)for(j=i+1;j4;j++)if(Lb.data[i]Lb.data[j]){t=Lb.data[i];Lb.data[i]=Lb.data[j];Lb.data[j]=t;}printf(Lb表为：\n);sqprint(Lb);Lc=sqint();i=0;while(La.length&&Lb.length)if(La.data[i]=Lb.data[i]){Lc=sqinsert(Lc,La.data[i]);La=sqdelete(La,i+1);}else{Lc=sqinsert(Lc,Lb.data[i]);Lb=sqdelete(Lb,i+1);}if(La.length==0)for(i=0;iLb.length;i++)Lc=sqinsert(Lc,Lb.data[i]);else7for(i=0;iLb.length;i++)Lc=sqinsert(Lc,La.data[i]);printf(Lc表为：\n);sqprint(Lc);}四、思考与提高假设两个顺序线性表La和Lb分别表示两个集合A和B，如何实现A=A∩B？#includestdio.h#includestdlib.h#definemaxsize30typedefstruct{intdata[maxsize];intlength;}seqlist;seqlistsqint(){seqlistL;L.length=0;returnL;}seqlistsqinsert(seqlistL,intx){if(L.length==maxsize){printf(overflow);exit(0);}L.length++;8L.data[L.length-1]=x;returnL;}seqlistsqdelete(seqlistL,inti){intj;if(i1||iL.length){printf(notthiselementinthelist.\n);exit(0);}for(j=i;jL.length;j++)L.data[j-1]=L.data[j];L.length--;returnL;}voidsqprint(seqlistL){inti;for(i=0;iL.length;i++)printf(%d\n,L.data[i]);}main(){inti,j,t;inta0,a1,a2,a3,a4,a5;intb1,b2,b3,b4,b5,b0;seqlistLa,Lb,Lc;printf(请输入La表的六个元素：\n);scanf(%d%d%d%d%d%d,&a0,&a1,&a2,&a3,&a4,&a5);La=sqint();La=sqinsert(La,a0);La=sqinsert(La,a1);La=sqinsert(La,a2);La=sqinsert(La,a3);La=sqinsert(La,a4);La=sqinsert(La,a5);for(i=0;i5;i++)for(j=i+1;j6;j++)if(La.data[i]La.data[j]){t=La.data[i];La.data[i]=La.data[j];La.data[j]=t;}printf(La表为：\n);sqprint(La);printf(请输入Lb表的六个元素：\n);scanf(%d%d%d%d%d%d,&b0,&b1,&b2,&b3,&b4,&b5);Lb=sqint();Lb=sqinsert(Lb,b0);Lb=sqinsert(Lb,b1);Lb=sqinsert(Lb,b2);9Lb=sqinsert(Lb,b3);Lb=sqinsert(Lb,b4);Lb=sqinsert(Lb,b5);for(i=0;i5;i++)for(j=i+1;j6;j++)if(Lb.data[i]Lb.data[j]){t=Lb.data[i];Lb.data[i]=Lb.data[j];Lb.data[j]=t;}printf(Lb表为：\n);sqprint(Lb);Lc=sqint();for(i=0;iLa.length;i++)for(j=0;jLb.length;j++)if(La.data[i]==Lb.data[j]){Lc=sqinsert(Lc,La.data[i]);La=sqdelete(La,i+1);Lb=sqdelete(Lb,j+1);i--;j--;}printf(Lc表为：\n);sqprint(Lc);}10实验二链表实验一、实验目的1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。2.掌握单链表基本操作及