考研数据结构复习121130分析课件.ppt

《考研数据结构复习121130分析课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》复习试卷类型及比例数据结构（40分）：选择题：10分，简答题：10分，算法题：20分。内容：1、线性表基本概念，顺序存储结构链式存储结构、相应操作。2、栈和队列的特点，栈的应用、递归算法的设计。3、树的基本概念，二叉树的性质、存储结构，树与森林，树的遍历及应用。4、图的基本概念，图的存贮结构，图的遍历和拓扑排序。5、查找的基本概念、查找性能分析、顺序查找、折半查找和二叉排序树查找。6、直接插入排序、希尔排序、快速排序、简单选择排序和归并排序。《数据结构》复习数据结构的研究内容：研究数据的逻辑结构、存储结构和运算集合。逻辑结构是数

2、据结构的抽象，存储结构是数据结构的实现存储结构的二种类型:顺序存储结构—通过在存储器中的相对位置，表示数据的逻辑结构。非顺序存储结构（链式存储结构）--由指针表示数据间的逻辑关系。常用的数据结构(1)线性结构：结构中的数据元素之间存在着一对一的线性关系。线性表、栈、队、字符串、数组(2)树形结构：结构中的数据元素之间存在着一对多的层次关系。---非线性结构(3)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。---非线性结构一线性表线性表是最简单、最常用的数据结构。栈、队列、串是特殊的线性表，数组和广义表是线性表的扩展--

3、线性结构线性表的概念设A=（a1,a2,...,ai-1,ai,ai+1,…,an）是一线性表，1）同一线性表中的元素必须是同一类型的；2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的前件，ai+1是ai的后件；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个前件，有且仅有一个后件；4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；用一组连续的内存单元依次存放线性表的数据元素。a1a2ai-1aiai+1an线性表（a1,a2,a3,...an）的顺序存储结构用顺序存储结构存储的线性表——称为

4、顺序表线性表的顺序存储和实现线性表的顺序存储结构线性表的链式存储和实现线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除需要存储自身的信息外，还要保存直接前趋元素或直接后继元素的存储位置。ai+1a1ai-1a2aian头指针：存放线性链表中第一个结点的存储地址;头结点：链表的第一个元素结点前的附加结点；带头结点的线性链表：第一个元素结点前增加一个附加结点的线性链表称为带头结点的线性链表；head是头指针ai-1aia2a1ai+1nan头结点空指针head线性链表的每个结点中只有一个

5、指针域故也称为单链表例1、设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,将此链表的记录按照key递增的次序进行就地排序。（不允许使用数组做辅助存储）例2、将单链表L1拆成二个链表，其中以L1为头的链表保持原来向后的链接，另一个链表的头为L2，其链接方向与L1相反，L1包含原链表的奇数序号的节点，L2包含原链表的偶数序号的节点。例3、线性表合并：二个有序线性表LA、LB合并为一个有序线性表,合并后不另设新表存储。线性表的顺序存储和实现顺序表是线性表最简单的一种存储结构小结顺序表的特点：1通过元素的存储顺序反映线

6、性表中数据元素之间的逻辑关系；2可随机存取顺序表的元素；3顺序表的插入、删除操作要通过移动元素实现；线性链表小结线性链表是线性表的一种链式存储结构线性链表的特点1通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；2插入、删除操作通过修改结点的指针实现；3不能随机存取元素；二栈与队列栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除栈的概念栈栈的示意图出栈进栈栈的特点后进先出第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为

7、栈底元素栈顶栈底ana2a1例:一个栈的输入序列为a,b,c,d，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？一个栈的输入序列为1,2,3,4……n,?小结1栈是限定仅能在表尾一端进行插入、删除操作的线性表；2栈的元素具有后进先出的特点；3栈顶元素的位置由一个称为栈顶指针的变量指示，进栈、出栈操作要修改栈顶指针；栈队列队列的概念一什么是队列队列是限定仅能在表头进行删除，表尾进行插入的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除队列a1a2a3an入队列队头队尾出队列队列的示意图队列的特点先进先出第一个入队的

8、元素在队头，最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素循环队列判分队空、队满有两种方法：1）另设一个标志位以