重庆大学《数据结构与算法》复习提纲(学生版).docVIP

重庆大学《数据结构与算法》复习提纲(学生版) 重庆大学《数据结构与算法》复习提纲(学生版) PAGE 重庆大学《数据结构与算法》复习提纲(学生版) 《数据结构与算法》复习提纲 一、程序设计原理 理解 二、栈 (1) 栈说明：栈的定义和基本操作 栈是一种特殊的线性表，只能在固定一段进行插入或者删除操作。包含栈顶，栈底。表中无元素时，成为空栈。 操作：empty,top,push,pop 栈的实现：顺序栈的实现 利用连续的存储单元依次存放数据元素。确定那一端表示栈底。一般top=-1来表示空栈。进栈操作时，先使top加1，用以指示新的栈顶位置。先进后出。 上溢，top=stacksize-1. 下溢，top=-1 (3) 应用-桌面计算器：理解 (4) 应用-括号的匹配：理解 (5) 抽象数据类型及其实现：理解 三、队列 (1) 定义：队列的定义和基本操作 队列也是一种特殊的线性表，删除操作限定在表的一段，而插入操作在表的另一端。队尾（rear）和对首（front）。先进先出。 append，server，retrieve，empty，clear，full，size 队列的实现：顺序队列的实现 删除操作由front指示，插入操作由rear指示。rear》=maxsize队满，rear=front，表示队空。 C++队列的循环实现：顺序队列的实现 演示和测试：理解 (5) 队列的应用-模拟：理解 操作系统中的各种资源请求排队和各种数据缓冲区的先进先出管理，各种应用系统的时间规划、时间模拟，树类和图类问题中的一些非递归搜索算法等等。 四、链式栈和链式队列 (1) 指针和链式结构：理解 链表的思想是为表结构的每一个元素扩充一个指针，这个指针给出了表中下一个元素的位置。 指针被定义为一个对象，经常是变量，用于存储其他对象的位置。动态内存分配。 动态内存分配的优点： 不需要预先分配存储空间，分配的空间可以根据程序的扩大和缩小 链栈：链式栈的实现 (3) 带保护的链栈：理解 (4) 链式队列：链式队列的实现 (5) 应用-多项式运算：理解 (6) 抽象数据类型及其实现：栈和队列的抽象数据类型定义 递归 (1) 递归导言：递归算法的两个组成部分、非形式化描述转化为递归定义（如求阶乘等） 每个递归过程包括两个部分：终止条件，循环部分 1.不需用递归处理的最小的、基本的问题 2.将特定的问题简化成一个或多个更小的问题的通用方法，由此向前，最终将问题一直简化成基本问题。 非形式化定义：n! = n*(n-1)*(n-2) 形式化定义：n! = 1 n=0 n*(n-1) n0 递归的原理：理解 找出关键步骤--找出停止规则--列出算法大纲--检查终止--画出递归树 (3) 回溯法-延缓工作：理解 四皇后问题 通过构造部分解，并总是保证部分解与问题的需求保持一致，从而完成关于问题的解的搜索。 之后，将部分解扩展到完善，但当发生与问题需求不一致的情况时，算法通过移去最近构造的解部分并进行倒退（回溯）以尝试另一种可能性。 适用：一开始有多种可能性，但实际只有少数几种会继续存在。 (4) 树结构的程序-在游戏中预测：不做要求 表和字符串 表的定义：表的定义和基本操作 表是一种抽象数据类型，允许改变序列中任意元素的操作。 construct, empty, full, size, clear, insert, remove, retrieve, replace, traverse 表的实现：顺序实现、简单链式实现、双链表 代码见书上 优缺点比较： 优点： 链表：动态存储的灵活性，除非计算机内存耗尽，否则不会出现上溢。 在中间进行修改比顺序表更快，特别是插入和删除。 缺点： 链表：链本身要占用空间，因此所占的空间要大很多。 不适合随机访问。需要长时间遍历才打到想要的结点 顺序存储通常更可取： 当个别看起来，元素非常小时； 编写程序是就已知表的长度时； 除了在表尾外只需要很少的插入和删除时； 当随机访问很重要时。 链式存储证明更优： 当元素较大时； 当事先不知道表的长度时； 当再插入、删除和重排元素中需要灵活性时。 (3) 字符串：不做要求 (4) 应用-文本编辑器：不做要求 数组链表：理解 基于数组实现链表 必须事先决定分配给每个数组多大的空间，所以失去了动态存储分配这一特征 数组链表可以获得修改链表的灵活性和在几个链表间共享同一信息域的能力，并通过使用下标直接访问元素从而具有随机访问的优点 (6) 应用-生成排列：不做要求 七、查找 (1) 查找-引言和符号：理解 键：一部分信息 记录：包含与这个键相关的其他信息 (2)顺序查找：算法流程、算法实现、算法分析（比较次数计算） 在表的一段开