实验三 归并排序的分治策略设计（4学时）
[实验目的]
１. 熟悉二分检索问题的线性结构表示和二分检索树表示; ２. 熟悉不同存储表示下求解二分检索问题的递归算法设计; ３. 通过实例转换, 掌握将递归算法转换成迭代算法的方法;
４. 掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略.
[预习要求]
１. 认真阅读算法设计教材和数据结构教材内容, 熟悉不同存储表示下求解二分检索问
题的原理或方法;
２. 针对线性结构表示和二分检索树表示设计递归算法;
３. 参考教材和课堂教学内容, 根据将递归算法转换成迭代算法的一般步骤将二分检索
递归算法转换成相应的迭代算法.
[算法或程序设计参考]
线性结构
int data[10]={ /* 10个互异的、无序的原始整数 */ }; typedef struct { int s[100]; int top;} STACK;
int Partition(int *data, int low, int high)
功能: 将data[low, high]进行快速分类划分, 返回枢轴记录关键字的位置索引. int QSort1(int *data, int low, int high)
功能: 将data[low, high]进行快速分类的递归算法. int QSort2(int *data, int low, int high)
功能: 将data[low, high]进行快速分类的迭代算法. int BSearch1(int *data, int key)
功能: 在data数组中检索key的二分检索递归算法, 成功时返回位置索引, 否则返回-1. int BSearch2(int *data, int key)
功能: 在data数组中检索key的二分检索迭代算法, 成功时返回位置索引, 否则返回-1. 树结构
typedef struct NODE{ int key; struct NODE *lch, *rch; }TNODE, *BT;
typedef struct Parameters { BT *t; int key; BT f; BT *p } PARA; typedef struct { PARA s[100]; int top;} STACK; int InsertBT(BT *t, int key)
功能: 在二分检索树t中插入关键字为key的元素, 成功时返回1, 否则返回0.
int TSearch1(BT *t, int key, BT f, BT *p)
功能: 用递归算法在二分检索树t中查找关键字为key的元素, 成功时返回1, p指向该元素节点, 否则p指向查找路径上最后一个节点并返回0, f指向t的双亲, 其初始调用值为NULL.
int TSearch2(BT *t, int key, BT f, BT *p)
功能: 用迭代算法在二分检索树t中查找关键字为key的元素, 成功时返回1, p指向该元素节点, 否则p指向查找路径上最后一个节点并返回0, f指向t的双亲, 其初始调用值为NULL.
[实验步骤]
1. 调试线性结构表示下的快速分类与二分检索递归程序, 直至正确为止; 2. 调试线性结构表示下的快速分类与二分检索迭代程序, 直至正确为止; 3. 待各功能子程序调试完毕, 去掉测试程序, 将程序整理成功能模块存盘备用.
[实验报告要求]
1. 阐述实验目的和实验内容; 2. 提交实验程序的功能模块;
3. 阐述将递归算法改写成迭代算法的一般方法;
4. 用类C语言阐述分治法递归与迭代实现抽象控制策略.
[思考与练习]
1. 怎样优化由递归程序改写的迭代程序?
2. 设计二分检索树的构造与检索递归程序, 并将其改写成相应的迭代算法。
实验四 哈夫曼编码的贪心算法设计（4学时）
[实验目的]
１. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; ２. 编程实现哈夫曼编译码器; ３. 掌握贪心算法的一般设计方法。
[预习要求]
1. 认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理; 2. 设计和编制哈夫曼编译码器。
[参考数据类型或变量]
typedef ElemType char； typedef struct node{ int w; int flag; ElemType c;
struct node *plink,*llink,*rlink; char code[m];
}Node;
Node *num[n], *root;
[参考子程序接口与功能描述]
void SetTree( NODE *root )
功能: 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树 void EnCode( Node *p )
功能: 利用已建好的哈夫曼树，对输入的正文进行编码 void DeCode( void )
功能: 利用已建好的哈夫曼树，将输入的代码进行译码
[实验步骤]
1. 设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止; 2. 设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止; 3. 设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止; 4. 将你的程序整理成功能模块存盘备用。
[实验报告要求]
1. 阐述实验目的和实验内容; 2. 提交实验程序的功能模块; 3. 记录最终测试数据和测试结果。
[思考题]
1.
试证明哈夫曼问题具有贪心选择性质；
试证明哈夫曼问题具有最优子结构性质。
实验五 Kruskal算法的设计（4学时）
[实验目的]
１. 根据算法设计需要, 掌握连通网的灵活表示方法; ２. 掌握最小生成树的Kruskal算法; ３. 基本掌握贪心算法的一般设计方法; ４. 进一步掌握集合的表示与操作算法的应用.
[预习要求]
１. 认真阅读算法设计教材和数据结构教材内容, 熟习连通网的不同表示方法和最小生
成树算法;
２. 设计Kruskal算法实验程序.
[参考数据类型或变量]
typedef NodeNumber int; /* 节点编号 */ typedef CostType int; /* 成本值类型 */
typedef ElemType NodeNumber /* 实型或任意其它元素类型 */
typedef struct { int ElemType; int tag; }NODE;
typedef struct { CostType cost; NodeNumber node1, node2; }EDGE; NODE set[]={{1,-1},…,{n,-1}}; /* 节点集, n为连通网的节点数 */
EDGE es[ ]={{values of e1},…,{ values of em}}; /* 边集, m为连通网的边数 */ EDGE st[n-1]; /* 最小生成树的边集 */
[参考子程序接口与功能描述]
int Find(NODE *set, ElemType elem)
功能: 在数组set中顺序查找元素elem, 如果不成功, 返回-1; 否则, 使用带压缩规则的
查找算法,返回所在子集的根节点索引.
int Union(NODE *set, ElemType elem1, ElemType elem2)
功能: 应用Find算法首先找到elem1和elem2所在的子集, 然后应用带加权规则的并运算算法合并两个子集. 不成功时, 返回-1; 否则, 返回并集的根节点索引.
void Sort(EDGE *es, int n)
功能: 用任意分类算法将连通图的边集按成本值的非降次序分类. void Kruskal(EDGE *es, int m, NODE *set, int n, EDGE *st)
功能: 对有n个节点, m条边的连通网, 应用Kruskal算法生成最小生成树, 最小生成树
的边存储在数组st中.
void Output(EDGE *st, int n) 功能: 输出最小生成树的各条边.
[实验步骤]
1. 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止; 2. 待各功能子程序调试完毕, 去掉测试程序, 将你的程序整理成功能模块存盘备用.
[实验报告要求]
1. 阐述实验目的和实验内容; 2. 阐述Kruskal算法的原理方法; 3. 提交实验程序的功能模块; 4. 提供测试数据和相应的最小生成树.
[思考与练习]
1. 设计由连通网初始边集数组生成最小堆的算法; 2. 设计输出堆顶元素, 并将剩余元素调整成最小堆的算法; 3. 针对连通网初始边集最小堆表示, 设计Kruskal算法;
4. 采用成本邻接矩阵表示连通网时, 在剩余边中如何实现最小成本边的查找? 采用成本邻接矩阵表示连通网时, 用C语言实现Prim算法.