数据结构实验报告答案doc.docx

数据结构实验报告答案doc.docx

《数据结构实验报告答案doc.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告答案doc.docx（7页珍藏版）》请在冰点文库上搜索。

数据结构实验报告答案doc

数据结构实验报告-答案

数据结构（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;}}elsebreak;}returnhead;}//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========ListNode*LocateNode（LinkListhead,char*key）{ListNode*p=head->next;//从开始结点比较while（p!

=NULL//扫描下一个结点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:

batInput#toendPleaseinputNode_data:

catInput#toendPleaseinputNode_data:

eatInput#toendPleaseinputNode_data:

fatInput#toendPleaseinputNode_data:

hatInput#toendPleaseinputNode_data:

jatInput#toendPleaseinputNode_data:

latInput#toendPleaseinputNode_data:

matInput#toendPleaseinputNode_data:

#mat,lat,jat,hat,fat,eat,cat,bat,Deletenode（y/n）:

yPleaseinputDelete_data:

hatmat,lat,jat,fat,eat,cat,bat,Insertnode（y/n）:

yPleaseinputInsert_data:

putposition:

5mat,lat,jat,fat,eat,put,cat,bat,请按任意键继续...示意图：

latjathatfateatcatbatmatNULLheadlatjathatfateatcatbatmatheadlatjatfateatputcatbatmatheadNULLNULL心得体会：

本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。

另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。

实验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//若左右深度为0，即为叶子。

return（max+1）;}elsereturn（0）;}//====利用“先进先出“（FIFO）队列，按层次遍历二叉树==========voidLevelorder（BinTreeT）{intfront=0,rear=1;BinTNode*cq[Max],*p;//定义结点的指针数组cqcq[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==0elsereturnhl+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“,//输入菜单序号（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:

PreorderTraversal2:

IorderTraversal3:

Postordertraversal4:

PostTreeDepth,Nodenumber,Leafnumber5:

LevelDepth0:

Exit*******************************1PrintBin_treePreorder:

ABDCEF2PrintBin_TreeInorder:

DBAECF3PrintBin_TreePostorder:

DBEFCA4BinTreeDepth=3BinTreeNodenumber=6BinTreeLeafnumber=35LevePrintBin_Tree:

ABCDEF0Pressanykeytocontinue二叉树示意图ABFEDC心得体会：

这次实验加深了我对二叉树的印象，尤其是对二叉树的各种遍历操作有了一定的了解。

同时认识到，在设计程序时辅以图形化的描述是非常有用处的。

实验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“,//输入顶点数和边数scanf（“%c“,printf（“InputVertexstring:

“）;for（i=0;in;i++）{scanf（“%c“,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“,//输入边（Vi，Vj）的顶点序号G->edges[i][j]=1;G->edges[j][i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句}}//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：

深度优先遍历的递归算法======voidDFSM（MGraph*G,inti）{//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵intj;printf（“%c“,G->vexs[i]）;//访问顶点Vivisited[i]=TRUE;//置已访问标志for（j=0;jn;j++）//依次搜索Vi的邻接点if（G->edges[i][j]==1//（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点}voidDFS（MGraph*G）{inti;for（i=0;in;i++）visited[i]=FALSE;//标志向量初始化for（i=0;in;i++）if（!

visited[i]）//Vi未访问过DFSM（G,i）;//以Vi为源点开始DFS搜索}//===========BFS：

广度优先遍历=======voidBFS（MGraph*G,intk）{//以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索inti,j,f=0,r=0;intcq[MaxVertexNum];//定义队列for（i=0;in;i++）visited[i]=FALSE;//标志向量初始化for（i=0;in;i++）cq[i]=-1;//队列初始化printf（“%c“,G->vexs[k]）;//访问源点Vkvisited[k]=TRUE;cq[r]=k;//Vk已访问，将其入队。

注意，实际上是将其序号入队while（cq[f]!

=-1）{//队非空则执行i=cq[f];f=f+1;//Vf出队for（j=0;jn;j++）//依次Vi的邻接点Vjif（G->edges[i][j]==1//访问Vjvisited[j]=TRUE;r=r+1;cq[r]=j;//访问过Vj入队}}}//==========main=====voidmain（）{inti;MGraph*G;G=（MGraph*）malloc（sizeof（MGraph））;//为图G申请内存空间CreatMGraph（G）;//建立邻接矩阵printf（“PrintGraphDFS:

“）;DFS（G）;//深度优先遍历printf（“\n“）;printf（“PrintGraphBFS:

“）;BFS（G,3）;//以序号为3的顶点开始广度优先遍历printf（“\n“）;}2．邻接链表作为存储结构#include“stdio.h“#include“stdlib.h“#defineMaxVertexNum50//定义最大顶点数typedefstructnode{//边表结点intadjvex;//邻接点域structnode*next;//链域}EdgeNode;typedefstructvnode{//顶点表结点charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中当前顶点数和边数}ALGraph;//图类型//=========建立图的邻接表=======voidCreatALGraph（ALGraph*G）{inti,j,k;chara;EdgeNode*s;//定义边表结点printf（“InputVertexNum（n）andEdgesNum（e）:

“）;scanf（“%d,%d“,//读入顶