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

数据结构(C语言版)严蔚敏著-数据结构实验指导/学年第学期姓名：学号：班级:指导教师：数学与统计学院2022预备实验C语言的函数数组指针结构体知识一、实验目的1、复习c语言中函数、数组、指针、结构体与共用体等的概念。2、 熟悉利用C语言进行程序设计的一般方法。二、实验预习说明以下C语言中的概念1、函数：2、数组：3、指针：4、结构体5、共用体三、实验内容和要求1、调试程序：输出100以内所有的素数(用函数实现)。#includeintiprime (into) /某判断一个数是否为素数某/intm; for (m=2 ;m某 m<=n;m+)printf ()printf (20intmain()intn;do( printf(printf(printf(printf(printf(canf (getchar () ; witch(n) while(n) jreturnO;运行程序输入：1tudenttudent2运行结果：2、实现串的模式匹配算法。补充下面程序，实现串的BF和KMP算法。 #include#include#defineMA 某SIZElOOtypedeftruct chardataMA 某SIZE;intlength;SqString;intinde (SqString 某,SqString 某 t, inttart);21voidgetNe 某t(SqString 某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 某while(ilength) if(j=-l)|(t->datai=t->dataj) i+;j+;ne 某ti=j;elej=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()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=(BiTree)malloc(izeof(tructBTNode);if (q-NULL) printf (q->data=;某 t=q;createBiTree(&q->lchild) ;/某递归建立左子树某/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);PotOrder(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(top>0)q=tack-top;eleq=NULL;voidreleae (BiTreet) /某释放二叉树空间某/if(t!=NULL) releae(t->lchild);releae(t- >rchild);free (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运行结果：10B4E7HAC2F5G63D31typedeftructedgenode /某图的邻接表：邻接链表结点某/intadjve 某;/某顶点序号某/tructedgenode某ne某t;/某下一个结点的指针某/ edgenode;typedeftructvnode/某图的邻接表：邻接表某/chardata;/某顶点信 息某/intind;/某顶点入度某/tructedgenode某1 ink; /某指向邻接链表指针某/ 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 ('输入顶点序列(以#结束)：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 ® malloc(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;根据输入，输出有向图的拓扑排序序列。并画出有向图。输入: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 (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 ;i<6; i+) / 某邻接矩阵初始化某/for (j=0; j<6 ;j+) g->arci j=INF;printf('输入边的信息：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;for (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;i<100;i+)if (iprime(i)=l)printf(returnO;运行结果：2、调试程序：对一维数组中的元素进行逆序排列。#include#defineNlOintmain () 2intaN = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9), i, temp;printf (for (i=0; itemp=ai ;ai=aN-i-l ;aN-i-l=temp;printf(for (i=0;ireturnO;运行结果：3、调试程序：在二维数组中，假设某一位置上的元素在该行中最大， 而在该列中最小，那么该元素即为该二维数组的一个鞍点。要求从键盘上输 入一个二维数组，当鞍点存在时，把鞍点找出来。ttincludelowcot k=0;/某顶点k纳入最小生成树某/for (j=0; jve某num; j+)/某求其他顶点到顶点k的权某/if (g- >arckj!=0&&g->arckjlowcotj=g->arckj;cloetj=k;voidprintPath(graphg, inttartVe 某,intEndVe某) inttackN, top=0;/ 某 堆栈某 /inti, k, j;intflagN ;/某输出路径顶点标志某/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算法求单源最短路径某 /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) ;/某输出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算法。输入实例的第一局部 为无向图，求其最小生成树；输入的第二局部为有向图，求其最短路径。最小生成 树最短路径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 I ude#def ineMA某 SIZE25#defineP13#define0Kl#defineERR0R0#defi neDUPLI CATE-1#defineTRUEIttdefineFALSEOtypedeftruct /某哈希表元素结构某/intkey;/某关键字值某/intflag; /某是否存放元素某/ ElemType;typedeftruct( ElemTypedataMA 某SIZE;intcount;/某元素个数某/intizeinde某;/某当前哈希表容量某/HahTable;intdl15 = 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, intd);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<0)k=(e%P+di)%MA 某 SIZE;i+;if(i>=15)returnERROR;H->datak. key=e;H->datak. flag=TRUE;H->count+;returnOK;/某构造哈希表某/intCreateHah(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=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 (输入选 择：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) printf (、未找到neleprintf (在哈希表中下标为%dngetchar() ;while(1) ;)intmain () menu () ;returnO;输入查找表为：(注意以输入一个非整数结束)。运行结果：1)线性探测散列：哈希表形态：84在哈希表中的位置:2)二次探测散列：哈希表形态：84在哈希表中的位置：四、实验小结五、教师评语43实验七排序一、实验目的1、掌握内部排序的基本算法； 2、分析比拟内部排序算法的效率。二、实验预习说明以下概念1、简单排序：2、希尔排序：3、快速排序：4、堆排序：三、实验内容和要求1 运行下面程序：#include#include#def ineMA 某 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 (i=2;i<=n;i+) node=lit i;j=i-l;while(j>=0&&node<litj)44#defineM3#defineN4intmain0 intaM N, i, j, k;printf (请输入二维数组的数据：nfor(i=0;ifor(j=0; jfor(j=0;jfor(i=0;i/某找出第i行的最大值某/if (ai j>ai 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, temp=liti;j=2 某i;while(j<=v)if(jv&&litjklitj+l)j+;/某假设右孩子较大,那么把j修改为右 孩子的下标某/if(templitj) 某将调到父亲的位置上某/i=j；j=2某i;/某修改i和j的值，以便继续向下筛选某/elebreak;/某筛选完成，终止循环某/liti=temp; /某被筛结点的值放入最终位置某/voidheapSort (intlit ,intn) inti=0, temp=0, count= 1 ;printf (、对序列进行堆排序：nprintf ( 初始序列为:printLit (lit, n);for(i=n/2;i>0;i一)heapAdjut (lit, i, n) ;/某建立初始堆某/printf ('建立的初始堆为：printLit (lit, n) ;for (i=n; i>l; 1_-)/某循环,完成堆排序某/temp=lit1;lit iktemp;/某将第一个元素同当前区间内最后一个元素对换某/45)heapAdjut (lit, 1, i-l) ;/某筛选出lit1结点某/printf (、第%d 次排 序结果：printLit (lit, n);/某生成待排序序列某/voidcreateLit (intlit, int 某n) inti=l, a;printf ('请输入待排序序列(长度小于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 (、退出nprintf (、请选择：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输入待排序序列：49386597132749 （以输入一个字符作为结束）运行 结果（写出每一趟的状态）：3、在1题中补充快速排序算法。算法代码：输入待排序序列：49386597132749 （以输入一个字符作为结束）运行 结果（写出每一趟的状态）：四、实验小结请比拟各个排序算法的性能。五、教师评语48for (p=aO;pprintf (returnO;运行结果：5、调试程序：设有一个教师与学生通用的表格，教师的数据有姓名、 年龄、职业、教研室四项，学生有姓名、年龄、专业、班级四项，编程输 入人员的数据,再以表格输出。ttinclude#def ineNlOtructtudent charname8 ;/某姓名某/intage;/某年龄某 /charjob;/某职业或专业，用或t表示学生或教师某/union (intcla;/某班级某/charoffice10 ;/某教研室某/depa; tuN ; intmain () inti;intn;printf ( "n请输入人员数(<10) : n" ) ; canf ( "%d" , &n) ; for (i=0; icanf (if (tui. job=' ' ) canf ( ele canf (printf ( "nameagejobcla/office" );for(i=0;iif(tui. job=,')printf (eleprintf (四、实验小结五、教师评语5intmain () SqStack;printf (CreateStack(&);printf (PrintStack(&);returnO;算法分析：输入元素序列12345,为什么输出序列为54321?表达了 栈的什么特性？2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算 法函数(要求利用栈来实现)，并验证其正确性。实现代码验证3、阅读并运行程序，并分析程序功能。#include#include#include#defineM20#defineelemtypechartypedeftruet(elemtypetackM;inttop;tacknode;voidinit(tacknode 某t);voidpuh(tacknode 某t, elemtype 某);voidpop(tacknode 某t);16voidinit (tacknode 某t) t->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->top>0)t->top-;eleprintf( StackiEmpty!n );intmain () 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、假设以带头结点的循环链表表示队列，并且只设一个指针指向队 尾结点(不设队头指针)，试编写相应的置空队列、入队列、出队列的算 法。实现代码：四、实验小结五、教师评语18实验三串的模式匹配一、实验目的1、了解串的基本概念2、掌握串的模式匹配算法的实现二、实验预习说明以下概念1、模式匹配：2、BF算法：3、KMP算法:三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include#include#defineMA MSIZElOOtypedeftruct chardataMA 某SIZE;intlength;SqString;voidtrSub (SqString 某,inttart, 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 某,inttart, intublen, SqString 某ub) inti;if(tart<l|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