数据结构总复习-2015华中科技大学讲述.ppt

总 复 习 华中科技大学计算机学院 数据结构 数据结构 主讲教师：周时阳 《数据结构》是计算机科学与技术类各专业的一门基础课。 课程主要对于线性结构、树型结构和图型结构三类基本结构，讨论它们的逻辑结构、逻辑结构上定义的运算、物理结构、逻辑结构与物理结构对应关系、运算的实现算法与效率分析，给出了实际应用的实例。 此外，专题讨论了查找和排序运算的各种实现算法。其中，排序包括内部排序和外部排序的两种运算。 内容摘要 重点讲解 一、 知识归纳 二、 试卷题型 三、 考试安排 目录 一、知识归纳 第一章 绪论 1. 基本概念 数据、数据元素、逻辑结构、物理结构、算法和复杂度等。 2. 逻辑结构的描述方法 3. 数据元素的存储结构 4. 算法分析方法 目录 第二章 线性表 1. 基本概念 线性表、表长、空表、前驱、后继、序号、有序表、存储结点、溢出、头结点和头指针等。 2. 存储结构 顺序表(动态与静态分配、寻址公式) 链表(单/双、头结点/非头结点、循环/非循环) 静态链表 3. 重要运算 插入、删除 4. 应用实例 有序表的归并、集合运算和多项式加法 目录 第三章 栈和队列 1. 基本概念 栈、队列、空栈/空队、栈长/对长、头尾指针和溢出等。 2. 存储结构 顺序栈、链式栈 循环队列(标志位、头尾指针、头指针队长)、链式队列 3. 重要运算 入栈/出栈、入队/出队、判空 4. 栈队的基本特性 5. 应用实例 数制转换、括弧配对、表达式求值、递归算法实现 第四章 串 1. 基本概念 串、空串、串长、串大小、子串、空格串和存储密度等。 2. 存储结构 定长顺序存储结构 堆分配顺序存储结构 块连式存储结构 3. 重要运算 求串长、判空串、串链接、求子串和串替换等 4. 应用实例 文本编辑*、词索引* 第五章 数组和广义表 1. 基本概念 数组、下标、广义表、表长、深度、特殊矩阵和稀疏矩阵等。 2. 存储结构 数组：顺序存储结构(行/列优先、寻址公式) 广义表：链式存储结构(一)、链式存储结构(二) 3. 应用实例 特殊矩阵压缩存储(寻址公式) 稀疏矩阵压缩存储：三元组顺序表、行逻辑链接顺序表*和十字链表 第六章 树和二叉树 1. 基本概念 树、有序树、树高度、树的度、森林、二叉树、线索二叉树、满二叉树、二叉树路径长度和带权路径长度WPL等。 2. 存储结构 二叉树：顺序表、二叉链表(带/不带双亲)、线索二叉链表 树：双亲法、多重链表(同构/异构)、孩子链表法(带/不带双亲)、孩子兄弟法 森林：孩子兄弟法 3. 重要运算：遍历(递归/非递归算法)、二叉树构造 4. 二叉树的性质、遍历的特点 5. 应用实例 赫夫曼树构造与编码、树带权路径长度计算、二叉树静态链表 … 第七章 图 1. 基本概念 图、顶点度、连通图、连通分量、路径长度、生成树等。 2. 存储结构 邻接矩阵法、邻接表/逆邻接表、十字链表、邻接多重表 3. 重要运算：遍历 4. 应用实例 生成树与连通性、最小生成树、重连通分量*、拓扑排序、关键路径*、最短路径* 1. 基本概念 查找、关键字、平均查找长度ASL、查找成功/失败、判定树、哨兵技术、二叉排序树、平衡二叉树、散列表散列函数、同义字与哈希冲突等。 2. ASL计算、二叉排序树构造、二叉树平衡化 3. 查找算法思想及效率 顺序法 折半法(取中法、菲波那契序列法* 、线性插值法*) 分块查找法 二叉排序树法 B-树法*和B+树法*、键树法* 哈希法(哈希函数、处理冲突方法) 第九章 查找 1. 基本概念 排序、次关键字、算法稳定性、正序与逆序等。 2. 堆构造 3. 查找算法思想及效率 直接插入排序、折半插入排序、2-路插入排序*、表插入排序*、希尔排序、冒泡排序、快速排序、简单选择排序、树形选择排序* 堆排序、归并排序、基数排序 第十章 内部排序 1. 基本概念 外部排序、外部设备、归并树、最佳归并树等。 2. I/O访问时间 3. 查找算法思想及效率 初始段生成(内部排序、置换排序)、k路归并 第十一章 外部排序* 华中科技大学计算机学院 数据结构 * *