数据结构(C语言版)实验报告 下载本文

printf(\ printf(\ printf(\ printf(\ printf(\ printf(\按层次遍历之前,先选择4,求出该树的结点数。 printf(\ printf(\ fflush(stdin); scanf(\ //输入菜单序号(0-5) switch (i-'0'){ case 1: printf(\ Preorder(root); //先序遍历 break; case 2: printf(\ Inorder(root); //中序遍历 break; case 3: printf(\ Postorder(root); //后序遍历 break; case 4: depth=TreeDepth(root); //求树的深度及叶子数 printf(\ BinTree Node number=%d\ printf(\ BinTree Leaf number=%d\ break; case 5: printf(\ Levelorder(root); //按层次遍历 break; default: exit(1); } printf(\ } while(i!=0); }

实验结果:

Creat Bin_Tree; Input preorder:ABD###CE##F## ********** select ************ 1: Preorder Traversal 2: Iorder Traversal 3: Postorder traversal 4: PostTreeDepth,Node number,Leaf number

5: Level Depth 0: Exit ******************************* 1 Print Bin_tree Preorder: ABDCEF 2 Print Bin_Tree Inorder: DBAECF

3 Print Bin_Tree Postorder: DBEFCA

4 BinTree Depth=3 BinTree Node number=6 BinTree Leaf number=3 5 LevePrint Bin_Tree: ABCDEF 0 Press any key to continue 二叉树示意图

A B C D E F

心得体会:

这次实验加深了我对二叉树的印象,尤其是对二叉树的各种遍历操作有了一定的了解。同时认识到,在设计程序时辅以图形化的描述是非常有用处的。

实验3

实验题目:图的遍历操作

实验目的:

掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。

实验要求:

采用邻接矩阵和邻接链表作为图的存储结构,完成有向图和无向图的DFS和BFS操作。

实验主要步骤:

设计一个有向图和一个无向图,任选一种存储结构,完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。

1. 邻接矩阵作为存储结构 #include\#include\

#define MaxVertexNum 100 //定义最大顶点数 typedef struct{

char vexs[MaxVertexNum]; //顶点表

int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵,可看作边表 int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) {

int i,j,k; char a;

printf(\

scanf(\输入顶点数和边数 scanf(\ printf(\ for(i=0;in;i++) {

scanf(\

G->vexs[i]=a; //读入顶点信息,建立顶点表 }

for(i=0;in;i++) for(j=0;jn;j++)

G->edges[i][j]=0; //初始化邻接矩阵 printf(\

for(k=0;ke;k++) { //读入e条边,建立邻接矩阵 scanf(\输入边(Vi,Vj)的顶点序号

G->edges[i][j]=1;

G->edges[j][i]=1; //若为无向图,矩阵为对称矩阵;若建立有向图,去掉该条语句 } }

//=========定义标志向量,为全局变量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum];

//========DFS:深度优先遍历的递归算法====== void DFSM(MGraph *G,int i)

{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索,邻接矩阵是0,1矩阵 int j;

printf(\访问顶点Vi visited[i]=TRUE; //置已访问标志

for(j=0;jn;j++) //依次搜索Vi的邻接点 if(G->edges[i][j]==1 && ! visited[j])

DFSM(G,j); //(Vi,Vj)∈E,且Vj未访问过,故Vj为新出发点 }

void DFS(MGraph *G) {

int i;

for(i=0;in;i++)

visited[i]=FALSE; //标志向量初始化 for(i=0;in;i++)

if(!visited[i]) //Vi未访问过

DFSM(G,i); //以Vi为源点开始DFS搜索 }

//===========BFS:广度优先遍历======= void BFS(MGraph *G,int k)

{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j,f=0,r=0;

int cq[MaxVertexNum]; //定义队列 for(i=0;in;i++)

visited[i]=FALSE; //标志向量初始化 for(i=0;in;i++)

cq[i]=-1; //队列初始化 printf(\访问源点Vk visited[k]=TRUE;

cq[r]=k; //Vk已访问,将其入队。注意,实际上是将其序号入队 while(cq[f]!=-1) { //队非空则执行 i=cq[f]; f=f+1; //Vf出队

for(j=0;jn;j++) //依次Vi的邻接点Vj

if(G->edges[i][j]==1 && !visited[j]) { //Vj未访问 printf(\访问Vj visited[j]=TRUE;

r=r+1; cq[r]=j; //访问过Vj入队 } } }

//==========main===== void main() {

int i; MGraph *G;

G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间 CreatMGraph(G); //建立邻接矩阵 printf(\

DFS(G); //深度优先遍历 printf(\

printf(\

BFS(G,3); //以序号为3的顶点开始广度优先遍历 printf(\}

2. 邻接链表作为存储结构 #include\#include\

#define MaxVertexNum 50 //定义最大顶点数 typedef struct node{ //边表结点 int adjvex; //邻接点域 struct node *next; //链域 }EdgeNode;

typedef struct vnode{ //顶点表结点 char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 }VertexNode;

typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型 typedef struct {

AdjList adjlist; //邻接表

int n,e; //图中当前顶点数和边数 } ALGraph; //图类型 //=========建立图的邻接表======= void CreatALGraph(ALGraph *G) {

int i,j,k; char a;

EdgeNode *s; //定义边表结点

printf(\

scanf(\读入顶点数和边数