数据结构实验报告答案.docx
《数据结构实验报告答案.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告答案.docx（39页珍藏版）》请在冰点文库上搜索。
数据结构实验报告答案
数据结构（C语言版）实验报告
专业班级学号姓名
实验1
实验题目：
单链表的插入和删除
实验目的：
了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。
实验要求：
建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。
实验主要步骤：
1、分析、理解给出的示例程序。
2、调试程序，并设计输入数据（如：
bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：
不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。
3、修改程序：
（1）增加插入结点的功能。
（2）将建立链表的方法改为头插入法。
程序代码:
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"ctype.h"
typedefstructnode//定义结点
{
chardata[10];//结点的数据域为字符串
structnode*next;//结点的指针域
}ListNode;
typedefListNode*LinkList;//自定义LinkList单链表类型
LinkListCreatListR1（）;//函数，用尾插入法建立带头结点的单链表
LinkListCreatList（void）;//函数，用头插入法建立带头结点的单链表
ListNode*LocateNode（）;//函数，按值查找结点
voidDeleteList（）;//函数，删除指定值的结点
voidprintlist（）;//函数，打印链表中的所有值
voidDeleteAll（）;//函数，删除所有结点，释放内存
ListNode*AddNode（）;//修改程序：
增加节点。
用头插法，返回头指针
//==========主函数==============
voidmain（）
{
charch[10],num[5];
LinkListhead;
head=CreatList（）;//用头插入法建立单链表，返回头指针
printlist（head）;//遍历链表输出其值
printf（"Deletenode（y/n）:
"）;//输入"y"或"n"去选择是否删除结点
scanf（"%s",num）;
if（strcmp（num,"y"）==0||strcmp（num,"Y"）==0）{
printf（"PleaseinputDelete_data:
"）;
scanf（"%s",ch）;//输入要删除的字符串
DeleteList（head,ch）;
printlist（head）;
}
printf（"Addnode?
（y/n）:
"）;//输入"y"或"n"去选择是否增加结点
scanf（"%s",num）;
if（strcmp（num,"y"）==0||strcmp（num,"Y"）==0）
{
head=AddNode（head）;
}
printlist（head）;
DeleteAll（head）;//删除所有结点，释放内存
}
//==========用尾插入法建立带头结点的单链表===========
LinkListCreatListR1（void）
{
charch[10];
LinkListhead=（LinkList）malloc（sizeof（ListNode））;//生成头结点
ListNode*s,*r,*pp;
r=head;
r->next=NULL;
printf（"Input#toend"）;//输入"#"代表输入结束
printf（"\nPleaseinputNode_data:
"）;
scanf（"%s",ch）;//输入各结点的字符串
while（strcmp（ch,"#"）!
=0）{
pp=LocateNode（head,ch）;//按值查找结点，返回结点指针
if（pp==NULL）{//没有重复的字符串，插入到链表中
s=（ListNode*）malloc（sizeof（ListNode））;
strcpy（s->data,ch）;
r->next=s;
r=s;
r->next=NULL;
}
printf（"Input#toend"）;
printf（"PleaseinputNode_data:
"）;
scanf（"%s",ch）;
}
returnhead;//返回头指针
}
//==========用头插入法建立带头结点的单链表===========
LinkListCreatList（void）
{
charch[100];
LinkListhead,p;
head=（LinkList）malloc（sizeof（ListNode））;
head->next=NULL;
while
（1）
{
printf（"Input#toend"）;
printf（"PleaseinputNode_data:
"）;
scanf（"%s",ch）;
if（strcmp（ch,"#"））
{
if（LocateNode（head,ch）==NULL）
{
strcpy（head->data,ch）;
p=（LinkList）malloc（sizeof（ListNode））;
p->next=head;
head=p;
}
}
else
break;
}
returnhead;
}
//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========
ListNode*LocateNode（LinkListhead,char*key）
{
ListNode*p=head->next;//从开始结点比较
while（p!
=NULL&&strcmp（p->data,key）!
=0）//直到p为NULL或p->data为key止
p=p->next;//扫描下一个结点
returnp;//若p=NULL则查找失败，否则p指向找到的值为key的结点
}
//==========修改程序：
增加节点=======
ListNode*AddNode（LinkListhead）
{
charch[10];
ListNode*s,*pp;
printf（"\nPleaseinputaNewNode_data:
"）;
scanf（"%s",ch）;//输入各结点的字符串
pp=LocateNode（head,ch）;//按值查找结点，返回结点指针
printf（"ok2\n"）;
if（pp==NULL）{//没有重复的字符串，插入到链表中
s=（ListNode*）malloc（sizeof（ListNode））;
strcpy（s->data,ch）;
printf（"ok3\n"）;
s->next=head->next;
head->next=s;
}
returnhead;
}
//==========删除带头结点的单链表中的指定结点=======
voidDeleteList（LinkListhead,char*key）
{
ListNode*p,*r,*q=head;
p=LocateNode（head,key）;//按key值查找结点的
if（p==NULL）{//若没有找到结点，退出
printf（"positionerror"）;
exit（0）;
}
while（q->next!
=p）//p为要删除的结点，q为p的前结点
q=q->next;
r=q->next;
q->next=r->next;
free（r）;//释放结点
}
//===========打印链表=======
voidprintlist（LinkListhead）
{
ListNode*p=head->next;//从开始结点打印
while（p）{
printf（"%s,",p->data）;
p=p->next;
}
printf（"\n"）;
}
//==========删除所有结点，释放空间===========
voidDeleteAll（LinkListhead）
{
ListNode*p=head,*r;
while（p->next）{
r=p->next;
free（p）;
p=r;
}
free（p）;
}
实验结果：
Input#toendPleaseinputNode_data:
bat
Input#toendPleaseinputNode_data:
cat
Input#toendPleaseinputNode_data:
eat
Input#toendPleaseinputNode_data:
fat
Input#toendPleaseinputNode_data:
hat
Input#toendPleaseinputNode_data:
jat
Input#toendPleaseinputNode_data:
lat
Input#toendPleaseinputNode_data:
mat
Input#toendPleaseinputNode_data:
#
mat,lat,jat,hat,fat,eat,cat,bat,
Deletenode（y/n）:
y
PleaseinputDelete_data:
hat
mat,lat,jat,fat,eat,cat,bat,
Insertnode（y/n）:
y
PleaseinputInsert_data:
put
position:
5
mat,lat,jat,fat,eat,put,cat,bat,
请按任意键继续...
示意图：
心得体会：
本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。
另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。
实验2
实验题目：
二叉树操作设计和实现
实验目的：
掌握二叉树的定义、性质及存储方式，各种遍历算法。
实验要求：
采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
实验主要步骤：
1、分析、理解程序。
2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。
实验代码
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#defineMax20//结点的最大个数
typedefstructnode{
chardata;
structnode*lchild,*rchild;
}BinTNode;//自定义二叉树的结点类型
typedefBinTNode*BinTree;//定义二叉树的指针
intNodeNum,leaf;//NodeNum为结点数，leaf为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTreeCreatBinTree（void）
{
BinTreeT;
charch;
if（（ch=getchar（））=='#'）
return（NULL）;//读入#，返回空指针
else{
T=（BinTNode*）malloc（sizeof（BinTNode））;//生成结点
T->data=ch;
T->lchild=CreatBinTree（）;//构造左子树
T->rchild=CreatBinTree（）;//构造右子树
return（T）;
}
}
//========NLR先序遍历=============
voidPreorder（BinTreeT）
{
if（T）{
printf（"%c",T->data）;//访问结点
Preorder（T->lchild）;//先序遍历左子树
Preorder（T->rchild）;//先序遍历右子树
}
}
//========LNR中序遍历===============
voidInorder（BinTreeT）
{
if（T）{
Inorder（T->lchild）;//中序遍历左子树
printf（"%c",T->data）;//访问结点
Inorder（T->rchild）;//中序遍历右子树
}
}
//==========LRN后序遍历============
voidPostorder（BinTreeT）
{
if（T）{
Postorder（T->lchild）;//后序遍历左子树
Postorder（T->rchild）;//后序遍历右子树
printf（"%c",T->data）;//访问结点
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
intTreeDepth（BinTreeT）
{
inthl,hr,max;
if（T）{
hl=TreeDepth（T->lchild）;//求左深度
hr=TreeDepth（T->rchild）;//求右深度
max=hl>hr?
hl:
hr;//取左右深度的最大值
NodeNum=NodeNum+1;//求结点数
if（hl==0&&hr==0）leaf=leaf+1;//若左右深度为0，即为叶子。
return（max+1）;
}
elsereturn（0）;
}
//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========
voidLevelorder（BinTreeT）
{
intfront=0,rear=1;
BinTNode*cq[Max],*p;//定义结点的指针数组cq
cq[1]=T;//根入队
while（front!
=rear）
{
front=（front+1）%NodeNum;
p=cq[front];//出队
printf（"%c",p->data）;//出队，输出结点的值
if（p->lchild!
=NULL）{
rear=（rear+1）%NodeNum;
cq[rear]=p->lchild;//左子树入队
}
if（p->rchild!
=NULL）{
rear=（rear+1）%NodeNum;
cq[rear]=p->rchild;//右子树入队
}
}
}
//====数叶子节点个数==========
intcountleaf（BinTreeT）
{
inthl,hr;
if（T）{
hl=countleaf（T->lchild）;
hr=countleaf（T->rchild）;
if（hl==0&&hr==0）//若左右深度为0，即为叶子。
return
（1）;
elsereturnhl+hr;
}
elsereturn0;
}
//==========主函数=================
voidmain（）
{
BinTreeroot;
chari;
intdepth;
printf（"\n"）;
printf（"CreatBin_Tree；Inputpreorder:
"）;//输入完全二叉树的先序序列，
//用#代表虚结点，如ABD###CE##F##
root=CreatBinTree（）;//创建二叉树，返回根结点
do{//从菜单中选择遍历方式，输入序号。
printf（"\t**********select************\n"）;
printf（"\t1:
PreorderTraversal\n"）;
printf（"\t2:
IorderTraversal\n"）;
printf（"\t3:
Postordertraversal\n"）;
printf（"\t4:
PostTreeDepth,Nodenumber,Leafnumber\n"）;
printf（"\t5:
LevelDepth\n"）;//按层次遍历之前，先选择4，求出该树的结点数。
printf（"\t0:
Exit\n"）;
printf（"\t*******************************\n"）;
fflush（stdin）;
scanf（"%c",&i）;//输入菜单序号（0-5）
switch（i-'0'）{
case1:
printf（"PrintBin_treePreorder:
"）;
Preorder（root）;//先序遍历
break;
case2:
printf（"PrintBin_TreeInorder:
"）;
Inorder（root）;//中序遍历
break;
case3:
printf（"PrintBin_TreePostorder:
"）;
Postorder（root）;//后序遍历
break;
case4:
depth=TreeDepth（root）;//求树的深度及叶子数
printf（"BinTreeDepth=%dBinTreeNodenumber=%d",depth,NodeNum）;
printf（"BinTreeLeafnumber=%d",countleaf（root））;
break;
case5:
printf（"LevePrintBin_Tree:
"）;
Levelorder（root）;//按层次遍历
break;
default:
exit
（1）;
}
printf（"\n"）;
}while（i!
=0）;
}
实验结果：
CreatBin_Tree；Inputpreorder:
ABD###CE##F##
**********select************
1:
PreorderTraversal
2:
IorderTraversal
3:
Postordertraversal
4:
PostTreeDepth,Nodenumber,Leafnumber
5:
LevelDepth
0:
Exit
*******************************
1
PrintBin_treePreorder:
ABDCEF
2
PrintBin_TreeInorder:
DBAECF
3
PrintBin_TreePostorder:
DBEFCA
4
BinTreeDepth=3BinTreeNodenumber=6BinTreeLeafnumber=3
5
LevePrintBin_Tree:
ABCDEF
0
Pressanykeytocontinue
二叉树示意图
心得体会：
这次实验加深了我对二叉树的印象，尤其是对二叉树的各种遍历操作有了一定的了解。
同时认识到，在设计程序时辅以图形化的描述是非常有用处的。
实验3
实验题目：
图的遍历操作
实验目的：
掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。
实验要求：
采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。
实验主要步骤：
设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。
1．邻接矩阵作为存储结构
#include"stdio.h"
#include"stdlib.h"
#defineMaxVertexNum100//定义最大顶点数
typedefstruct{
charvexs[MaxVertexNum];//顶点表
intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表
intn,e;//图中的顶点数n和边数e
}MGraph;//用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
voidCreatMGraph（MGraph*G）
{
inti,j,k;
chara;
printf（"InputVertexNum（n）andEdgesNum（e）:
"）;
scanf（"%d,%d",&G->n,&G->e）;//输入顶点数和边数
scanf（"%c",&a）;
printf（"InputVertexstring:
"）;
for（i=0;in;i++）
{
scanf（"%c",&a）;
G->vexs[i]=a;//读入顶点信息，建立顶点表
}
for（i=0;in;i++）
for（j=0;jn;j++）
G->edges[i][j]=0;//初始化邻接矩阵
printf（"Inputedges,CreatAdjacencyMatrix\n"）;
for（k=0;ke;k++）{//读入e条边，建立邻接矩阵
scanf（"%d%d",&i,&j）;//输入边（Vi，Vj）的顶点序号
G->edges[i]
升级会员 