数据结构导论串讲

数据结构导论串讲第一页，共一百四十八页，编辑于2023年，星期三

概述

《数据结构导论》是计算机科学与技术专业的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：线性表、栈、队列、串、数组、树、二叉树、图等基本数据结构及其应用；排序和查找的原理与方法；数据在外存上的组织方法。第二页，共一百四十八页，编辑于2023年，星期三第一章概论第三页，共一百四十八页，编辑于2023年，星期三第四页，共一百四十八页，编辑于2023年，星期三本章总述要求熟悉各名词、术语的含义，掌握基本概念。包括数据、数据元素、数据项、逻辑关系和逻辑结构、运算和基本运算、数据结构、存储方式和存储结构、算法及算法分析等。注意这些概念之间的联系。第五页，共一百四十八页，编辑于2023年，星期三本章重点逻辑结构和数据结构的概念。本章难点算法的时间复杂性分析。第六页，共一百四十八页，编辑于2023年，星期三本章知识点

1.数据、数据元素、数据项数据—能被计算机存储、加工的对象通称为数据。数据元素—是数据的基本单位，在程序中作为一个整体来考虑和处理。具有完整确定的实际意义。数据项—是数据不可分割的最小标识单位。数据元素可由若干个数据项组成，数据项通常不具有完整确定的实际意义。第七页，共一百四十八页，编辑于2023年，星期三数据数据项数据元素数据、数据元素和数据项构成了数据组织的三个层次，如下图所示:第八页，共一百四十八页，编辑于2023年，星期三

2.数据结构数据结构是数据元素之间的相互关系。结构分为逻辑结构与物理结构。线性结构树形结构图状结构集合结构第九页，共一百四十八页，编辑于2023年，星期三存储结构：逻辑结构在计算机中的表示（映像）被称为存储结构，其中应该包含数据元素的内容及其关系的表示。

四种基本存储方式：

顺序存储方式特点：借助于数据元素在存储器中的位置来表示数据元素之间的逻辑关系

链式存储方式特点：借助指示元素存储地址的指针来表示数据元素之间的逻辑关系

索引存储方式

散列存储方式第十页，共一百四十八页，编辑于2023年，星期三

3.算法算法就是解决问题的方法。算法分析主要从时间复杂度、空间复杂度方面进行算法分析。时间复杂度:最坏情况时间复杂度,平均时间复杂度。Tnnlog2nn2本章结束第十一页，共一百四十八页，编辑于2023年，星期三第二章线性表第十二页，共一百四十八页，编辑于2023年，星期三第十三页，共一百四十八页，编辑于2023年，星期三本章总述本章主要讨论了线性表及它的两种存储实现：顺序实现和链接实现；另外，简单介绍了串这种特殊的线性表的运算和存储实现。线性表是一种最简单最常见的数据结构第十四页，共一百四十八页，编辑于2023年，星期三本章重点

线性结构的定义和特点；线性表的运算；顺序表和单链表的组织方法和算法设计。本章难点

单链表上的算法设计。第十五页，共一百四十八页，编辑于2023年，星期三线性表的逻辑结构定义线性表是一个含有n个数据元素的有限序列。L=(a1,a2,a3,a4,a5,a6,....,an)ai-1,

ai

,

ai+1直接前驱

直接后继线性表长度第十六页，共一百四十八页，编辑于2023年，星期三

线性结构的基本特征:线性结构是一个数据元素的有序（次序）集

1.集合中必存在唯一的一个“第一元素”；

2.集合中必存在唯一的一个“最后元素”；

3.除最后元素之外，均有唯一的后继；

4.除第一元素之外，均有唯一的前驱。第十七页，共一百四十八页，编辑于2023年，星期三顺序存储结构

用一组地址连续的存储单元依次存储线性表的元素。

顺序表特点：

逻辑顺序与物理顺序一致；

