《数据结构》C语言版严蔚敏著数据结构实验指导Word格式.docx
《《数据结构》C语言版严蔚敏著数据结构实验指导Word格式.docx》由会员分享，可在线阅读，更多相关《《数据结构》C语言版严蔚敏著数据结构实验指导Word格式.docx（25页珍藏版）》请在冰点文库上搜索。
要求从键盘上输入一个二维数组，当鞍点存在时，把鞍点找出来。
#defineM3#defineN4intmain（）{inta[M][N],i,j,k;
printf（\请输入二维数组的数据：
\\n\
for（i=0;
for（j=0;
j
/某找出第i行的最大值某/
if（a[i][j]>
a[i][k]）k=j;
if（a[j][k]
/某在第i行找到鞍点某/
break;
if（j==M）
printf（\
3
4、调试程序：
利用指针输出二维数组的元素。
#includeintmain（）{
inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23};
int某p;
for（p=a[0];
p
5、调试程序：
设有一个教师与学生通用的表格，教师的数据有姓名、年龄、职业、教研室四项，学生有姓名、年龄、专业、班级四项，编程输入人员的数据，再以表格输出。
#defineN10tructtudent{charname[8];
/某姓名某/intage;
/某年龄某/charjob;
/某职业或专业，用或t表示学生或教师某/
union{
intcla;
/某班级某/
charoffice[10];
/某教研室某/}depa;
}tu[N];
intmain（）{
intn;
printf（“\\n请输入人员数（<
10）:
\\n”）;
canf（“%d”,&
n）;
canf（\if（tu[i].job==’’）canf（\
4
ele
canf（\}printf（“nameagejobcla/office”）;
if（tu[i].job==’’）
eleprintf（\
四、实验小结
五、教师评语
5
SqStack;
printf（\CreateStack（&
）;
printf（\PrintStack（&
}算法分析：
输入元素序列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{
top=t->
top+1;
tack[t->
top]=某;
}}
voidpop（tacknode某t）{
top>
0）t->
top--;
eleprintf（“StackiEmpty!
char[M];
tacknode某p;
printf（\p=malloc（izeof（tacknode））;
init（p）;
printf（\get（）;
if（[i]=='
（'
）
puh（p,[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（）;
19
ilength&
&
ilength;
i++）if（1->
data[i]!
=2->
data[i]）
return1->
data[i]-2->
data[i];
length-2->
length;
printf（\get（1.data）;
1.length=trlen（1.data）;
printf（\get（2.data）;
2.length=trlen（2.data）;
printf（\}
voidtrSub（SqString某,inttart,intublen,SqString某ub）{
if（tart<
1||tart>
->
length||ublen>
length-tart+1）{ub->
length=0;
ub->
data[i]=->
data[tart+i-1];
length=ublen;
voidhow_ubString（）{SqString,ub;
inttart,ublen,i;
printf（\printf（\get（.data）;
.length=trlen（.data）;
printf（\canf（\
trSub（&
tart,ublen,&
ub）;
if（ub.length==0）printf（\ele{
20
intmain（）{intn;
do{
printf（\printf（\printf（\printf（\printf（\canf（\getchar（）;
witch（n）{
}while（n）;
运行程序
1
tudenttudent
2、实现串的模式匹配算法。
补充下面程序，实现串的BF和KMP算法。
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）;
printf（\get（t.data）;
t.length=trlen（t.data）;
printf（\getNe某t（&
t,ne某t）;
printf（\printf（\for（i=0;
printf（\printf（\}
how_inde某（）;
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（&
rchild）;
/某递归建立右子树某/
24
voidPreOrder（BiTreep）{/某先序遍历二叉树某/if（p!
=NULL）{
printf（\PreOrder（p->
PreOrder（p->
voidInOrder（BiTreep）{/某中序遍历二叉树某/if（p!
InOrder（p->
printf（\InOrder（p->
voidPotOrder（BiTreep）{/某后序遍历二叉树某/if（p!
PotOrder（p->
voidPreorder_n（BiTreep）{/某先序遍历的非递归算法某/BiTreetack[MA某],q;
inttop=0,i;
while（q!
if（q->
rchild!
=NULL）tack[top++]=q->
rchild;
lchild!
=NULL）q=q->
lchild;
if（top>
0）q=tack[--top];
eleq=NULL;
voidreleae（BiTreet）{/某释放二叉树空间某/if（t!
releae（t->
free（t）;
25
graphga;
inti,j;
createGraph（&
ga）;
printf（\无向图的邻接矩阵：
init_viit（）;
tdf（&
tbf（&
根据右图的结构验证实验，输入：
ABCDEFGH#0,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;
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;
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（\邻接表:
\
32
=adjlit[i].link;
while（!
printf（\=->
ne某t;
}}}
voidtopSort（vnodeg[],intn）{/某拓扑排序某/}
vnodeadjlit[N];
intn,某p;
p=&
n;
createGraph_lit（adjlit,p）;
根据输入，输出有向图的拓扑排序序列。
并画出有向图。
输入:
ABCDEF#0,11,22,34,14,5-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;
g->
ve某num=0;
arcnum=0;
）{
ve某[i]=v;
/某读入顶点信息某/i++;
ve某num=i;
6;
i++）/某邻接矩阵初始化某/for（j=0;
j<
j++）
arc[i][j]=INF;
printf（\输入边的信息：
canf（\读入边（i,j,w）某/while（i!
=-1）/某读入i为－1时结束某/{
arc[i][j]=w;
34
if（flag==1）
arc[j][i]=w;
canf（\}}
voidprim（graph某g,intu）/某出发顶点u某/{
intlowcot[N],cloet[N],i,j,k,min;
ive某num;
i++）/某求其他顶点到出发顶点u的权某/{
lowcot[i]=g->
arc[u][i];
cloet[i]=u;
lowcot[u]=0;
for（i=1;
i++）/某循环求最小生成树中的各条边某/{min=INFIN;
jve某num;
j++）/某选择得到一条代价最小的边某/if（lowcot[j]!
=0&
lowcot[j]
min=lowcot[j];
k=j;
printf（\/某输出该边某/
lowcot[k]=0;
/某顶点k纳入最小生成树某/
j++）/某求其他顶点到顶点k的权某/if（g->
arc[k][j]!
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某;
35
flag[j]=1;
tack[top++]=k;
while（top>
0）/某找j到k的路径某/{
if（path[k][i]==1&
flag[i]==0）/某j到k的路径含有i顶点某/{
if（g.arc[j][i]!
=INF）/某j到i的路径含有中间顶点某/{
printf（\/某输出j到k的路径的顶点i某/flag[i]=1;
j=i;
k=tack[--top];
if（i!
=k）tack[top++]=i;
/某break;
某/}}}}
voiddijktra（graphg,intv）{/某dijktra算法求单源最短路径某/intpath[N][N],dit[N],[N];
intmindi,i,j,u,k;
dit[v]=0;
[v]=1;
for（i=0,u=1;
36
if（[j]==0）
if（dit[j]
mindi=dit[j];
[u]=1;
if（（[j]==0）&
dit[u]+g.arc[u][j]
printf（\顶点%c->
到各顶点的最短路径\\n\for（i=0;
顶点%c：
\if（dit[i]==INF||dit[i]==0）printf（\无路径\
ele{
printf（\经过顶点：
printPath（g,v,i）;
/某输出v到i的路径某/}}}
voidhowprim（）/某最小生成树prim算法演示某/{
createGraph_w（&
ga,1）;
prim（&
ga,0）;
voidhowdij（）{/某dijtra算法演示某/graphga;
dijktra（ga,0）;
howprim（）;
/某prim算法演示某/getchar（）;
howdij（）;
/某dijtra算法演示某/
37
下面的输入分别验证prim算法和dijtra算法。
输入实例的第一部分为无向图，求
其最小生成树；
输入的第二部分为有向图，求其最短路径。
最小生成树最短路径
ABCDEF#0,1,60,2,10,3,51,2,51,4,32,3,52,4,62,5,43,5,24,5,6-1,-1,-1运行结果：
（并画出两个图）
最小生成树
ABCDEF#0,2,100,5,1000,4,301,2,52,3,503,4,203,5,104,3,204,5,60-1,-1,-1
最短路径
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
升级会员 