数据结构与算法分析.doc

《数据结构与算法分析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构与算法分析》――课程内容体系主要内容教学单元模块具体教学内容绪论绪论部分是全书的预备知识，主要对ADL语言、数据结构与算法、算法分析基础、OOP、和C++做了简单介绍基本数据结构基本数据结构部分包括线性表、堆栈与队列、数组、字符串、整数集合类、树（包括AVL树、伸展树等）、图（包括网络流等问题的讨论）、散列（Hash）等典型算法典型算法部分主要介绍了若干典型算法的实现，并给出必要的复杂性分析和比较过程，具体包括递归、排序、查找和内存管理等复杂数据结构复杂数据结构部分主要包括优先级队列、不相交集合类和文件结构等算法设计技巧典型算法设计技巧的介绍，主要包括贪婪算法、

2、分治算法、动态规划、回溯算法和随机化算法等应用应用部分是上述数据结构和典型算法的一些应用示例，具体包括事件驱动模拟、等价类、残缺棋盘和图象压缩等问题的讨论，在课时允许的情况下还会介绍摊还分析、红黑树等《数据结构与算法分析》课程实践内容体系主要内容实践教学单元模块实践教学基本要求实践教学具体内容趣味程序设计实践1.熟悉编程环境2.复习C语言程序设计的基本内容1.开学第一、二周布置若干趣味程序设计题目，如奇数阶幻阵算法、万年历算法、迷宫算法等。并完成：2.随机产生n个整数，然后用一种排序算法将它们从小到大排序。3.试编一程序，用贪心法求解一般的着色问题。链表应用实验1.熟悉链

3、表结构2.掌握链表结构上的各种操作3.学会运用链表结构求解问题1.试将本章介绍的两种Josephus问题的求解过程在计算机中实现，实现时要求输出的不是整数，而是实际的人名。2.设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的指针。请写出并在计算机上实现将这两个链表合并为一个带头结点的有序循环链表的算法。栈与队列应用实验1.熟悉栈和队列结构2.掌握栈和队列结构上的各种操作3.学会运用栈和队列结构求解问题1.设计实现一个求解n阶Hanoi塔问题的算法提示：将n个圆盘

4、由A依次移到C，B作为辅助塔座。当n=1时，可以直接完成。否则，将塔座A顶上的n-1个圆盘移动到塔座B上，用塔座C作为辅助塔座；然后移第n个圆盘；最后将塔座B上的n-1个圆盘移到塔座C上，并用塔座A作为辅助塔座。2.根据书中介绍的思想，设计并实现一个对简化表达式求值的系统。3.在计算机上模拟实现农夫过河问题的解。文本文件检索实验1.熟悉字符串的操作2.学会运用字符串的操作进行文本检索和查询。1.根据课堂介绍设计实现KMP算法2.试设计一个简单的文本编辑器，使之具有对字符串的输入、输出、插入、删除、查找和替换等功能3.设计实现一个通用的判定回文个数问题的算法程序稀疏矩阵和广

5、义表实验1．熟悉稀疏矩阵和广义表结构2．掌握稀疏矩阵和广义表结构上的各种操作3．学会运用稀疏矩阵和广义表结构求解问题1.设计实现两个普通矩阵相乘的算法2.实现用三元组表示法实现稀疏矩阵相加及转置算法3.设计实现两个N次一元多项式相加的算法程序树结构实验1.熟悉树和二叉树结构2.掌握树和二叉树结构上的各种操作3.学会运用树和二叉树结构求解问题1.设计一个程序，根据二叉树的先根序列和对称序序列创建一棵用左右指针表示的二叉树2.根据哈夫曼算法创建哈夫曼树，并求树中每个外部结点的编码3.设计一个程序，把中缀表达式转换成一棵二叉树，然后通过后序遍历计算表达式的值4.设计实现一个完成

6、对BST树进行插入、删除、查找操作的算法，并希望有部分同学能进一步把该算法改写为针对AVL树的相关算法图结构实验1.熟悉图结构2.掌握图结构上的各种操作3.学会运用图结构求解问题采用两种不同的图的表示方法，实现拓扑排序和关键路径的求解过程。使用实现的算法对于下图所示的AOE网，求出各活动的可能的最早开始时间和最晚开始时间。输出整个工程的最短完成时间是多少?哪些活动是关键活动?说明哪项活动提高速度后能导致整个工程提前完成?分析不同存储结构对于算法效率的影响。散列表实验1.熟悉散列表结构2.掌握散列函数的生成方法,掌握常规冲突处理办法3.学会运用散列结构求解问题试根据全年级学

7、生的姓名，构造一个散列表，选择适当的散列函数和解决碰撞方法，设计并实现插入、删除和查找算法，统计碰撞发生的次数。（用拉链法解决碰撞时负载因子取2，用开地址法时取1/2）航班信息查询与检索实验设计1.掌握查找与排序的各种算法2.学会选用和设计实际问题所需的查找与排序算法对于直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序和堆排序等六种算法进行上机实习。要求：1.被排序的对象由计算机随机生成，长度分别取20，100，500三种。2.算法中增加比较次数和移动次数的统计功能。3.对实习的结果做比较分析。4.设计实现一个航