属随机存取的存储结构。第十八页，共一百四十八页，编辑于2023年，星期三......a1a2a3a4a5a6anbb+Lb+2Lb+3Lb+(n-1)L假设线性表中每个元素需占用L个存储单元LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*LL:一个数据元素所占存储量↑基地址第十九页，共一百四十八页，编辑于2023年，星期三插入、删除算法的分析插入算法的数学期望值删除算法的数学期望值设：pi=1/(n+1),qi=1/n，则可以得出：第二十页，共一百四十八页，编辑于2023年，星期三顺序表表示的优缺点优点：随机存取表中的任一结点。缺点：插入和删除运算不方便，须移动大量的结点；存储分配只能预先分配。第二十一页，共一百四十八页，编辑于2023年，星期三链式存储结构用一组任意的存储单元（可能不连续）存储线性表的数据元素。......a3......a2......a1......a4...........第二十二页，共一百四十八页，编辑于2023年，星期三链式存储结构数据元素内容该数据元素的直接后继地址datanext数据域指针域第二十三页，共一百四十八页，编辑于2023年，星期三L=(a1,a2,a3,a4,a5,a6)结点La1a2a3a4a5a6^以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。第二十四页，共一百四十八页，编辑于2023年，星期三含有头结点的空表//////^

ＬL////a1a2......an^头结点有时为了操作方便，在第一个结点之前附设一个“头结点”，以指向头结点的指针为链表的头指针指针域为空第二十五页，共一百四十八页，编辑于2023年，星期三

特点:逻辑顺序与物理顺序有可能不一致。属顺序存取的存储结构，即存取每个数据元素所花费的时间不相等。第二十六页，共一百四十八页，编辑于2023年，星期三datanextprior特点：克服单链表的单向性其它形式的链表1.双向链表(doublelinkedlist)每个结点有两个指针域第二十七页，共一百四十八页，编辑于2023年，星期三

2.循环链表表中最后一个结点的指针域指向头结点，链表形成一个环。特点从表中任何一个结点出发可扫描整个链表中的所有结点。第二十八页，共一百四十八页，编辑于2023年，星期三顺序实现与链接实现的比较时间性能比较定位运算:顺序表和单链表,均为O(n)读表元：顺序表-O(1)(随机存取);单链表-O(n)链入/摘除：顺序表-0(n);单链表-O(1)（插入、删除方便）第二十九页，共一百四十八页，编辑于2023年，星期三第三章栈、队列和数组第三十页，共一百四十八页，编辑于2023年，星期三第三十一页，共一百四十八页，编辑于2023年，星期三本章总述栈和队列是两种常用的数据结构，这两种结构与线性表有密切的联系。栈和队列的逻辑结构是线性结构，它们的基本运算与线性表的基本运算十分类似，可看作是运算受限的线性表。数组与线性表也有密切的联系。第三十二页，共一百四十八页，编辑于2023年，星期三本章重点栈和队列的特点；顺序栈和链栈上基本运算的实现和简单算法；链队上基本运算实现和简单算法设计。本章难点循环队的组织，队满、队空的条件及算法设计。第三十三页，共一百四十八页，编辑于2023年，星期三栈的类型定义插入、删除只在表尾进行的线性表被称为栈。a1a2a3a4....an插入删除第三十四页，共一百四十八页，编辑于2023年，星期三栈的特点后进先出----LIFO(LastInFirstOut)栈顶浮动栈底固定a1a2a3a4出进栈底栈顶第三十五页，共一百四十八页，编辑于2023年，星期三栈的表示和实现顺序存储结构：

顺序栈链式存储结构：

链栈第三十六页，共一百四十八页，编辑于2023年，星期三队列定义若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为队列。第三十七页，共一百四十八页，编辑于2023年，星期三a1,a2,a3,a4,...,an删除端插入端队头front队尾rear第三十八页，共一百四十八页，编辑于2023年，星期三队列特点FIFO(FirstInFirstOut)队头、队尾均是浮动的队列类型的实现链队列——链式映象循环队列——顺序映象第三十九页，共一百四十八页，编辑于2023年，星期三q4q3q2q1frontrear3210入队

Q[rear++]=e;出队

