自学专业考试数据结构重点总结分析02331(2014整理).doc

《自学专业考试数据结构重点总结分析02331(2014整理).doc》由会员分享，可在线阅读，更多相关《自学专业考试数据结构重点总结分析02331(2014整理).doc（21页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、.自考数据结构重点（自考数据结构重点（20142014 整理）整理）第一章第一章 概论概论 1.瑞士计算机科学家沃思提出：算法+数据结构=程序。算法是对数据运算的描述，而数据结构包括逻辑结构和存储 结构。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大 程度上取决于描述实际问题的数据结构。 2.2.数据数据是信息的载体。数据元素数据元素是数据的基本单位。一个数据元素可以由若干个数据项数据项组成，数据项数据项是具有独立含 义的最小标识单位。数据对象数据对象是具有相同性质的数据元素的集合。 3.3.数据结构数据结构指的是数据元素之间的相互关系，即数据的

2、组织形式。 数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算 数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。 数据的逻辑结构分类数据的逻辑结构分类: : 线性结构和非线性结构 数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）数据的存储结构（物理结构） 。 数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。 数据的运算数据的运算。最常用的检索、插入、删除、更新、排序等。 4. .数据的四种基本存储方法数据的四种基本存储方法: :

3、 顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：通常借助程序设计语言的数组数组描述。 （2）链接存储：通常借助于程序语言的指针来描述。 （3）索引存储：索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。 （4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。 5.算法必须满足 5 个准则：输入输入，0 个或多个数据作为输入；输出输出，产生一个或多个输出；有穷性有穷性，算法执行有限 步后结束；确定性确定性，每一条指令的含义都明确；可行性可行性，算法是可行的。 算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算

4、机程序语言、数学语言或 约定的符号语言来描述。目前常用的描述算法语言有两类：类 Pascal 和类 C。 6.评价算法的优劣：算法的“正确性“是首先要考虑的。此外，主要考虑如下三点： 执行算法所耗费的时间，即时间复杂性； 执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性； 算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 以上几点最主要的是时间复杂性，时间复杂度常用渐进时间复杂度表示。 7.算法求解问题的输入量输入量称为问题的规模,用一个正整数 n 表示。 8.常见的时间复杂度按数量级递增排列依次为：常数阶 0(1)、对数阶 0(log2n)、线性阶 0(n)、线性对数阶 0(

5、nlog2n)、平方阶 0(n2)立方阶 0(n3)、k 次方阶 0(nk)、指数阶 0(2n)和阶乘阶 0(n!)。 9.一个算法的空间复杂度 S(n)定义为该算法所耗费的存储空间，它是问题规模 n 的函数,它包括存储算法本身所占 的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。第二章第二章 线性表线性表 1.数据的运算是定义在逻辑结构上的，而运算的具体实现是在存储结构上进行的。 2.只要确定了线性表存储的起始位置，线性表中任意一个元素都可随机存取，所以顺序表是一种随机存取结构。 3.常见的线性表的基本运算: (1)置空表 InitList（L） 构造一个空

6、的线性表 L。 (2)求表长 ListLength（L）求线性表 L 中的结点个数，即求表长。 (3)GetNode（L，i） 取线性表 L 中的第 i 个元素。 (4)LocateNode（L，x）在 L 中查找第一个值为 x 的元素，并返回该元素在 L 中的位置。若 L 中没有元素的值为 x ，则返回 0 值。 (5)InsertList（L，i，x）在线性表 L 的第 i 个元素之前插入一个值为 x 的新元素，表 L 的长度加 1。 (6)DeleteList（L，i）删除线性表 L 的第 i 个元素，删除后表 L 的长度减 1。 4.顺序存储方法：把线性表的数据元素按逻辑次序依次存放在

7、一组地址连续的存储单元里的方法。 顺序表（Sequential List）：用顺序存储方法存储的线性表称为顺序表。顺序表顺序表是一种随机存取结构随机存取结构, ,顺序表的.特点是逻辑上相邻的结点其物理位置亦相邻。 5.顺序表上实现的基本运算：顺序表上实现的基本运算： （1 1）插入：）插入：该算法的平均时间复杂度是 O(n)，即在顺序表上进行插入运算，平均要移动一半结点（n/2） 。 （2 2）删除）删除：顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是 O(n)。 6.采用链式存储结构可以避免频繁移动大量元素。一个单链表可由头指针唯一确定，因此单链表可以用头指

