《数据结构》(C语言)实验报告

1《数据结构》实验报告姓名：刘高学号：031041113成绩：＿＿＿＿＿2目录实验一，线性表的应用……………………………………3实验二，栈和队列的应用…………………………………8实验三，数组的应用………………………………………13实验四，树和二叉树的应用………………………………19实验五，图的应用…………………………………………24实验六，查找表的应用……………………………………32实验七，排序算法的应用…………………………………443实验一线性表的应用【实验目的】1.熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3.掌握线性表的动态分配顺序存储结构的定义和基本实现；4.通过对本章实验帮助学生加深对C语言的使用（特别是函数参数调用、指针类型的应用和链表的建立等各种基本操作）。【实验内容】约瑟夫问题的实现：n只猴子要选猴王，所有猴子按1,2，…，n编号围坐一圈，从第1只开始按1，2，…，m报数，凡报到m号的猴子退出圈外，如此循环报数，直到圈内省剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】1.要求用顺序表和链表分别实现约瑟夫问题；2.独立完成，严禁抄袭；3.上交的实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。4实验结果：一，源程序：#includestdio.h#includestdlib.h#defineMaxsize80structSeqList{intdata[Maxsize];intlen;};typedefstructSeqListSeqList;voidInitList(SeqList*L){L=(SeqList*)malloc(sizeof(SeqList));L-len=0;}voidMadeList(SeqList*L){inti;5intpeople;printf(请输入参选的总数:\n);scanf(%d,&people);for(i=0;ipeople;i++){L-data[i]=i+1;printf(%d,L-data[i]);}printf(\n);L-len=people;}voidWentList(SeqList*L){intm,i,j;intk=0;printf(请输入出列数：\n);scanf(%d,&m);for(i=L-len;i0;i--)6{k=(k+m-1)%i;printf(%d,L-data[k]);for(j=k;ji-1;j++){L-data[j]=L-data[j+1];}L-len=L-len-1;}printf(\n);}voidmain(){SeqList*L;InitList(L);MadeList(L);WentList(L);}7二，运行结果及截屏视图：8实验二栈和列队的应用【实验目的】1.熟练掌握栈和列队的结构，以及这两种数据结构的特点；2.能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空时的判断条件和描述方法；3.熟练掌握链队列和循环列表的基本运算，特别注意队列满和队列空时的判断条件和描述方法。【实验内容】9表达式求值的实现：输入一个包含“+“、”-“、”*“、”/“、正整数和圆括号的合法表达式，用算法优先法计算该表达式的结果。【实验要求】1.要求用栈实现表达式求值问题；2.独立完成，严禁抄袭；3.上交的实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一，源程序:#defineDATATYPE1int#defineMAXSIZE100typedefstruct{DATATYPE1data[MAXSIZE];inttop;}SEQSTACK;#includestdio.hvoidinitstack(SEQSTACK*s){s-top=0;}intpush(SEQSTACK*s,DATATYPE1x){if(s-top==MAXSIZE-1){printf(栈满\n);return0;}else{s-top++;(s-data)[s-top]=x;return1;}}DATATYPE1pop(SEQSTACK*s){DATATYPE1x;10if(s-top==0){printf(栈空\n);x=0;}else{x=(s-data)[s-top];s-top--;}returnx;}DATATYPE1gettop(SEQSTACK*s){DATATYPE1x;if(s-top==0){printf(栈空\n);x=0;}elsex=(s-data)[s-top];returnx;}check(SEQSTACK*s){intbool;charch;push(s,'#');printf(请输入一串括号，回车键结束:);ch=getchar();bool=1;while(ch!='\n'&&bool){if(ch=='(')push(s,ch);if(ch==')')if(gettop(s)=='#')bool=0;11elsepop(s);ch=getchar();}if(gettop(s)!='#')bool=0;if(bool)printf(\n括号配对正确\n);elseprintf(\n括号配对错误\n);}main(){SEQSTACKst,*s;s=&st;initstack(s);check(s);}二，实验结果及截屏视图：121314实验三数组的应用【实验目的】1.掌握数组的两种存储表示方法；2.掌握对特殊矩阵进行压缩存储时的下标变换公式；3.掌握稀疏矩阵的两种压缩存储方法的特点和适用范围。【实验内容】稀疏矩阵转置的实现:用三元组顺序表做存储结构，实现稀疏矩阵的转置。【实验要求】151.已知某一稀疏矩阵的三元顺序表，由其直接得到其转置矩阵的三元顺序表；2.独立完成，严禁抄袭；3.上交的实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一，源程序；#includestdio.h#defineMAX80structtuple3tp{inti,j,v;};structsparmattp{intm,n,u;structtuple3tpdata[MAX];};structsparmattpa,b;voidcrt_sparmat(){inti;printf(输入稀疏矩阵行值，列值，最大非零元的个数：);scanf(%d%d%d,&a.data[i].i,&a.data[i].j,&a.data[i].v);for(i=1;i=a.u;i)printf(输入行坐标，列坐标，非零元);scanf(%d%d%d,&a.data[i].i,&a.data[i].j,&a.data[i].v);}16voidtrans_sparmat(){intcol,p,q;b.m=a.n;b.n=a.m;b.u=a.u;if(b.u!=0){q=1;for(col=1;col=a.n;col++)for(p=1;p=a.u;p++)if(a.data[p].j==col){b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;q++;}}}out(structsparmattpx){inti,j,k,flag;for(i=1;i=x.m;i++)for(j=1;j=x.n;j++)flag=0;for(k=1;k=x.u;k++){if(((x.data[k].i==i)&&((x.data[k].j)==j))){flag=1;17printf(%5d,x.data[k].v);}}if(flag=0)printf(0);}main(){printf(稀疏矩阵的建立与专置\n);crt_sparmat();trans_sparmat();printf(\n);out(a);printf(\n);out(b);}二，实验结果及截屏视图：181920实验四树和二叉树的应用【实验目的】1.熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；2.重点掌握二叉树的生成、遍历及求深度等算法；3.掌握哈夫曼树的含义及其应用；214.掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。【实验内容】二叉树采用二叉链表作存储结构，试编写程序实现二叉树的如下基本操作：1.按先序序列构造一棵二叉树T；2.对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列；3.求二叉树的深度/结点数目/叶结点数目。【实验要求】1.上交实验报告。2.独立完成，严禁抄袭。3.实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一，源程序#includestdio.h#includestdlib.h#definebitreptrstructtypel#defineNULL0#definelensizeof(bitreptr)bitreptr*bt;intf,g;bitreptr{chardata;22bitreptr*lchild,*rchild;};preorder(bitreptr*bt){if(g==1)printf(先序遍历为:\n);g=g+1;if(bt){printf(%6c,bt-data);preorder(bt-lchild);preorder(bt-rchild);}elseif(g==2)printf(树空\n);}bitreptr*crt_bt(){bitreptr*bt;charch;if(f==1)printf(请输入根节点，以#结束\n);elseprintf(输入节点，以#结束\n);scanf(\n%c,&ch);f=f+1;if(ch=='#')bt=NULL;else{bt=(bitreptr*)malloc(len);bt-data=ch;printf(%c,bt-data);23bt-rchild=crt_bt();printf(%c,bt-data);bt-rchild=crt_bt();}return(bt);}main(){f=1;g=1;bt=crt_bt();preorder(bt);}二，实验结果及截屏图示：242526实验五图的应用【实验目的】1.熟练掌握图的邻接矩阵和邻接表的存储方式；2.实现图的一些基本运算，特别是深度遍历和广度遍历；3.掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等。【实验内容】271.由给定的顶点和边的信息构造图的邻接矩阵存储；2.对该图进行深度优先搜索，输出搜索得到的结点序列；3.以邻接表作存储结构，用克鲁斯卡尔算法构造最小生成树。【实验要求】1.上交实验报告。2.独立完成，严禁抄袭。3.实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一，源程序：图一：#includestdio.h#defineINF9999#defineMAXVEX100typedefcharvertexType;typedeffloatadjtype;typedefstruct{vertexTypevexs[MAXVEX];adjtypearcs[MAXVEX][MAXVEX];intn,e;}mGraph;voidcreateAdjMatrix(mGraph*G){inti,j,k;floatw;scanf(%d%d,&G-n,&G-e);for(k=0;kG-n;k++)28scanf(%c,&G-vexs[k])