e=Q[front++]队列的顺序存储结构第四十页，共一百四十八页，编辑于2023年，星期三队列的顺序存储结构frontrear“假溢出”现象解决的方法:将队列构成环状q4q3q2q1第四十一页，共一百四十八页，编辑于2023年，星期三循环队列012345678q1q2q3q4q5rearfront入队操作：sq.rear=(sq.rear+1)%maxsize;出队操作：sq.front=(sq.front+1)%maxsize;队列空：sq.rear=sq.front队列满：((sq.rear+1)%maxsize)==sq.front;第四十二页，共一百四十八页，编辑于2023年，星期三数组是一种已经在高级语言中实现了的数据结构。通常采用顺序存储结构来存放数组。

有两种顺序映象的方式（二维数组）:

1)以行序为主序(低下标优先);

2)以列序为主序(高下标优先);第四十三页，共一百四十八页，编辑于2023年，星期三例如：

称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j

的存储位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

第四十四页，共一百四十八页，编辑于2023年，星期三矩阵的压缩存储矩阵可用二维数组来表示。实际问题中，会碰到阶数高的矩阵，但存在许多值相同的元素和零元素。压缩存储的基本思想：值相同的多个元素只分配一个存储空间，零元素不分配空间。特殊矩阵的压缩存储(对称矩阵，三角矩阵)稀疏矩阵的压缩存储(三元组顺序表)第四十五页，共一百四十八页，编辑于2023年，星期三第四章树第四十六页，共一百四十八页，编辑于2023年，星期三第四十七页，共一百四十八页，编辑于2023年，星期三本章总述本章是数据结构课程的重点之一。主要内容包括：树形结构的基本概念，定义在树形结构上的两种重要的数据结构-二叉树和树，它们的常见存储结构、遍历运算的实现以及它们之间的转换。第四十八页，共一百四十八页，编辑于2023年，星期三本章重点树形结构的概念；二叉树的定义、存储结构和遍历算法本章难点二叉树的遍历算法第四十九页，共一百四十八页，编辑于2023年，星期三二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树第五十页，共一百四十八页，编辑于2023年，星期三二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树第五十一页，共一百四十八页，编辑于2023年，星期三二叉树的重要特性性质1:

在二叉树的第i

层上至多有2i-1个结点。(i≥1)性质2:

深度为k的二叉树上至多含2k-1个结点（k≥1）性质3:

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1两类特殊的二叉树：（1）满二叉树：指的是深度为k且含有2k-1个结点的二叉树。（2）完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。性质4:

具有n个结点的完全二叉树的深度为log2n+1第五十二页，共一百四十八页，编辑于2023年，星期三性质5:

若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：

(1)若i=1，则该结点是二叉树的根，无双亲,否则，编号为i/2的结点为其双亲结点;

(2)若2i>n，则该结点无左孩子，

否则，编号为2i的结点为其左孩子结点；

(3)若2i+1>n，则该结点无右孩子结点，

否则，编号为2i+1的结点为其右孩子结点。第五十三页，共一百四十八页，编辑于2023年，星期三二叉树的存储结构1、二叉树的顺序存储表示

适用于完全二叉树或满二叉树。2、二叉树的链式存储表示

二叉链表三叉链表第五十四页，共一百四十八页，编辑于2023年，星期三二叉树遍历

顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。

遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法以遍历为基础，可以实现二叉树上的许多复杂运算。第五十五页，共一百四十八页，编辑于2023年，星期三

若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：第五十六页，共一百四十八页，编辑于2023年，星期三

若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：第五十七页，共一百四十八页，编辑于2023年，星期三

若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：第五十八页，共一百四十八页，编辑于2023年，星期三PreOrder:abcdegfhInOrder:cbegdfahPostOrder:cgefdbhaabcdefgh第五十九页，共一百四十八页，编辑于2023年，星期三树和森林

树的三种存储结构双亲表示法孩子链表表示法孩子-兄弟存储表示法

树的遍历先根遍历后根遍历层次遍历

树、森林与二叉树的关系(相互转换)注意：（1）与树对应的二叉树的根结点的右子树一定为空（2）和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟第六十页，共一百四十八页，编辑于2023年，星期三树的带权的路径长度树中所有叶子结点的带权路径长度之和