8、针的名 字来命名。生成结点变量的标准函数生成结点变量的标准函数 p=( ListNode *)malloc(sizeof(ListNode)； /函数 malloc 分配 一个类型为 ListNode 的结点变量的空间,并将其首地址放入指针变量 p 中释放结点变量空间的标准函数释放结点变量空间的标准函数 free(p)； /释放 p 所指的结点变量空间 结点分量的访问结点分量的访问 方法二：p-data 和 p-next 指针变量指针变量 p p 和结点变量和结点变量*p*p 的关系的关系: : 指针变量 p 的值结点地址, 结点变量*p 的值结点内容 7.建立单链表建立单链表: : （1）

9、头插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode);/生成新结点p-data=ch; /将读入的数据放入新结点的数据域中p-next=head;head=p;（2） 尾插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode); /生成新结点p-data=ch; /将读入的数据放入新结点的数据域中if (head=NULL)head=p;/新结点插入空表elserear-next=p;/将新结点插到*r 之后rear=p;/尾指针指向新表尾（3） 尾插法建带头结点的单链表： 头结点及作用：头结点及作用：头结点是在链表

10、的开始结点之前附加一个结点。它具有两个优点:由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上 操作一致,无须进行特殊处理;无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空） ，因此空表和非空表 的处理也就统一了。 头结点数据域的阴影表示该部分不存储信息。在有的应 用中可用于存放表长等附加信息。具体算法：r=head; / 尾指针初值也指向头结点while(ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);/生成新结点s-data=ch; /将读入的数据放入新结点的数

