数据结构c语言版复习提纲及重点.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,-,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,Data Structures,西安电子科技大学,软件学院,-,School of Software,Xidian University,China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数据结构c语言版复习提纲及重点,数据结构c语言版复习提纲及重点数据结构c语言版复习提纲及重点,2,关于考试,考题形式：,选择题（20,%,）,简答题（60%）,算法题（20%）,课程成绩：,期末考试成绩占,70%,，平时成绩占,30%,平时成绩由作业、考勤、程序验收和实验报告组成。,2,3,第一章 绪论,本章内容：,1.1 什么是数据结构,1.2,基本概念和术语,1.3,抽象数据类型的表示及实现,1.4,算法和算法分析,1.4.1,算法的概念及,5,个重要特性,1.4.2,算法设计的要求,1.4.3,算法效率的度量,1.4.4,算法的存储空间的需求,3,4,第一章 绪论,本章学习要点：,熟悉各名词、术语的含义，理解逻辑结构和存储结构（物理结构）概念。,理解算法五个重要特性的确切含义。,掌握计算语句频度和估算算法时间复杂度的基本方法。,4,5,例题,数据结构中的逻辑结构是指,(,),，物理结构是指（）。,算法的基本特征包括有穷性、,(),、,(),、有输入和输出。,算法的有穷性是指（）。,算法的确定性是指（）。,算法的可行性是指（）。,算法分析的两个主要内容是分析算法的（）和空间复杂度。,5,6,例题,语句频度是指（）。,设,n,为正整数，对下面的程序段，写出语句,、,、的频度及该程序段的时间复杂度。,for(i=1;i=n;i+),s=0;,n,for(j=1;j,MAXQSIZE,(2),（,Q.rear,+1,）,MAXQSIZE,(3)Q.baseQ.rear,1,2,7,0,3,5,4,6,e,6,e,7,e,8,e,9,e,10,Q.rear,27,例题,#define MAXQSIZE 100 /,最大队列长度,typedef struct,Qelemtype*base;/,队列空间的首地址,int length,rear;/,队列长度和队尾元素位置,SqQueue,；,Status DeQueue,（,SqQueue&Q,Qelemtype&e,）,/,非空队列,Q,队头元素出队列,if,（,（,1,）,）,return ERROR,；,/,队列空,e=Q.base,（,2,）,;/,计算队头元素,e,的位置,Q.length-,；,/,队列长度减,1,return OK;,/,(1)Q.length=0,(2),（,Q.rear Q.length,+1+MAXQSIZE,）,MAXQSIZE,1,2,7,0,3,5,4,6,e,6,e,7,e,8,e,9,e,10,Q.rear,28,29,第四章 串,本章内容：,4.1,串类型的定义,4.2,串的表示和实现,4.3,串的模式匹配算法,4.4,串操作应用示例,29,30,第四章 串,本章学习要点：,掌握串的七种基本操作（串赋值、求子串、串替换、串连接等）的定义。,掌握串在不同存储方式下基本运算的实现方法。,掌握基本的串的模式匹配算法，了解串匹配的,KMP,算法。,掌握,NEXT,函数的定义及计算。,30,31,第五章 数组及广义表,本章内容：,5.1,数组的定义,5.2,数组的表示和实现,5.3,矩阵的压缩存储,5.3.1,特殊矩阵,5.3.2,稀疏矩阵,5.4,广义表,5.3.1,基本概念，非空广义表求表头、表尾运算,5.3.2,存储结构,31,32,第五章 数组及广义表,本章学习要点：,掌握数组在按行（列）存储的元素地址计算方法。,掌握特殊矩阵进行压缩存储时的下标变换方式。,了解稀疏矩阵的压缩存储方法。,了解广义表的基本概念、运算和存储结构。,32,33,例题,设有下三角矩阵,A0.8,0.8,如下所示，将该三角矩阵的非零元素按行优先压缩存储在数组,B1.m,中，如果每个元素占两个存储单元，问：,1)m,的值至少为多少？,A3,1,的值存储在数组,B,的哪个元素中？,2),若,A0,0,（即,B1,）的起始地址为,100,，则元素,Ai,j(0i8,0ji),的地址计算公式是什么？,45 B8,100,+(,i(i,+1)/2+j)*2,33,34,第六章 树和二叉树,本章内容,6.1,树的定义和基本术语,6.2,二叉树,6.2.1,二叉树的定义及基本运算,6.2.2,二叉树的性质,6.2.3,二叉树的存储结构,6.3,遍历二叉树和线索二叉树,6.3.1,遍历二叉树,6.3.2,线索二叉树,6.4,树和森林,6.4.1,树的存储结构,6.4.2,森林及二叉树的转换,6.6,哈夫曼树及应用,6.6.1,哈夫曼树（最优二叉树）,6.6.2,哈夫曼编码,34,35,第六章 树和二叉树,本章要点：,掌握二叉树的结构特性和性质。,熟悉二叉树的顺序存储和链式存储。,掌握二叉树的先序、中序和后序遍历递归算法。,了解线索二叉树的概念。,理解树的孩子兄弟表示法，掌握树、森林及二叉树之间的转换方法。,掌握建立哈夫曼树和哈夫曼编码的方法。,35,36,例题,一棵满二叉树中共有,n,个结点，其中有,m,个叶子结点，则,n,和,m,的关系为（,n=2m-1,）。,2.,将一棵有,50,个结点的完全二叉树从树根结点开始，由根向下，每一层从左到右，顺序地存储在一个一维数组,bt1.50,中，这棵二叉树最下面一层上最左边一个结点存储在数组元素,(),中。,36,37,例题,在有,n,个结点的二叉树的二叉链表中必定存在（,n+1,）个空链域。,先序遍历序列及中序遍历序列相同的二叉树为（,D,）。,A.,根结点无左子树的二叉树,B.,根结点无右子树的二叉树,C.,只有根结点的二叉树或非叶子结点只有左子树的二叉树,D.,只有根结点的二叉树或非叶子结点只有右子树的二叉树,已知一棵二叉树的后序遍历序列为,G,DB,EF,CA,，中序遍历序列为,DGBAECF,，画出此二叉树。,37,38,例题,二叉树第,i,层上的结点数目最多为（,2,i-1,）。,假设二叉树中所有非叶子结点都有左、右子树，则对有,m,个叶子结点的此类二叉树，结点总数为（,2m-1,）。,树,T,的度为,4,，其中度为,1,、,2,、,3,、,4,的结点个数分别为,4,、,2,、,1,、,1,，则,T,中的叶子结点个数为（,8,）。,/t,0,=t,2,+2t,3,+3t,4,+1,高度为的满,k,叉树，第,i,层（,i,）的结点数目为（,k,i-1,）。,5.,可采用孩子,-,兄弟表示法将树转换成二叉树，因此，在对应的二叉树中，（,D,）。,A.,在树中,A,是,B,的父结点，在二叉树中,A,是,B,的左兄弟,B.,在树中,A,是,B,的父结点，在二叉树中,A,是,B,的左孩子,C.,在树中,A,是,B,的右兄弟结点，在二叉树中,A,是,B,的父结点,D.,在树中,A,是,B,的右兄弟结点，在二叉树中,A,是,B,的右孩子,38,39,第七章 图,本章内容：,7.1,图的定义和术语,7.2,图的存储结构,7.2.1,数组表示法（邻接矩阵表示法）,7.2.2,邻接表,7.3,图的遍历,7.4,最小代价生成树,7.5,拓扑排序、关键路径,7.6,最短路径,39,40,第七章 图,本章学习要点：,熟悉图的基本概念。,掌握图的邻接矩阵存储（数组表示法）和邻接表存储结构。,掌握图的深度优先遍历和广度优先遍历算法。,了解求解最小生成树的算法（Prim算法和Kruskal算法）,了解AOV网、AOE网的概念和拓扑排序的方法；,了解最短路径问题及其求解算法。,40,41,T7.1,5,1,4,2,3,6,0 0 0 0 0 0,1 0 0 1 0 0,0 1 0 0 0 1,0 0 1 0 1 1,1 0 0 0 0 0,1 1 0 0 1 0,(2),邻接矩阵,(3),邻接表,1,4,2,6,5,6,3,1,1,2,5,1,2,3,4,5,6,V,1,V,2,V,3,V,4,V,5,V,6,1,2,3,4,5,6,1 2 3 4 5 6,41,42,例题,对于有,n,个顶点的完全无向图，其边数,e,等于（,n(n-1)/2,）。,一个连通图的生成树是一个（,极小,）连通子图，,n,个顶点的生成树有（,n-1,）条边。,有,5,个顶点的无向图，至少需要（,7,）条边才能保证是连通的。,假设含,n,个结点的无向图形成一个环，则它的生成树为（,n,）个。,G,是一个有,28,条边的非连通无向图，则该图至少有（,9,）个顶点。,在一个无向图的邻接表中，若表结点的个数是,m,，则图中边的条数是（,m/2,）条。,42,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示；,2.,写出该图的邻接表表示；,3.,给出从顶点,v1,出发的深度优先遍历序列；,4.,若将该图视为无向图，用克鲁斯卡尔算法求最小生成树；,5.,写出该有向图所有可能的拓扑序列。,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,43,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示,；,2.,写出该图的邻接表表示；,3.,给出从顶点,v1,出发的深度优先遍历序列；,3,5,30 60 ,40 5,6,4,5,50 ,3,1,3,6,70,1,2,3,4,5,6,7,1 2 3 4 5 6 7,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,44,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示；,2.,写出该图的邻接表表示,；,3.,给出从顶点,v1,出发的深度优先遍历序列；,1,2,3,4,5,6,7,2,35,3,30,4,60,3,40,5,56,5,45,6,50,7,31,3,36,7,70,V,1,V,2,V,3,V,4,V,5,V,6,V,7,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,深度优先遍历序列：,v1 v2 v3 v5 v7 v4 v6,45,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示；,2.,写出该图的邻接表表示；,3.,给出从顶点,v1,出发的深度优先遍历序列；,4.,若将该图视为无向图，用克鲁斯卡尔算法求最小生成树。,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,v1,v4,v3,v2,v5,v6,v7,（a）生成树的起始状态,46,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示；,2.,写出该图的邻接表表示；,3.,给出从顶点,v1,出发的深度优先遍历序列；,4.,若将该图视为无向图，用克鲁斯卡尔算法求最小生成树。,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,v1,v4,v3,v2,v5,v6,v7,30,（b）加入第1条边,47,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示；,2.,写出该图的邻接表表示；,3.,给出从顶点,v1,出发的深度优先遍历序列；,4.,若将该图视为无向图，用克鲁斯卡尔算法求最小生成树。,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,v1,v4,v3,v2,v5,v6,v7,30,31,（c）加入第2条边,48,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示；,2.,写出该图的邻接表表示；,3.,给出从顶点,v1,出发的深度优先遍历序列；,4.,若将该图视为无向图，用克鲁斯卡尔算法求最小生成树。,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,v1,v4,v3,v2,v5,v6,v7,30,31,35,（d）加入第3条边,49,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示；,2.,写出该图的邻接表表示；,3.,给出从顶点,v1,出发的深度优先遍历序列；,4.,若将该图视为无向图，用克鲁斯卡尔算法求最小生成树。,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,v1,v4,v3,v2,v5,v6,v7,30,31,35,36,（e）加入第4条边,50,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示；,2.,写出该图的邻接表表示；,3.,给出从顶点,v1,出发的深度优先遍历序列；,4.,若将该图视为无向图，用克鲁斯卡尔算法求最小生成树。,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,v1,v4,v3,v2,v5,v6,v7,30,31,35,36,45,（f）加入第5条边,51,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示；,2.,写出该图的邻接表表示；,3.,给出从顶点,v1,出发的深度优先遍历序列；,4.,若将该图视为无向图，用克鲁斯卡尔算法求最小生成树。,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,v1,v4,v3,v2,v5,v6,v7,30,31,35,36,45,50,（g）加入第6条边，完成,52,例题,已知一赋权有向图如下：,1.,写出该图的邻接矩阵表示；,2.,写出该图的邻接表表示；,3.,给出从顶点,v1,出发的深度优先遍历序列；,4.,若将该图视为无向图，用克鲁斯卡尔算法求最小生成树；,5.,写出该有向图所有可能的拓扑序列。,35,30,60,40,56,45,36,50,31,70,v1,v4,v3,v2,v5,v6,v7,v1 v2 v4 v6 v3 v5 v7,v1 v4 v6 v2 v3 v5 v7,v1 v4 v2 v6 v3 v5 v7,53,54,第九章 查找,本章内容：,9.1,静态查找表,9.1.1,顺序表的查找,9.1.2,有序表的查找,9.1.4,索引顺序表的查找,9.2,动态查找表,9.2.1,二叉排序树和平衡二叉树,9.2.2 B-树和B+树,9.3,哈希表,54,55,第九章 查找,本章要点：,掌握顺序查找方法和折半查找算法。,掌握二叉排序树的构造和查找算法，以及在二叉排序树中插入结点和删除结点的过程。,了解平衡二叉树的定义和特点，了解B-树的定义。,掌握哈希表的构造方法，理解哈希表及其它结构查找表的差别。,掌握按定义计算各种查找方法在等概率情况下查找成功和不成功的平均查找长度。,55,56,例题,对于查找算法来说,通常以（,平均查找长度,）作为衡量查找算法好坏的依据,.,在关键字序列为（,5,10,19,21,28,34,41,，,53,58,65,）的顺序表中，用折半法查找关键字为,5,的记录（,mid,（,low,high,）,DIV 2,），需要经过（,3,）次比较。,二叉排序树的特点是（）。,在平衡二叉树中，任意结点的左、右子树的高度之差为（,-1,、,0,、,1,）。,56,57,例题,在有,15,个元素构成的有序表,A1.15,中进行折半查找（向上取整），画出折半查找判定树，等概率查找的情况下，平均查找长度是（,49/15,）。,a,8,a,4,a,12,a,2,a,6,a,10,a,14,a,1,a,3,a,5,a,7,a,9,a,11,a,13,a,15,57,例题,依次输入表,(30,，,15,，,28,，,20,，,24,，,10,，,12,，,68,，,35,，,50,，,46,，,55),中的元素，生成一棵二叉树排序树。,（,1,）试画出生成之后的二叉排序树；,（,2,）在等概率下，计算对该二叉排序树查找成功和不成功的平均查找长度。,30,15,28,20,24,10,12,68,35,50,46,55,ASL,成功,=(1+2*2+3*3+4*3+5*3)/12,=41/12,ASL,不成功,=(2+3*3+4*3+6*5)/13,=53/13,58,59,例题,设哈希函数,H(key),key,%,9,，哈希地址空间为,0 10,，对关键字序列（,31,，,12,，,48,，,54,，,21,，,33,，,22,，,60,）。,（,1,）用线性探查法解决冲突构造哈希表，并计算在等概率情况下查找成功的平均查找长度；,（,2,）用拉链法解决冲突构造哈希表，并计算在等概率情况下查找成功的平均查找长度。,59,60,例题,设哈希函数,H(key),key,%,9,，哈希地址空间为,0 10,，对关键字序列（,31,，,12,，,48,，,54,，,21,，,33,，,22,，,60,）。,（,1,）用线性探查法解决冲突构造哈希表，并计算在等概率情况下查找成功和不成功的平均查找长度（写出算式）；,12,21,33,22,1,2,3,4,5,6,7,8,60,9,10,54,0,31,48,解：,ASL,成功,=(1+1+3+1+4+2+5+4)/8,=21/8,ASL,不,成功,=(,2,+1+,1,+,8,+,7,+,6+,5+4,+3,)/,9,=,37,/,9,60,61,例题,设哈希函数,H(key),key,%,9,，哈希地址空间为,0 10,，对关键字序列（,31,，,12,，,48,，,54,，,21,，,33,，,22,，,60,）。,（,2,）用拉链法解决冲突构造哈希表，并计算在等概率情况下查找成功和不成功的平均查找长度。,1,2,3,4,5,6,7,8,9,10,0,解：,ASL,成功,=(1+1+1+1+2+2+2+3)/8=13/8,31,12,48,54,21,33,22,60,ASL,不,成功,=(1+,3,+,2,+,2,)/,9,=,8,/,9,61,62,第十章 内部排序,本章内容：,10.1,概述,10.2,插入排序,10.1.1,直接插入排序,10.1.2,其他插入排序,10.1.3,希尔排序,10.3,快速排序,10.4,选择排序,10.4.1,简单选择排序,10.4.2,树型选择排序,10.4.3,堆排序,10.5,归并排序,10.6,基数排序,10.7,各种排序方法的比较,62,63,第十章 排序,本章学习要点：,了解各种排序方法的过程和特点。能从,”,关键字间的比较次数,”,分析排序算法在最坏情况和平均情况时的时间性能。,按平均时间复杂度划分，内部排序可分为：,O(n,2,),的简单排序方法，,O(nlogn),的高效排序方法和,O(d*n),的基数排序方法。,理解排序方法,”,稳定,”,或,”,不稳定,”,的含义。,掌握简单的排序方法（直接插入排序、冒泡排序、简单选择排序）。,掌握快速排序算法，理解堆排序、归并排序算法。,63,64,例题,1.,排序方法的稳定性是指（）。,2.,对于直接插入排序,当待排序列中记录按关键字（,有序,）排列时,所需进行关键字间比较的次数达最小值,n-1,记录不需移动。,3.,每趟排序都是从未排序的子序列中依次取出元素及已经排好序的序列中元素进行比较，然后将其放在已经排好序的序列的合适位置。这种排序法称为（,直接插入,）排序法。,4.,直接插入排序用监视哨的作用是（）。,64,65,例题,1.,在希尔排序、冒泡排序、选择排序、直接插入排序、快速排序、基数排序等方法中，关键字比较的次数及记录的初始排列次序无关的排序方法是（,选择排序、基数排序,）。,2.,设有序列（,503,，,87,，,512,，,61,，,908,，,170,，,897,）,（,1,）写出增量为,3,时进行一趟希尔排序的结果；,（,2,）建成一个小顶堆；,（,3,）给出执行一趟快速排序的结果；,（,4,）写出进行,3,路归并排序的过程。,65,66,例题,8.,设有序列（,503,，,87,，,512,，,61,，,908,，,170,，,897,）,（,1,）写出增量为,3,时进行一趟希尔排序的结果；,503,，,87,，,512,，,61,，,908,，,170,，,897,503 61 897,87 908,512 170,61,87,170,503,908,512,897,66,例题,6.,设有序列（,503,，,87,，,512,，,61,，,908,，,170,，,897,）,（,2,）建成一个小顶堆；,503,512,87,908,61,897,170,(a),503,170,87,908,61,897,512,(b),503,170,61,908,87,897,512,(c),61,170,503,908,87,897,512,(d),61,170,87,908,503,897,512,(e),67,例题,6.,设有序列（,503,，,87,，,512,，,61,，,908,，,170,，,897,）,（,3,）给出执行一趟快速排序的结果；,503,，,87,，,512,，,61,，,908,，,170,，,897,170,，,87,，,61,，,503,，,908,，,512,，,897,（,4,）,3,路归并排序过程；,503,，,87,，,512,，,61,，,908,，,170,，,897,87,，,503,，,512,61,，,170,，,908,897,61,，,87,，,170,，,503,，,512,，,897,，,908,68,69,End,69,谢谢大家！,