文档介绍：《数据结构与算法分析》在世界上我们只活一次,所以应该爱惜光阴。必须过真实的生活,过有价值的生活。——巴甫洛夫《数据结构与算法分析》――课程内容体系主要内容教学单元模块具体教学内容绪论绪论部分是全书的预备知识,主要对 ADL 语言、数据结构与算法、算法分析基础、 OOP 、和 C++ 做了简单介绍基本数据结构基本数据结构部分包括线性表、堆栈与队列、数组、字符串、整数集合类、树( 包括 AVL 树、伸展树等)、图( 包括网络流等问题的讨论)、散列( Hash )等典型算法典型算法部分主要介绍了若干典型算法的实现, 并给出必要的复杂性分析和比较过程,具体包括递归、排序、查找和内存管理等复杂数据结构复杂数据结构部分主要包括优先级队列、不相交集合类和文件结构等算法设计技巧典型算法设计技巧的介绍, 主要包括贪婪算法、分治算法、动态规划、回溯算法和随机化算法等应用应用部分是上述数据结构和典型算法的一些应用示例, 具体包括事件驱动模拟、等价类、残缺棋盘和图象压缩等问题的讨论, 在课时允许的情况下还会介绍摊还分析、红黑树等《数据结构与算法分析》课程实践内容体系主要内容实践教学单元模块实践教学基本要求实践教学具体内容趣味程序设计实践 1. 熟悉编程环境 2. 复习 C 语言程序设计的基本内容 1. 开学第一、二周布置若干趣味程序设计题目,如奇数阶幻阵算法、万年历算法、迷宫算法等。并完成: 2. 随机产生 n 个整数,然后用一种排序算法将它们从小到大排序。 3. 试编一程序,用贪心法求解一般的着色问题。链表应用实验 1. 熟悉链表结构 2. 掌握链表结构上的各种操作 3. 学会运用链表结构求解问题 1. 试将本章介绍的两种 Josephus 问题的求解过程在计算机中实现, 实现时要求输出的不是整数,而是实际的人名。 分别为两个带有头结点的有序循环链表( 所谓有序是指链接点按数据域值大小链接,本题不妨设按数据域值从小到大排列) , list1 和 list2 分别为指向两个链表的指针。请写出并在计算机上实现将这两个链表合并为一个带头结点的有序循环链表的算法。栈与队列应用实验 1. 熟悉栈和队列结构 2. 掌握栈和队列结构上的各种操作 3. 学会运用栈和队列结构求解问题 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. 试设计一个简单的文本编辑器, 使之具有对字符串的输入、输出、插入、删除、查找和替换等功能 3. 设计实现一个通用的判定回文个数问题的算法程序稀疏矩阵和广义表实验 1 .熟悉稀疏矩阵和广义表结构 2 .掌握稀疏矩阵和广义表结构上的各种操作 3 .学会运用稀疏矩阵和广义表结构求解问题 1. 设计实现两个普通矩阵相乘的算法 2