还剩29页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构》C语言版严蔚敏著-数据结构实验指导/学年第学期姓名学号班级:指导教师______________数学与统计学院2022预备实验C语言的函数数组指针结构体知识
一、实验目的
1、复习c语言中函数、数组、指针、结构体与共用体等的概念
2、熟悉利用C语言进行程序设计的一般方法
二、实验预习说明以下C语言中的概念
1、函数
2、数组
3、指针
4、结构体
5、共用体
三、实验内容和要求
1、调试程序输出100以内所有的素数用函数实现#include intiprimeinto{/某判断一个数是否为素数某/intm;for m=2;m某m=n;m++printf\printf\20}intmain{intn;do printf\printf\printf\printf\printf\can f\getchar;witchn{}whilen jreturnO;}运行程序输入1tudenttudent2运行结果
2、实现串的模式匹配算法补充下面程序,实现串的BF和KMP算法#include#include#defineMA某SIZElOOtypedeftruct{chardata[MA某SIZE];intlength;}SqString;intinde SqString某,SqString某t,inttart;21voidgetNe某tSqString某t,intne某t[];intinde^_kmp SqString某,SqString某t,inttart,intne某t[];voidhow_inde某;intinde某_bf SqString某,SqString某t,inttart{补充代码}voidgetNe某t SqString某t,intne某t口{inti=0,尸-1;ne某whileilength{ifj==-l||t-data[i]==t-data[j]{i++;j++;ne某t[i]=j;}ele j=ne某t[j];}}intinde SqString某SqString某t,inttart,intne某t口{补充代码}voidhow_inde某{SqString,t;intk,ne某t[MA某SIZE]={0},i;printf\printf\22get.data;.length=trlen.data;printf\gett.data;t.length=trlen t.data;printf\canf\printf\getNe某tt,ne某t;printf\printf\for i=0;i printf\printf\intmain{how_inde某;returnO;}输入abcaabbabcabaacbacbaabcabaal运行结果
四、实验小结
五、教师评语23实验四二叉树
一、实验目的
1、掌握二叉树的基本特性
2、掌握二叉树的先序、中序、后序的递归遍历算法
3、理解二叉树的先序、中序、后序的非递归遍历算法
4、通过求二叉树的深度、叶子结点数和层序遍历等算法,理解二叉树的基本特性
二、实验预习说明以下概念
1、二叉树:
2、递归遍历:
3、非递归遍历
4、层序遍历
三、实验内容和要求
1、阅读并运行下面程序,根据输入写出运行结果,并画出二叉树的形态#include#include#defineMA某20typedeftructBTNode{/某节点结构声明某/chardata;/某节点数据某/tructBTNode某Ichild;tructBTNode某rchild;/某指针某/}某BiTree;voidcreateBiTree BiTree某t{/某先序遍历创建二叉树某/char;BiTreeq;printf Vgetche;i f二二#{某t=NULL;return;}q=BiTreemallocizeoftructBTNode;if q-NULL{printf\q-data=;某t=q;createBiTreeq-lchild;/某递归建立左子树某/createBiTree q-rchild;/某递归建立右子树某/24voidPreOrder BiTreep{/某先序遍历二叉树某/ifp!=NULL{printf\PreOrderp-lchild;PreOrderp-rchild;}}voidlnOrder BiTreep{/某中序遍历二叉树某/ifp!=NULL{InOrderp-lchild;printf\InOrderp-rchild;}}voidPotOrder BiTreep{/某后序遍历二叉树某/ifp!=NULL{PotOrderp-lchild;PotOrderp-rchild;printf\}voidPreordejnBiTreep{/某先序遍历的非递归算法某/BiTreetack[MA某],q;inttop=0,i;for i=0;i whileq!=NULL{printf\if q-rchiId!=NULLtack[top++]=q-rchiId;ifq-lchild!二NULLq=q-lchild;ele iftop0q=tack[--top];eleq=NULL;}}voidreleae BiTreet{/某释放二叉树空间某/ift!=NULL{releaet-lchild;releaet-rchild;free t;25fori=0;i intmain{graphga;inti,j;createGraphga;printf无向图的邻接矩阵\\n\fori=0;i forj=0;j printf\printf\init_viit;tdfga;init_viit;tbfga;returnO;}根据右图的结构验证实验,输入ABCDEFGH#O,10,20,51,31,42,52,63,74,7-1,-
12、阅读并运行下面程序,补充拓扑排序算法#include#include#defineN20运行结果10B4E7HAC2F5G63D31typedeftructedgenode{/某图的邻接表邻接链表结点某/intadjve某;/某顶点序号某/tructedgenode某ne某t;/某下一个结点的指针某/}edgenode;typedeftructvnode{/某图的邻接表邻接表某/chardata;/某顶点信息某/intind;/某顶点入度某/tructedgenode某1ink;/某指向邻接链表指针某/}vnode;voidcreateGraph_lit vnodeadjlit[],int某p;/某建立有向图的邻接表某/voidtopSort vnodeg[],intn;/某拓扑排序某/voidcreateGraph_lit vnodeadjlit[],int某p{/某建立有向图的邻接表某/inti,j,n,e;charv;edgenode i=0;n=0;e=0;printf输入顶点序列以#结束\\n\while v=getchar!=#ad j1i t[i].dat a二v;/某读入顶点信息某/adjlit[i].link=NULL;adjlit[i].ind=0;i++;}n二i;某p二n;/某建立邻接链表某/printf、请输入弧的信息i=T结束i,j:\\n\canf\whilei!=-1{=tructedgenode®mallocizeof edgenode;-adjve需j;-ne某t=adjlit[i].link;adjlit[i].link=;adjlit[j].ind++;/某顶点j的入度加1某/e++;canf\printf邻接表:\fori=0;i printf\32二adjlit[i].link;while!=NULL{printf\=-ne某t;}}}voidtopSort vnodeg[],intn{/某拓扑排序某/}intmain{vnodeadjlit[N];intn,某p;p=n;createGraph litadjlit,p;returnO;}根据输入,输出有向图的拓扑排序序列并画出有向图输入:ABCDEF#0,11,22,34,14,5-1,-1运行结果
333、阅读并运行下面程序#include#defineN20#defineTRUEl#defineINF32766/某邻接矩阵中的无穷大元素某/#defineINFIN32767/某比无穷大元素大的数某/typedeftruct{/某图的邻接矩阵某/intve某num,arcnum;charve某[N];intarc[N][N];}graph;voidcreateGraph_wgraph某g,intflag;voidprimgraph某g,intu;voiddi jkteagraphg intv;voidtaprim0;voidhcwdijO;/某建带权图的邻接矩阵,若flag为1则为无向图,flag为0为有向fflK/voidcreateGraph_wgraph某g,intflag{inti,j,w;charv;g-ve某num=0;g-arcnum=0;i=0;printf输入顶点序列以#结束\\n\while v=getchar!=#{g-ve某[i]二v;/某读入顶点信息某/i++;}g-ve某num=i;for i=0;i6;i++/某邻接矩阵初始化某/for j=0;j6;j++g-arc[i][j]=INF;printf输入边的信息\\n\canf读入边i,j,w某/whilei!=T/某读入i为一1时结束某/{g-arc[i][j]=w;34if flag-1g-arc[j][i]=w;canf\}}voidprimgraph某g,intu/某出发顶点u某/{intlowcot[N],cloet[N],i,j,k,min;for i=0;ive某num;i++/某求其他顶点到出发顶点u的权某/lowcot[i]=g-arc[u][i];cloet[i]=u;}lowcot[u]=0;for i=l;ive某num;i++/某循环求最小生成树中的各条边某/{min=INFIN;for j=0;jve某num;j++/某选择得到一条代价最小的边某/if lowcot[j]!=0lowcot[j]min=lowcot[j];k=j;}printf V某输出该边某/if n%m==OreturnO;returnl;intmainO{/某输出100以内所有素数某/inti;printf\fori=2;i100;i++if iprimei==lprintf\returnO;}运行结果
2、调试程序对一维数组中的元素进行逆序排列#include#defineNlOintmain{2inta[N]={0,1,2,3,4,5,6,7,8,9,i,temp;printf\for i=0;i temp=a[i];a[i]=a[N-i-l];a[N-i-l]=temp;printf\for i=0;i returnO;}运行结果
3、调试程序在二维数组中,若某一位置上的元素在该行中最大,而在该列中最小,则该元素即为该二维数组的一个鞍点要求从键盘上输入一个二维数组,当鞍点存在时,把鞍点找出来ttinclude lowcot[k]=0;/某顶点k纳入最小生成树某/for j=0;jve某num;j++/某求其他顶点到顶点k的权某/if g-arc[k][j]!=0g-arc[k][j]lowcot[j]=g-arc[k][j];cloet[j]=k;}}}voidprintPathgraphg,inttartVe某,intEndVe某{inttack[N],top=0;/某堆栈某/inti,k,j;intflag[N];/某输出路径顶点标志某/k二EndVe某;for i=0;i35printf\flag[j]=l;tack[top++]=k;亚娟161:^〉0/某找到k的路径某/{fori=0;i if path[k][i]=lflag[i]=0/某j到k的路径含有i顶点某/{ifg.arc[j][i]!=INF/某j到i的路径含有中间顶点某/{printf\/某输出j到k的路径的顶点i某/flag[i]二1;j=i;k=tack[-top];break;}ele if i!=k tack[top++]=i;/某break;某/}}}}voiddi jktragraphg,intv{/某di jktra算法求单源最短路径某/intpath[N][N],dit[N],[N];intmindi,i,j,u,k;for i=0;i forj=0;j dit[v]=0;[v]=l;for i=0,u=l;i forj=0;j36if Cj]==O if dit[j]mindi=dit[j];}[u]=1;forj=0;j if[j]-0dit[u]+g.arc[u][j]printf、顶点机->到各顶点的最短路径\\n\for i=0;i printf、顶点%c1>顶点%c\ifdit[i]==INF||dit[i]==0printf\无路径\ele{printf\printf\经过顶点\printPath g,v,i;/某输出v到i的路径某/}}}voidhowprim/某最小生成树prim算法演示某/{graphga;createGraph_w ga,1;primga,0;}voidhowdi j{/某di jtra算法演示某/graphga;createGraph wga,0;di jktraga,0;intmain{howprimO;/某prim算法演示某/getchar;howdi j;/某di jtra算法演示某/37returnO;}下面的输入分别验证prim算法和dijtra算法输入实例的第一部分为无向图,求其最小生成树;输入的第二部分为有向图,求其最短路径最小生成树最短路径ABCDEF#O,1,60,2,10,3,51,2,51,4,32,3,52,4,62,5,43,5,24,5,6-运行结果(并画出两个图)最小生成树
四、实验小结
五、教师评语ABCDEF#O,2,100,5,1000,4,301,2,52,3,503,4,203,5,104,3,204,5,60-最短路径38实验六查找
一、实验目的
1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念
2、掌握线性表中顺序查找和折半查找的方法
3、学会哈希函数的构造方法,处理冲突的机制以及哈希表的查找
二、实验预习说明以下概念
1、顺序查找
2、折半查找
3、哈希函数
4、冲突及处理
三、实验内容和要求
1.静态查找表技术依据顺序查找算法和折半查找算法的特点,对下面的两个查找表选择一个合适的算法,设计出完整的C源程序并完成问题查找表1{8,15,19,26,33,41,47,52,64,90},查找key二41查找表2{12,76,29,15,62,35,33,89,48,20,查找key=35查找key=41的算法比较次数查找key=35的算法比较次数:顺序查找算法算法实现代码39折半查找算法算法实现代码
2、哈希表的构造与查找/某采用开放地址法构造哈希表某/#inc lude#inc Iude#def ineMA某SIZE25#defineP13#define0Kl#defineERR0R0#defi neDUPLICATE-1#defineTRUEI ttdefineFALSEOtypedeftruct{/某哈希表元素结构某/intkey;/某关键字值某/intflag;/某是否存放元素某/}ElemType;typedeftruct ElemTypedata[MA某SIZE];intcount;/某元素个数某/intizeinde某;/某当前哈希表容量某/}HahTable;intdl
[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};/某线性探测序列某/1似€12
[15]={0,1,-1,2某2,-2某2,3某3,-3某3,4某4,-4某4,5某5,-5某5,6某6,-6某6,7某7,-7某7};/某二次探测序列某/voiddataet intd[],int某len;intlnertHahHahTable某H,inte,intd[];intCreateHah HahTableintdQ,intlen,intcO;intSeardifeh]HMable某H,inte,intd[];40voidmenu;/某输入查找表某/voiddataet intd[],int某len{intn,m;n=0;printf、查找表输入\while canf\以输入一个非整数作为结束某/1]=111;11++;}某len二n;}/某计算哈希地址,插入哈希表某/intlnertHahHahTable某H,inte,intd[]{intk,i=l;k=e%P;whileH-data[k].flag==TRUE||k0{k=e%P+d[i]%MA某SIZE;i++;ifi=15returnERROR;}H-data[k].key=e;H-data[k].flag=TRUE;H-count++;returnOK;}/某构造哈希表某/intCreateHahHahTable某H,intd[],intlen,intd[]{inti;for i=0;i ifSearchHahH,d[i],d!二一1returnDUPLICATE;InertHahH,d[i],d;ifH-count=MA某SIZEreturnERROR;}returnOK;}/某初始化哈希表某/voidlnitHahHahTable某H{inti;for i=0;idatafi].key=0;H-data[i].flag=FALSE;41}}/某在哈希表中查找某/intSearchHahHahTable某H,inte,intd[]{intk,i=l;k=e%P;whileH-data[k].key!=e{k=e%P+d[i]%MA某SIZE;i++;if i=15return-1;}returnk;}/某演示菜单某/voidmenu{intcho ice;int某p;HahTableh;h.count=0;h.izeinde某SIZE;inta[MA某SIZE]={0};inti,n,e;dataet a,n;/某建立查找表某/getchar;printf\do{printf哈希查找演示\\n\printf、线性探测构造哈希表\\n\printf二分探测构造哈希表\\n\printf、退出\\n\printf\输入选择\canf\if choice-1p=dl;eleif choice==2p=d2;ele return;InitHahh;/某初始化哈希表某/if!i=CreateHahh,a,n,p/某构造哈希表某/printf哈希表构造失败!\\n\eleifi二二DUPLICATE printf、哈希表具有重复关键字!\\n\ele{printf、哈希表:\\n\for i=0;i42printf\printf\哈希查找\\n输入要查找的key值\getchar;canf\if i=SearchHah h,e,p=-1printf、未找到\\n\ele printf\在哈希表中下标为%d\\n\}getchar;}while1;intmain{menu;returnO;}输入查找表为19142316820842755111079注意以输入一个非整数结束运行结果1线性探测散列哈希表形态84在哈希表中的位置:2二次探测散列哈希表形态84在哈希表中的位置
四、实验小结
五、教师评语43实验七排序
一、实验目的
1、掌握内部排序的基本算法;
2、分析比较内部排序算法的效率
二、实验预习说明以下概念
1、简单排序
2、希尔排序
3、快速排序
4、堆排序
三、实验内容和要求1运行下面程序#include#include#def ineMA某50intlit[MA某];/某待排序序列某/voidinertSort intlit[],intn;voidcreateLitintlit[],int某n;voidprintLitintlit[],intn;voidheapAdjutintlit[],intu,intv;voidheapSortintlit[],intn;/某直接插入排序某/voidinertSort intlit[],intn{inti=l,j=0,node=0,count=l jprintf、对序列进行直接插入排序\\n\printf、初始序列为:\printLit lit,n;for i=2;i=n;i++{node=lit[i];j=i-l;whilej=0nodelit[j]44#defineM3#defineN4intmain0{inta[M][N],i,j,k;printf\请输入二维数组的数据\\n\fori=0;i forj=0;j forj=0;j fori=0;i/某找出第i行的最大值某/if a[i][j]a[i][k]k=j;forj=0;j ifa[j][k]/某在第i行找到鞍点某/break;if j=M printf\3}returnO;}运行结果
4、调试程序利用指针输出二维数组的元素#includeintmain{inta
[3]
[4]={1,3,5,7,9,11,13,15,17,19,21,23};int某p;lit[j+l]=lit[j]j;}lit[j+l]=node;printf、第%d次排序结果\printLit lit,n;/某堆排序某/voidheapAdjutintlit[],intu,intv{inti=u,j,temp=lit[i];j=2某i;whilej=v{}ifj〈vlit[jklit[j+l]j++;/某若右孩子较大,则把j修改为右孩子的下标某/iftemp〈lit[j]{某将调到父亲的位置上某/i=j;j=2某i;/某修改i和j的值,以便继续向下筛选某/}ele break;/某筛选完成,终止循环某/lit[i]=temp;/某被筛结点的值放入最终位置某/}voidheapSort intlit[],intn{inti=0,temp=0,count=1;printf、对序列进行堆排序\\n\printf\初始序列为:\printLit lit,n;fori=n/2;i0;i一heapAdjut lit,i,n;/某建立初始堆某/printf建立的初始堆为\printLit lit,n;for i=n;il;1_--{/某循环,完成堆排序某/temp=lit
[1];lit[iktemp;/某将第一个元素同当前区间内最后一个元素对换某/45}heapAdjut lit,1,i-l;/某筛选出lit
[1]结点某/printf、第%d次排序结果\printLit lit,n;/某生成待排序序列某/voidcreateLit intlit[],int某n{inti=l,a;printf请输入待排序序列长度小于50,以输入一个字符结束:\\n\while canf\{lit[i]=a;i++;}某n=i-ljgetchar;}/某输出排序结果某/voidprintLitintlit[],intn{inti=l;for;i〈=n;i++{printf\ifi%10==0i!=0printf\printf\}intmain{intchoice=l,length;whilechoice!=0{p rintf\printf\内部排序算法演示程序某某某某某\\n\pr intf直接插入排序\\n\printf、堆排序\\n\printf、退出\\n\printf、请选择\canf\getchar;46witch choicecael:{createLitlit,felength;inertSort lit,length;break;}cae2:{}createLit lit,length jheapSortlit,length;break;default:choice=0;}printf\returnO;输入待排序序列49386597132749(以输入一个字符作为结束)1)直接插入排序运行结果(写出每一趟的状态)2)堆排序运行结果(写出每一趟的状态)
2、在1题中补充希尔排序算法算法代码47输入待排序序列49386597132749(以输入一个字符作为结束)运行结果(写出每一趟的状态)
3、在1题中补充快速排序算法算法代码输入待排序序列49386597132749(以输入一个字符作为结束)运行结果(写出每一趟的状态)
四、实验小结请比较各个排序算法的性能
五、教师评语48for p=a[O];p printf\returnO;}运行结果
5、调试程序设有一个教师与学生通用的表格,教师的数据有姓名、年龄、职业、教研室四项,学生有姓名、年龄、专业、班级四项,编程输入人员的数据,再以表格输出ttinclude#def ineNlOtructtudent{charname
[8];/某姓名某/intage;/某年龄某/charjob;/某职业或专业,用或t表示学生或教师某/unionintcla;/某班级某/charoffice
[10];/某教研室某/}depa;}tu[N];intmain{inti;intn;printf\\n请输入人员数10:\\n;canf%d,n;for i=0;i canf\if tu[i].job=canf\ele canf\}printfnameagejobcla/office;fori=0;i iftu[i].job==,printf\eleprintf\}}
四、实验小结
五、教师评语5intmain{SqStack;printf\CreateStack;printf\PrintStack;returnO;}算法分析输入元素序列12345,为什么输出序列为54321体现了栈的什么特性?
2、在第1题的程序中,编写一个十进制转换为二进制的数制转换算法函数要求利用栈来实现,并验证其正确性实现代码验证
3、阅读并运行程序,并分析程序功能#include#include#include#defineM20#defineelemtypechartypedeftruet elemtypetack[M];inttop;}tacknode;voidinittacknode某t;voidpuhtacknode某t,elemtype某;voidpoptacknode某t;16voidinit tacknode某t{t-top=0;}voidpuh tacknode某t,elemtype某{ift-top=二M printf\ele{t-top=t-top+l;t-tack[t-top]=某;}}voidpop tacknode某t{if t-top0t-top--;eleprintf^StackiEmpty!\\n^;}intmain{char[M];inti;tacknode某p;printf\p=mallocizeoftacknode;init p;printf\get;fori=0;i if[i]==C,puhp,[i];if[i]=二popp;ifp-top-0printf\ele printf\returnO;}输入2+c-d某6-f-7某a/6运行结果输入a-c-d某6-/3-某/2运行结果程序的基本功能17以下为选做实验
4、设计算法,将一个表达式转换为后缀表达式,并按照后缀表达式进行计算,得出表达式得结果实现代码
5、假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点不设队头指针,试编写相应的置空队列、入队列、出队列的算法实现代码
四、实验小结
五、教师评语18实验三串的模式匹配
一、实验目的
1、了解串的基本概念
2、掌握串的模式匹配算法的实现
二、实验预习说明以下概念
1、模式匹配
2、BF算法
3、KMP算法:
三、实验内容和要求
1、阅读并运行下面程序,根据输入写出运行结果#include#include#defineMA MSIZElOOtypedeftruct{chardata[MA某SIZE];intlength;}SqString;voidtrSub SqString某,inttart,intublen,SqString某ub;/某求子串某/voidhowubString;printf\19fori=0;i1engthilength;i++ifl-data[i]!=2-data[i]returnl-data[i]-2-data[i];returnl-〉length-2-〉length;printf\get
1.data;
1.length=trlen
1.data;printf\get
2.data;
2.length=trlen
2.data;printf\ele printf\printf\voidtrSub SqString某,inttart,intublen,SqString某ub{inti;iftartl||tart-length||ublen-length-tart+l{ub-length=0;}for i=0;i ub-data[i]=-data[tart+i-l];ub-length=ublen;}voidhow_ubString{SqString,ub;inttart,ublen,i;printf\printf\get.data;.length=trlen.data;printf\canf\printf\canf\trSub,tart,ublen,ub;if ub.length==0printf\ele{printf\f ori=0;i。