数据结构导论串讲精.ppt

数据结构导论串讲数据结构导论串讲第1页，本讲稿共148页 概述概述数据结构导论是计算机科学与技术专业的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：线性表、栈、队列、串、数组、树、二叉树、图等基本数据结构及其应用；排序和查找的原理与方法；数据在外存上的组织方法。第2页，本讲稿共148页第一章概论第一章概论第3页，本讲稿共148页第4页，本讲稿共148页本章总述本章总述要求熟悉各名词、术语的含义，掌握基本概念。包括数据、数据元素、数据项、逻辑关系和逻辑结构、运算和基本运算、数据结构、存储方式和存储结构、算法及算法分析等。注意这些概念之间的联系。第5页，本讲稿共148页本章重点本章重点逻辑结构和数据结构的概念。本章难点本章难点算法的时间复杂性分析。第6页，本讲稿共148页本章知识点本章知识点 1.1.数据、数据元素、数据项数据、数据元素、数据项数据能被计算机存储、加工的对象通称为数据。数据元素是数据的基本单位，在程序中作为一个整体来考虑和处理。具有完整确定的实际意义。数据项是数据不可分割的最小标识单位。数据元素可由若干个数据项组成，数据项通常不具有完整确定的实际意义。第7页，本讲稿共148页数据数据数据项数据项数据元素数据元素数据、数据元素和数据项构成了数据组织的三个层次，如下图所示:第8页，本讲稿共148页2.2.数据结构数据结构数据结构是数据元素之间的相互关系。结构分为逻辑结构逻辑结构与物理结构物理结构。线性结构树形结构图状结构集合结构第9页，本讲稿共148页存储结构：逻辑结构在计算机中的表示（映像）被称为存储结构，其中应该包含数据元素的内容及其关系的表示。四种基本存储方式：四种基本存储方式：顺序存储方式顺序存储方式特点：借助于数据元素在存储器中的位置来表示数据元素之间的逻辑关系链式存储方式链式存储方式 特点：借助指示元素存储地址的指针来表示数据元素之间的逻辑关系索引存储方式索引存储方式 散列存储方式散列存储方式 第10页，本讲稿共148页3.3.算法算法算法就是解决问题的方法。算法分析主要从时间复杂度、空间复杂度方面进行算法分析。时间复杂度:最坏情况时间复杂度,平均时间复杂度。Tnnlog2nn2本章结束本章结束第11页，本讲稿共148页第二章线性表第二章线性表第12页，本讲稿共148页第13页，本讲稿共148页本章总述本章总述本章主要讨论了线性表及它的两种存储实现：顺序实现和链接实现；另外，简单介绍了串这种特殊的线性表的运算和存储实现。线性表线性表是一种最简单最常见的数据结构数据结构第14页，本讲稿共148页本章重点本章重点 线性结构的定义和特点；线性表的运算；顺序表和单链表的组织方法和算法设计。本章难点本章难点 单链表上的算法设计。第15页，本讲稿共148页线性表的逻辑结构定义线性表的逻辑结构定义线性表是一个含有n个数据元素的有限序列。L=(a1,a2,a3,a4,a5,a6,.,an)ai-1,ai ,ai+1直接前驱直接前驱 直接后继直接后继线性表长度线性表长度第16页，本讲稿共148页线性结构的基本特征线性结构的基本特征:线性结构是一个数据元素的有序（次序）集1.集合中必存在唯一的一个“第一元素”；2.集合中必存在唯一的一个“最后元素”；3.除最后元素之外，均有唯一的后继；4.除第一元素之外，均有唯一的前驱。第17页，本讲稿共148页顺序存储结构顺序存储结构用一组地址连续的存储单元依次存储线性表的元素。顺序表特点：顺序表特点：逻辑顺序与物理顺序一致；属随机存取的存储结构。第18页，本讲稿共148页.a1a1a2a2a3a3a4a4a5a5a6a6ananb bb+Lb+Lb+2Lb+2Lb+3Lb+3Lb+(n-1)Lb+(n-1)L假设线性表中每个元素需占用L个存储单元LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*LL:L:一个数据元素所占存储量一个数据元素所占存储量基地址基地址第19页，本讲稿共148页插入、删除算法的分析插入、删除算法的分析插入算法的数学期望值删除算法的数学期望值设：pi=1/(n+1),qi=1/n，则可以得出：第20页，本讲稿共148页顺序表表示的优缺点顺序表表示的优缺点优点：优点：随机存取随机存取表中的任一结点。缺点：缺点：插入和删除运算不方便，须移动大量的结点；存储分配只能预先分配。第21页，本讲稿共148页链式存储结构链式存储结构用一组任意任意的存储单元（可能不连续）存储线性表的数据元素。.a3.a2.a1.a4.第22页，本讲稿共148页链式存储结构链式存储结构数据元素内容该数据元素的直接后继地址datanext数据域指针域第23页，本讲稿共148页L=(a1,a2,a3,a4,a5,a6)结点L La1a2a3a4a5a6以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。第24页，本讲稿共148页含有头结点的空表空表/L L/a1a2.an头结点头结点有时为了操作方便，在第一个结点之前附设一个“头结点”，以指向头结点的指针为链表的头指针指针域为空指针域为空第25页，本讲稿共148页特点特点:逻辑顺序与物理顺序有可能不一致。属顺序存取顺序存取的存储结构，即存取每个数据元素所花费的时间不相等。第26页，本讲稿共148页datanextprior特点：克服单链表的单向性特点：克服单链表的单向性其它形式的链表其它形式的链表1.1.双向链表双向链表 (double linked list)(double linked list)每个结点有两个指针域第27页，本讲稿共148页2.2.循环链表循环链表表中最后一个结点的指针域指向头结点，链表形成一个环。特点特点从表中任何一个结点出发可扫描整个链表中的所有结点。第28页，本讲稿共148页顺序实现与链接实现的比较顺序实现与链接实现的比较时间性能比较时间性能比较定位运算:顺序表和单链表,均为 O(n)读表元：顺序表-O(1)(随机存取);单链表-O(n)链入/摘除：顺序表-0(n);单链表-O(1)（插入、删除方便）第29页，本讲稿共148页第三章栈、队列和数组第三章栈、队列和数组第30页，本讲稿共148页第31页，本讲稿共148页本章总述本章总述栈和队列是两种常用的数据结构，这两种结构与线性表有密切的联系。栈和队列的逻辑结构是线性结构，它们的基本运算与线性表的基本运算十分类似，可看作是运算受限的线性表。数组与线性表也有密切的联系。第32页，本讲稿共148页本章重点本章重点栈和队列的特点；顺序栈和链栈上基本运算的实现和简单算法；链队上基本运算实现和简单算法设计。本章难点本章难点循环队的组织，队满、队空的条件及算法设计。第33页，本讲稿共148页栈的类型定义栈的类型定义插入、删除只在表尾表尾进行的线性表被称为栈栈。a1 a2 a3 a4 .an插入插入删除删除第34页，本讲稿共148页栈的特点栈的特点后进先出-LIFO (Last In First Out)栈顶浮动栈底固定a1a2a3a4出出 进进栈底栈底栈顶栈顶第35页，本讲稿共148页栈的表示和实现栈的表示和实现顺序存储结构：顺序存储结构：顺序栈链式存储结构：链式存储结构：链栈第36页，本讲稿共148页队列定义队列定义若线性表的插入操作插入操作在一端进行，删除操作删除操作在另一端进行，则称此线性表为队列队列。第37页，本讲稿共148页a1,a2,a3,a4,.,an删除端删除端插入端插入端队头队头frontfront队尾队尾rearrear第38页，本讲稿共148页队列特点队列特点 FIFO(First In First Out)队头、队尾均是浮动的队列类型的实现队列类型的实现链队列链式映象循环队列顺序映象第39页，本讲稿共148页q4q3q2q1frontrear3210入队入队 Qrear+=e;Qrear+=e;出队出队 e=Qfront+e=Qfront+队列的顺序存储结构队列的顺序存储结构第40页，本讲稿共148页队列的顺序存储结构队列的顺序存储结构frontrear“假溢出”现象解决的方法:将队列构成环状环状q4q3q2q1第41页，本讲稿共148页循环队列循环队列012345678q1q2q3q4q5rearfront入队操作：sq.rear=(sq.rear+1)%maxsize;出队操作：sq.front=(sq.front+1)%maxsize;队列空：sq.rear=sq.front 队列满：(sq.rear+1)%maxsize)=sq.front;第42页，本讲稿共148页数组数组是一种已经在高级语言中实现了的数据结构。通常采用顺序存储结构来存放数组。有两种顺序映象的方式（二维数组）有两种顺序映象的方式（二维数组）:1)以行序为主序(低下标优先);2)以列序为主序(高下标优先);第43页，本讲稿共148页例如：例如：称为基地址基地址或基址。以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 第44页，本讲稿共148页矩阵的压缩存储矩阵的压缩存储矩阵可用二维数组来表示。实际问题中，会碰到阶数高的矩阵，但存在许多值相同的元素和零元素。压缩存储的基本思想：值相同的多个元素只分配一个存储空间，零元素不分配空间。特殊矩阵的压缩存储特殊矩阵的压缩存储(对称矩阵，三角矩阵对称矩阵，三角矩阵 )稀疏矩阵的压缩存储稀疏矩阵的压缩存储(三元组顺序表三元组顺序表)第45页，本讲稿共148页第四章树第四章树第46页，本讲稿共148页第47页，本讲稿共148页本章总述本章总述本章是数据结构课程的重点之一。主要内容包括：树形结构的基本概念，定义在树形结构上的两种重要的数据结构-二叉树和树，它们的常见存储结构、遍历运算的实现以及它们之间的转换。第48页，本讲稿共148页本章重点本章重点树形结构的概念；二叉树的定义、存储结构和遍历算法本章难点本章难点二叉树的遍历算法第49页，本讲稿共148页二叉树或为空树空树；或是由一个根结点根结点加上两棵两棵分别称为左子树左子树和右子树的、互不交的二叉树互不交的二叉树组成。ABCDEFGHK根结点根结点左子树左子树右子树右子树第50页，本讲稿共148页二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均不为左右子树均不为空树空树第51页，本讲稿共148页二叉树的重要特性二叉树的重要特性性质性质1:1:在二叉树的第 i 层上至多有2i-1 个结点。(i1)性质性质2:2:深度为 k 的二叉树上至多含 2k-1 个结点（k1）性质性质3:3:对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1两类特殊的二叉树：两类特殊的二叉树：（1）满二叉树：指的是深度为k且含有2k-1个结点的二叉树。（2）完全二叉树：树中所含的n个结点和满二叉树中编号为1 至n的结点一一对应。性质性质4:4:具有 n 个结点的完全二叉树的深度为 log2n+1第52页，本讲稿共148页性质性质5:5:若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1)若 i=1，则该结点是二叉树的根，无双亲,否则，编号为 i/2 的结点为其双亲结点;(2)若 2in，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。第53页，本讲稿共148页二叉树的存储结构二叉树的存储结构1、二叉树的顺序存储表示 适用于完全二叉树或满二叉树。适用于完全二叉树或满二叉树。2、二叉树的链式存储表示 二叉链表 三叉链表第54页，本讲稿共148页二叉树遍历二叉树遍历 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。遍历算法遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法以遍历为基础，可以实现二叉树上的许多复杂运算。第55页，本讲稿共148页 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：第56页，本讲稿共148页 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：第57页，本讲稿共148页 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：第58页，本讲稿共148页PreOrder:a b c d e g f hInOrder:c b e g d f a hPostOrder:c g e f d b h aabcdefgh第59页，本讲稿共148页 树和森林树和森林树的三种存储结构树的三种存储结构 双亲表示法 孩子链表表示法 孩子-兄弟存储表示法树的遍历树的遍历 先根遍历 后根遍历 层次遍历树、森林与二叉树的关系树、森林与二叉树的关系(相互转换相互转换)注意：注意：（1）与树对应的二叉树的根结点的右子树一定为空（2）和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟第60页，本讲稿共148页树的带权的路径长度树中所有叶子结点的带权路径长度之和Huffman树设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫Huffman树哈夫曼算法 判定树和哈夫曼树判定树和哈夫曼树 本章结束本章结束第61页，本讲稿共148页第五章图第五章图第62页，本讲稿共148页第63页，本讲稿共148页本章总述本章总述本章主要讨论图这一重要的数据结构。图不同于线性结构，也不同于树形结构，在任何两个顶点之间都可能存在邻接关系。图的存储结构、图的遍历以及图的应用最小生成树、拓扑排序。第64页，本讲稿共148页本章重点本章重点图的存储结构和连通图的遍历。本章难点本章难点Prim算法。第65页，本讲稿共148页名词和术语名词和术语网、子图 完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林第66页，本讲稿共148页图的存储结构图的存储结构一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示 邻接表是图的一种链式存储结构。为图中每个顶点建立一个单链表，第i个单链表中的结点表示依 附于顶点Vi的边（有向图中指以Vi为尾的弧）。第67页，本讲稿共148页邻接矩阵特点邻接矩阵特点无向图的邻接矩阵是对称矩阵；有向图的邻接矩阵不一定是对称矩阵；判断任意两个点的邻接关系容易；适用于稠密图的表示。ABDCE0101000100000010010011000A B C D EA BCDE第68页，本讲稿共148页邻接表特点邻接表特点无向图中:顶点Vi的度为第i个单链表中的结点数。有向图中：顶点Vi的出度为第i个单链表中的结点个数；顶点Vi的入度需遍历整个邻接表,邻接点域指向Vi的结点个数。第69页，本讲稿共148页图的遍历图的遍历从图中某个顶点出发访问图中每个顶点一次且仅一次的过程。连通图深度优先搜索 连通图广度优先搜索深度优先搜索：深度优先搜索：V0V0 V1 V1 V3V3 V7 V7V4V4V2 V2 V5 V5 V6 V6 广度优先搜索序列：广度优先搜索序列：V0V0 V1 V1 V2V2 V3 V3 V4V4V5V5V6V6V7V7V0V1V3V4V2V6V5V7第70页，本讲稿共148页从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图中的其余顶点，直至图中所有和V0有路径相通的顶点都被访问到为止。连通图的深度优先搜索遍历连通图的深度优先搜索遍历第71页，本讲稿共148页 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，随后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有与V0有路径相通的顶点都被访问到为止。连通图的广度优先搜索遍历连通图的广度优先搜索遍历第72页，本讲稿共148页最小生成树最小生成树问题的提出：假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？该问题等价于：该问题等价于：构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。第73页，本讲稿共148页最小生成树构造最小生成树构造普里姆普里姆PrimPrim算法算法指定图中某个顶点 v 作为生成树的根，随后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n 个顶点为止。第74页，本讲稿共148页12abcdegf例如例如:1951418271682137aedcbgf所得生成树权值和所得生成树权值和=14+8+3+5+16+21=67第75页，本讲稿共148页如何进行拓扑排序？如何进行拓扑排序？1.从有向图中选取一个没有前驱的顶点，并输出之；2.从有向图中删去此顶点以及所有以它为尾的弧；重复上述两步，直至图空或者图不空但找不到无前驱的顶点为止。第76页，本讲稿共148页3614752初始初始AOVAOV网网361475输出结点输出结点2 2后后36147输出结点输出结点5后后3647输出结点输出结点1后后367输出结点输出结点4后后67输出结点输出结点3后后6输出结点输出结点7后后空空输出结点输出结点6后后本章结束本章结束第77页，本讲稿共148页第六章查找表第六章查找表第78页，本讲稿共148页第79页，本讲稿共148页本章总述本章总述本章主要介绍了查找表和查找的概念，查找表的分类，并分别详细讨论了静态查找表与动态查找表的各种常用的实现方法。散列是一种重要的查找方法。散列技术的原始动机是无需键值比较而完成查找。第80页，本讲稿共148页本章重点本章重点 二分查找 二叉排序树的查找 散列表的查找本章难点本章难点 二叉排序树的插入算法第81页，本讲稿共148页查找表概念查找表概念查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵活且方便的结构。第82页，本讲稿共148页查找表的常见操作查找表的常见操作1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。第83页，本讲稿共148页查找表的两个类别：查找表的两个类别：静态查找表静态查找表仅作查询和检索操作的查找表。动态查找表动态查找表有时在查询之后，还需要将“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。第84页，本讲稿共148页静态查找表静态查找表一、顺序查找表一、顺序查找表在等概率查找的情况下，顺序表查找成功的平均查找长度为：二、有序查找表二、有序查找表 (二分查找二分查找)三、索引顺序表三、索引顺序表静态查找表的上述三种不同实现方法各有优缺点。顺序查找效率最低但限制最少；二分查找效率最高但限制最强；分块查找则介于上述二者之间。第85页，本讲稿共148页动态查找表动态查找表-二叉排序树二叉排序树1定义2查找算法3插入算法4删除算法5查找性能的分析第86页，本讲稿共148页二叉排序树定义二叉排序树定义二叉排序树或者是一棵空二叉树;或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；（3）它的左、右子树也都分别是二叉排序树。重要性质：重要性质：中根遍历一棵二叉树所得的结点访问序列是键值的递增序列。第87页，本讲稿共148页查找性能的分析查找性能的分析对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。第88页，本讲稿共148页由关键字序列 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第89页，本讲稿共148页二叉平衡树是二叉排序树的另一种形式，其特点为：树中每个结点的左、右子树深度之差的绝对值不大于1，即548254821是平衡树不是平衡树构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。第90页，本讲稿共148页散列表散列表1)散列函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要不超出地址集合允许的范围即可；2)由于散列函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1key1 key2 key2，而 H(key1)=H(key2)H(key1)=H(key2)。第91页，本讲稿共148页构造散列函数的方法构造散列函数的方法对数字的关键字可有下列构造方法：1.数字分析法2.平方取中法3.基数转换法4.除留余数法5.随机数法实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。第92页，本讲稿共148页散列表散列表按照组织形式的不同，通常有两类散列表：开散列表开散列表与闭散列表闭散列表。开散列表的组织方式：将所有散列地址相同的记录都链接在同一链表中。闭散列表解决冲突的基本思想：为每个键值生成一个散列地址序列d0 d1 di dm-1d0=H(K),是K的散列地址，其余 di(0im)是后继散列地址。线性探测法线性探测法 二次探测法二次探测法 多重散列法多重散列法 公共溢出区法公共溢出区法散列技术的原始动机是无需键值比较而完成查找。散列技术的原始动机是无需键值比较而完成查找。但由于同义词的存在，不能实现。但由于同义词的存在，不能实现。本章结束本章结束第93页，本讲稿共148页第七章文件第七章文件第94页，本讲稿共148页第95页，本讲稿共148页本章总述本章总述本章针对在外存储器中的数据，讨论了它的组织方法和操作方法。文件结构是以记录的集合作为逻辑结构。如何有效的实现文件结构是本章的重点。本章着重介绍了顺序文件、索引文件以及散列文件等几种常见的组织方法。第96页，本讲稿共148页本章总要求本章总要求 熟悉文件的概念；熟悉顺序文件、索引文件和散列文件的组织方式和操作方式。第97页，本讲稿共148页通常将存放在外存中的数据称为文件。文件是由特性相同的记录所构成的集合，每个记录由一个或多个数据项构成，这是文件的逻辑结构。文件在存储介质（如磁盘和磁带）上的实际组织方式称为文件的存储结构或物理结构，常见的有四种：顺序组织、索引组织、散列组织和链组织。文件在外存储器上组织结构主要有三种：顺序文件 散列文件 索引文件 第98页，本讲稿共148页ISAMISAM文件文件索引顺序存取方法ISAM(Indexed Sequential Method)是一种专为磁盘存取设计的索引顺序文件组织方式。ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。第99页，本讲稿共148页VSAMVSAM文件文件VSAM(Virtual Storage Access Method)虚拟存储存取方法，是一种索引顺序文件的组织方式，采用动态索引结构。B-B-树与树与B+B+树树定义B-树与B+树 的差异B+树广泛的使用在包括VSAM文件在内的多种文件系统中。本章结束本章结束第100页，本讲稿共148页第八章排序第八章排序第101页，本讲稿共148页第102页，本讲稿共148页本章总述本章总述对于数据处理工作，排序是其最基本的运算之一。为了提高计算机的工作效率，人们提出了各种各样的排序方法和算法。本章重点介绍了5种内部排序算法：直接插入排序、快速排序、直接选择排序、堆排序和归并排序。另外，也介绍了冒泡排序等。第103页，本讲稿共148页本章重点本章重点快速排序，堆排序。本章难点本章难点堆排序。第104页，本讲稿共148页什么是排序？什么是排序？所谓排序是指将一组“无序”的记录序列调整为“有序”的记录序列的过程。例如：下列是一组记录对应的关键字序列(52,49,80,36,14,58,61,23,97,75)调整为(14,23,36,49,52,58,61,75,80,97)第105页，本讲稿共148页内部排序和外部排序内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序为内部排序；反之，若参加排序的记录数量很大，整个排序过程不可能在内存中完成，则称此类排序为外部排序。第106页，本讲稿共148页内部排序的方法内部排序的方法按照内部排序过程使用的基本手段可以将排序方法分为5个类别：插入排序交换排序选择排序归并排序分配排序第107页，本讲稿共148页1.1.插入排序插入排序不断地将无序子序列中的记录“插入”到有序序列中，从而逐渐地增加有序子序列的长度，直到所有记录都进入有序序列中为止。直接插入排序（基于顺序查找）折半插入排序（基于折半查找）第108页，本讲稿共148页2.2.交换排序交换排序不断地考查待排序列中关键字之间的有序性，一旦发现非有序关系，将其“交换”，直到所有记录均按照有序性就位为止。冒泡排序快速排序第109页，本讲稿共148页3.3.选择排序选择排序不断地从无序子序列中“选择”关键字最小(或最大)者，并将其加入到有序子序列中，以此方法增加有序子序列的长度，直到所有的记录都进入有序序列中为止。简单选择排序堆排序第110页，本讲稿共148页4.4.归并排序归并排序通过“归并”两个或两个以上的有序子序列，逐步增加有序序列的长度，直到所有的记录都进入一个有序序列中为止。2-路归并排序第111页，本讲稿共148页堆排序堆排序堆是满足下列性质的记录序列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不是堆(小顶堆)(大顶堆)1 2 3 4 5 6 7 8 9 10 11第112页，本讲稿共148页rir2i r2i+1 通常将该记录序列看作一棵完全二叉树，则 r2i 是 ri 的左孩子；r2i+1 是 ri 的右孩子。1236276549817355403498是堆14不不第113页，本讲稿共148页堆排序是指利用堆的特性对记录序列进行排序的一种排序方法。基本过程：1。根据原始记录序列创建堆；2。将根与堆中的最后一个结点交换；3。将堆中的最后结点从堆中删去；4。将剩余的结点重新调整成堆。第114页，本讲稿共148页1、如何“建初堆”？需要解决的两个问题:2、如何调整“堆”？第115页，本讲稿共148页建“初堆”的基本方法：从堆中最后一个有孩子的结点开始利用调整。40554973816436122798（40,55,49,73,12,27,98,81,64,36)12368173499881735598494064361227第116页，本讲稿共148页9881497355641236274012在 98 和 12 进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。98128173641298第117页，本讲稿共148页73496455129836274081在 81 和 12 进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。1281比较比较1273比较比较645512第118页，本讲稿共148页73644955128198362740在 73 和 12 进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。127312645512第119页，本讲稿共148页64554912738198362740在 64 和 40 进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。6440405540第120页，本讲稿共148页55404912738198362764在 55 和 27 进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。5527274927第121页，本讲稿共148页49402712738198365564在 49 和 36 进行互换之后，破坏了“堆”的特性，因此，需要对它进行“筛选”。49364036第122页，本讲稿共148页12273640738198495564排序后的记录序列：12，27，36，40，49，55，64，73，81，98第123页，本讲稿共148页各种排序方法的综合比较各种排序方法的综合比较1.1.平均的时间性能平均的时间性能时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序时间复杂度为 O(n2)：直接插入排序、冒泡排序和简单选择排序第124页，本讲稿共148页2.2.最坏时间性能最坏时间性能时间复杂度为 O(nlogn)：堆排序和归并排序时间复杂度为 O(n2)：快速排序、直接插入排序、冒泡排序和简单选择排序第125页，本讲稿共148页3.3.当待排记录序列按关键字顺序有序时当待排记录序列按关键字顺序有序时直接插入排序和起泡排序能达到O(n)的时间复杂度，快速排序的时间性能退化为O(n2)。4.4.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。改变。第126页，本讲稿共148页5.5.空间性能空间性能指的是排序过程中所需的辅助空间大小1.所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；2.快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；3.归并排序所需辅助空间最多，其空间复杂度为 O(n)。本章结束本章结束第127页，本讲稿共148页考情交流考情交流本课程的应试方法和技巧复习技巧最近几年必考的内容考试情况的预测分析历年考题真题示例讲解第128页，本讲稿共148页本课程的应试方法和技巧本课程的应试方法和技巧通过对历年自考试卷的分析和以往教学环节的整理总结，我认为这门课程大家学习的时候要以本课程大纲中所确定的识记、领会和应用的有关要求为依据，同时要求大家认真分析历届的真题，抓住考题的方向和规律，将理论和实际的应用联系与结合起来。大家一定要注意，不是书上所有的东西都要背下来，而是要根据不同的知识结构特点，记住基础知识，领会基本原理，认真思考实际应用。第129页，本讲稿共148页复习技巧复习技巧1.1.注意归纳整理注意归纳整理2.2.注意联系实际注意联系实际3.3.熟记基础理论熟记基础理论4.4.学会独立思考学会独立思考第130页，本讲稿共148页考试题型考试题型一、单项选择题一、单项选择题二、填空题二、填空题三、应用题三、应用题四、算法设计题四、算法设计题 第131页，本讲稿共148页最近几年必考的内容最近几年必考的内容1 1这几年出题频率高的知识点如下：1.线性表的插入删除（顺序表、链表）2.数组、矩阵的存储（地址计算）3.二叉树的相关性质、存储以及遍历等算法4.图的邻接表存储第132页，本讲稿共148页5.Prim算法构造最小生成树6.散列表的构建及平均查找长度分析7.构建二叉排序树8.排序方法，如：冒泡排序、直接插入排序、快速排序；堆排序的过程（建立初始堆、调整堆）最近几年必考的内容最近几年必考的内容2 2第133页，本讲稿共148页考试情况的预测分析考试情况的预测分析根据历年来的考题分析推理，我预计（只代表个人意见）这门课的出题方向主要集中在以下知识环节上：1.线性表的存储结构及操作（顺序表、链表）2.基本概念理论（栈、循环队列的特点等）3.数组、矩阵的存储4.二叉树的相关性质、存储及遍历算法5.图的存储结构及应用（邻接矩阵、邻接表）6.散列表的构建及平均查找长度分析 7.各种排序方法排序过程及时间复杂度分析第134页，本讲稿共148页1.1.单项选择题：单项选择题：若在长度为n的顺序表中插入一个结点，则其结点的移动次数（）。A、最少为0，最多为n B、最少为1，最多为nC、最少为0，最多为n+1 D、最少为1，最多为n+1答案：答案：A A历年考题真题示例讲解历年考题真题示例讲解第135页，本讲稿共148页2.2.填空题：填空题：对顺序表执行删除操作，其删除算法的平均时间复杂性为 （n-1）/2。其他算法定位算法：平均时间复杂性量级为O(n)求表长算法、读表元算法：时间复杂性为O(1).第136页，本讲稿共148页3.3.选择题：选择题：设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（D ）Aa，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b第137页，本讲稿共148页4.4.填空题：填空题：二维数组A56 采用按照列为主序的存储方式，每个元素占3个存储单元，若A00的存储地址是100,则A43的存储地址为：157 (100+(5*3+4)*3)=1575.5.选择题：选择题：FORTRAN语言对数组元素的存放方式通常采用（B）A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.按行和列为主的存储结构第138页，本讲稿共148页6.6.选择题：选择题：关于二叉树性质的描述，正确的是（A）A.二叉树结点的个数可以为0B.二叉树至少含有一个根结点C.二叉树若存在两个结点，则必有一个为根，另一个为左 孩子D.二叉树若存在三个结点，则必有一个为根，另两个分别 为左、右孩子第139页，本讲稿共148页7.7.选择题：选择题：下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（A）A.集合B.线性结构C.树形结构D.图形结构8一棵平衡二叉树中任一结点的平衡因子只可能是_-1,0,1_。9.对二叉排序树进行_中根_遍历，可得到排好序的递增结点序列。第140页，本讲稿共148页10.10.选择题选择题:具有10个顶点的有向完全图应具有（）。A.20条狐 B.50条狐 C.90条狐 D.100条狐答案：C11.11.填空题：填空题：对于n个顶点的生成树，其边的个数为 n-1 。第141页，本讲稿共148页12.12.选择题选择题:对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（A）A.24 B.25 C.98 D.99第142页，本讲稿共148页13.13.选择题选择题:设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（B ）A36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88 D.44，36，49，55，88，8149，81，55，36，44，8844，81，55，36，49，8844，49，55，36，81，8844，36，55，49，81，8844，36，49，55，81，88第143页，本讲稿共148页14.有向图G用邻接矩阵A1n，1n存储，其第i列的所有元素之和等于顶点Vi的_入度_。15.快速排序最好情况下的时间复杂度为_o(nlogn)_，最坏情况下的时间复杂度为_O(n2)_。第144页，本讲稿共148页251334720153716.从一个空的二叉排序树开始，依次插入关键字25、13、15