发布时间 : 星期一 文章数据结构实习报告12345更新完毕开始阅读1f4d4353a300a6c30c229f71
}
BSTree(&T,stu[k]); }
printf(\信息输入完毕...\\n\
printf(\二叉排序树构建成功...\\n\
printf(\输入你想要在此二叉排序树中查找的学号：\scanf(\BTree s;
s=(BTree)malloc(sizeof(struct BinSTreeNode)); s=BSTreeSearch(T,x);
printf(\所查找的学生信息如下：\\n 学号\\t 姓名\\t成绩\\n\printf(\
3.4测试结果：
4构造n个城市连接的最小生成树
一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得
20
到的最小生成树的代价。基本要求： 1) 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)
4.1设计思路
本程序需要实现在一个具有权值的n个城市间的有向距离网中，通过调用函数建立最小生成树，并通过计算求得各个城市之间最小的权值。
在设计程序时通过gnode value数组直接对各个城市之间的信息进行设置，而不是手动输入。城市的个数也默认设置为6个，路的个数也只设置成十个，所以在程序运行时不需要输入城市的相关信息。由于能力不足，在最后打印两个城市之间最短路径时，只显示路径所经过的顶点，而不是一次经过的顶点。
4.2数据结构定义
本程序的主要内容是通过函数调用构建最小生成树，实现求的两个城市之间的最短路径，并通过函数调用打印出来最短路径所经过的顶点，所有本程序便定义了三个结构体，每个结构体的作用如下所示。以及这六个城市和十条边的图也在下面显示出来：
typedef char vertextype[7]; typedef char infoptr; typedef int vrtype;
typedef enum{DG,DN,UG,UN}graphkind; typedef struct { vrtype adj; //对于无权图，用1表示相邻，0表示不相邻，对于带权图，存储权值 infoptr *info; //与弧或边的相关信息 }arcnode,adjmatrix[max][max];
typedef struct //图的类型定义 { vertextype vex[max]; //用于存储顶点 adjmatrix arc; //邻接矩阵、存储边或弧的信息 int vexnum,arcnum; //顶点数和边（弧）的数目 graphkind kind; //图的类型
21
}mgraph;
typedef struct
{ //添加一个存储网的行、列和权值的类型定义 int row; int col; int weight; }gnode;
4.3系统功能模块
4.4 运行结果：
22
5哈夫曼编码的应用
（1）哈夫曼树的建立 （2） 哈夫曼编码的生成 （3） 编码文件的译码
5.1问题分析哈夫曼树的定义
1.哈夫曼树节点的数据类型定义为： typedef struct{ //赫夫曼树的结构体
char ch;
int weight; //权值 int parent,lchild,rchild;
}htnode,*hfmtree;
2）所实现的功能函数如下
1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树。此函数块调用了Select（）函数。
void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点 2、 int main()
主函数： 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入） 对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。 3、Encoding
编码功能：对输入字符进行编码 4、Decoding
译码功能： 利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat 中。
Print() 打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。 5.主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。 使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。
23