级数据结构复习参考.docVIP

数据结构 广州大学2006级本科计算机专业期末复习参考 数据结构是一门研究数据组织、存储和运算的一般方法的科学。 绪论 数据结构的三个方面： 数据的逻辑结构 集合结构 线性结构：栈、队列、字串，…… 层次结构（树结构） 图形结构（网状结构）链是特殊的树，树是特殊的图 数据的物理结构 顺序(数组) 链接(指针) 索引 散列 数据的运算 2. Pro. Niklaus Wirth提出的著名公式：算法+数据结构=程序 3. 算法的五个特性： 有穷性、确定性、可行性、输入（可以没有）、输出 4. 简单的算法分析 常见：O(1), O(log 2n), O(n), O(nlog2n), O(n2), O(n3), O(2n) 算法设计的要求：正确性、可读性、健壮性（考虑周到，不易崩溃）、高效率（算法复杂性低）与低存储量、可移植性（通用性强）等。 算法的表示： 流程图 自然语言 程序设计语言（比如C＋＋） 数学语言或其他约定的符号语言 7．算法与程序的关系： 一个程序不一定满足有穷性（死循环）；程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。 线性表 线性表的定义 线性表的顺序（数组）存储：插入n/2、删除(n-1)/2算法及其复杂度 线性表的链式（指针）存储： 单向链表、带表头的单向链表、循环链表、双向链表、双向循环链表是什么？ 链表与数组比较，各有什么优缺点？ 顺序存储：优，设计简便+可随机存取元素；缺：数据元素最大个数要预先给定+插入删除需移动大量元素 链表存储：优：无需预先给定数据元素最大数+插入删除时无需移动大量元素；缺：对结点的操作不能直接进行+结点指针域占空间大 链表的翻转（逆置）的算法： 顺序存储：只增加一个工作单元： 链式存储：只增加一个指针，不增加工作单元： 有序表和无序表在插入、删除等操作上有何异同？ 栈和队列 后进先出线性表(Last In First Out)：堆栈 堆栈的抽象数据类型的定义； 栈的实现（数组、指针） 栈的应用：括号的匹配、递归的实现、中缀表达式转后缀表达式 2． 进先出线性表(First In First Out)：队列 队列的抽象数据类型的定义； 队列的实现（数组、指针）； 队列的应用（图的先广查找、树的层次遍历等） 在什么情况下使用循环数组实现的队列？ 串 什么是串、子串（子串的数目如何计算）？ 两个串相等的充分必要条件 两个串大小比较的依据：字典顺序 串的数组存储：结束符 串的操作： 单串： 输入、输出 求长度 大小写转换 求子串 串/串： 复制 合并（首尾连接、交叉合并两种） 比较（字典顺序） 模式匹配：判别是否子串（返回真假、返回首位置、返回所有位置） 插入子串 删除子串 串的置换（先删除、再插入） 串的模式匹配算法的思路（只要求掌握BF算法，KMP算法不要求） 数组和广义表 C＋＋语言多维数组顺序存储的规则：最右下标变化最快 某个元素的位置的计算； 某个位置的元素的下标； 特殊矩阵（二维数组）的优化存储： 对称矩阵：用三角矩阵存放； 稀疏矩阵：三元组表示法（重点掌握）、十字链表表示法 稀疏矩阵的三元组表示法的含义及两种转置算法 三元组表示法的两种转置算法 两个三元组表示的矩阵的相加（参照两个多项式相加的算法） 递归 1．定义 递归：一个对象的组成包含了自身。 递归算法(程序)：一个算法(程序)直接或间接地调用自己。 2．递归方式： 直接递归和间接递归 3．递归的类型 ??? ? 定义是递归的，如裴波那契数列 问题的解法是递归的，如折半查找 4．递归算法的设计： 把对原问题的求解分解成对子问题的求解； 设计递归出口 5．如何消除递归 每一个递归程序都可以改写成相应的非递归程序 有时非递归程序效率更高：将递归求解过程改变为非递归求解过程的目的是提高速度 消除递归的通用方法：使用堆栈模拟递归 树和二叉树 树的定义和基本术语（根、叶片、内结点、结点的度等等） 树的逻辑表示法： 直观示意图 凹入表示法 集合表示法 广义表表示法，如：( A ( B ( E ( J，K，L )，F )，C (G )，D ( H ( M )，I ) ) ) 关系表示法，如：{A,B, A,C, A,D, B,E, B,F, E,J, E,K, E,L, C,G, D,H, D,I, H,M} 二叉树的性质、存储结构、完全二叉树结点的编号 树、森林与二叉树之间的相互转换 讨论这一问题的意义：把各种树和森林均转换为二叉树，简化问题，方便处理； 二叉树的先序、中序、后序遍历（目的：非线性结构--线性结构） 手工