Huffman树设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫Huffman树哈夫曼算法判定树和哈夫曼树本章结束第六十一页，共一百四十八页，编辑于2023年，星期三第五章图第六十二页，共一百四十八页，编辑于2023年，星期三第六十三页，共一百四十八页，编辑于2023年，星期三本章总述本章主要讨论图这一重要的数据结构。图不同于线性结构，也不同于树形结构，在任何两个顶点之间都可能存在邻接关系。图的存储结构、图的遍历以及图的应用—最小生成树、拓扑排序。第六十四页，共一百四十八页，编辑于2023年，星期三本章重点图的存储结构和连通图的遍历。本章难点

Prim算法。第六十五页，共一百四十八页，编辑于2023年，星期三名词和术语网、子图完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林第六十六页，共一百四十八页，编辑于2023年，星期三图的存储结构一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示邻接表是图的一种链式存储结构。为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）。第六十七页，共一百四十八页，编辑于2023年，星期三邻接矩阵特点无向图的邻接矩阵是对称矩阵；有向图的邻接矩阵不一定是对称矩阵；判断任意两个点的邻接关系容易；适用于稠密图的表示。ABDCE0101000100000010010011000ABCDEABCDE第六十八页，共一百四十八页，编辑于2023年，星期三邻接表特点无向图中:顶点Vi的度为第i个单链表中的结点数。有向图中：顶点Vi的出度为第i个单链表中的结点个数；顶点Vi的入度需遍历整个邻接表,邻接点域指向Vi的结点个数。第六十九页，共一百四十八页，编辑于2023年，星期三图的遍历从图中某个顶点出发访问图中每个顶点一次且仅一次的过程。连通图深度优先搜索连通图广度优先搜索深度优先搜索：V0V1V3V7V4V2V5V6广度优先搜索序列：V0V1V2V3V4V5V6V7V0V1V3V4V2V6V5V7第七十页，共一百四十八页，编辑于2023年，星期三从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图中的其余顶点，直至图中所有和V0有路径相通的顶点都被访问到为止。连通图的深度优先搜索遍历第七十一页，共一百四十八页，编辑于2023年，星期三

从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，随后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有与V0有路径相通的顶点都被访问到为止。连通图的广度优先搜索遍历第七十二页，共一百四十八页，编辑于2023年，星期三最小生成树问题的提出：假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？该问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。第七十三页，共一百四十八页，编辑于2023年，星期三最小生成树构造—普里姆Prim算法指定图中某个顶点v作为生成树的根，随后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n个顶点为止。第七十四页，共一百四十八页，编辑于2023年，星期三12abcdegf例如:1951418271682137aedcbgf所得生成树权值和=14+8+3+5+16+21=67第七十五页，共一百四十八页，编辑于2023年，星期三如何进行拓扑排序？

1.从有向图中选取一个没有前驱的顶点，并输出之；

2.从有向图中删去此顶点以及所有以它为尾的弧；

重复上述两步，直至图空或者图不空但找不到无前驱的顶点为止。第七十六页，共一百四十八页，编辑于2023年，星期三3614752初始AOV网361475输出结点2后36147输出结点5后3647输出结点1后367输出结点4后67输出结点3后6输出结点7后空输出结点6后本章结束第七十七页，共一百四十八页，编辑于2023年，星期三第六章查找表第七十八页，共一百四十八页，编辑于2023年，星期三第七十九页，共一百四十八页，编辑于2023年，星期三本章总述本章主要介绍了查找表和查找的概念，查找表的分类，并分别详细讨论了静态查找表与动态查找表的各种常用的实现方法。散列是一种重要的查找方法。散列技术的原始动机是无需键值比较而完成查找。第八十页，共一百四十八页，编辑于2023年，星期三本章重点二分查找二叉排序树的查找散列表的查找本章难点二叉排序树的插入算法第八十一页，共一百四十八页，编辑于2023年，星期三查找表概念查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵活且方便的结构。第八十二页，共一百四十八页，编辑于2023年，星期三查找表的常见操作1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。第八十三页，共一百四十八页，编辑于2023年，星期三查找表的两个类别：

静态查找表仅作查询和检索操作的查找表。

