《数据结构》(C语言版)严蔚敏著-数据结构实验指导.docx

《《数据结构》(C语言版)严蔚敏著-数据结构实验指导.docx》由会员分享，可在线阅读，更多相关《《数据结构》(C语言版)严蔚敏著-数据结构实验指导.docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构(C语言版)严蔚敏著-数据结构实验指导/学年第学期姓名：学号：班级:指导教师：数学与统计学院2022预备实验C语言的函数数组指针结构体知识一、实验目的1、复习c语言中函数、数组、指针、结构体与共用体等的概念。2、 熟悉利用C语言进行程序设计的一般方法。二、实验预习说明以下C语言中的概念1、函数：2、数组：3、指针：4、结构体5、共用体三、实验内容和要求1、调试程序：输出100以内所有的素数(用函数实现)。#includeintiprime (into) /某判断一个数是否为素数某/intm; for (m=2 ;m某 mdatai=t-dataj) i+;j+;ne 某ti=j;ele

2、j=ne 某tj;intinde (SqString 某 SqString 某t, inttart, intne 某t口)补充代码voidhow_inde 某()SqString, t;intk,ne 某tMA 某SIZE=0, i;printf (printf(22get (. data);.length=trlen(. data);printf(get(t. data);t. length=trlen (t. data);printf (canf(printf(getNe 某t(&t,ne 某t) ;printf(printf(for (i=0;iprintf (printf()intma

3、in () how_inde 某();returnO;输入：abcaabbabcabaacbacbaabcabaal运行结果：四、实验小结五、教师评语23实验四二叉树一、实验目的1、掌握二叉树的基本特性2、掌握二叉树的先序、中序、后序的递归遍历算法3、理解二叉树 的先序、中序、后序的非递归遍历算法4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉 树的基本特性二、实验预习说明以下概念1、二叉树:2、递归遍历: 3、非递归遍历：4、层序遍历：三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的 形态。#include#include#defineMA 某20t

4、ypedeftructBTNode /某节点结构声明某/chardata;/某节点数据某/tructBTNode 某Ichild;tructBTNode 某rchild; /某指针某/某BiTree;voidcreateBiTree (BiTree 某t) /某先序遍历创立二叉树某/char;BiTreeq;printf (Vgetche ();i f (二二#) 某 t=NULL; return;q=(BiTree)malloc(izeof(tructBTNode);if (q-NULL) printf (q-data=;某 t=q;createBiTree(&q-lchild) ;/某递归

5、建立左子树某/createBiTree (&q-rchild) ;/某递归建立右子树某/24voidPreOrder (BiTreep) /某先序遍历二叉树某/if(p!=NULL) printf(PreOrder(p-lchild);PreOrder(p-rchild) ; voidlnOrder (BiTreep) /某中序遍历二叉树某/if(p!=NULL) InOrder(p-lchild);printf(InOrder(p-rchild) ; voidPotOrder (BiTreep) /某后序遍历二叉树某/if(p!=NULL) PotOrder(p-lchild);PotOrd

6、er(p-rchild);printf()voidPreordejn(BiTreep) /某先序遍历的非递归算法某 /BiTreetackMA 某,q;inttop=0, i;for (i=0;iwhile(q!=NULL)printf (if (q-rchiId!=NULL)tacktop+=q-rchiId;if(q- lchild!二NULL)q=q-lchild;eleif(top0)q=tack-top;eleq=NULL;voidreleae (BiTreet) /某释放二叉树空间某/if(t!=NULL) releae(t-lchild);releae(t- rchild);fr

7、ee (t);25for(i=0;i intmain () graphga;inti, j;createGraph(&ga);printf(无向图的邻接矩阵：nfor(i=0;ifor(j=0; jprintf (printf()init_viit();tdf(&ga);init_viit();tbf(&ga);returnO;根据右图的结构验证实验，输入：ABCDEFGH#O, 10, 20, 51,31,42, 52, 63, 74, 7-1,-12、阅读并运行下面程序，补充拓扑排序算法。#include#include#defineN20运行结果：10B4E7HAC2F5G63D31ty

8、pedeftructedgenode /某图的邻接表：邻接链表结点某/intadjve 某;/某顶点序号某/tructedgenode某ne某t;/某下一个结点的指针某/ edgenode;typedeftructvnode/某图的邻接表：邻接表某/chardata;/某顶点信 息某/intind;/某顶点入度某/tructedgenode某1 ink; /某指向邻接链表指针某/ vnode;voidcreateGraph_lit (vnodeadjlit , int 某p) ； /某建立有向图的 邻接表某/voidtopSort (vnodeg, intn) ； /某拓扑排序某/voidcr

9、eateGraph_lit (vnodeadjlit , int 某p) /某建立有向图的邻 接表某/inti, j, n, e;charv;edgenode i=0;n=0;e=0;printf (输入顶点序列(以#结束)：nwhile (v=getchar () !=#)(ad j 1 i t i . dat a二v; /某读入顶点信息某/adjliti. link=NULL;adjliti. ind=0;i+;n二i ;某 p二n;/某建立邻接链表某/printf (、请输入弧的信息(i=T 结束)：i, j:ncanf ( while(i!=-1) =(tructedgenode ma

10、lloc(izeof (edgenode) ;-adjve 需j;-ne 某 t=adjliti. link;adjliti. link=;adjlitj. ind+;/某顶点j的入度加1某/e+;canf()printf (邻接表:for(i=0;iprintf(32二adjliti. link;while(!=NULL) printf(=-ne 某t;voidtopSort (vnodeg, intn) /某拓扑排序某/intmain () vnodeadjlitN;intn, 某 p;p=&n;createGraph lit(adjlit, p);returnO;根据输入，输出有向图的拓

11、扑排序序列。并画出有向图。输入:ABCDEF#0, 11,22, 34,14, 5-1,-1运行结果：333、阅读并运行下面程序。#include#defineN20#defineTRUEl#defineINF32766/某邻接矩阵中的无穷大元素某/#defineINFIN32767/某比无穷大元素大的数某/typedeftruct /某图的邻接矩阵某/intve 某num, arcnum; charve 某 N;intarcNN;graph;voidcreateGraph_w(graph 某g, intflag);voidprim(graph 某 g, intu); voiddi jktea

12、 (graphg intv); voidtaprim 0 ;voidhcwdijO ;/某建带权图的邻接矩阵，假设flag为1那么为无向图，flag为0为有向 fflK/voidcreateGraph_w(graph 某g, intflag) inti, j, w;charv;g-ve 某num=0;g-arcnum=0;i=0;printf (输入顶点序列(以#结束)： nwhile (v=getchar ()!=#)g-ve某i二v; /某读入顶点信息某/i+;g-ve 某num=i;for (i=0 ;i6; i+) / 某邻接矩阵初始化某/for (j=0; jarci j=INF;p

13、rintf(输入边的信息：ncanf (读入边(i, j, w)某/while(i!=T)/某读入i为一1时结束某/ g-arci j=w;34if (f lag-1)g-arcj i=w;canf (voidprim(graph 某g, intu)/某出发顶点u 某/ intlowcotN, cloetN, i, j, k, min;for (i=0; ive某num; i+)/某求其他顶点到出发顶点u的权某/( lowcot i=g-arcu i ; cloet i=u;lowcotu=0;for (i=l; ive某num; i+)/某循环求最小生成树中的各条边某/min=INFIN;f

14、or (j=0; jve某num; j+)/某选择得到一条代价最小的边某/if (lowcot j !=0&lowcot jmin=lowcotj;k=j; printf (V某输出该边某/if (n%m=O)returnO;returnl;intmainO /某输出100以内所有素数某/inti;printf(for(i=2;iarckj!=0&g-arckjlowcotj=g-arckj;cloetj=k;voidprintPath(graphg, inttartVe 某,intEndVe某) inttackN, top=0;/ 某 堆栈某 /inti, k, j;intflagN ;/某

15、输出路径顶点标志某/k二EndVe某；for (i=0; i35printf(flagj=l;tacktop+=k;亚娟16(1:(0)/某找)到k的路径某/ for(i=0;iif (pathk i=l&flagi=0)/某 j 到k 的路径含有i 顶点某/ if(g.arcji!=INF)/某j到i的路径含有中间顶点某/ printf (/某输出j到k的路径的顶点i某/flagi二1; j=i ;k=tack-top;break;eleif (i !=k) tacktop+=i;/某 break;某/voiddi jktra(graphg, intv) /某di jktra算法求单源最短路

16、径某 /intpathNN, ditN, N;intmindi, i, j, u, k;for (i=0;ifor(j=0; jditv=0; v=l;for (i=0,u=l;ifor(j=0;j36if (Cj=O)if (ditjmindi=ditj;u=1;for(j=0;jif (j-0)&dit u +g. arc u jprintf (、顶点机-到各顶点的最短路径nfor (i=0; iprintf (、顶点%c1顶点c： if (diti=INF| | diti=0)printf ( 无路径ele printf (printf (经过顶点：printPath (g, v, i)

17、 ;/某输出v到i的路径某/voidhowprim() /某最小生成树prim算法演示某/ graphga;createGraph_w (&ga, 1) ; prim(&ga, 0) ;voidhowdi j () /某 di jtra 算法演示某/graphga;createGraph w (&ga, 0) ; di jktra(ga, 0) ;)intmain () howprimO ;/某 prim 算法演示某/getchar ();howdi j () ;/某di jtra算法演示某/37returnO;下面的输入分别验证prim算法和dijtra算法。输入实例的第一局部 为无向图，求

18、其最小生成树；输入的第二局部为有向图，求其最短路径。最小生成 树最短路径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、学会哈希函数的构造方法，处理冲

19、突的机制以及哈希表的查找。二、实验预习说明以下概念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、哈

20、希表的构造与查找/某采用开放地址法构造哈希表某/# inc lude# inc I ude#def ineMA某 SIZE25#defineP13#define0Kl#defineERR0R0#defi neDUPLI CATE-1#defineTRUEIttdefineFALSEOtypedeftruct /某哈希表元素结构某/intkey;/某关键字值某/intflag; /某是否存放元素某/ ElemType;typedeftruct( ElemTypedataMA 某SIZE;intcount;/某元素个数某/intizeinde某;/某当前哈希表容量某/HahTable;intdl1

21、5 = 0, 1,2, 3,4, 5,6, 7, 8, 9, 10, 11, 12, 13, 14 ;/某线性探测序 列某/1似1215=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);intlnertHah(HahTable 某H, inte, intd);intCreateHah (HahTable intdQ, intlen, intcO ;intSeardifeh(HMable 某H, inte, i

22、ntd);40voidmenu();/某输入查找表某/voiddataet (intd, int 某len)intn, m;n=0;printf(、查找表输入：while (canf (以输入一个非整数作为结束某/(1=111；11+;某len二n;/某计算哈希地址，插入哈希表某/intlnertHah(HahTable 某H, inte, intd)intk, i=l;k=e%P;while(H-datak. flag=TRUE|k=15)returnERROR;H-datak. key=e;H-datak. flag=TRUE;H-count+;returnOK;/某构造哈希表某/intC

23、reateHah(HahTable 某H, intd,intlen, intd)inti;for (i=0;iif (SearchHah(H, di, d)!二一1)returnDUPLICATE;InertHah(H, di, d);if(H-count=MA 某 SIZE)returnERROR;returnOK;/某初始化哈希表某/voidlnitHah(HahTable 某H)inti;for (i=0;idatafi. key=0;H-datai. flag=FALSE;41/某在哈希表中查找某/intSearchHah(HahTable 某H, inte, intd)intk, i

24、=l;k=e%P;while(H-datak. key!=e)k=(e%P+di)%MA 某SIZE;i+;if (i=15)return-1;returnk;/某演示菜单某/voidmenu() intchoice;int 某p;HahTableh;h.count=0;h. izeinde某SIZE;intaMA 某SIZE=0;inti, n, e;dataet (a, &n) ; /某建立查找表某/getchar ();printf (do printf (哈希查找演示 nprintf (、线性探测构造哈希表 nprintf (二分探测构造哈希表nprintf (、退出nprintf (

25、输入选 择：canf (if (choice-1) p=dl;eleif (choice=2)p=d2;elereturn;InitHah(&h) ;/某初始化哈希表某/if (! (i=CreateHah(&h, a, n, p)/某构造哈希表某/printf (哈希表构 造失败！ neleif(i二二DUPLICATE)printf (、哈希表具有重复关键字！nele printf (、哈希表:nfor (i=0; i42printf (printf (哈希查找n输入要查找的key值：getchar ();canf(if (i=SearchHah (&h, e, p) =-1) print

26、f (、未找到neleprintf (在哈希表中下标为%dngetchar() ;while(1) ;)intmain () menu () ;returnO;输入查找表为：(注意以输入一个非整数结束)。运行结果：1)线性探测散列：哈希表形态：84在哈希表中的位置:2)二次探测散列：哈希表形态：84在哈希表中的位置：四、实验小结五、教师评语43实验七排序一、实验目的1、掌握内部排序的基本算法； 2、分析比拟内部排序算法的效率。二、实验预习说明以下概念1、简单排序：2、希尔排序：3、快速排序：4、堆排序：三、实验内容和要求1 运行下面程序：#include#include#def ineMA 某

27、 50intlitMA某;/某待排序序列某/voidinertSort (intlit, intn);voidcreateLit(intlit, int 某 n);voidprintLit(intlit, intn);voidheapAdjut(intlit, intu, intv);voidheapSort(intlit, intn )；/某直接插入排序某/voidinertSort (intlit ,intn) inti=l, j=0, node=0, count=l jprintf (、对序列进行直接插入排序： nprintf (、初始序列为:printLit (lit, n);for

28、(i=2;i=0&nodeai k)k=j;for(j=0; jif(ajk/某在第i行找到鞍点某/break; if (j=M)printf (3returnO;运行结果：4、调试程序：利用指针输出二维数组的元素。#includeintmain() inta3 4 = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23；int 某p;litj+l=litjj;litj+l=node;printf (、第d 次排序结果：printLit (lit, n);/某堆排序某/voidheapAdjut(intlit, intu, intv) inti=u,j, tem

29、p=liti;j=2 某i;while(j0;i一)heapAdjut (lit, i, n) ;/某建立初始堆某/printf (建立的初始堆为：printLit (lit, n) ;for (i=n; il; 1_-)/某循环,完成堆排序某/temp=lit1;lit iktemp;/某将第一个元素同当前区间内最后一个元素对换某/45)heapAdjut (lit, 1, i-l) ;/某筛选出lit1结点某/printf (、第%d 次排 序结果：printLit (lit, n);/某生成待排序序列某/voidcreateLit (intlit, int 某n) inti=l, a;p

30、rintf (请输入待排序序列(长度小于50,以输入一个字符结 束):nwhile (canf ( liti=a;i+;某 n=i-ljgetchar ();/某输出排序结果某/voidprintLit(intlit,intn) inti=l;for (;i=n;i+)printf( if (i%10=0&i!=0)printf(printf (intmain () intchoice=l,length;while(choice!=0) printf (printf (内部排序算法演示程序某某某某某npr intf (直接插入排 序nprintf (、堆排序nprintf (、退出nprint

31、f (、请选择：canf(getchar ();46witch (choice)(cael:createLit(lit, felength);inertSort (lit, length);break;cae2:createLit (lit, &length) jheapSort(lit, length);break;default:choice=0;printf () returnO;输入待排序序列：49386597132749 （以输入一个字符作为结束）1）直接插入排序运行结果（写出每一趟的状态）：2）堆排序运行结果（写出每一趟的状态）：2、在1题中补充希尔排序算法。算法代码：47输入待排

32、序序列：49386597132749 （以输入一个字符作为结束）运行 结果（写出每一趟的状态）：3、在1题中补充快速排序算法。算法代码：输入待排序序列：49386597132749 （以输入一个字符作为结束）运行 结果（写出每一趟的状态）：四、实验小结请比拟各个排序算法的性能。五、教师评语48for (p=aO;pprintf (returnO;运行结果：5、调试程序：设有一个教师与学生通用的表格，教师的数据有姓名、 年龄、职业、教研室四项，学生有姓名、年龄、专业、班级四项，编程输 入人员的数据,再以表格输出。ttinclude#def ineNlOtructtudent charname8

33、;/某姓名某/intage;/某年龄某 /charjob;/某职业或专业，用或t表示学生或教师某/union (intcla;/某班级某/charoffice10 ;/某教研室某/depa; tuN ; intmain () inti;intn;printf ( n请输入人员数(top=0;voidpuh (tacknode 某t, elemtype某) if(t-top=二M)printf (ele t-top=t-top+l;t-tackt-top=某;voidpop (tacknode 某t) if (t-top0)t-top-;eleprintf( StackiEmpty!n );in

34、tmain () charM;inti;tacknode 某 p;printf(p=malloc(izeof(tacknode);init (p);printf (get ();for(i=0;iif(i= C)puh(p, i) ;if (i=二)，)pop(p) ;)if (p-top-0)printf (eleprintf (returnO;输入：2+(c-d)某6- (f-7)某a)/6运行结果：输入：a-(c-d)某6-(/3-某)/2运行结果：程序的基本功能：17以下为选做实验：4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式 进行计算，得出表达式得结果。实现代码5、假

35、设以带头结点的循环链表表示队列，并且只设一个指针指向队 尾结点(不设队头指针)，试编写相应的置空队列、入队列、出队列的算 法。实现代码：四、实验小结五、教师评语18实验三串的模式匹配一、实验目的1、了解串的基本概念2、掌握串的模式匹配算法的实现二、实验预习说明以下概念1、模式匹配：2、BF算法：3、KMP算法:三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include#include#defineMA MSIZElOOtypedeftruct chardataMA 某SIZE;intlength;SqString;voidtrSub (SqString 某,inttart

36、, intublen, SqString 某ub) ;/某求 子串某/voidhowubString();printf (19for(i=0;i1ength&ilength;i+)if(l-datai!=2-datai) returnl-datai-2-datai;returnl-length-2-length;printf(get (1.data);length=trlen(1. data);printf(get(2. data);1. length=trlen(2. data);printf (eleprintf (printf ()voidtrSub (SqString 某,inttar

37、t, intublen, SqString 某ub) inti;if(tart-length|ublen-length-tart+l)ub-length=0;for (i=0;iub-datai=-datatart+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=0)printf (ele printf (f or (i=0;i