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

《数据结构》（C语言版）严蔚敏著-数据结构实验指导

/学年第学期

姓名：学号：班级：

指导教师：______________

数学与统计学院

2022

预备实验C语言的函数数组指针结构体知识

一、实验目的

1、复习C语言中函数、数组、指针、结构体与共用体等的概念。2、

熟悉利用C语言进行程序设计的一般方法。

二、实验预习

说明以下C语言中的概念I、函数：

2、数组：

3、指针：

4、结构体

5、共用体

三、实验内容和要求

1、调试程序：输出100以内所有的素数（用函数实现）。#include

intiprime（intn）{/某判断一个数是否为素数某/intm;for（m=2;m某

m<=n;m++)

if(n%m==O)returnO;returnl;

)

intmainO{/某输出100以内所有素数某/

inti;printf(\for(i=2;i<100;i++)

if(iprime(i)==1)printf(\returnO;

}

运行结果：

2、调试程序：对一维数组中的元素进行逆序排列。

#include#defineNlOintmain(){

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-l];a[N-i-l]=temp;

printf(\for(i=0;i

returnO;}

运行结果：

3、调试程序：在二维数组中，若某一位置上的元素在该行中最大，

而在该列中最小，则该元素即为该二维数组的一个鞍点。要求从键盘上输

入一个二维数组，当鞍点存在时，把鞍点找出来。ftinclude

#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

)

returnO;}

运行结果：

4、调试程序：利用指针输出二维数组的元素。

ttincludeintmainO{inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23}

；int某p;