动态查找表有时在查询之后，还需要将“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。第八十四页，共一百四十八页，编辑于2023年，星期三静态查找表一、顺序查找表在等概率查找的情况下，顺序表查找成功的平均查找长度为：二、有序查找表(二分查找)三、索引顺序表静态查找表的上述三种不同实现方法各有优缺点。顺序查找效率最低但限制最少；二分查找效率最高但限制最强；分块查找则介于上述二者之间。第八十五页，共一百四十八页，编辑于2023年，星期三动态查找表--二叉排序树1．定义2．查找算法3．插入算法4．删除算法5．查找性能的分析第八十六页，共一百四十八页，编辑于2023年，星期三二叉排序树定义二叉排序树或者是一棵空二叉树;或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；（3）它的左、右子树也都分别是二叉排序树。

重要性质：中根遍历一棵二叉树所得的结点访问序列是键值的递增序列。第八十七页，共一百四十八页，编辑于2023年，星期三查找性能的分析对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。第八十八页，共一百四十八页，编辑于2023年，星期三由关键字序列3，1，2，5，4构造而得的二叉排序树，由关键字序列1，2，3，4，5构造而得的二叉排序树，2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2第八十九页，共一百四十八页，编辑于2023年，星期三二叉平衡树是二叉排序树的另一种形式，其特点为：树中每个结点的左、右子树深度之差的绝对值不大于1，即548254821是平衡树不是平衡树构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。第九十页，共一百四十八页，编辑于2023年，星期三散列表

1)散列函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要不超出地址集合允许的范围即可；

2)由于散列函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1key2，而H(key1)=H(key2)。第九十一页，共一百四十八页，编辑于2023年，星期三构造散列函数的方法对数字的关键字可有下列构造方法：

1.数字分析法

2.平方取中法

3.基数转换法

4.除留余数法

5.随机数法实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。第九十二页，共一百四十八页，编辑于2023年，星期三散列表按照组织形式的不同，通常有两类散列表：开散列表与闭散列表。开散列表的组织方式：将所有散列地址相同的记录都链接在同一链表中。闭散列表解决冲突的基本思想：为每个键值生成一个散列地址序列d0d1…di…dm-1

d0=H(K),是K的散列地址，其余di(0<i<m)是后继散列地址。

线性探测法二次探测法

多重散列法公共溢出区法散列技术的原始动机是无需键值比较而完成查找。但由于同义词的存在，不能实现。本章结束第九十三页，共一百四十八页，编辑于2023年，星期三第七章文件第九十四页，共一百四十八页，编辑于2023年，星期三第九十五页，共一百四十八页，编辑于2023年，星期三本章总述本章针对在外存储器中的数据，讨论了它的组织方法和操作方法。文件结构是以记录的集合作为逻辑结构。如何有效的实现文件结构是本章的重点。本章着重介绍了顺序文件、索引文件以及散列文件等几种常见的组织方法。第九十六页，共一百四十八页，编辑于2023年，星期三本章总要求

熟悉文件的概念；熟悉顺序文件、索引文件和散列文件的组织方式和操作方式。第九十七页，共一百四十八页，编辑于2023年，星期三通常将存放在外存中的数据称为文件。文件是由特性相同的记录所构成的集合，每个记录由一个或多个数据项构成，这是文件的逻辑结构。文件在存储介质（如磁盘和磁带）上的实际组织方式称为文件的存储结构或物理结构，常见的有四种：顺序组织、索引组织、散列组织和链组织。文件在外存储器上组织结构主要有三种：顺序文件散列文件索引文件第九十八页，共一百四十八页，编辑于2023年，星期三

ISAM文件索引顺序存取方法ISAM(IndexedSequentialMethod)是一种专为磁盘存取设计的索引顺序文件组织方式。

ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。第九十九页，共一百四十八页，编辑于2023年，星期三

VSAM文件

VSAM(VirtualStorageAccessMethod)虚拟存储存取方法，是一种索引顺序文件的组织方式，采用动态索引结构。

B-树与B+树定义

B-树与B+树的差异

