《专升本数据结构.ppt》由会员分享，可在线阅读，更多相关《专升本数据结构.ppt（426页珍藏版）》请在三一办公上搜索。
1、数据结构与算法,主讲：XXX,北上数据结构考前复习,辅导课需要具备的先导知识辅导课的侧重点、难度辅导课的时间、内容安排,辅导课需要具备的先导知识,C语言的基本概念，至少能够看懂简单的C语言代码。最好有上过数据结构课程，未上过数据结构课程会有些吃力。有一点点高等数学基础更好。,专升本数据结构的特点,课本的组织形式基本上是以代码来讲解理论，这给读书带来一定难度。专升本的考试重点不在代码实现，而在理论知识的掌握。09级的数据结构课程按照理论+题库的讲解模式，应试能力明显增强。,辅导课的侧重点、难度,基本上讲解理论知识+题目，尽量不涉及C语言(必要的C语言结构会进行讲解)。讲解过程采用新课+复习模式，
2、按照新课讲授，例子可能采用后面的章节。希望大家在过程中做好笔记。难度与专升本考试难度持平，相当于学习期间，中游同学可以掌握的难度。,考试大纲见word文档,数据结构的主体内容,线性数据结构集合(散列数据结构)树形(层次)数据结构图(网状)数据结构,时间复杂度排序查找相关数据结构(二叉排序树、堆)递归及其他,辅导课的时间、内容安排,7月26日上午：算法数据结构概念、时间复杂度、线性数据结构(表)7月26日下午：线性数据结构(栈、队列)、排序7月28日下午：树形数据结构7月29日上午：集合（散列数据结构）、二叉排序树、堆、哈夫曼7月29日下午：图（网状）数据结构7月30日上午：其它内容（编程题目）
3、、复习、测验,开篇：数据结构的定义,数据元素是数据的基本单位，但数据元素是可分的，数据元素由数据项组成。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，基本结构有4类：集合、线性结构、树形结构、图状结构或网状结构存储结构，即数据的物理结构，是数据结构在计算机中的表示。包括数据元素的表示和关系的表示。主要有顺序存储结构、链式存储结构、索引存储方法和散列存储方法等。,习题,要表示高校的校，系，班级的有关数据及其关系，选择_比较合适。【福建 2009 专升本】A 线性结构 B 树结构 C 图结构 D 集合结构_是数据的基本单位，即数据集合中的个体。【福建 2009 专升本】A 数据结构 B
4、 数据项 C 数据元素 D 数据对象,答案:B C,习题,以下哪一个术语与数据的存储结构无关_【福建 2007 专升本】A 队列 B 静态数组 C 线索二叉树 D 双向链表,答案:A,算法定义及复杂度的概念,需要掌握的知识点 算法的定义及其五条基本性质 时间复杂度的概念、时间复杂度与什么有关 最坏、最好、平均情况下的时间复杂度时间复杂度的O表示 给定函数式，可以用O表示。能够比较两个函数式代表的复杂度。给出C简单代码，能够计算复杂度（O表示）。熟记常用算法的复杂度(O表示)。,算法(Algorithm),算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外
5、部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。(5)可行性：任意合法输入都对应正确输出,算法复杂性分析,算法复杂性=算法所需要的计算机资源。算法的时间复杂性T(n)。算法的空间复杂性S(n)。数据结构主要讨论时间复杂性。时间复杂性与问题规模和数据初始状态有关，与其它内容无关。,最坏情况、最好情况和平均情况下时间复杂性,三种情况下时间复杂性是针对初始数据进行分类的，与n没有关系。,渐近分析的记号,对所有n，f(n)0，g(n)0。渐近上界记号O的定义
6、O(g(n)=f(n)|存在正常数c和n0使得对所有n n0有：0 f(n)cg(n)O符号具有的特点：O符号忽略所有的系数。O符号仅在乎整个表达式的主项（值最大的项）。,习题,下列函数中渐进时间复杂度最小的是_。【2009 专升本】,答:A若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为_。【2007 专升本】,O(nlogn),习题,算法的计算量的大小称为计算的_【北京邮电大学2000 二、3】A 效率 B 复杂性 C 现实性 D 难度算法的时间复杂度取决于_【中科院计算所 1998 二、1】A仅和问题的规模有关 B 仅和待处理数据的初态有关C和问题的规
7、模及待处理数据的初态有关D和问题的规模、待处理数据的初态、CPU的执行速度有关一个算法的定义是_。【中山大学 1998 二、1】A 程序 B 问题求解步骤的描述 C 满足五个基本特性的东西,答:B C B,算法的时间复杂性及看C代码写复杂度见其它课件,常用算法的时间复杂性的大小关系为：常数级 对数级 多项式级 指数级,时间复杂性总结,第二章：表（线性数据结构）,表是由n(n=0)个同一类型的元素(element)a(1),a(2),a(n)组成的有限序列。其中，元素的个数n定义为表的长度。长度等于0的表是空表。表中的数据关系是一对一的线性关系。线性表和数组的差别在于线性表的长度是动态变化的。线
8、性表的主要操作包括添加元素、删除元素、根据元素查找位置、根据位置查找元素等。,表的常用运算,ListEmpty(L):测试表L是否为空。ListLength(L):表L的长度。ListLocate(x,L):元素x在表L中的位置。若x在表中重复出现多次，则返回最前面的x的位置。ListRetrieve(K,L):返回表L的位置k处的元素。表中没有位置k时，该运算无定义。ListInsert(k,x,L):在表L的位置k之后插入元素x,并将原来占据该位置的元素及其后面的元素都向后推移一个位置。ListDelete(k,L)；从表L中删除位置k处的元素，并返回被删除的元素。,线性表的两种实现方式,
9、线性表的实现主要有顺序实现和链式实现。顺序实现就是顺序表，也就是数组实现。在这种实现方式下表的容量是固定的。链式实现是指针实现方式，分为单链表、双链表、循环链表、带头结点链表等。提示：栈和队列等线性结构也都是这两种实现方式。,顺序表（数组实现表）,数组实现表就是用一段连续的存储空间依次存放表元素。这种实现方式的优点有：存储密度大(无需额外空间)根据位置查找元素方便在尾部添加删除元素方便这种实现方式的缺点有：插入删除可能需要移动元素表容量固定,顺序表(数组实现表)的C语言结构,typedef struct alist*List;typedef struct alist int n;int max
10、size;ListItem*table;Alist;书上20页中的table 应改为：*table;,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,对应C代码：L-table6=L-table5,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,对应C代码：L-table5=L-table4,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,对应C代码：L-t
11、able4=L-table3,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,对应C代码：L-table3=L-table2,顺序表(数组实现表)的插入操作,在第2个元素后面添加70的过程,表中有6个元素(L-n=6)：,对应C代码：L-table2=70;L-n+;,插入操作移动元素的平均次数,最少情况为表尾插入，移动0次。最多情况为表首插入，移动n次。平均次数=移动的总次数/位置个数,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程
12、,表中有7个元素(L-n=7)：,对应C代码：L-table2=L-table3,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：L-table3=L-table4,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：L-table4=L-table5,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：L-table5=L-table6,顺序表(数组实现表)的删除操作,删除表中第三个元素的过程,表中有7个元素(L-n=7)：,对应C代码：L
13、-n-,删除操作移动元素的平均次数,最少情况为表尾删除，移动0次。最多情况为表首删除，移动n-1次。平均次数=移动的总次数/位置个数,单链表（指针实现表）,单链表采用指针的方式将物理上并不相邻的单元串联起来。这种实现方式的优点有：插入删除不需要移动元素表容量可任意变化这种实现方式的缺点有：需要额外的指针空间查找指定位置元素的复杂度高,单链表（指针实现表）,a(1),a(2),a(3),a(n),first,单链表：表的定义,typedef struct node*link;typedef struct node ListItem element;link next;Node;typedef s
14、truct llist*List;typedef struct llist link first;Llist;,单链表：第2个结点后插入y指向的结点,a(1),a(2),a(3),a(n),first,y,单链表：第2个结点后插入y指向的结点,a(1),a(2),a(3),a(n),first,y,对应代码：p=L-first,p,单链表：第2个结点后插入y指向的结点,a(1),a(2),a(3),a(n),first,y,对应代码：p=p-next,p,单链表：第2个结点后插入y指向的结点,a(1),a(2),a(3),a(n),first,y,对应代码：y-next=p-next,p,单链
15、表：第2个结点后插入y指向的结点,a(1),a(2),a(3),a(n),first,y,对应代码：p-next=y,p,单链表：删除第3个结点,a(1),a(2),a(3),a(n),first,对应代码：p=L-first,p,单链表：删除第3个结点,a(1),a(2),a(3),a(n),first,对应代码：p=p-next,p,单链表：删除第3个结点,a(1),a(2),a(3),a(n),first,对应代码：p-next=p-next-next,p,其它链表形式,a(1),a(2),a(3),a(n),first,循环链表,双链表,a(1),a(2),a(3),first,头结点
16、,表章节重点,理解表所代表的线性关系的意义。了解表的顺序和链式实现的优缺点。清楚表的插入删除查询过程中移动元素比较元素的次数。能够根据要求填写（至少判断）简单的C实现代码。,表习题,线性表是一个_【福建 2009 专升本】A 有限序列，可以为空 B 有限序列，不能为空 C 无限序列，可以为空 D 无限序列，不能为空某链表中最常见的操作是在已知的一个结点之前插入一个新的结点和删除其之前一个结点，则采用 _存储方式最节省运算时间【福建 2009 专升本】A 双向链表 B 带头指针的单向链表 C 带尾指针的单向链表 D 单向循环链表,答案：A A,表习题,下述哪一条是顺序存储方式的优点_【福建 20
17、07 专升本】A 存储密度大 B 插入运算方便 C 删除运算方便 D 可方便地用于各种逻辑结构的存储表示对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为_【福建 2007 专升本】A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表在长度为n的顺序表的第i(1 i n+1)个位置上插入一个元素，元素的移动次数为_【福建 2007 专升本】A n-i+1 B n-i C i D i-1,答案：A C A,表习题,链表的结点类型定义如下:typedef struct node*link;struct node ListItem element;link le
18、ft;link right;*p,*q,*r;删除双链表中结点p(由p指向的结点)的操作是_【福建 2008 专升本】A q=p-left;r=p-right;q-right=r;r-left=q;B q=p-right;r=p-left;q-right=r;r-left=q;C q=p-left;r=p-right;q-left=r;r-right=q;D q=p-left;r=p-right;q-right=r-left;,答案：A,表习题,已知单链表结点构造为struct node int data;struct node*next;*p,*q,*r;删除单链表中结点p(由p指向的结点)
19、后面的结点的操作不正确的是_【福建 2006 专升本】A q=p-next;p-next=q-next;B p-next=p-next-next;C r=p-next;p-next=q-next;D q=p-next;r=q-next;p-next=r;单链表中有n个结点,在其中查找值为x的结点,查找成功时,需比较的平均次数是_【福建 2006 专升本】A n B(n-1)/2 C n/2 D(n+1)/2线形表采用链式存储时,结点的存储地址_【福建 2006 专升本】A 必须是不连续的 B 连续与否均可 C 必须是连续的 D 和头结点的存储地址相连续,答案：C D B,第三章：栈（线性数据结
20、构）,栈是一种特殊的表，这种表只在表的一端进行插入和删除操作。因此，这一端对于栈来说具有特殊的意义，称为栈顶。相应地，另外一端称为栈底。不含任何元素的栈称为空栈。栈是限定仅在表一端进行插入或删除操作的线性表，又称后进先出（LIFO）的线性表。栈顶栈底,a(n),.,a(2),a(1),栈的常用运算,StackEmpty(S):测试栈S是否为空StackFull(S):测试栈S是否已满StackTop(S):返回栈S的栈顶元素Push(x,S):在栈S的栈顶插入元素x,简称为将元素x入栈Pop(S):删除并返回S的栈顶元素，简称为抛栈。提示：这些代码基本上是一句话，希望大家能够掌握,栈的实现,栈
21、的实现也有顺序和链式两种方式。数组实现栈中，栈元素存储在数组data中。用top指向当前栈顶位置。栈顶元素存储在datatop中。栈的容量为maxtop+1。两个栈可以共享一个数组data。指针实现栈时用top指针指向栈顶。,数组实现栈的结构,typedef struct astack*Stack;typedef struct astack int top,maxtop;StackItem*data;Astack;,指针实现栈的结构,typedef struct snode*slink;typedef struct snode StackItem element;slink next;Stac
22、kNode;,栈的应用,表达式求值、括号匹配、进制转换、图的深度优先遍历等。实际上，凡是满足先进后出的应用都可用栈实现。,栈的进出顺序,一个栈的进栈顺序是123n,在进栈的过程中允许出栈，那么出栈的顺序会如何？判断：有n 个数顺序进栈，出栈序列有 种。输出序列中不可能出现”大、小、中”的情况。要会记录出入栈的情况。,栈的习题,假设进栈的元素序列依次是a、b、c、d,指出不可能的出栈序列_【福建2006专升本】A abcd B adbc C acbd D dcba有6个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列_【福建 2007 专升本】A 5,4,3,6,1,2 B
23、4,5,3,1,2,6 C 3,4,6,5,2,1 D 2,3,4,1,5,6递归方法实现递归算法时通常需要使用_【福建 2008 专升本】A 循环队列 B 栈 C 二叉树 D 双向队列,答案：B C B,第四章：队列(线性数据结构),队列是一种特殊的表，这种表只在表首进行删除操作，在表尾进行插入操作。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出表，简称FIFO表。假设队列为a(1),a(2),a(n),那么a(1)就是队首元素，a(n)为队尾元素。,队列的常用运算,QueueEmpty(Q):测试队列Q是否为空。QueueFull(Q):测试队列Q是否已满。QueueFirst
24、(Q):返回队列Q的队首元素。QueueLast(Q):返回队列Q的队尾元素。EnterQueue(x,S):在队列Q的队尾插入元素x。DeleteQueue(Q):删除并返回Q的队首元素。,指针实现队列的结构,typedef struct qnode*qlink;typedef struct qnode QItem element;qlink next;Qnode;typedef struct lque*Queue;typedef struct lque qlink front;qlink rear;Lqueue;,循环数组实现队列的结构,typedef struct aque*Queue;
25、typedef struct aque int maxsize;int front;int rear;QItem*queue;Aqueue;,循环数组实现队列添加元素的过程,A,1,0,B,2,C,3,4,5,6,7,D,E,F,front,rear,队列添加G:,循环数组实现队列添加元素的过程,A,1,0,B,2,C,3,4,5,6,7,D,E,F,front,rear,队列添加G:Q-rear=(Q-rear+1)%Q-maxsize,循环数组实现队列添加元素的过程,A,1,0,B,2,C,3,4,5,6,7,D,E,F,front,rear,队列添加G:Q-queueQ-rear=x,G
26、,循环数组实现队列删除元素的过程,1,0,B,2,C,3,4,5,6,7,D,E,F,front,rear,队列删除:Q-front=(Q-front+1)%Q-maxsize,G,循环数组实现队列删除元素的过程,1,0,2,C,3,4,5,6,7,D,E,F,front,rear,队列删除:Q-front=(Q-front+1)%Q-maxsize,G,循环数组实现队列删除元素的过程,1,0,2,3,4,5,6,7,D,E,F,front,rear,队列删除:Q-front=(Q-front+1)%Q-maxsize,G,循环数组实现队列添加元素的过程,1,0,2,3,4,5,6,7,D,E
27、,F,front,rear,队列添加:Q-rear=(Q-rear+1)%Q-maxsize,G,X,循环数组实现队列添加元素的过程,1,0,2,3,4,5,6,7,D,E,F,front,rear,队列添加:Q-rear=(Q-rear+1)%Q-maxsize,G,X,Y,第四章队列的重点,理解先进先出的数据结构。循环数组实现队列是本章节重点。重点掌握front和rear游标如何判空、判满、计算队列长度、入队、出队等。,队列的习题,设数组queuem作为循环队列Q的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front的值为_【福建 2006 专升本】A f
28、ront=(front+1)%m B front=(front-1)%m C front=(front+1)%(m-1)B front=front+1以下哪一个术语与数据的存储结构无关_【福建 2007 专升本】A 队列 B 静态数组 线索二叉树 D 双向链表会引起循环队列队头位置发生变化的操作是_【福建 2008 专升本】A)取队首元素B)入队列C)取队尾元素D)出队列,答案：,队列的习题,若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为_【浙江大学1999 四、1】A)4和2B)1和
29、5C)5和1D)2和4判断：无论如何实现，也无法使队列的入队、出队两个操作的时间复杂度同时将为O(1)。判断：双端队列在逻辑上是队列。,答案：错错,排序算法概述,在一般情况下，排序问题的输入是n个数a0,a1an-1的一个序列，要设计一个有效的排序算法，产生输入序列的一个重排，使序列元素从小到大的顺序排列。掌握排序算法重点是掌握每种排序每趟过程、复杂度（最好最坏平均）、移动元素、交换元素的个数等问题。重点考的排序算法：冒泡、插入、选择、快速。希望掌握的其它排序：合并、希尔、堆排序。,第六章排序,外部排序 外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，
30、需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,第六章排序,若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。假定在待排序的记录序列中，存在多个具有相同键值的记录，若经过排序，
31、这些记录的相对次序保持不变，即在原序列中，ki=kj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。快速排序、希尔排序、堆排序、选择排序不是稳定的排序算法，而基数排序、冒泡排序、插入排序、归并排序是稳定的排序算法,冒泡排序过程演示,原序列：,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：25和10进行交换,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：30和12进行交换,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：30和7进行交换,冒泡排序过程演示,第一趟：保持稳定，相等不交换。,冒泡排
32、序过程演示,第一趟：,冒泡排序过程演示,第一趟：30和24交换,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：30和6交换,冒泡排序过程演示,第一趟：,冒泡排序过程演示,第一趟：30和15交换，第一趟结束，30确定位置,冒泡排序过程演示,第一趟结束，30确定位置,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示,第二趟,冒泡排序过程演示
33、,第二趟结束,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟,冒泡排序过程演示,第三趟结束,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟,冒泡排序过程演示,第四趟结束,冒泡排序过程演示,第五趟,冒泡排序过程演示,第五趟,冒泡排
34、序过程演示,第五趟,冒泡排序过程演示,第五趟,冒泡排序过程演示,第五趟,冒泡排序过程演示,第五趟结束,冒泡排序过程演示,第六趟,冒泡排序过程演示,第六趟,冒泡排序过程演示,第六趟,冒泡排序过程演示,第六趟,冒泡排序过程演示,第六趟结束,冒泡排序过程演示,第七趟,冒泡排序过程演示,第七趟,冒泡排序过程演示,第七趟结束,冒泡排序过程演示,第八趟,冒泡排序过程演示,第八趟结束，冒泡排序完成,插入排序过程演示,原序列：,插入排序过程演示,第一趟：,插入排序过程演示,第一趟：,插入排序过程演示,第一趟：,插入排序过程演示,第一趟结束,插入排序过程演示,第二趟,插入排序过程演示,第二趟结束,插入排序过程演
35、示,第三趟,插入排序过程演示,第三趟,插入排序过程演示,第三趟,插入排序过程演示,第三趟,插入排序过程演示,第三趟,插入排序过程演示,第三趟结束,插入排序过程演示,第四趟,插入排序过程演示,第四趟,插入排序过程演示,第四趟,插入排序过程演示,第四趟,插入排序过程演示,第四趟,插入排序过程演示,第四趟结束,插入排序过程演示,第五趟,插入排序过程演示,第五趟结束,插入排序过程演示,第六趟,插入排序过程演示,第六趟,插入排序过程演示,第六趟,插入排序过程演示,第六趟,插入排序过程演示,第六趟结束,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟,
36、插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟,插入排序过程演示,第七趟结束,插入排序过程演示,第八趟,插入排序过程演示,第八趟,插入排序过程演示,第八趟,插入排序过程演示,第八趟,插入排序过程演示,第八趟,插入排序过程演示,第八趟结束，插入排序结束,选择排序过程演示,原序列：,目前最小下标：,选择排序过程演示,第一趟：,目前最小下标：0,选择排序过程演示,第一趟：,目前最小下标：1,选择排序过程演示,第一趟：,目前最小下标：1,选择排序过程演示,第一趟：,目前最小下标：1,选择排序过程演示,第一趟：,目前最小下标：4,选择排序过程演示,
37、第一趟：,目前最小下标：4,选择排序过程演示,第一趟：,目前最小下标：4,选择排序过程演示,第一趟：,目前最小下标：7,选择排序过程演示,第一趟：,目前最小下标：7,选择排序过程演示,第一趟：结束,目前最小下标：7,选择排序过程演示,第二趟：,目前最小下标：1,选择排序过程演示,第二趟：,目前最小下标：1,选择排序过程演示,第二趟：,目前最小下标：1,选择排序过程演示,第二趟：,目前最小下标：4,选择排序过程演示,第二趟：,目前最小下标：4,选择排序过程演示,第二趟：,目前最小下标：4,选择排序过程演示,第二趟：,目前最小下标：4,选择排序过程演示,第二趟：,目前最小下标：4,选择排序过程演示
38、,第二趟：结束,目前最小下标：4,选择排序过程演示,第三趟：,目前最小下标：2,选择排序过程演示,第三趟：,目前最小下标：3,选择排序过程演示,第三趟：,目前最小下标：4,选择排序过程演示,第三趟：,目前最小下标：4,选择排序过程演示,第三趟：,目前最小下标：4,选择排序过程演示,第三趟：,目前最小下标：4,选择排序过程演示,第三趟：,目前最小下标：4,选择排序过程演示,第三趟：结束,目前最小下标：4,选择排序过程演示,第四趟：,目前最小下标：3,选择排序过程演示,第五趟：,目前最小下标：4,选择排序过程演示,第五趟：,目前最小下标：4,选择排序过程演示,第五趟：,目前最小下标：6,选择排序过
39、程演示,第五趟：,目前最小下标：6,选择排序过程演示,第五趟：,目前最小下标：8,选择排序过程演示,第五趟：结束,目前最小下标：8,选择排序过程演示,第六趟：,目前最小下标：5,选择排序过程演示,第六趟：,目前最小下标：6,选择排序过程演示,第六趟：,目前最小下标：6,选择排序过程演示,第六趟：,目前最小下标：6,选择排序过程演示,第六趟：结束,目前最小下标：6,选择排序过程演示,第七趟：,目前最小下标：6,选择排序过程演示,第七趟：,目前最小下标：7,选择排序过程演示,第七趟：,目前最小下标：7,选择排序过程演示,第七趟：结束,目前最小下标：7,选择排序过程演示,第八趟：,目前最小下标：7,
40、选择排序过程演示,第八趟：,目前最小下标：8,选择排序过程演示,第八趟：结束，选择排序结束,目前最小下标：8,快速排序过程演示,原序列：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：0 小数下标：7 交换,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：0 小数下标：7 交换,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：2 小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：2 小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标
41、：2 小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：2 小数下标：4 交换,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：小数下标：,快速排序过程演示,第一趟：以最后一个元素15为基准,大数下标：4 小数下标：无,快速排序过程演示,第一趟：结束,大数下标：4 小数下标：无,快速排序过程演示,第二趟：以12为基准,大数下标：小数下标：,快速排序过程演示,第二趟：以12为基准,大数下标：小数下标：,快速排序过程演示,第二趟：以12为基准,大数下标：小数下标：,快速排序过程演示,第二
42、趟：以12为基准,大数下标：3 小数下标：无,快速排序过程演示,第二趟：以30为基准,大数下标：5 小数下标：7 交换,快速排序过程演示,第二趟：以30为基准,大数下标：小数下标：,快速排序过程演示,第二趟：以30为基准,大数下标：7 小数下标：无,快速排序过程演示,第二趟：结束,大数下标：7 小数下标：无,快速排序过程演示,第三趟：分别以7、24、31为基准,快速排序过程演示,第三趟：结束,快速排序过程演示,第四趟结束，排序宣告结束,合并排序思想,合并排序算法是用分治策略实现对n个元素进行排序的算法。其基本思想是：当n=1时终止排序，否则将待排序元素分成大小大致相同的两个子集，分别对两个子集
43、进行排序，最终将排好序的子集合并成为所要求的排好序的集合。自底向上的合并排序：可以首先将数组中相邻元素两两配对，用合并算法将它们排序，构成n/2组长度为2的排好序的子数组段，然后再将它们排序成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。,排序章节总结,冒泡、插入、选择是简单排序，平均复杂度。快速、合并是较快的排序算法，平均复杂度。快速排序在最坏情况下的时间复杂度为，合并为快速排序的最坏情况是排好序的情况，与其它排序算法不同。简单排序中，插入排序的复杂度与初态有关，另外两个无关。插入排序可能在最后一趟之前，所有元素都不在最终位置。选择、快速排序不稳定，其它稳定。,第六章排序：习
44、题,若待排序对象序列在排序前已按其关键字递增排列，则采用_比较次数最少【福建2006专升本】A 直接插入排序 B 快速排序 C 合并排序 D 简单选择排序在下列排序算法中，时间复杂度为O(nlogn)的是_【福建2006专升本】A 冒泡排序 B 简单选择排序 C 直接插入排序 D 堆排序,答案：A D,第六章排序：习题,在待排序记录已基本有序的前提下，下述排序方法中效率最高的是_【福建2007专升本】A 直接插入排序 B 简单选择排序 C 快速排序 D 归并排序平均排序效率最好的排序方法是_【福建2009专升本】A 直接插入排序 B 快速排序 C 简单选择排序 D 冒泡排序,答案：A B,第七
45、章树(层次数据结构),树章节的重点内容：树的相关概念(度、高度、深度、层)。树和二叉树的三序遍历。已知二叉树前中或中后序画二叉树。树中结点和度之间的关系。树和二叉树的转换。(左儿子右兄弟)线索二叉树（了解即可）。,树的定义,树是一个具有层次结构的集合，它在客观世界中广泛存在。树是由一个集合以及在该集合上定义的一种层次关系构成的。集合中的元素是树的结点，结点间的关系为父子关系。树结点之间的父子关系建立了树的层次结构。在这种层次结构中，有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。,树的定义,树的递归定义单个结点是一棵树，树根就是该结点本身。设T1Tk是树，他们的根结点为n1,
46、nk。用一个新结点n作为n1,nk的父亲，则得到一棵新树。结点n就是新树的根。结点n1,nk成为一组兄弟结点，它们都是结点n的儿子结点。还称T1,Tk为结点n的子树。为方便起见，将空集合也看作是树，成为空树，用表示。空树中没有结点。,树的定义及相关概念,A,左图所示的树，由结点的有限集A,B,C,D,E,F,G,H,I,J构成。其中A是根结点。T中其余结点分成3个互不相交的子集T1=B,E,F,I,JT2=C T3=D,G,HT1,T2,T3是根A的三棵子树，且本身又都是一棵树。,C,B,E,J,I,H,G,D,F,树的定义及相关概念,A,一个结点的儿子结点个数称为该结点的度。一棵树的度是指该
47、树中结点最大度数。树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。在左图中，A,B,E的度分别为3，2，0其中A为根结点，B为内部结点，E为叶结点，树的度为3。,C,B,E,J,I,H,G,D,F,树的定义及相关概念,A,4.如果存在树中的一个结点序列k1,k2,kj,使得结点ki是结点k(i+1)的父结点，则称该结点序列是树中从结点k1到结点kj的一条路径或道路。称这条路经的长度为j-1,它是该路径所经过的边的数目。树中任一结点有一条到其自身的长度为0的路径。左图中，结点A到结点I有一条路经ABFI,它的长度为3,C,B,
48、E,J,I,H,G,D,F,树的定义及相关概念,A,5.如果在树中存在一条从结点k到结点m的路径，则称结点k是结点m的祖先，也称结点m是结点k的子孙或后裔。在左图中，结点F的祖先有A,B和F自己，而它的子孙包括F,I和J。6.将树中一个结点的非自身的祖先和子孙分别称为该结点的真祖先和真子孙。在一棵树中，树根是唯一没有真祖先的结点。叶结点是没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。,C,B,E,J,I,H,G,D,F,树的定义及相关概念,A,7.树中一个结点的高度是指从该结点到各叶结点的最长路经的长度。树的高度是指根结点的高度。在左图中，B,C,D的高度分别为2,0,1,而
49、树的高度与结点A的高度相同为3。从树根到任意结点n有唯一的一条路经，称这条路经的长度为结点n的深度或层数。根结点的深度为0，其余结点的深度为其父结点的深度加1。深度相同的结点属于同一层。在左图中，A的深度为0，结点B,C,D的深度为1，结点E,F,G,H的深度为2，结点I,J的深度为3。在树的第2层结点有E,F,G和H,树的第0层只有一个根结点A.,C,B,E,J,I,H,G,D,F,树的遍历,树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的系统的访问，即依次对树中每个结点访问一次且仅访问一次。树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。,树的遍历,三种遍历方式的递
50、归定义：如果T是一棵空树，那么对T进行前序遍历、中序遍历和后序遍历都是空操作，得到的列表为空表。如果T是一棵单结点树，那么对T进行前序遍历、中序遍历、后序遍历都只访问这个单结点。否则对T进行前序遍历是先访问树根n,然后依次前序遍历T1,Tk,即前序遍历T1,前序遍历T2,最后前序遍历Tk。对T进行中序遍历是先中序遍历T1,然后访问树根n,接着依次对T2,Tk进行中序遍历对T进行后序遍历是先依次对T1,T2Tk进行后序遍历，最后访问树根n。,前序遍历演示,A,C,B,E,J,I,H,G,D,F,A,B,E,F,I,J,C,D,G,H,中序遍历演示,A,C,B,E,J,I,H,G,D,F,A,B,
