3．从森林中删除选取的两棵树，并将新树加入森林； 4．重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。 由已形成的哈夫曼树求哈夫曼编码： 对每个叶结点都进行如下的处理：
扫描由叶结点到根结点的各条分支，若分支中的当前结点与双亲结点是左支关系，则生成编码0，若分支中的当前结点与双亲结点是右支关系，则生成编码1，由此生成的二进制码的序列即为该结点的哈夫曼编码。
思考题
1．用非递归算法实现二叉树的前序、中序和后序遍历； 2．设计一个哈夫曼编码器的译码系统。
实验4 图的遍历的实现
实验编号 JX020101-04 所属院系 计算机科学与技术 所属年级 2012-03 所属课程 数据结构试验
实验目的
1．掌握图的邻接矩阵、邻接表的表示方法。 2．掌握建立图的邻接矩阵的算法。 3．掌握建立图的邻接表的算法。
4．加深对图的理解，逐步培养解决实际问题的编程能力。
实验要求
实验环境
硬件平台：计算机CPU 主频2.0G以上；内存128兆以上； 软件平台：Windows2003或以上版本，Visual C++6.0
实验内容
1．建立图的邻接矩阵、邻接表。
2．对建立好的邻接矩阵表示的图进行深度优先搜索遍历。
实验步骤
实验指导
1．图的结构定义
#define VMAX 30 /*图中最多顶点数*/
typedef struct node /*邻接表中链表的结点类型*/ {
int vno; /*邻接顶点的顶点序号*/ struct node *next; /*后继邻接顶点*/ }EdgeNode;
typedef EdgeNode *lgraph[VMAX]; /*邻接表类型*/
typedef int mgraph[VMAX][VMAX]; /*邻接矩阵类型*/
int visited[VMAX]; /*访问标志*/
int queue[VMAX]; /*广度优先搜索遍历存储队列*/
2．函数定义
int create_graph(lgraph lg,mgraph mg)
/*输入无向图的边，建立图的邻接表，邻接矩阵*/
void ldfs(lgraph g,int i) /*邻接表表示的图的深度优先搜索遍历*/ void lbfs(lgraph g,int s,int n) /*广度优先搜索遍历*/
3．主函数例 void main() {
lgraph lg; mgraph mg; int n,i;
n=create (lg,mg); /*调用create函数，建立图的邻接表、邻接矩阵*/ for(i=0;i visited[i]=0; /*置全部顶点未访问标志*/ printf(\邻接表表示的图的递归深度优先搜索遍历\ ldfs(lg,0); /*调用ldfs函数*/ printf(\邻接表表示的图的递归广度优先搜索遍历\ lbfs(lg,0,n); /*调用lbfs函数*/ printf(\} 思考题 1．图的遍历 2．最小生成树 实验5 哈希表设计 实验编号 JX020101-05 所属院系 计算机科学与技术 所属年级 2012-03 所属课程 数据结构试验 实验目的 1．熟悉有关哈希表的基本概念； 2．熟悉构造哈希表的方法； 3．掌握哈希冲突的处理方法。 实验要求 实验环境 硬件平台：计算机CPU 主频2.0G以上；内存128兆以上； 软件平台：Windows2003或以上版本，Visual C++6.0 实验内容 对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。 实验步骤 实验指导 1．开放定址哈希表的存储结构 /* HashTableDef.h 开放定址哈希表的存储结构 */ int hashsize[]={11,19,29,37}; /* 哈希表容量递增表，一个合适的素数序列 */ int m=0; /* 哈希表表长，全局变量 */ struct HashTable { ElemType *elem; /* 数据元素存储基址，动态分配数组 int count; /* 当前数据元素个数 */ int sizeindex; // hashsize[sizeindex]为当前容量 }; 2．函数的定义 /* 哈希函数的基本操作 */ Status InitHashTable(HashTable &H) /* 操作结果: 构造一个空的哈希表 */ void DestroyHashTable(HashTable &H) /* 初始条件: 哈希表H存在。操作结果: 销毁哈希表H */ unsigned Hash(KeyType K) /* 一个简单的哈希函数(m为表长，全局变量) */ void collision(int &p,int d) // 线性探测再散列 /* 开放定址法处理冲突 */ Status SearchHash(HashTable H,KeyType K,int &p,int &c) /* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 */ Status InsertHash(HashTable &,ElemType); /* 对函数的声明 */ void RecreateHashTable(HashTable &H) // 重建哈希表 /* 重建哈希表 */ Status InsertHash(HashTable &H,ElemType e) /* 查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK； */ /* 若冲突次数过大，则重建哈希表，算法9.18 */ void TraverseHash(HashTable H,void(*Vi)(int,ElemType)) /* 按哈希地址的顺序遍历哈希表 */ Status Find(HashTable H,KeyType K,int &p) /* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 元素在表中位置,并返回SUCCESS;否则,返回UNSUCCESS */ 思考题 采用除留余数法定义哈希表来建立相应的哈希表和完成查找过程