《数据结构复习.ppt》由会员分享，可在线阅读，更多相关《数据结构复习.ppt（14页珍藏版）》请在三一文库上搜索。
1、复习,通过本课程的学习，应能掌握数据结构的特点、存储方法和基本运算，培养自己运用C+语言正确编写算法及调试的能力，运用数据结构解决简单的实际问题的能力，可为后续计算机方面课程的学习打下坚实的基础。,本课程学习的目的:,基本要求:,1、掌握重要数据结构的逻辑结构、存储结构及基本运算的实现，会运用线性表、二叉树等设计算法以解决一些简单的实际问题，会通过阅读算法理解算法； 2、学会做简单的算法分析，包括算法的时间复杂度和空间复杂度。,题型：,一、选择题（20分）20*1 二、填空题（20分）10*2 三、应用题（45分 二叉树（二叉树的遍历和转换、哈夫曼树和编码）、图（最小生成树或单源点最短路径）、
2、查找（散列查找）、排序（希尔、快速或堆）5*9 四、算法设计题（15分 单链表的应用、二叉树遍历的应用） 题目给出函数框架，只需实现函数功能即可,设一颗二叉树以二叉链表为存储结构，设计一个算法求此二叉树上度为1的结点个数。,struct BiNode /二叉树的结点结构 int data; BiNode *lchild, *rchild; ; int count(BiNode * root) /* root为二叉树的根结点*/ ,第一章 概论,基本要求: 1、熟悉数据、数据元素(数据项)、数据结构、数据的逻辑结构与物理结构概念 2、熟悉逻辑结构分线性和非线性（树、图）结构 及每种结构的基本特征
3、 3、了解物理结构分顺序存储和链式存储 4、了解算法的定义、算法的特性、算法的时间复杂度、算法的空间复杂度 5、了解简单的计算语句频度和估算算法时间复杂度的方法,第二章 线性表,基本要求： 1、了解线性表的逻辑结构特性，以及线性表的两种存储实现方式 2、熟练掌握两种存储结构的描述方法。链表是本章的重点和难点。 3、灵活掌握顺序表的定义与基本操作的实现，包括插入、删除算法的实现； 4、灵活掌握链表结构实现线性表基本操作的实现算法； 5、能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 6、会用线性表解决简单的实际问题。,第三章 栈、队列,基本要求： 1、掌握栈和队列
4、的定义、特性，并能正确应用它们解决实际问题；会通过阅读算法理解算法。 2、熟练掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件；（主要是出栈和入栈）掌握递归函数的阅读。 3、熟练掌握队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况及队列空和队列满的条件及元素的个数。,循环队列 空：front=rear 满：(rear+1) %MAXN=front 队列的元素个数： （rear-front+MAXN)%MAXN 入队:rear=(rear+1)%MAXN; datarear=x; 出队：front=(front+1)%MAXN retur
5、n(datafront);,第4章 串和数组,1、掌握数组在以行（列）为主的存储结构中的地址计算法； 2、掌握对特殊矩阵（主要是下三角）进行压缩存储时的下标变换公式； 3、了解稀疏矩阵的三元组压缩存储方法 4、理解串的基本操作的含义，并能利用这些基本操作来实现串的其它各种操作的方法。,基本要求： 1、了解树和森林的概念。包括树的定义、树的术语； 2、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点和性质； 3、熟练掌握二叉树的遍历方法及遍历算法和算法的应用； 4、了解树的各种存储结构及其特点，掌握树、森林与二叉树的转换方法； 5、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算
6、. 完全二叉树、满二叉树,第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、了解归并排序方法。,