数据结构复习.ppt
数据结构复习 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望通过本课程的学习，应能掌握数据结构的特点、存储方通过本课程的学习，应能掌握数据结构的特点、存储方法和基本运算，培养自己运用法和基本运算，培养自己运用C+语言正确编写算法及语言正确编写算法及调试的能力，运用数据结构解决简单的实际问题的能力，调试的能力，运用数据结构解决简单的实际问题的能力，可为后续计算机方面课程的学习打下坚实的基础。可为后续计算机方面课程的学习打下坚实的基础。本课程学习的目的本课程学习的目的:基本要求基本要求:1、掌握重要数据结构的逻辑结构、存储结构及基本运算、掌握重要数据结构的逻辑结构、存储结构及基本运算的实现，会的实现，会运用线性表、二叉树等设计算法以解决一些简运用线性表、二叉树等设计算法以解决一些简单的实际问题，会通过阅读算法理解算法单的实际问题，会通过阅读算法理解算法；2、学会做简单的算法分析，包括算法的时间复杂度和空、学会做简单的算法分析，包括算法的时间复杂度和空间复杂度。间复杂度。题型：一、选择题（一、选择题（20分）分）20*1二、填空题（二、填空题（20分）分）10*2三、应用题（三、应用题（45分分二叉树（二叉树的遍二叉树（二叉树的遍历和转换、哈夫曼树和编码）、图（最小历和转换、哈夫曼树和编码）、图（最小生成树或单源点最短路径）、查找（散列生成树或单源点最短路径）、查找（散列查找）、排序（希尔、快速或堆）查找）、排序（希尔、快速或堆）5*9四、算法设计题（四、算法设计题（15分分单链表的应用、单链表的应用、二叉树遍历的应用）二叉树遍历的应用）题目给出函数框架，只需实现函数功能题目给出函数框架，只需实现函数功能即可即可设一颗二叉树以二叉链表为存储结构，设计一个算设一颗二叉树以二叉链表为存储结构，设计一个算法求此二叉树上度为法求此二叉树上度为1 1的结点个数。的结点个数。struct BiNode /二叉树的结点结构二叉树的结点结构 int data;BiNode*lchild,*rchild;int count(BiNode *root)/*root为二叉树的根结点为二叉树的根结点*/第一章第一章概论概论基本要求:1、熟悉数据、数据元素、熟悉数据、数据元素(数据项数据项)、数据结构、数据的、数据结构、数据的逻辑结构与物理结构概念逻辑结构与物理结构概念2、熟悉逻辑结构分线性和非线性（树、图）结构、熟悉逻辑结构分线性和非线性（树、图）结构 及及每种结构的基本特征每种结构的基本特征3、了解物理结构分顺序存储和链式存储、了解物理结构分顺序存储和链式存储4、了解算法的定义、算法的特性、算法的时间复杂度、了解算法的定义、算法的特性、算法的时间复杂度、算法的空间复杂度算法的空间复杂度5、了解简单的计算语句频度和估算算法时间复杂度的、了解简单的计算语句频度和估算算法时间复杂度的方法方法第二章第二章线性表线性表基本要求：1、了解、了解线性表的逻辑结构特性，以及线性表的两种存储线性表的逻辑结构特性，以及线性表的两种存储实现方式实现方式2、熟练掌握、熟练掌握两种存储结构的描述方法。链表是本章的重两种存储结构的描述方法。链表是本章的重点和难点。点和难点。3、灵活掌握、灵活掌握顺序表的定义与基本操作的实现，包括插入、顺序表的定义与基本操作的实现，包括插入、删除算法的实现；删除算法的实现；4、灵活掌握、灵活掌握链表结构实现线性表基本操作的实现算法；链表结构实现线性表基本操作的实现算法；5、能够从时间和空间复杂度的角度综合比较线性表两种能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。存储结构的不同特点及其适用场合。6、会用线性表解决简单的实际问题。、会用线性表解决简单的实际问题。第三章第三章栈、队列栈、队列基本要求：1、掌握、掌握栈和队列的定义、特性，并能正确应用它们解决实栈和队列的定义、特性，并能正确应用它们解决实际问题；会通过阅读算法理解算法。际问题；会通过阅读算法理解算法。2、熟练掌握、熟练掌握栈的顺序表示、链表表示以及相应操作的实现。栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件；（主要是出栈和入栈）掌握特别注意栈空和栈满的条件；（主要是出栈和入栈）掌握递归函数的阅读。递归函数的阅读。3、熟练掌握熟练掌握队列的顺序表示、链表表示以及相应操作的实队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况及队列现。特别是循环队列中队头与队尾指针的变化情况及队列空和队列满的条件及元素的个数。空和队列满的条件及元素的个数。循环队列循环队列空：空：front=rear满：满：(rear+1)%MAXN=front队列的元素个数：队列的元素个数：（rear-front+MAXN)%MAXN入队入队:rear=(rear+1)%MAXN;datarear=x;出队：出队：front=(front+1)%MAXNreturn(datafront);第第4 4章章 串和数组串和数组1、掌握数组在以行（列）为主的存储结构中的地址计算法；、掌握数组在以行（列）为主的存储结构中的地址计算法；2、掌握对特殊矩阵（主要是下三角）进行压缩存储时的下标变换、掌握对特殊矩阵（主要是下三角）进行压缩存储时的下标变换公式；公式；3、了解稀疏矩阵的三元组压缩存储方法、了解稀疏矩阵的三元组压缩存储方法4、理解串的基本操作的含义，并能利用这些基本操作来实现串的、理解串的基本操作的含义，并能利用这些基本操作来实现串的其它各种操作的方法。其它各种操作的方法。基本要求：基本要求：1、了解树和森林的概念。包括树的定义、树的术语；、了解树和森林的概念。包括树的定义、树的术语；2、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点和性质；的特点和性质；3、熟练掌握二叉树的遍历方法及遍历算法和算法的应用；、熟练掌握二叉树的遍历方法及遍历算法和算法的应用；4、了解树的各种存储结构及其特点，掌握树、森林与二叉树、了解树的各种存储结构及其特点，掌握树、森林与二叉树的转换方法；的转换方法；5、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算计算.完全二叉树、满二叉树完全二叉树、满二叉树第第5章章树树基本要求基本要求1、理解图的基本概念，熟悉图的各种存储结构（邻接、理解图的基本概念，熟悉图的各种存储结构（邻接矩阵和邻接表）；矩阵和邻接表）；2、熟练掌握图的两种搜索路径的遍历；、熟练掌握图的两种搜索路径的遍历；3、掌握构造最小生成树（、掌握构造最小生成树（prim算法）的方法，并理解算法）的方法，并理解克鲁斯卡尔算法；克鲁斯卡尔算法；4、理解求、理解求AOV网的拓扑排序的方法；网的拓扑排序的方法；5、掌握用、掌握用Dijkstra方法求解单源最短路径问题；方法求解单源最短路径问题；6、了解在、了解在AOE网中求关键路径的方法。网中求关键路径的方法。第第6章章图图基本要求基本要求1、熟熟练练掌掌握握顺顺序序表表和和有有序序表表的的查查找找算算法法及及其其性性能能分分析析方法方法:顺序查找、二分查找（判定树）顺序查找、二分查找（判定树）2、熟熟练练掌掌握握哈哈希希函函数数的的构构造造及及解解决决冲冲突突的的方方法法（根根据据哈希函数构造哈希表，并计算平均查找长度）哈希函数构造哈希表，并计算平均查找长度）3、理解二叉排序树的特点、创建和查找、理解二叉排序树的特点、创建和查找第第7章章查找查找例：设哈希函数H(K)=k%13,给定键值序列为87,25,310,8,27,132,68,95,187,123,70,63,47，处理冲突的方法为线性探测再散列，试在018的散列地址空间中对该关键字序列构造哈希表，并计算该表的成功查找的平均查找长度。第第8章章排序排序基本要求：1、掌握排序的基本概念和各种排序方法的特点，并能加、掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；以灵活应用；2、掌握插入排序、交换排序、选择排序的方法及其性能、掌握插入排序、交换排序、选择排序的方法及其性能分析方法；分析方法；3、了解归并排序方法。、了解归并排序方法。
