吉林大学内部绝密资料-数据结构总复习.ppt

《吉林大学内部绝密资料-数据结构总复习.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构总复习教学内容第一章绪论第二章线性表、堆栈和队列第三章数组和字符串第六章递归第四章树第五章图第七章排序第八章查找基础知识基础知识线性结构非线性结构非线性结构重点内容三三两两三要素（逻辑结构、存储结构、操作）三个数据结构（线性表、树、图）两类算法（排序、查找）两个评价算法的主要标准（时间、空间复杂性）两个表（3×3，2×2）3×3（2、3、4、5章）线性表树图逻辑结构存储结构操作2×2（7、8章）时间复杂性空间复杂性排序插入、交换、选择、合并…查找有序表的查找杂凑…重点内容3+2三类数据结构线性表树图两类算法排序

2、查找教学内容基础知识第一章绪论一、基础知识掌握数据结构的基本概念和术语包括：数据、数据元素、数据项、数据结构等基本概念。算法和算法分析掌握算法、算法的时间复杂度和空间复杂度等概念掌握算法分析的方法，对一般算法能分析出时间复杂度。一、基础知识数据:计算机程序要处理的“原料”数据元素:是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和处理。数据项:每个数据元素都有学号、姓名这两个数据项构成。数据项是构成数据的最小单位。一、基础知识数据结构的定义：按某种逻辑关系将一批数据元素组织起来按一定的存储方式把它们存储起来

3、；在数据上定义需要施加的操作。一、基础知识数据结构的组成：数据的逻辑结构数据的存储结构数据需要施加的操作逻辑结构数据元素之间的逻辑关系称为数据的逻辑结构。逻辑结构的形式化表示逻辑结构表示为二元组L=(N,R)，其中N(L)是结点的有限集合，R(L)是N上的关系集合。逻辑结构的分类线性结构结构中有且仅有一个始结点和一个终结点，始结点只有一个后继结点，终结点只有一个前趋结点，每个内结点有且仅有一个前趋结点和一个后继结点。非线性结构（树、图）结构中的结点可能有多个前趋结点和多个后继结点数据的存储结构数据在计算机中的存储表示称

4、为数据的存储结构。顺序存储结构链接存储结构数据需要施加的操作数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。线性表树图算法描述语言——ADLADL的格式算法<标识符>（变量i1,…,变量im.变量j1,…,变量jn）//单行注释（或/*…*/多行注释）步骤名1[步骤1所执行操作的高度概括]语句序列.…步骤名n[步骤n所执行操作的高度概括]语句序列.时间复杂性度量算法的标准：（1）能告诉算法所采用的方法的时间效率；（2）与算法描述语言及设计风格无关；（3）与算法的许多细节无关；（4）足够

5、精确和具有一般性。基本运算（关键操作）对所研究问题的基本操作时间复杂性一个算法的时间复杂性是指该算法的基本运算次数。数据结构逻辑结构存储结构操作线性结构树型结构图状结构集合顺序存储结构链式存储结构二、常用数据结构线性表树图线性表掌握线性表的定义和逻辑结构，了解线性表的基本运算。掌握顺序表的插入和删除操作及平均时间性能分析。熟练掌握单链表查找、插入和删除操作并分析其时间复杂度。了解循环单链表算法和单链表上相应算法的异同点。熟练利用单链表设计算法解决简单的应用问题。掌握双链表的基本操作。掌握顺序表和链表的主要优缺点线性表线

6、性表定义：一个线性表是由零个或多个具有相同类型的结点组成的有序集合。用（a0，a1，…，an-1）来表示一个线性表。当n>0时，a0称为表的始结点，an-1称为表的终结点，当n=0时，线性表中有零个结点，称为空表。线性表的存储结构顺序存储结构链接存储结构单链表循环链表双向循环链表栈和队列（线性表的应用）掌握栈的逻辑结构特点。掌握顺序栈和链栈上实现的进栈、退栈等基本算法。掌握队列的逻辑结构特点。掌握顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。栈和队列（线性表的应用）栈和队列都是操作受限的线性表栈的定义

7、：栈是插入和删除只能在其一端进行的线性表。并按先进后出（FILO)或后进先出（ＬIＦＯ）的原则进行操作。队列的定义：队列是插入在一端进行而删除在其另一端进行的线性表。并按先进向出（FIFO）的原则进行操作。能进行删除的一端称为队首（front），能进行插入操作的一端称为队尾（rear）。栈的应用——算术表达式求值运算规则：(1)先计算括号内，后计算括号外；(2)在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加减运算的优先级；(3)同一优先级运算，从左向右依次进行。数组、字符串和集合（线性结

8、构）掌握一维、二维数组的存储方法及对任意元素求地址公式掌握稀疏矩阵的概念及存储方法掌握串的有关概念及基本算法。了解串的两种存储表示。了解模式匹配算法树掌握树的常用术语及含义。掌握二叉树的递归定义及树与二叉树的差别。熟练掌握二叉树的性质。掌握二叉树的两种存储方法。熟练掌握二叉树的四种遍历算法。熟练掌握确定四种遍历所得到的相应的结点访