11、据域中.r-next=s;r=s;r-next=NULL;/终端结点的指针域置空，或空表的头结点指针域置空 以上三个算法的时间复杂度均为以上三个算法的时间复杂度均为 O(n)O(n)。 8.单链表上的查找：（带头结点） （1）按结点序号查找：序号为 0 的是头结点。 算法：p=head;j=0;/从头结点开始扫描while(p-nextj+;if(i=j)return p;/找到了第 i 个结点else return NULL;/当 i0 时，找不到第 i 个结点时间复杂度：在等概率假设下，平均时间复杂度为：为时间复杂度：在等概率假设下，平均时间复杂度为：为 n/2=O(n)n/2=O(n)

12、（2）按结点值查找： 具体算法：ListNode *p=head-next;/从开始结点比较。表非空，p 初始值指向开始结点while(p/扫描下一结点return p;/若 p=NULL，则查找失败，否则 p 指向值为 key 的结点 时间复杂度为：时间复杂度为：O(n)O(n) 9.插入运算：插入运算是将值为 x 的新结点插入到表的第 i 个结点的位置上，即插入到 ai-1与 ai之间。s=(ListNode *)malloc(sizeof(ListNode); s-data=x;s-next=p-next;p-next=s; 算法的时间主要耗费在查找结点上，故时间复杂度亦为 O(n)。

13、10.删除运算删除运算r=p-next;/使 r 指向被删除的结点 aip-next=r-next;/将 ai从链上摘下free(r);/释放结点 ai的空间给存储池 算法的时间复杂度也是 O（n） 。 p 指向被删除的前一个结点。链表上实现的插入和删除运算，无须移动结点，仅需修改指针。 11.单循环链表在单链表中，将终端结点的指针域 NULL 改为指向表头结点或开始结点即可。判断空链表的条件是head=head-next; 12.仅设尾指针的单循环链表仅设尾指针的单循环链表: : 用尾指针 rear 表示的单循环链表对开始结点 a1和终端结点 an查找时间都是 O(1)。 而表的操作常常是在

14、表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。判断空链表的条件为.rear=rear-next;13.13.循环链表：循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。 若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是 O(1)。具体算法： LinkList Connect(LinkList A,LinkList B) /假设 A，B 为非空循环链表的尾指针 LinkList p=A-next;/保存 A 表的头结点位置A-next=B-next-next;/B 表的开始结点链接到 A 表尾free(B-nex

15、t);/释放 B 表的头结点B-next=p;/return B;/返回新循环链表的尾指针 循环链表中没有 NULL 指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别 p 或 p-next 是否 为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。 在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单 循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。 14.双向链表双向链表: : 双（向）链表中有两条方向不同的链，即每个结点中除 next 域存放后继结点地址外，还增加一个指 向其直接前趋

16、的指针域 prior。 双链表由头指针 head 惟一确定的。 带头结点的双链表的某些运算变得方便。 将头结点和尾结点链接起来，为双（向）循环链表。15.双向链表的前插和删除本结点操作双向链表的前插和删除本结点操作 双链表的前插操作void DInsertBefore(DListNode *p,DataType x)/在带头结点的双链表中，将值为 x 的新结点插入*p 之前，设pNULL.DListNode *s=malloc(sizeof(DListNode);/s-data=x;/s-prior=p-prior;/s-next=p;/p-prior-next=s;/p-prior=s;/

17、双链表上删除结点*p 自身的操作void DDeleteNode(DListNode *p)/在带头结点的双链表中，删除结点*p，设*p 为非终端结点p-prior-next=p-next;/p-next-prior=p-prior;/free(p);/ 与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的 时间复杂度均为 O(1)。 16.顺序表和链表比较 时间性能：a、线性表：经常性的查找； b、链式存储结构：经常插入删除操作； 空间性能：a、对数据量大小事先能够知道的用线性表； b、数据量变化较大的用链式存储结构。 存储密度越大，存储空间的

18、利用率越高。显然，顺序表的存储密度是 1，链表的存储密度肯定小于 1。第三章 栈和队列 1.栈称为后进先出后进先出（Last In First Out）的线性表，简称为 LIFOLIFO 表表。栈是运算受限的线性表，顺序栈也是用数组表示的。进栈操作：进栈时，需要将 S-top 加 1， S-top=StackSize-1 表示栈满 “上溢上溢“现象-当栈满时，再做进栈运算产生空间溢出的现象。 退栈操作：退栈时，需将 S-top 减 1， S-topfront=Q-rear=0; 判队空判队空: : return Q-rear=Q-front; 判队满判队满: : return (Q-rear+

19、1)%QueueSize=Q-front; 入队入队 Q-dataQ-rear=x; /新元素插入队尾Q-rear=(Q-rear+1)%QueueSize; 出队出队 temp=Q-dataQ-front;Q-front=(Q-front+1)%QueueSize; /循环意义下的头指针加 1return temp; 取队头元素取队头元素 return Q-dataQ-front; 6.队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。为了简化处理，在队头结点之前附加一个头结点，并设队头指针指向此结点。链队列的基本运算链队列的基本运算: :（带头结点）（带头结点） （1

20、） 构造空队：Q-rear=Q-front；Q-rear-next=NULL; （2） 判队空：return Q-rear=Q-front; （3） 入队：QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode);/申请新结点p-data=x; p-next=NULL;Q-rear-next=p; /*p 链到原队尾结点后Q-rear=p; /队尾指针指向新的尾 （4） 出队：当队列长度大于 1 时，只需修改头结点指针，尾指针不变s=Q-front-next; Q-front-next=s-next; x=s-data; free(s); retur

21、n x; 当队列长度等于 1 时，不仅要修改头结点指针，还要修改尾指针s=Q-front-next; Q-front-next=NULL; Q-rear=Q-front; x=s-data; free(s); return x; （5） 取队头元素：return Q-front-next-data; 因为有头结点，所以用了 next 和链栈类似，无须考虑判队满的运算及上溢。 在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点 时亦需修改尾指针，且删去此结点后队列变空。 7.用计算机来处理计算算术表达式问题，首先要解决的问题是如何将人们习惯书写的中

22、缀表达式转换成后缀表达式。.第四章 多维数组和广义表 1.数组的顺序存储方式数组的顺序存储方式: :一般采用顺序存储方法表示数组。 （1）行优先顺序 a11,a12,a1n,a21,a22,a2n,，am1,am2,，amn （2）列优先顺序 a11,a21,am1,a12,a22,am2,，a1n,a2n,，amnPascal 和 C 语言是按行优先顺序存储的，而 Fortran 语言是按列优先顺序存储的。 2.为了节省存储空间，可以对矩阵中有许多值相同或值为零的元素的矩阵，采用压缩存储。 特殊矩阵是指相同值的元素或零元素在矩阵中的分布有一定的规律。常见的有对称矩阵、三角矩阵。 （1）对称矩

23、阵 在一个 n 阶方阵 A 中，若元素满足下述性质： aij=aji 0i，jn-1 称为 n 阶对称矩阵，它的元素是关于主对角线对称的，所以只需要存储矩阵上三角或下三角元素即可，让两个 对称的元素共享一个存储空间。 矩阵元素 aij和数组元素 sa【k】之间的关系是k=i(i+1)/2+j ij 0k,有 向边又称为弧，起点称为弧尾，终点称为弧头。无向图的顶点对用圆括号表示(vi,vj)。 在无向图中，称 vi和 vj相邻接，在有向图中称顶点 vi邻接到 vj，顶点 vj邻接于 vi 在无向图中，n 的取值范围是 0-n(n-1)/2，将具有 n(n-1)/2 条边的无向图称为无向完全图。

24、在有向图中，n 的取值范围是 0-n(n-1)，将具有 n(n-1)条边的有向图称为有向完全图。 无向图中，顶点的度定义为以该顶点为一个端点的边的数目，有向图的度等于出度和入度之和。 在无向图中，任意两顶点都有路径，则称两顶点连通。若图 G 中的任意两个顶点都连通，称 G 为连通图。无向图 的极大连通子图称为连通分量，显然，任何连通图的连通分量只有一个，即其自身，而非连通的无向图有多个连通而非连通的无向图有多个连通 分量分量。 在有向图中，图 G 中任意两顶点连通，称为强连通图，极大连通子图称为强连通分量。 若在一个图的每条边上标上某种数值，该数值称为该边的权。边上带权的图称为带权图，带权的连

25、通图称为网络。 2.图的存储结构：邻接矩阵和邻接表表示法。图的顶点编号从 0 开始。邻接矩阵表示法邻接矩阵表示法：或(vi,vj)是边，则值为 1，不是边则值为 0。 无向图的邻接矩阵是按主对角线对称的。若 G 是带权图，只要把 1 换成相应边上的权值即可，0 的位置上可以不动 或将其换成无穷大表示。无向图的邻接矩阵表示法可以仅存储主对角线以下的元素，时间复杂度为 O(n2)邻接表表示法：邻接表表示法：邻接表是图的一种链式存储结构。将无向图的邻接表称为边表，将有向图的邻接表称为出边表， 将邻接表的表头向量称为顶点表。若无向图有 n 个顶点和 e 条边，则它的邻接表共有 n 个头结点和 2e 个

26、表结点。 建立邻接表的时间复杂度是 O(n+e)。图的邻接表表示不是唯一的,这是因为在每个顶点的邻接表中，各边结点的 链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。 3.图的遍历：遍历图的算法是求解图的连通性、图的拓扑排序等算法的基础。 图的遍历常用的是深度优先搜索遍历和广度优先搜索遍历两种方法。深度优先搜索遍历深度优先搜索遍历(DFS)(DFS)类似于前序(先根)遍历。按访问顶点的先后次序得到的顶点序列称为图的深度优先遍历 序列，或简称为 DFS 序列。共需要搜索 n2个矩阵元素，时间复杂度为邻接矩阵 O(n2)或邻接表 O(n+e)。广度优先搜索遍历广度优先搜索遍历(B

27、FS)(BFS)类似于树的按层次遍历，先被访问的顶点，其邻接点也先被访问，就是先进先出。 时间复杂度为邻接矩阵 O(n2)或邻接表 O(n+e)，空间复杂度都是 O(n)。.4.生成树是连通图的包含图中所有顶点的一个极小连通子图，一个图的极小连通子图恰为一个无回路的连通图，也 就是说，若图中任意添加一条边，就会出现回路，若去掉任意一条边，都会使之成为非连通图。因此，一个具有 n 个顶点的生成树有且仅有 n-1 条边，但有 n-1 条边的图不一定是生成树，同一个图可以有不同 的生成树。 生成树定义为：若从图的某顶点出发，可以系统的访问到图的所有顶点，则遍历时经过的边和图的所有顶点所构 成的子图，

28、称为该图的生成树。最小生成树：图的生成树不唯一，把权值最小的生成树称为最小生成树（MST） 。构造最小生成树的算法：普里姆普里姆 PrimPrim 算法的时间复杂度为 O（n2）与网中边数无关适于稠密图。 克鲁斯卡尔克鲁斯卡尔 KruskalKruskal 算法的时间复杂度为 O（eloge） ，主要取决于边数，较适合于稀疏图。5.最短路径：Dijkstra 迪杰斯特拉算法，提出了按路径长度递增的顺序产生诸顶点的最短路径算法。拓扑排序：子工程称为活动，顶点代表活动，有向边代表活动的先后关系。这样的有向无环图 DAG 称为顶点活动 网，简称为 AOV 网。 将有向无环图 G 中所有顶点排成一个线

29、性序列，若E（G） ，则在线性序列 u 在 v 之前，这种线性序列称为拓扑序列。由 AOV 网构造拓扑序列的过程称为拓扑排序。检测的方法是：对有向图构造其顶点的拓扑序列，若网中所有顶点都在他的拓扑序列中，则 AOV 网必定不存在环。AOV 网的拓扑序列不是唯一的。拓扑排序的描述思想：a、在有向图中选一个没有前趋在有向图中选一个没有前趋( (入度为零入度为零) )的顶点的顶点，且输出之。b、从有向图中删除该顶点 及其与该顶点有关的所有边。c、重复上述步骤，直到全部顶点都已输出或图中剩余的顶点中没有前趋顶点为止。 d、输出剩余的无前趋结点。拓扑排序实际上是对邻接表表示的图 G 进行遍历的过程。时间

30、复杂度是 O(n+e)。.第七章 排序 1.如果待排序文件中存在多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不 变，该排序方法是稳定的；反之，则是不稳定的。 排序在内存中处理，不涉及数据的内外存交换，称为内部排序，反之为外部排序。内部排序又分为五类：插入、 选择、交换、归并和分配排序。 在排序过程中需进行两种操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身，而待排序记录的 存储形式一般有三种：顺序结构、链式结构和辅助表。 评价排序算法的标准：执行算法需要的时间，以及算法所需要的附加空间。还有算法本身的复杂度。 排序的时间开销，一般情况下可用算法中关键

31、字的比较次数和记录的移动次数来衡量。 2.插入排序插入排序：每次将一个待排序记录按其关键字大小插入到前面已排好序的文件中的适当位置。直接插入排序：每次从无序区取出第一个元素把它插入到有序区的适当位置，使之成为新的有序区，经过 n-1 次 插入后完成。算法中 R0作用：保存 Ri副本，监视数组下标变量 j 是否越界。所以 R0称为哨兵。每次的比较每次的比较 是从后往前比较的是从后往前比较的。 时间复杂度最好是 O(n)，最坏是 O(n2)，所以是 O(n2)。空间复杂度 O(1)，所以是就地排序。 是稳定的算法。 初始情况是有序区中只有一个元素初始情况是有序区中只有一个元素 R1R1，无序区中，

32、无序区中 R2.nR2.n。 希尔排序(缩小增量排序)：算法不稳定。记录的总比较次数和总移动次数都要比直接插入排序少得多，特别是当 n 越大越明显。希尔排序的时间依赖于增量序列，最后一个增量必须是 1，尽量避免增量互为倍数的情况。.3.交换排序交换排序：两两比较待排序记录的关键字，如果发现两个记录的次序相反时即进行交换，直到没有反序位置。冒泡排序(起泡排序)：通过相邻元素之间比较和交换，使较小移向顶部，从后往前两两比较从后往前两两比较。 时间复杂度最好是 O(n)，最坏是 O(n2)，所以是 O(n2)。是稳定的排序算法。快速排序(划分交换排序)：是冒泡排序的改进。比较和交换从两端向中间进行。

33、 一趟快速排序步骤：设两个指针 i 和 j，初值分别为 low 和 high，基准为 x=Ri，首先从 j 位置开始向前搜索第 一个小于基准 x.key 的记录存入 i 所指位置上，i 自增 1，然后从 i 所指位置向后搜索找到第一个大于基准 x.key 的记录存入 j 所指位置上，j 自减 1，重复直至 i=j 为止。 快速排序是不稳定的。有非常好的时间复杂度，优于其他各种排序算法，O(nlog2n)，但是当记录关键字有序或基 本有序时复杂度反而大了使之转变成冒泡排序为 O(n2)。快速排序是递归的，需要一个栈空间，空间复杂度 O(log2n)。4.选择排序选择排序：每一趟在待排序的记录中选

34、出关键字最小的记录，依次存放在已排序好的记录序列的最后。直接选择排序：初始时，R1.n为无序区，R1为空；第一趟是在 R1.n中选出最小的记录与 R1交换，R1为 有序区；第二趟是在 R2.n中选出最小的记录与 R2交换，R1.2为有序区。时间复杂度 O(n2)，是不稳定的。 初始情况是有序区为空，无序区中初始情况是有序区为空，无序区中 R1.nR1.n，第一趟从，第一趟从 R1.nR1.n选择最小记录与选择最小记录与 R1R1交换。交换。堆排序：是对直接选择排序的改进，是一种树形选择排序。基本思想：在排序过程中，将记录数组 R1.n看成 是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结

35、点和孩子结点之间的内在关系，在当前无序区中选择 关键字最大或最小记录。 每一趟排序：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将他和无序区中最后一个记录交换。 堆排序是一个不断建堆的过程。构造堆的过程：R1作为二叉树的根，R2.n依次逐层从左到右顺序排列，构成一棵完全二叉树，任意结点 Ri的左孩子是 R2i，右孩子是 R2i+1，双亲是 Ri/2，此称为筛选法。从n/2开始。 每一趟的时间复杂度是 O(log2n)，整个堆排序的时间复杂度是 O(nlog2n)。5.归并排序归并排序：首先将待排序文件看成 n 个长度为 1 的有序子文件，把这些子文件两两归并，得到n/2个长度为 2

36、的有序子文件，然后再将他们两两归并，如此反复，直到得到一个长度为 n 的有序文件，此称为二路归并排序。 每一趟归并排序的时间复杂度是 O(n)，所以总的时间复杂度是 O(nlog2n)。.6.分配排序分配排序：前面方法都至少需要进行nlogn次比较，而分配排序将时间复杂度降为 O(n)。箱排序(桶排序)： 基数排序：是对箱排序的改进和推广。箱排序只适用于关键字取值范围较小的情况，否则所需箱子数目太多。 每个分量可能取值的个数 rd 称为基数，基数的选择和关键字的分解因关键字的类型而异。d 趟箱排序。 基数排序中，没有进行关键字的比较和记录的移动，而只是扫描链表和进行指针赋值，所以排序的时间主要

37、用在修 改指针上，初始化链表时间为 O(n)。 7.内部排序方法分析比较：本章除基数排序外，都是在顺序表上实现的。时间复杂度空间复杂度稳定性直接插入O(n2)O(1)稳定插入希尔排序O(nlog2n)或 O(n1.25)O(1)不稳定冒泡排序O(n2)O(1)稳定交换快速排序O(nlog2n)O(log2n)不稳定直接选择O(n2)O(1)不稳定选择堆排序O(nlog2n)O(1)不稳定归并排序归并排序O(nlog2n)O(n)稳定基数排序O(rd+n)稳定分配排序箱排序O(d*(rd+n)rd 是基数， d 是关键字位数.n 是元素个数选取排序方法时需要考虑的主要因素：选取排序方法时需要考虑

38、的主要因素：a、待排序的记录个数，b、记录本身的大小和存储结构，c、关键字的分布 情况，d、对排序稳定性的要求，e、时间和空间复杂度要等 排序方法的选取：排序方法的选取： a、若待排序的一组记录数目 n 较小(如 n50)时，可采用插入排序或选择排序；b、n 较大时，则应采用快速排 序、堆排序或归并排序；c、若待排序记录按关键字基本有序时，则宜选用直接插入排序或冒泡排序；d、当 n 很大， 而且关键字位数较少时，采用链式基数排序较好；e、关键字比较次数与记录的初始排列顺序无关的排序方法是选 择排序。 一般的排序方法都可以在顺序结构上实现，当记录本身信息量较大时，可采用链式存储结构。 插入、归并

39、、基数排序易于在链表上实现；快速排序和堆排序可以提取关键字建立索引表，然后对索引表进行排 序。第八章：查找 1.查找又称检索，是数据处理中经常使用的一种重要运算。 查找也分为内查找和外查找。运算查找的主要操作是关键字的比较，因此把查找过程中的平均比较次数(也称为平均查找长度)作为衡量算法效 率优劣的标准。 2.顺序表的查找：顺序查找和二分查找顺序查找又称线性查找：顺序查找又称线性查找：查找成功的平均查找长度(n+1)/2，即约为表长的一半。 如果查找成功和不成功机会相等，那么平均查找长度 3(n+1)/4。 优点是简单，对表的结构无任何要求，无论是顺序存储和链式存储、无论是否有序，都同样适用，

40、缺点是效率低。对于有序表来说，该算法的平均查找长度是(n+1)/2。 二分查找二分查找( (折半查找折半查找) )：要求查找对象的线性表必须是顺序存储结构的有序表。查找过程是递归的。.树中每个子树的根节点对应当前查找区间的中位记录 Rmid，它的左子树和右子树分别对应区间的左子表和右 子表，通常将此树称为二叉判定树。由于二分查找是在有序表上进行的，所以其对应的判定树必定是一棵二叉排序 树。 二叉判定树一定是二叉排序树，二叉排序树又称为二叉查找树二叉判定树一定是二叉排序树，二叉排序树又称为二叉查找树。从判定树上可见，关键字比较的次数恰好为该结点在树中的层数。因此，二分查找算法在查找成功时进行关键

41、字 比较的次数最多不超过判定树的深度。查找成功时的平均查找长度 (n+1)/nlog2(n+1)-1，当 n 很大时，可近似用 log2(n+1)-1 表示。因为判定树度数小于 2 的结点只可能在最下面的两层，所以 n 个结点的判定树的深度和 n 个结点的完全二叉树的深度相同，即为log2(n+1)。可见，二分查找的最坏性能和平均性能相当接近。二叉判定树的输出：每次以(low+high)/2为根建树。3.索引顺序查找(分块查找)：是一种介于顺序查找和二分查找之间的查找方法。要求分块有序分块有序，前一块的最大关键 字小于后一块的最小关键字，抽取各块中的最大关键字及其起始位置构成索引表。分块查找的

42、基本思想是：首先查找索引表，可用二分查找或顺序查找，然后在确定的块中进行顺序查找。 平均查找长度：二分查找 log(n/s+1)+s/2， 顺序查找(s2+2s+n)/2s。 4.三种查找方法比较顺序查找缺点是 n 较大时，查找成功约为(n+1)/2，失败需要比较 n+1 次。二分查找成功时约为 log2(n+1)-1，但是他要求表以顺序存储且按关键字有序，适用于表不易变动且又经常查找 的情况。分块查找的优点是，在表中插入或删除一个记录时，只要找到该记录所属的块，就可以在该块内进行插入或删除 操作，因为块内记录是无序的，所以插入或删除比较容易，无需移动大量记录。主要缺点是需要增加一个辅助数组

43、的存储空间和将初始表块排序的运算，它也不适用于链式存储结构。上述三种查找的时间复杂度分别是 O(n)、O(log2n)和 O(n 的平方根) 5.二叉排序树二叉排序树(二叉查找树)：或者是一棵空树，或者具有下面性质：a、若右子树非空，则右子树上所有结点的值 均大于根节点的值。b、若左子树非空，则左子树上所有结点的值均小于根节点的值。c、左右子树本身又各是一棵 二叉排序树。 由此可得，按中序遍历二叉排序树所得到的遍历序列是一个递增有序序列。由此可得，按中序遍历二叉排序树所得到的遍历序列是一个递增有序序列。 同样一组关键字序列，由于其输入顺序不同，所得到的二叉排序树也有所不同，含有同样一组关键字序

44、列，由于其输入顺序不同，所得到的二叉排序树也有所不同，含有 n n 个结点的二叉排序树不是唯个结点的二叉排序树不是唯 一的。一的。 构造二叉排序树的真正目的并不是为了排序，而是为了更好地查找，又称为二叉查找树。构造二叉排序树的真正目的并不是为了排序，而是为了更好地查找，又称为二叉查找树。 二叉排序树的查找与给定值的比较次数不会超过树的深度。若二叉排序树是一颗理想的平衡树或接近理想的平衡树， 则时间复杂度为 O(log2n)，若退化为一棵单支树，则时间复杂度为 O(n)。.二叉排序树的删除：二叉排序树的删除：被删除结点为 p，其父结点为 f。具体操作为： a、若 p 是叶子结点，直接删除 p；

45、b、若 p 只有一棵子树(左子树或右子树)，直接用 p 的左子树(或右子树)取代 p 的位置而成为 f 的一棵子树。即 p 是左子树则 p 的子树变为 f 的左子树； c、若 p 既有左子树又有右子树，任选一种方法： (1)、用 p 的直接前驱结点代替 p，即从 p 的左子树中选择值最大的结点 s 放在 p 的位置(用结点 s 的内容替换 结点 p 内容)，然后删除结点 s。s 是 p 的左子树中最右边的结点且没有右子树； (2)、用 p 的直接后继结点代替 p，即从 p 的右子树中选择值最小的结点 s 放在 p 的位置(用结点 s 的内容替换 结点 p 内容)，然后删除结点 s。s 是 p

46、的右子树中最左边的结点且没有左子树。 在二叉排序树上实现插入和查找操作的平均时间复杂度为 O(log2n)，但在最坏得情况下，会变成 O(n)。 平衡二叉树：既能满足 BST 性质又能保证二叉排序树二叉排序树的深度在任何情况下均为 O(log2n)。6.B 树是一种平衡的多路查找树。一棵 m(m3)阶的 B 树，或为空树，或为满足下列性质的 m 叉树a、每个结点至少包含下列信息域；b、每个结点至多有 m 棵子树；c、若树为非空，则根结点至少有 1 个关键字， 至多有 m-1 个关键字。因此，若根结点不是叶子，则它至少有两颗子树。d、每个非根结点中所含的关键字个数满 足：m/2-1nm-1，因为

47、每个内部结点的度数正好是关键字总数加 1，所以处根结点之外的所有非终端结点至少有m/2棵子树，至多有 m 棵子树。在 B 树上插入和删除元素的运算比较复杂，它要求进行运算后的结点中关键字个数m/2-1，在 B 树进行查找包括两种基本操作：在 B 树中查找结点、在结点中查找关键字。7.B+树是一种文件组织的 B 树的变形树，通常有两个头指针 root 和 sqt，前者指向根结点，后者指向关键字最小的 叶子结点。因此可对 B+树进行两种查找运算：一种是从最小关键字起进行顺序查找，一种是从根结点开始进行随机.查找。 8.散列表查找是通过对记录的关键字值进行某种运算直接求出记录的地址，是一种由关键字到

48、地址的直接转换方法。散列存储中使用的函数称为散列函数或哈希函数，散列地址或哈希地址，散列表或哈希表。 具有相同散列地址的关键字称为同义词。冲突的频度除了与散列函数 H 相关外，还与散列表的填满程度相关。 如何尽量避免冲突和冲突发生后如何解决冲突如何尽量避免冲突和冲突发生后如何解决冲突，就成了散列存储的两个关键问题。 散列函数的目标是使散列地址尽可能均匀的分布在散列空间上，同时使计算尽可能简单。 直接地址法：计算简单，并且没有冲突。适合于关键字的分布基本连续的情况。 数字分析法：从中提取数字分布比较均匀的若干位作为散列地址。 除余数法：p 最好取小于或等于表长 m 的最大素数。这是一种最简单也最常用的方法。 平方取中法： 折叠法：把关键字分割成位数相同的几段，分为移位叠加和边界叠加。 9.处理冲突的方法：开放定址法和拉链法。 开放定址法：线性探查法、二次探查法和双重散列法(几种方法中最好的方法)。 二次探查法：d+