B+树广泛的使用在包括VSAM文件在内的多种文件系统中。本章结束第一百页，共一百四十八页，编辑于2023年，星期三第八章排序第一百零一页，共一百四十八页，编辑于2023年，星期三第一百零二页，共一百四十八页，编辑于2023年，星期三本章总述对于数据处理工作，排序是其最基本的运算之一。为了提高计算机的工作效率，人们提出了各种各样的排序方法和算法。本章重点介绍了5种内部排序算法：直接插入排序、快速排序、直接选择排序、堆排序和归并排序。另外，也介绍了冒泡排序等。第一百零三页，共一百四十八页，编辑于2023年，星期三本章重点快速排序，堆排序。本章难点堆排序。第一百零四页，共一百四十八页，编辑于2023年，星期三什么是排序？所谓排序是指将一组“无序”的记录序列调整为“有序”的记录序列的过程。例如：下列是一组记录对应的关键字序列

(52,49,80,36,14,58,61,23,97,75)调整为

(14,23,36,49,52,58,61,75,80,97)第一百零五页，共一百四十八页，编辑于2023年，星期三内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序为内部排序；反之，若参加排序的记录数量很大，整个排序过程不可能在内存中完成，则称此类排序为外部排序。

第一百零六页，共一百四十八页，编辑于2023年，星期三内部排序的方法按照内部排序过程使用的基本手段可以将排序方法分为5个类别：插入排序交换排序选择排序归并排序分配排序第一百零七页，共一百四十八页，编辑于2023年，星期三

1.插入排序不断地将无序子序列中的记录“插入”到有序序列中，从而逐渐地增加有序子序列的长度，直到所有记录都进入有序序列中为止。直接插入排序（基于顺序查找）折半插入排序（基于折半查找）第一百零八页，共一百四十八页，编辑于2023年，星期三

2.交换排序不断地考查待排序列中关键字之间的有序性，一旦发现非有序关系，将其“交换”，直到所有记录均按照有序性就位为止。冒泡排序快速排序第一百零九页，共一百四十八页，编辑于2023年，星期三

3.选择排序不断地从无序子序列中“选择”关键字最小(或最大)者，并将其加入到有序子序列中，以此方法增加有序子序列的长度，直到所有的记录都进入有序序列中为止。简单选择排序堆排序第一百一十页，共一百四十八页，编辑于2023年，星期三

4.归并排序通过“归并”两个或两个以上的有序子序列，逐步增加有序序列的长度，直到所有的记录都进入一个有序序列中为止。

2-路归并排序第一百一十一页，共一百四十八页，编辑于2023年，星期三堆排序堆是满足下列性质的记录序列{r1,r2,…，rn}：或堆的定义:{12,36,27,65,40,34,98,81,73,55,49}是小顶堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小顶堆)(大顶堆)1234567891011第一百一十二页，共一百四十八页，编辑于2023年，星期三rir2ir2i+1通常将该记录序列看作一棵完全二叉树，则r2i

是ri

的左孩子；r2i+1

是ri

的右孩子。1236276549817355403498是堆14不第一百一十三页，共一百四十八页，编辑于2023年，星期三

堆排序是指利用堆的特性对记录序列进行排序的一种排序方法。基本过程：1。根据原始记录序列创建堆；2。将根与堆中的最后一个结点交换；3。将堆中的最后结点从堆中删去；4。将剩余的结点重新调整成堆。第一百一十四页，共一百四十八页，编辑于2023年，星期三1、如何“建初堆”？需要解决的两个问题:2、如何调整“堆”？第一百一十五页，共一百四十八页，编辑于2023年，星期三建“初堆”的基本方法：从堆中最后一个有孩子的结点开始利用调整。40554973816436122798（40,55,49,73,12,27,98,81,64,36)12368173499881735598494064361227第一百一十六页，共一百四十八页，编辑于2023年，星期三9881497355641236274012在98和12进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。98128173641298第一百一十七页，共一百四十八页，编辑于2023年，星期三73496455129836274081在81和12进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。1281比较1273比较645512第一百一十八页，共一百四十八页，编辑于2023年，星期三73644955128198362740在73和12进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。127312645512第一百一十九页，共一百四十八页，编辑于2023年，星期三64554912738198362740在64和40进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。6440405540第一百二十页，共一百四十八页，编辑于2023年，星期三55404912738198362764在55和27进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。5527274927第一百二十一页，共一百四十八页，编辑于2023年，星期三49402712738198365564在49和36进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。49364036第一百二十二页，共一百四十八页，编辑于2023年，星期三12273640738198495564排序后的记录序列：{12，27，36，40，49，55，64，73，81，98}第一百二十三页，共一百四十八页，编辑于2023年，星期三各种排序方法的综合比较1.平均的时间性能时间复杂度为O(nlogn)：快速排序、堆排序和归并排序时间复杂度为O(n2)：直接插入排序、冒泡排序和简单选择排序第一百二十四页，共一百四十八页，编辑于2023年，星期三2.最坏时间性能时间复杂度为O(nlogn)：堆排序和归并排序时间复杂度为O(n2)：快速排序、直接插入排序、冒泡排序和简单选择排序第一百二十五页，共一百四十八页，编辑于2023年，星期三

