数据结构与算法分析.doc

文档介绍：《数据结构与算法分析》
――课程内容体系主要内容
教学单元模块
具体教学内容
绪论
绪论部分是全书的预备知识,主要对ADL语言、数据结构与算法、算法分析基础、OOP、和C++做了简单介绍
基本数据结构
基本数据结构部分包括线性表、堆栈与队列、数组、字符串、整数集合类、树(包括AVL树、伸展树等)、图(包括网络流等问题的讨论)、散列(Hash)等
典型算法
典型算法部分主要介绍了若干典型算法的实现,并给出必要的复杂性分析和比较过程,具体包括递归、排序、查找和内存管理等
复杂数据结构
复杂数据结构部分主要包括优先级队列、不相交集合类和文件结构等
算法设计技巧
典型算法设计技巧的介绍,主要包括贪婪算法、分治算法、动态规划、回溯算法和随机化算法等
应用
应用部分是上述数据结构和典型算法的一些应用示例,具体包括事件驱动模拟、等价类、残缺棋盘和图象压缩等问题的讨论,在课时允许的情况下还会介绍摊还分析、红黑树等
《数据结构与算法分析》
课程实践内容体系主要内容
实践教学单元模块
实践教学基本要求
实践教学具体内容
趣味程序设计实践


、二周布置若干趣味程序设计题目,如奇数阶幻阵算法、万年历算法、迷宫算法等。并完成:
,然后用一种排序算法将它们从小到大排序。
,用贪心法求解一般的着色问题。
链表应用实验



,实现时要求输出的不是整数,而是实际的人名。
(所谓有序是指链接点按数据域值大小链接,本题不妨设按数据域值从小到大排列),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. 根据课堂介绍设计实现KMP算法
2. 试设计一个简单的文本编辑器,使之具有对字符串的输入、输出、插入、删除、查找和替换等功能
3. 设计实现一个通用的判定回文个数问题的算法程序
稀疏矩阵和广义表实验



1. 设计实现两个普通矩阵相乘的算法
2. 实现用三元组表示法实现稀疏矩阵相加及转置算法
3. 设计实现两个N次一元多项式相加的算法程序
树结构实验