for(p=a[O];p

printf(\

returnO;}

运行结果：

5、调试程序：设有一个教师与学生通用的表格，教师的数据有姓名、

年龄、职业、教研室四项，学生有姓名、年龄、专业、班级四项，编程输

入人员的数据，再以表格输出。ttinclude

#defineNlOtructtudent{charname[8];/某姓名某/intage;/某年龄某

/cha门ob;/某职业或专业，用或t表示学生或教师某/

union{

intcla;

/某班级某/

charoffice[10];/某教研室某/}depa;

}tu[N];intmain(){

inti;intn;

printf(u\\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

ifjob==,')

printf(\

eleprintf(\

}

}

四、实验小结

五、教师评语

5

intmain(){

SqStack;

printf(\CreateStack(&);

printf(\PrintStack(&);returnO;

}算法分析：输入元素序列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+l;;}}

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(\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某SIZElOOtypedeftruct{

chardata[MA某SIZE];intlength;}SqString;

voidtrSub(SqString某,inttart,intublen,SqString某ub);/某求

子串某/

voidhowubString();

printf(\

19

for(i=0;ilength&&ilength;i++)if(l->data[i]!=2->data[i])

returnl->data[i]-2->data[i];returnl->length-2->length;

printf(\get(1.data);

1.length=trlen(1.data)jprintf(\get(2.data);

2.length=trlen(2.data);

printf(\ele

printf(\

printf(\)

voidtrSub(SqString某,inttart,intublen,SqString某

ub){inti;

if(tart<l1|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==0)printf(\ele{printf(\f

or(i=0;i

printf(\}

printf(\

20

)

intmain(){intn;do{printf(\printf(\printf(\printf(\printf(\can

f(\getchar();witch(n){

}while(n);returnO;}

运行程序

输入：1

tudenttudent

2

运行结果：

2、实现串的模式匹配算法。补充下面程序，实现串的BF和KMP算法。

#include#include#defineMA某SIZElOOtypedeftruct{

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=T;ne某

t[0]=T;

while(ilength){

if((j==-l)||(t->data[i]==t-

>data[j])){i++;j++;ne某t[i]=j;}ele

j=ne某t[j];}}

intindeM_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(){

howinde某();returnO;

}

输入：

abcaabbabcabaacbacbaabcabaal

运行结果：

四、实验小结

五、教师评语

23

实验四二叉树

一、实验目的

1、掌握二叉树的基本特性

2、掌握二叉树的先序、中序、后序的递归遍历算法3、理解二叉树

的先序、中序、后序的非递归遍历算法

4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉

树的基本特性

二、实验预习

说明以下概念1、二叉树:

2、递归遍历:

3、非递归遍历：

4、层序遍历：

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的

形态。#include#include#defineMA某20

typedeftructBTNode{/某节点结构声明某/chardata;/某节点数据某/

tructBTNode某Ichild;

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);}}voidlnOrder(BiTreep){/某中序遍历二叉树某

/if(p!=NULL){InOrder(p->lchild);printf(\InOrder(p-

>rchild);}}voidPotOrder(BiTreep){/某后序遍历二叉树某

/if(p!=NULL){PotOrder(p->lchild);PotOrder(p-

>rchild);printf(\

}}

voidPreordern(BiTreep){/某先序遍历的非递归算法某

/BiTreetack[MA某],q;inttop=0,i;

for(i=0;i

while(q!=NULL){

printf(\

if(q->rchi1d!=NULL)tack[top++]=q->rchiId;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)jreturnO;

}

根据右图的结构验证实验，输入：

ABCDEFGH#O,10,20,51,31,42,52,63,74,7-1,-1

2、阅读并运行下面程序，补充拓扑排序算法。

#include#include#defineN20

运行结果：

10B4E7HAC2F5G6

3D31

typedeftructedgenode{/某图的邻接表：邻接链表结点某/intadjve

某;/某顶点序号某/

tructedgenode某ne某t;/某下一个结点的指针某/}edgenode;

typedeftructvnode{/某图的邻接表：邻接表某/chardata;/某顶点信

息某/

intind;/某顶点入度某/

tructedgenode某link;/某指向邻接链表指针某/}vnode;

voidcreateGraphlit(vnodeadjlit[],int某p)；/某建立有向图的

邻接表某/voidtopSort(vnodeg口，intn)；/某拓扑排序某/

voidcreateGraph1it(vnodeadj1it[],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=T结束)：i,j:\\n\canf(\

while(i!=-1){

=(tructedgenodeM)malloc(izeof(edgenode));->adjve塞j;

->ne某t=adjlit[i].link;adjlit[i].link=;

adjlit[j].ind++;/某顶点j的入度加1某%++;

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);returnO;

)

根据输入，输出有向图的拓扑排序序列。并画出有向图。输

入:ABCDEF#0,11,22,34,14,5-1,-1

运行结果：

33

3、阅读并运行下面程序。

#include#defineN20#defineTRUEl

#defineINF32766/某邻接矩阵中的无穷大元素某

/#defineINFIN32767/某比无穷大元素大的数某/

typedeftruct{/某图的邻接矩阵某/intve某num,arcnum;charve某

[N];intarc[N][N];}

graph;

voidcreateGraphw(graph某g,intflag);voidprim(graph某

g,intu);voiddijktra(gr^iig,intv);voidbovprimOjvoichjdijO;

/某建带权图的邻接矩阵，若flag为1则为无向图，flag为0为有向

S^/voidcreateGraphw(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==l)

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=l;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]=l;

tack[top++]=k;

while(top>0)/某找j到k的路径某

/{for(i=0;i

if(path[k][i]==l&&flag[i]==0)/某j到k的路径含有i顶点某

/{]£1@%口]"]!=1小)/某上到i的路径含有中间顶点某

/{printf(\/某输出j到k的路径的顶点i某;j=i;

k=tack[-top];break;}ele

if(i!=k)tack[top++]=i;/某break;某/}}}}

voiddijktra(graphg,intv){/某dijktra算法求单源最短路径某

/intpath[N][N],dit[N],[N];intmindi,i,j,u,k;

for(i=0;i

for(j=0;j

dit[v]=0;[v]=l;

for(i=0,u=l;i

for(j=0;j

36

if([j]==0)

if(dit[j]

mindi=dit[j];}

[u]=l;

for(j=0;j

if(([j]==0)&&dit[u]+g.arc[u][j]

printf('顶点%c-＞到各顶点的最短路径\\n\for(i=0;i

printf(、顶点%c-＞顶点％c：\if(dit[i]==INF||dit[i]==0)printf(\

无路径\

ele{

printf(\

printf(、经过顶点：\

printPath(g,v,i);/某输出v到i的路径某/}}}

voidhowprim。/某最小生成树prim算法演示某

/{graphga;

createGraph_w(&ga,1);prim(&ga,0);}

voidhowdij(){/某dijtra算法演示某/graphga;

createGraphw(&ga,0);dijktra(ga,0);}

intmain(){

howprimO;/某prim算法演示某/getchar();

howdij();/某dijtra算法演示某/

37

returnO;

}

下面的输入分别验证prim算法和dijtra算法。输入实例的第一部分

为无向图，求

其最小生成树；输入的第二部分为有向图，求其最短路径。最小生成

树最短路径

ABCDEFftO,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、哈希表的构造与查找

/某采用开放地址法构造哈希表某/#include#incIude#defineMA某

SIZE25#defineP13

#define0Kl#defineERR0R0

#defineDUPLICATE-1#defineTRUEI

ttdefineFALSEO

typedeftruct{/某哈希表元素结构某/intkey;/某关键字值某/

intflag;/某是否存放元素某/}ElemType;

typedeftruct{ElemTypeda

ta[MA某SIZE];

intcount;/某元素个数某/intizeinde某;/某当前哈希表容量某

/}HahTable;

intdl[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};/某线性探测序

列某/

intd2[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);

intlnertHah(HahTable某H,inte,intd[]);

intCreateHah(HahTableintd[],intlm,intd[])jintSeaidifahGblirable

某H,inte,intd[]);

40

voidmenu();

/某输入查找表某/

voiddataet(intd[],int某len){intn,m;n=0;

printf(、查找表输入：\

while(canf(、以输入一个非整数作为结束某/d[n]=m;n++;}某len=n;}

/某计算哈希地址，插入哈希表某/

intlnertHah(HahTable某H,inte,intd[]){intk,i=l;k=e%P;

while(H->data[k].flag==TRUE||k<0){k=(e%P+d[i])%MA某

SIZE;i++;if(i>=15)

returnERROR;}

H->data[k].key=e;

H->data[k].flag=TRUE;H->count++;returnOK;}

/某构造哈希表某/

intCreateHah(HahTable某H,intd[],intlen,intd[]){inti;

for(i=0;i

if(SearchHah(H,d[i],d)!=-

1)returnDUPLICATE;InertHah(H,d[i],d);if(H->count>=MA某

SIZE)returnERROR;}

returnOK;}

/某初始化哈希表某/

voidlnitHah(HahTable某H){inti;

for(i=0;idata[i].key=0;

H->data[i].flag=FALSE;

41

)

)

/某在哈希表中查找某/

intSearchHah(HahTable某H,inte,intd[]){intk,i=l;

k=e%P;

while(H->data[k].key!=e){k=(e%P+d[i])%MA某

SIZE;i++;if(i>=15)return-1;}

returnk;}

/某演示菜单某/

voidmenu(){intcho

ice;int某p;

HahTableh;

h.count=0;h.izeinde某=MA某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==l)p=dl;

eleif(choice==2)p=d2;ele

return;

InitHah(&h);/某初始化哈希表某/

if(!(i=CreateHah(&h,a,n,p)))/某构造哈希表某/printf(、哈希表构

造失败！\\n\eleif(i==DUPLICATE)

printf('哈希表具有重复关键字！

\\n\ele{printf(、哈希表：\\n\for(i=0;i

42

printf(\

printf(、哈希查找\\n输入要查找的key值：\getchar();

canf(\

if((i=SearchHah(&h,e,p))=-1)printf(、未找到\\n\ele

printf(\在哈希表中下标为%d\\n\}

getchar();}while(1);}

intmain(){menu();returnO;

}

输入查找表为：19142316820842755111079(注意以输入一个非整数

结束)。运行结果：1)线性探测散列：哈希表形态：

84在哈希表中的位置:2)二次探测散列：哈希表形态：

84在哈希表中的位置：

四、实验小结

五、教师评语

43

实验七排序

一、实验目的

1、掌握内部排序的基本算法；

2、分析比较内部排序算法的效率。

二、实验预习

说明以下概念1、简单排序：

2、希尔排序：

3、快速排序：

4、堆排序：

三、实验内容和要求

1运行下面程序：#include#include#defineMA某50

intlitEMA某];/某待排序序列某/

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;printf('对序列进行直接插入排序：

\\n\printf(\初始序列为:

\printLit(lit,n);for(i=2;i<=n;i++){node=lit[i];j=i-l;

while(j>=0&&node<lit[j])

44

lit[j+l]=lit[j]j;}

lit[j+l]=node;

printf(\第％d次排序结果：\printLit(lit,n);

/某堆排序某/

voidheapAdjut(intlit[],intu,intv){inti=u,

j,temp=lit[i];j=2某i;while(j<=v){}

if(j〈v&&lit[jklit[j+l])j++;/某若右孩子较大,则把j修改为右

孩子的下标某/if