《2016暑_算法与数据结构综合训练_第一阶段_任务安排.docx》由会员分享，可在线阅读，更多相关《2016暑_算法与数据结构综合训练_第一阶段_任务安排.docx（3页珍藏版）》请在三一文库上搜索。
1、2016 年信 1405-1、2 班 算法与数据结构综合训练 安排第一阶段：基本算法演示程序【时间安排】2016 暑季学期2016 暑季学期2016 暑季学期7.47.57.6周一周二周三5-8 节5-8 节5-8 节【检查时间】2016 暑季学期 7.6 周三 开始，每组挑选 1 人进行演示说明。【任务内容】要求分组实现 KMP 模式匹配算法、哈夫曼编码算法、由遍历序列恢复二叉树、Prim 算法、Kruskal 算法、Floyd 算法、Dijkstra 算法、拓扑排序、关键路径算法、二叉排序树生成算法（含平衡化）、哈希表生成及哈希查找算法、希尔排序、快速排序、堆排序、归并排序、基数排序。（四
2、则表达式计算、矩阵运算、有向图的强连通分量求解）演示算法检查要求：要求人工输入数据或从文件读入数据，检查测试结果，具体要求如下：1、 KMP 模式匹配算法输入：模式串，主串功能要求：输出模式串的 next 值表，输出匹配结果2、哈夫曼编码算法输入：字符及其权值，待译码字符串，待解码字符串功能要求：输出各字符的哈夫曼编码，输出译码字符串，输出解码字符串3、由遍历序列恢复二叉树输入：遍历序列功能要求：输出二叉树形态或输出二叉树的三种遍历序列4、Prim 算法输入：无向图（顶点序列，边序列）功能要求：输出最小生成树的各组成边及最小生成树的权值5、Kruskal 算法输入：无向图（顶点序列，边序列）功
3、能要求：输出最小生成树的各组成边及最小生成树的权值6、Floyd 算法输入：有向图（顶点序列，有向边序列）功能要求：输出各顶点对间最短路径和路径长度7、Dijkstra 算法输入：有向图（顶点序列，有向边序列），起始顶点功能要求：输出起始顶点到其它各顶点的最短路径和路径长度8、拓扑排序输入：有向图（顶点序列，有向边序列）功能要求：能判断是否是 AOV 网；输出有效的拓扑排序序列9、关键路径算法输入：有向图（顶点序列，有向边序列）功能要求：能判断是否是 AOE 网；输出各关键活动或输出关键路径（包括关键路径的长度）10、二叉排序树生成算法（含平衡化）输入：待排序数据序列功能要求：输出平衡的二叉排
4、序树的形态或输出二叉树的三种遍历序列11、哈希表生成及哈希查找算法输入：待哈希数据序列功能要求：输出哈希方法和解决冲突的方法（文字输出），输出哈希表12、希尔排序输入：待排序数据序列功能要求：输出每步骤的步长和排序情况；希望能进行排序方向的选择（从大到小或从小到大）13、快速排序输入：待排序数据序列功能要求：输出每步骤的枢轴选择和排序情况；希望能进行排序方向的选择（从大到小或从小到大）14、堆排序输入：待排序数据序列功能要求：输出每步骤排序情况；希望能进行排序方向的选择（从大到小或从小到大）15、归并排序输入：待排序数据序列功能要求：输出每步骤排序情况；希望能进行排序方向的选择（从大到小或从小
5、到大）16、基数排序输入：待排序数据序列功能要求：输出每步骤排序情况；希望能进行排序方向的选择（从大到小或从小到大）17、四则表达式计算输入：中缀表达式功能要求：输出后缀表达式和计算结果18、矩阵运算输入：待运算矩阵功能要求：输出矩阵加法、减法和乘法的运算结果19、有向图的强连通分量求解输入：有向图（顶点序列，有向边序列）功能要求：输出各强连同分量的顶点序列和有向边序列【分组要求及成绩说明】1、自由分组，要求 5 人 1 组，组长 1 名（要求专业基础突出）每组四人，组长合理平均分配任务；组长负责将各程序整合成统一的演示程序以供检查；2、算法中要求的链表结构和数组结构的基本操作要求单独函数实现（同组内算法要求共享使用）。3、要求数据结构基本算法演示程序具有菜单选择，算法要有结果的显示形式，显示程序框架由组长负责实现。请在菜单上显示出算法编写者姓名，以便检查。每组提交一份实习报告，内容包括任务分工说明，程序源代码及注释，数据测试及说明等。4、 每人的成绩由所负责算法的程序实现情况和本组集体得分综合给出。