数据结构实验三 树的遍历生成树
广州大学学生实验报告
开课实验室：计算机科学与工程实验（电子楼418A） 2019年4月19日
|
学院 |
计算机科学与教育软件学院 |
年级、专业、班 |
计算机科学与技术 |
姓名 |
|
学号 |
|
|
|
实验课程名称 |
数据结构实验 |
成绩 |
|
|||||
|
实验项目名称 |
实验三 树的的遍历生成树 |
指导老师 |
玲 |
|||||
|
一、实验目的 1、把图转化为程序能识别的邻接矩阵； 2、理解图的遍历方法及对应的生成树。 二、使用仪器、器材 微机一台 操作系统：Win10 编程软件：C++ 三、实验内容及原理 1．图的输入：邻接矩阵直接写入源程序，或键盘输入，或读入数据文件 起始结点的输入：运行时由键盘输入 输出：生成树的边，用结点的序偶表示，
GRAPH.H #pragma once //图的邻接表存储结构 #define INF 32767 //定义∞ #define MAXV 100 //最大顶点个数 #define MAX 100 //最大全局数组 #define MaxSize 100 typedef char InfoType; typedef int ElemType; typedef struct ANode { int adjvex; struct ANode *nextarc; int weight; }ArcNode; typedef struct Vnode { char info; ArcNode *firstarc; }VNode; typedef struct { VNode adjlist[MAXV]; int n, e; }AdjGraph; //环形队列 typedef struct { ElemType data[MaxSize]; int front, rear; //队首和队尾指针 } SqQueue;
void CreateAdj(AdjGraph* &G, int A[MAXV][MAXV], int n, int e);//创建图的邻接表 void DispAdj(AdjGraph*G);//输出邻接表 void DestroyAdj(AdjGraph *&G);//销毁邻接表 void DFS(AdjGraph* G, int v);//深度优先遍历生成树
//--------------------------------------------------------- //--广度优先遍历中使用队列的基本运算算法------------------- //--------------------------------------------------------- void InitQueue(SqQueue *&q); void DestroyQueue(SqQueue *&q); bool QueueEmpty(SqQueue *q); bool enQueue(SqQueue *&q, ElemType e);//进栈 bool deQueue(SqQueue *&q, ElemType &e); //---------------------------------------------------------
void BFS(AdjGraph *G, int v);//广度优先遍历生成树 GRAPH.CPP #include"pch.h" #include "graph.h" #include"malloc.h" #include<iostream> using namespace std;
void CreateAdj(AdjGraph *& G, int A[MAXV][MAXV], int n, int e) { int i, j; ArcNode *p;
for (i = 0; i < n; i++) //给邻接表中所有头节点指针置初值 { G->adjlist[i].firstarc = NULL; } for (i = 0; i < n; i++) //检查邻接矩阵每个元素 { for (j = n - 1; j >= 0; j--) { if (A[i][j] != 0 && A[i][j] != INF) //存在一条边 { p = (ArcNode*)malloc(sizeof(ArcNode)); //创建一个结点p p->adjvex = j; // 存放邻接点 p->weight = A[i][j]; //存放权 p->nextarc = G->adjlist[i].firstarc; //头插法 G->adjlist[i].firstarc = p; } } } G->n = n; G->e = e; }
void DispAdj(AdjGraph * G) { int i; ArcNode *p; for (i = 0; i < G->n; i++) { p = G->adjlist[i].firstarc; printf("%3d: ", i); while (p != NULL) { printf("%3d[%d]→", p->adjvex, p->weight); p = p->nextarc; } printf("∧\n"); } }
void DestroyAdj(AdjGraph *& G) { int i; ArcNode *pre, *p; for (i = 0; i < G->n; i++) //扫描所有的单链表 { pre = G->adjlist[i].firstarc; //p指向第i个单链表的首结点 if (pre != NULL) { p = pre->nextarc; while (p != NULL) //释放第i个单链表的所有边结点 { free(pre); pre = p; p = p->nextarc; } free(pre); } } free(G); //释放头结点数组 }
int visited[MAX] = { 0 }; void DFS(AdjGraph* G, int v) //深度优先遍历 { ArcNode*p; visited[v] = 1; //置已访问标记 //cout << v << endl; //输出被访问顶点的编号 p = G->adjlist[v].firstarc; //p指向顶点v的第一个邻接点 while (p != NULL) { if (visited[p->adjvex] == 0) { cout << "(" << v << "," << p->adjvex << ")" << endl; DFS(G, p->adjvex); } p = p->nextarc; //p指向顶点v的下一个邻接点 } }
void InitQueue(SqQueue *& q) { q = (SqQueue *)malloc(sizeof(SqQueue)); q->front = q->rear = 0; }
void DestroyQueue(SqQueue *& q) { free(q); }
bool QueueEmpty(SqQueue * q) { return(q->front == q->rear); }
bool enQueue(SqQueue *& q, ElemType e) { if ((q->rear + 1) % MaxSize == q->front) //队满上溢出 return false; q->rear = (q->rear + 1) % MaxSize; q->data[q->rear] = e; return true; }
bool deQueue(SqQueue *& q, ElemType & e) { if (q->front == q->rear) //队空下溢出 return false; q->front = (q->front + 1) % MaxSize; e = q->data[q->front]; return true; }
void BFS(AdjGraph * G, int v) //广度优先遍历 { int w, i; ArcNode *p; SqQueue *qu; //定义环形队列指针 InitQueue(qu); //初始化队列 int visited[MAXV]; //定义顶点访问标志数组 for (i = 0; i < G->n; i++) visited[i] = 0; //访问标志数组初始化 //printf("%2d ", v); //输出被访问顶点的编号 visited[v] = 1; //置已访问标记 enQueue(qu, v); while (!QueueEmpty(qu)) //队不空循环 { deQueue(qu, w); //出队一个顶点w p = G->adjlist[w].firstarc; //指向w的第一个邻接点 while (p != NULL) //查找w的所有邻接点 { if (visited[p->adjvex] == 0) //若当前邻接点未被访问 { cout << "(" << w << "," << p->adjvex << ")" << endl; //printf("%2d ", p->adjvex); //访问该邻接点 visited[p->adjvex] = 1; //置已访问标记 enQueue(qu, p->adjvex); //该顶点进队 } p = p->nextarc; //找下一个邻接点 } } printf("\n"); }
MAIN.CPP
#include "pch.h" #include <iostream> #include"graph.h" using namespace std;
int main() { AdjGraph *G=new AdjGraph; int A[MAXV][MAXV] = { {0,1,1,1,0,0,0,0,0,0,0},{1,0,0,0,1,1,0,0,0,0,0}, {1,0,0,1,0,1,1,0,0,0,0},{1,0,1,0,0,0,0,1,0,0,0}, {0,1,0,0,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0}, {0,0,1,0,0,0,0,1,1,1,0},{0,0,0,1,0,0,1,0,0,0,1}, {0,0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0,0,0}, {0,0,0,0,0,0,0,1,0,0,0} } ; int n = 11, e = 12; CreateAdj(G, A, n, e); //建立《教程》中图8.1(a)的邻接表 //printf("图G的邻接表:\n"); //DispAdj(G); //输出邻接表G cout << "请输入起始结点" << endl; int a; cin >> a; printf("深度优先序列(递归)生成树:"); printf("\n"); DFS(G, a); printf("\n"); printf("广度优先序列生成树:"); printf("\n"); BFS(G, a); printf("\n"); DestroyAdj(G); //销毁邻接表 return 1; }
五、实验结果及分析 从3出发，分别进行深度优先生成树和广度优先生成树。 |
||||||||
|
从0出发，分别进行深度优先生成树和广度优先生成树。
|
||||||||