数据结构及算法分析.docVIP

《数据结构与算法分析》 ――课程内容体系主要内容 教学单元模块 具体教学内容 绪论 绪论部分是全书的预备知识，主要对ADL语言、数据结构与算法、算法分析基础、OOP、和C++做了简单介绍 基本数据结构 基本数据结构部分包括线性表、堆栈与队列、数组、字符串、整数集合类、树（包括AVL树、伸展树等）、图（包括网络流等问题的讨论）、散列（Hash）等 典型算法 典型算法部分主要介绍了若干典型算法的实现，并给出必要的复杂性分析和比较过程，具体包括递归、排序、查找和内存管理等 复杂数据结构 复杂数据结构部分主要包括优先级队列、不相交集合类和文件结构等 算法设计技巧 典型算法设计技巧的介绍，主要包括贪婪算法、分治算法、动态规划、回溯算法和随机化算法等 应用 应用部分是上述数据结构和典型算法的一些应用示例，具体包括事件驱动模拟、等价类、残缺棋盘和图象压缩等问题的讨论，在课时允许的情况下还会介绍摊还分析、红黑树等 《数据结构与算法分析》 课程实践内容体系主要内容 实践教学单元模块 实践教学基本要求 实践教学具体内容 趣味程序设计实践 1.熟悉编程环境复习C语言程序设计的基本内容.随机产生n个整数，然后用一种排序算法将它们从小到大排序。.试编一程序，用贪心法求解一般的着色问题。链表应用实验1.熟悉链表结构 2掌握链表结构上的各种操作 3学会运用链表结构求解问题1.试将本章介绍的两种Josephus问题的求解过程在计算机中实现，实现时要求输出的不是整数，而是实际的人名。2.设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的指针。请写出并在计算机上实现将这两个链表合并为一个带头结点的有序循环链表的算法。栈与队列应用实验熟悉栈和队列结构 掌握栈和队列结构上的各种操作 学会运用栈和队列结构求解问题1. 设计实现一个求解n阶Hanoi塔问题提示：将n个圆盘由A依次移到C，B作为辅助塔座。当n=1时，可以直接完成。否则，将塔座A顶上的n-1个圆盘移动到塔座B上，用塔座C作为辅助塔座；然后移第n个圆盘；最后将塔座B上的n-1个圆盘移到塔座C上，并用塔座A作为辅助塔座。2. 根据介绍的思想，设计并实现一个对简化表达式求值的系统。3. 在上模拟农夫过河问题的解。文本文件检索实验1.熟悉字符串的操作 2学会运用字符串的操作进行文本检索和查询。1. 根据课堂介绍设计实现KMP算法 2. 试设计一个简单的文本编辑器，使之具有对字符串的输入、输出、插入、删除、查找和替换等功能 稀疏矩阵和广义表实验1．熟悉稀疏矩阵和广义表结构 2．掌握稀疏矩阵和广义表结构上的各种操作 3．学会运用稀疏矩阵和广义表结构求解问题1. 设计实现两个普通矩阵相乘的算法 2. 实现用三元组表示法实现稀疏矩阵相加及转置算法 3. 设计实现两个N次一元多项式相加的算法程序 树结构实验1.熟悉树和二叉树结构 2掌握树和二叉树结构上的各种操作 3学会运用树和二叉树结构求解问题1. 设计一个程序，根据二叉树的先根序列和对称序序列创建一棵用左右指针表示的二叉树2. 根据哈夫曼算法创建哈夫曼树，求树中每个外部结点的编码3. 设计一个程序，把中缀表达式转换成一棵二叉树，然后通过后序遍历计算表达式的值图结构实验1.熟悉图结构 2掌握图结构上的各种操作 3学会运用图结构求解问题采用两种不同的图的表示方法，实现拓扑排序和关键路径的求解过程。使用实现的算法对于所示的AOE网，求出各活动的可能的最早开始时间和最晚开始时间。输出整个工程的最短完成时间是多少? 哪些活动是关键活动? 说明哪项活动提高速度后能导致整个工程提前完成?分析不同存储结构对于算法效率的影响。 散列表实验 1.熟悉散列表结构 2.掌握散列函数的生成方法,掌握常规冲突处理办法 3. 学会运用结构求解问题试根据全年级学生的姓名，构造一个散列表，选择适当的散列函数和解决碰撞方法，设计并实现插入、删除和查找算法，统计碰撞发生的次数。（用拉链法解决碰撞时负载因子取2，用开地址法时取1/2） 航班信息查询与检索实验设计1.掌握查找与排序的各种算法 2学会选用和设计实际问题所需的查找与排序算法对于直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序和堆排序等六种算法进行上机实习。要求：1. 被排序的对象由计算机随机生成，长度分别取20，100，500三种。2. 算法中增加比较次数和移动次数的统计功能。3. 对实习的结果做比较分析。 教材：魏开平等编著. 数据结构辅导与实验. 清华大学出版社，2006年第1版《数据结构与算法分析》 课程设计内容体系主要内容 《数据结构课程设计》课程，可使学生深化理解书本知