二叉树的应用及图的创建和遍历一、 实验目的1. 熟练掌握二叉树的应用2. 理解图的抽象数据类型的定义，及在C语言环境中的表示方法。3. 理解图的基本操作的算法，及在C语言环境中一些主要基本操作的实现。 4. 在C语言环境下实现图的应用操作： 使用邻接矩阵存储结构，实现无向网的创建和输出。使用邻接表存储结构，实现无向网的创建和输出 利用基本操作集，实现采用邻接表表示的无向图的非递归的广度优先遍历算法二、 实验内容1.构造haffman树，并求haffman编码（P97,14题中数据为主程序代码#include #define HUGE 999#define N 8#define M 2*N-1struct HuffmanNodeint weight;int parent;int left;int right;struct HuffmanCodeint bitN;int start;int weight=2,3,5,7,11,13,17,19,0,0,0,0,0,0,0; /将各个顶点权值赋给数组struct HuffmanNode HTM; /通过改变权值，可以构造不同的struct HuffmanCode HCN; /哈弗曼树void init() /只有一个循环，时间复杂度为o(M)int i;for(i=0;iM;i+)HTi.parent=-1;HTi.weight=weighti;HTi.left=-1;HTi.right=-1; int minimum() /时间复杂度为o(M) int i,k; int min=HUGE; for(i=0;iweighti&weighti!=0) min=weighti; k=i; weightk=HUGE; return k; void huffmantree() /时间复杂度为o(M-N) int i,l,r; for(i=N;iM;i+) l=minimum(); r=minimum(); HTl.parent=i; HTr.parent=i; HTi.left=l; HTi.right=r; HTi.weight=HTl.weight+HTr.weight; weighti=HTi.weight; void huffmancode() /循环嵌套，时间复杂度为o(N2) int i,p,j,c; struct HuffmanCode cd; for(i=0;iN;i+) cd.start=N-1; c=i; p=HTc.parent; while(p!=0) if(HTp.left=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=HTc.parent; for(j=cd.start+1;jN;j+) HCi.bitj=cd.bitj; HCi.start=cd.start; int main() int i,j; init(); huffmantree(); for(i=0;iM;i+) printf(%5d%5d%5d%5dn,HTi.weight,HTi.parent,HTi.left,HTi.right); printf(n); huffmancode(); for(i=0;iN;i+) printf(%5d: ,HTi.weight); for(j=HCi.start+2;jN;j+) printf(%d ,HCi.bitj); printf(n); n 关键部分加注释(见源代码注释）n 执行结果n 算法分析(见源代码注释）2.无向图创建和输出（邻接矩阵）程序代码#include #include #include#define MAXSIZE 999#define N 6int visitedN=0,0,0,0,0,0;int martixNN;void setup() /创建一个无向网 int u,v,i,j,w; /u,v为顶点数字，w为权值 printf(请输入相邻顶点和权值:n);for(i=0;iN;i+) /双循环，时间复杂度为o(N2)for(j=0;j=0)martixuv=w; /因为是无向网，呈对称分布martixvu=w;scanf(%d%d%d,&u,&v,&w);void print() /创建一个无向网int i,j; /双循环，时间复杂度为o(N2)for(i=0;iN;i+)for(j=0;j=N)printf(该顶点不在图中);exit(0);elsefor(j=0;jN;j+)printf(%4d,martixkj); int main()int n; setup();print();printf(请输入所要检索的顶点数字标号:n);scanf(%d,&n);lookfor(n);n 关键部分加注释(见源代码注释）n 执行结果n 算法分析(见源代码注释）3.无向图创建和输出（邻接表）源代码#include #include #include#define MAXVERTEX 100 struct node int vertex; struct node *next; ; struct node *adjlistMAXVERTEX;void setup(int n) /两个并列循环，时间复杂度均为o（n） int u,v,i; struct node *p; for(i=0;i=0) p=(struct node *)malloc(sizeof(struct node); p-vertex=v; p-next=adjlistu; adjlistu=p; scanf(%d%d,&u,&v); void print(int n) /输出邻接表 /设每个顶点平均边数为e，则时间复杂度为o(n*e)struct node *p;int i;for(i=0;ivertex);p=p-next;printf(n); void lookfor(int k,int n) /查找顶点是否在邻接表struct node *p;if(k=n)printf(该顶点不在图中);exit(0);elseprintf(%d,k);p=adjlistk;while(p!=NULL)printf(%d,p-vertex);p=p-next;int main() int n,i,k; printf(please input vertex number of graph:); scanf(%d,&n); setup(n); print( n);k=2;lookfor(k,n); n 关键部分加注释(见源代码注释）n 执行结果4.非递归广度优先遍历 源代码#include #include #include #define MAXSIZE 100#define MAXVERTEX 100 struct node int vertex; struct node *next; ;struct queueint elementMAXSIZE;int front;int rear; struct node *adjlistMAXVERTEX; int visitedMAXVERTEX; struct queue q; void init()q.front=q.rear=0; void inqueue(int x)q.rear=(q.rear+1)%MAXSIZE;q.elementq.rear=x; int outqueue() q.front=(q.front