3.当待排记录序列按关键字顺序有序时直接插入排序和起泡排序能达到O(n)的时间复杂度，快速排序的时间性能退化为O(n2)。

4.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。第一百二十六页，共一百四十八页，编辑于2023年，星期三

5.空间性能指的是排序过程中所需的辅助空间大小

1.所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；

2.快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；

3.归并排序所需辅助空间最多，其空间复杂度为O(n)。本章结束第一百二十七页，共一百四十八页，编辑于2023年，星期三考情交流本课程的应试方法和技巧复习技巧最近几年必考的内容考试情况的预测分析历年考题真题示例讲解第一百二十八页，共一百四十八页，编辑于2023年，星期三本课程的应试方法和技巧通过对历年自考试卷的分析和以往教学环节的整理总结，我认为这门课程大家学习的时候要以本课程大纲中所确定的识记、领会和应用的有关要求为依据，同时要求大家认真分析历届的真题，抓住考题的方向和规律，将理论和实际的应用联系与结合起来。大家一定要注意，不是书上所有的东西都要背下来，而是要根据不同的知识结构特点，记住基础知识，领会基本原理，认真思考实际应用。第一百二十九页，共一百四十八页，编辑于2023年，星期三复习技巧1.注意归纳整理2.注意联系实际3.熟记基础理论4.学会独立思考第一百三十页，共一百四十八页，编辑于2023年，星期三考试题型一、单项选择题二、填空题三、应用题四、算法设计题第一百三十一页，共一百四十八页，编辑于2023年，星期三最近几年必考的内容1这几年出题频率高的知识点如下：1.线性表的插入删除（顺序表、链表）2.数组、矩阵的存储（地址计算）3.二叉树的相关性质、存储以及遍历等算法4.图的邻接表存储第一百三十二页，共一百四十八页，编辑于2023年，星期三

5.Prim算法构造最小生成树

6.散列表的构建及平均查找长度分析

7.构建二叉排序树

8.排序方法，如：冒泡排序、直接插入排序、快速排序；堆排序的过程（建立初始堆、调整堆）最近几年必考的内容2第一百三十三页，共一百四十八页，编辑于2023年，星期三考试情况的预测分析根据历年来的考题分析推理，我预计（只代表个人意见）这门课的出题方向主要集中在以下知识环节上：

1.线性表的存储结构及操作（顺序表、链表）

2.基本概念理论（栈、循环队列的特点等）

3.数组、矩阵的存储

4.二叉树的相关性质、存储及遍历算法

5.图的存储结构及应用（邻接矩阵、邻接表）

6.散列表的构建及平均查找长度分析

7.各种排序方法排序过程及时间复杂度分析第一百三十四页，共一百四十八页，编辑于2023年，星期三

1.单项选择题：若在长度为n的顺序表中插入一个结点，则其结点的移动次数（）。

A、最少为0，最多为n

B、最少为1，最多为n

C、最少为0，最多为n+1

D、最少为1，最多为n+1

答案：A历年考题真题示例讲解第一百三十五页，共一百四十八页，编辑于2023年，星期三

2.填空题：对顺序表执行删除操作，其删除算法的平均时间复杂性为

（n-1）/2

。

其他算法定位算法：平均时间复杂性量级为O(n)求表长算法、读表元算法：时间复杂性为O(1).第一百三十六页，共一百四十八页，编辑于2023年，星期三3.选择题：设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（D）

A．a，b，c，d B.a，b，d，cC.d，c，b，a D.c，d，a，b第一百三十七页，共一百四十八页，编辑于2