《数据结构》(C语言版)严蔚敏著-数据结构实验指导
下面是小编为大家整理的《数据结构》(C语言版)严蔚敏著-数据结构实验指导,供大家参考。
《数据结构》（C 语言版）严蔚敏著-数据结构实验指导
/学年第学期
姓名：
学号：
班级：
指导教师：
数学与统计学院
2022
预备实验C 语言的函数数组指针结构体知识一、实验目的
1、复习C 语言中函数、数组、指针、结构体与共用体等的概念。2、熟悉利用C 语言进行程序设计的一般方法。
二、实验预习
说明以下C 语言中的概念 1、函数：
2、数组：
3、指针：
4、结构体
5、共用体
三、实验内容和要求
1、调试程序：输出 100 以内所有的素数（用函数实现）。#include intiprime(intn){/某判断一个数是否为素数某/intm;for(m=2;m 某 m<=n;m++)
if(n%m==0)return0;return1;
}
intmain(){/某输出 100 以内所有素数某/ inti;printf(\for(i=2;i<100;i++) if(iprime(i)==1)printf(\return0; }
运行结果：
2、调试程序：对一维数组中的元素进行逆序排列。#include#defineN10intmain(){ 2
inta[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-1];a[N-i-1]=temp; printf(\for(i=0;i return0;}
运行结果：
3、调试程序：在二维数组中，若某一位置上的元素在该行中最大， 而在该列中最小，则该元素即为该二维数组的一个鞍点。要求从键盘上输入一个二维数组，当鞍点存在时，把鞍点找出来。#include
#defineM3#defineN4intmain(){inta[M][N],i,j,k;printf(\请输入二维数组的数据：\\n\ for(i=0;i for(j=0;j for(j=0;j for(i=0;i /某找出第i 行的最大值某/ if(a[i][j]>a[i][k])k=j; for(j=0;j if(a[j][k]
/某在第i 行找到鞍点某/ break;if(j==M) printf(\ 3
}
return0;}
运行结果：
4、调试程序：利用指针输出二维数组的元素。#includeintmain(){ inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23};int 某 p;
for(p=a[0];p printf(\ return0;} 运行结果：
5、调试程序：设有一个教师与学生通用的表格，教师的数据有姓名、年龄、职业、教研室四项，学生有姓名、年龄、专业、班级四项，编程输入人员的数据，再以表格输出。#include #defineN10tructtudent{charname[8];/某姓名某/intage;/某年龄某 /charjob;/某职业或专业，用或t 表示学生或教师某/ union{ intcla;
/某班级某/
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(\
4
ele
canf(\}printf(“nameagejobcla/office”);for(i=0;i if(tu[i].job==’’) printf(\ eleprintf(\ }
}
四、实验小结五、教师评语5 intmain(){
SqStack; printf(\CreateStack(&); printf(\PrintStack(&);return0; }算法分析：输入元素序列 12345，为什么输出序列为 54321？体现了栈的什么 特性？
2、在第 1 题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。实现代码 验证
3、阅读并运行程序，并分析程序功能。#include#include#include#defineM20 #defineelemtypechartypedeftruct{ elemtypetack[M];inttop;} tacknode; voidinit(tacknode 某t);
voidpuh(tacknode 某t,elemtype 某);voidpop(tacknode 某t);
16
voidinit(tacknode 某t){ t->top=0;} voidpuh(tacknode 某t,elemtype 某){ if(t->top==M) printf(\ele{
t->top=t->top+1;t->tack[t->top]=某;}} voidpop(tacknode 某t){ if(t->top>0)t->top--; eleprintf(“StackiEmpty!\\n”);} intmain(){ char[M];inti;
tacknode 某 p; printf(\p=malloc(izeof(tacknode));init(p); printf(\get(); for(i=0;i if([i]=="(") puh(p,[i]);if([i]==")")pop(p);} if(p->top==0) printf(\ele printf(\return0;} 输入：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 某SIZE100typedeftruct{ chardata[MA 某SIZE];intlength;}SqString;
voidtrSub(SqString 某,inttart,intublen,SqString 某ub);/某求子串某/ voidhow_ubString(); printf(\ 19
for(i=0;ilength&&ilength;i++)if(1->data[i]!=2->data[i]) return1->data[i]-2->data[i];return1->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; if(tart<1||tart>->length||ublen>->length-tart+1){ub- >length=0;}
for(i=0;i
ub->data[i]=->data[tart+i-1];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(\for(i=0;i
printf(\} printf(\ 20 }
intmain(){intn;do{ printf(\printf(\printf(\printf(\printf(\canf(\getchar(); witch(n){ }while(n);return0;} 运行程序 输入：1 1
tudenttudent
2 2
运行结果：
2、实现串的模式匹配算法。补充下面程序，实现串的BF 和 KMP 算法。#include#include#defineMA 某SIZE100typedeftruct{ chardata[MA 某SIZE];intlength;
}SqString;
intinde 某_bf(SqString 某,SqString 某t,inttart);
21
voidgetNe 某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,j=-1;ne 某t[0]=-1; while(ilength){
if((j==-1)||(t->data[i]==t->data[j])){ i++;j++;ne 某 t[i]=j;}ele j=ne 某t[j];}}
intinde 某_kmp(SqString 某,SqString 某t,inttart,intne 某t[]){补充代码 } voidhow_inde 某(){SqString,t; intk,ne 某t[MA 某SIZE]={0},i; printf(\printf(\ 22
get(.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;i printf(\printf(\} intmain(){
how_inde 某();return0;
}
输入：
abcaabbabcabaacbacbaabcabaa1
运行结果：
四、实验小结五、教师评语
23
实验四二叉树一、实验目的
1、掌握二叉树的基本特性
2、掌握二叉树的先序、中序、后序的递归遍历算法 3、理解二叉树的先序、中序、后序的非递归遍历算法 4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性 二、实验预习
说明以下概念 1、二叉树：
2、递归遍历：
3、非递归遍历：
4、层序遍历：
三、实验内容和要求
1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。#include#include#defineMA 某 20 typedeftructBTNode{/某节点结构声明某/chardata;/某节点数据某/ tructBTNode 某lchild; tructBTNode 某rchild;/某指针某/
}某BiTree;
voidcreateBiTree(BiTree 某t){/某先序遍历创建二叉树某/char; BiTreeq; printf(\=getche(); if(=="#"){某t=NULL;return;} q=(BiTree)malloc(izeof(tructBTNode)); if(q==NULL){printf(\q->data=; 某 t=q;
createBiTree(&q->lchild);/某递归建立左子树某 /createBiTree(&q->rchild);/某递归建立右子树某/
24
}
voidPreOrder(BiTreep){/某先序遍历二叉树某/if(p!=NULL){ printf(\PreOrder(p->lchild);PreOrder(p->rchild);}} voidInOrder(BiTreep){/某中序遍历二叉树某/if(p!=NULL){ InOrder(p->lchild);printf(\InOrder(p->rchild);}} voidPotOrder(BiTreep){/某后序遍历二叉树某/if(p!=NULL){ PotOrder(p->lchild);PotOrder(p->rchild);printf(\ }}
voidPreorder_n(BiTreep){/某先序遍历的非递归算法某 /BiTreetack[MA 某],q;inttop=0,i; for(i=0;i while(q!=NULL){ printf(\ if(q->rchild!=NULL)tack[top++]=q->rchild;if(q- >lchild!=NULL)q=q->lchild;ele if(top>0)q=tack[--top];eleq=NULL;}} voidreleae(BiTreet){/某释放二叉树空间某/if(t!=NULL){ releae(t->lchild);releae(t->rchild);free(t);
25
for(i=0;i intmain(){ graphga; inti,j; createGraph(&ga);
printf(\无向图的邻接矩阵：\\n\ for(i=0;i for(j=0;j printf(\printf(\} init_viit();tdf(&ga);init_viit();tbf(&ga);return0;
}
根据右图的结构验证实验，输入：
ABCDEFGH#0,10,20,51,31,42,52,63,74,7- - 1,- -1 1
2、阅读并运行下面程序，补充拓扑排序算法。#include#include#defineN20 运行结果：
10B4E7HAC2F5G6
3D31
typedeftructedgenode{/某图的邻接表：邻接链表结点某/intadjve 某;/某顶点序号某/ tructedgenode 某ne 某t;/某下一个结点的指针某/}edgenode;
typedeftructvnode{/某图的邻接表：邻接表某/chardata;/某顶点信息某/ intind;/某顶点入度某/ tructedgenode 某link;/某指向邻接链表指针某/}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())!="#")
{
adjlit[i].data=v;/某读入顶点信息某 /adjlit[i].link=NULL;adjlit[i].ind=0;i++;} n=i;某 p=n; /某建立邻接链表某/
printf(\请输入弧的信息(i=-1 结束)：i,j:\\n\canf(\ while(i!=-1){
=(tructedgenode 某)malloc(izeof(edgenode));->adjve 某=j;
->ne 某 t=adjlit[i].link;adjlit[i].link=; adjlit[j].ind++;/某顶点j 的入度加 1 某/e++; canf(\} printf(\邻接表:\ for(i=0;i printf(\ 32
=adjlit[i].link; while(!=NULL){ printf(\=->ne 某t;}}} voidtopSort(vnodeg[],intn){/某拓扑排序某/} intmain(){ vnodeadjlit[N];intn, 某 p;p=&n; createGraph_lit(adjlit,p);return0; }
根据输入，输出有向图的拓扑排序序列。并画出有向图。输入 :ABCDEF#0,11,22,34,14,5- - 1,- -1 1
运行结果：
33
3、阅读并运行下面程序。
#include#defineN20#defineTRUE1
#defineINF32766/某邻接矩阵中的无穷大元素某 /#defineINFIN32767/某比无穷大元素大的数某/
typedeftruct{/某图的邻接矩阵某/intve 某num,arcnum;charve 某[N];intarc[N][N];} graph;
voidcreateGraph_w(graph 某g,intflag);voidprim(graph 某g,intu);voiddijktra(graphg,intv);voidhowprim();voidhowdij(); /某建带权图的邻接矩阵,若flag 为 1 则为无向图，flag 为 0 为有向图某/voidcreateGraph_w(graph 某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;i<6;i++)/某邻接矩阵初始化某/for(j=0;j<6;j++) g->arc[i][j]=INF;
printf(\输入边的信息：\\n\
canf(\读入边(i,j,w)某/while(i!=-1)/某读入i 为－1 时结束某/{ g->arc[i][j]=w; 34
if(flag==1)
g->arc[j][i]=w; canf(\}} voidprim(graph 某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=1;ive 某num;i++)/某循环求最小生成树中的各条边某 /{min=INFIN;
for(j=0;jve 某num;j++)/某选择得到一条代价最小的边某 /if(lowcot[j]!=0&&lowcot[j] min=lowcot[j]; k=j;}
printf(\/某输出该边某/
lowcot[k]=0;/某顶点k 纳入最小生成树某/
for(j=0;jve 某num;j++)/某求其他顶点到顶点k 的权某/if(g- >arc[k][j]!=0&&g->arc[k][j]
lowcot[j]=g->arc[k][j];cloet[j]=k;}}} voidprintPath(graphg,inttartVe 某,intEndVe 某){ inttack[N],top=0;/ 某 堆 栈 某 /inti,k,j; intflag[N];/某输出路径顶点标志某/k=EndVe 某; for(i=0;i 35
printf(\ flag[j]=1; tack[top++]=k; while(top>0)/某找j 到k 的路径某/{ for(i=0;i if(path[k][i]==1&&flag[i]==0)/某 j 到k 的路径含有i 顶点某/{ if(g.arc[j][i]!=INF)/某 j 到i 的路径含有...