2022年数据结构知识点总结整理资料

《2022年数据结构知识点总结整理资料》由会员分享，可在线阅读，更多相关《2022年数据结构知识点总结整理资料（31页珍藏版）》请在金锄头文库上搜索。

1、数据结构知识点总结整理资料0 、常考基础必知必会A. 排序: 排序有几种 , 各种排序的比较 , 哪些排序是稳定的 , 快排的算法 ; B. 查找: 哈希查找、二叉树查找、折半查找的对比, 哈希映射和哈希表的区别 ? C. 链表和数组的区别 , 在什么情况下用链表什么情况下用数组? D. 栈和队列的区别 ? E. 多态, 举例说明 ;overload 和 override 的区别 ? F. 字符串有关的函数 , 比如让你写一个拷贝字符串的函数啊, 或者字符串反转啊什么的。strcpy 和 memcpy? G. 继承、多继承 ? H. 面向对象有什么好处 ? I. 说说static 的与众不同之

2、处, 如果一个变量被声明为static,它会被分配在哪里 ?在什么时候分配空间等 ? J. 什么是虚函数、纯虚函数、虚的析构函数, 用途? K. 内存泄漏及解决方法 ? 网络部分 : 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 31 页OSI 模型 7 层结构,TCP/IP 模型结构 ? B. TCP/UDP 区别? C. TCP 建立连接的步骤 ? D. 香农定理 ? 1 、二叉树三种遍历的非递归算法(背诵版 ) 本贴给出二叉树先序、中序、后序三种遍历的非递归算法, 此三个算法可视为标准算法, 直接用于考研答题。1. 先序遍 历非

3、递 归算法#define size 100 typedef struct Bitree Elemsize;int top; SqStack; void PreOrderUnrecBitree t SqStack s;StackInits;pt;while p!null | !StackEmptys while p!null/遍 历 左 子 树visitep-data; pushs,p; pp-lchild; /endwhile if !StackEmptys /通过下一次循环中的内 嵌while 实 现 右 子 树 遍 历ppops; pp-rchild; /endif/endwhile/Pr

4、eOrderUnrec 2. 中序遍 历非递 归算法#define size 100 typedef struct Bitree Elemsize;int top; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 31 页SqStack; void InOrderUnrecBitree t SqStack s;StackInits;pt;while p!null | !StackEmptys while p!null/遍历左子树 pushs,p; pp-lchild; /endwhile if !StackEmptys ppops; v

5、isitep-data; /访 问 根 结 点pp-rchild; /通 过 下 一 次 循 环 实 现 右 子 树 遍 历/endif/endwhile /InOrderUnrec 3. 后序遍 历非递 归算法#define size 100 typedef enumL,R tagtype; typedef structBitree ptr;tagtype tag; stacknode; typedef struct stacknode Elemsize;int top; SqStack; / 后序遍历void PostOrderUnrecBitree t SqStack s;stackno

6、de x;StackInits;pt; do while p!null /遍历左子树 x.ptr p;x.tag L; /标记为左子树 pushs,x; pp-lchild; while !StackEmptys &s.Elems.top.tagR x pops; p x.ptr; visitep-data;/tag 为 R, 表示右子树访问完毕, 故访精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 31 页问根结点 if !StackEmptys s.Elems.top.tag R; /遍历右子树 ps.Elems.top.ptr-r

7、child; while !StackEmptys; /PostOrderUnrec 4. 层次遍 历算法/ 二叉树的数据结构structBinaryTree int value; / 不写模板了 , 暂时用整形代替节点的数据类型BinaryTree *left;BinaryTree *right; ; BinaryTree*root; / 已知二叉树的根节点/ 层次 遍历voidLevel const BinaryTree *root Queue *buf new Queue; / 定义一个空队列 , 假设此队列的节点数据类型也是整形的 BinaryTree t; / 一个临时变量 buf.

8、push_backroot;/令根节 点 入 队while buf.empty false / 当 队 列 不 为 空p buf.front; / 取出队列的第一个元素 coutp-value ; if p-left ! NULL / 若左子树不空, 则令其入队 q.push p-left ; if p-right ! NULL / 若右子树不空 , 则令其入队 q.push p-right ; buf.pop; / 遍历过的节点出队 coutendl; 2 、线性表(1) 性表的链式存储方式及以下几种常用链表的特点和运算: 单精选学习资料 - - - - - - - - - 名师归纳总结 -

9、 - - - - - -第 4 页，共 31 页链表、循环链表 , 双向链表 , 双向循环链表。(2) 单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。(3) 单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。3 、栈与队列你可以问一下自己是不是已经知道了以下几点:1 栈、队列的定义及其相关数据结构的概念, 包括 : 顺序栈, 链栈 , 共 享栈 , 循环队列, 链队等。栈与队列存取数据 ( 请注意包括 : 存和取两部分 )的特点。2 递归算法。栈与递归的关系 , 以及借助栈将递归转向于非递归的经典算法 :

10、n!阶乘问题 , fib 数列问题 ,hanoi 问题 , 背包问题 , 二叉树的递归和非递归 遍历问题, 图的 深 度遍历与栈的关系等。其中, 涉及到树与图的问题 , 多半会在树与图的相关章节中进行考查。 3 栈的应用 : 数 值表 达式的求解, 括 号的配 对等的原理, 只作原理性了解 , 具体要求考查此为题目的算法设计题不多。4 循环队列中判队空、队满条件,循环队列中入队与出队 (循环队列在插入时也要判断其精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 31 页是否已满 , 删除时要判断其是否已空) 算法。 【循环队列的队空队满条

11、件为了方便起见 , 约定 : 初始化建空队时, 令 frontrear0, 当队空时 :frontrear, 当队满时 :frontrear 亦成立 , 因此只凭等式frontrear 无法判断队空还是队满。有两种方法处理上述问题:(1)另设一个标志位以区别队列是空还是满。(2) 少用一个元素空间 , 约定以“队列头指针 front 在队尾指针 rear 的下一个位置上”作为队列“满”状态的标志。队空时 : frontrear , 队满时 : rear+1%sizefront】如果你已经对上面的几点了如指掌,栈与队列一章可以不看书了。注意, 我说的是可以不看书, 并不是可以不作题哦。/ 循环队

12、列的主要操作 : 1创建循环队列 2 初始化循环队列 3 判断循环队列是否为空 4 判断循环队列是否为满 5 入队、出队 /空出头尾之间的一个元素不用 #include #include #define SIZE 100 typedef struct intelemSIZE;intfront, rear; Quque; /定义队头 int initQueQuque *q / 初始化 *q-front0; *q-rear0; int isFullQuque *q ifq-frontq-rear+1%SIZE/判满空出一个元素不用 刘勉刚 return 1; else return 0; int

13、insertQueQuque *q,int elem ifisFull*qreturn -1; *q-elem*q-rearelem; *q-rear*q-rear+1%SIZE;/插入 return0; int isEmptyQuque *q ifq-frontq-rear/判 空return 1; else return 0; int 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 31 页deleteQueQuque * q,int *pelem ifisEmpty*q return 0; *pelem*q-elem*q-fron

14、t; *q-front*q-front +1%SIZE; return0; 4 、串串一章需要攻破的主要堡垒有: 1. 串的基本概念 , 串与线性表的关系 ( 串 是其元素均 为字符型 数据的 特殊线 性表), 空串与空格串的区别 , 串相等的条件 ; 2. 串的基本操作 , 以及这些基本函数的使用, 包括: 取子串 , 串连接, 串替 换, 求串长等等。运用串的基本操作去完成特 定的算法是很多学校在基本操作上的考查重点。 3. 顺序串与链串及块链串的区别和联系 , 实现方式。4. KMP 算法思想。 KMP 中 next 数组以及 nextval 数组的求法。 明确传统模式匹配算法的不足,

15、明确 next 数组需要改进。可能进行的考查方式是: 求 next 和nextval 数组值 , 根据求得的 next 或 nextval 数组值给出运用 KMP 算法进行匹配的匹配过程。5 、多维数组和广义表矩阵包括 : 对称 矩阵, 三角 矩阵, 具有某种特点的稀疏 矩阵等。熟悉稀疏矩阵的三种不同存储方式: 三元组 , 带辅 助行 向量的二 元组, 十字链表存储。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 31 页掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。6 、树与二叉树树一章的知识点包括 : 二叉树的概念、性质和

16、存储结构, 二叉 树遍历 的三 种算法 ( 递归与 非递归 ), 在三种基本遍历算法的基础上实现二叉树的其它算法, 线索二 叉树的概念和 线索化 算法以及线索化后的查找算法, 最优二 叉树的概念、构成和应用, 树的概念和存储形式 ,树与森林的遍历算法及其与二叉树遍历算法的联系 ,树 与森 林和二叉树的转 换。1 二叉树的概念、性质和存储结构考查方法可有 : 直接考查二叉树的定义, 让你说明二叉树与普通双分支树左右子树无序的区别; 考查满二叉树和完全二叉树的性质 , 普通二叉树的五个性质: A.第 i 层的最多结点数 , B.深度为 k 的二叉树的最多结点数 , C.n0n2+1 的性质 , D

17、.n 个结点的完全二叉树的深度, E. 顺序存储二叉树时孩子结点与父结点之间的换算关系(root 从 1 开始, 则左为 :2*i,右为: 2*i+1) 。二叉树的顺序存储和二 叉链 表存储的各自优缺点及适用场精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 31 页合, 二叉树的三叉链 表表示方法。 2 二叉树的三种遍历 算法这一知识点掌握的好坏 , 将直接关系到树一章的算法能否理解, 进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种: 先序 , 中序和后序。其划分的依据是视其每个算法中对根结点 数据的 访问 顺序而定。

18、不仅要熟练掌握三种遍历的递归算法 , 理解其执行的实际步骤, 并且应该熟练掌 握三 种遍历的非递归 算法。由于二叉树一章的很多算法 ,可以直接根据三种递归算法改造而来 (比如: 求叶子个数 ), 所以, 掌握了三种遍历的非递归算法后 , 对付诸如 : “利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。3 可在三种遍历算法的基础上改造完成的其它二 叉树算法 : 求叶子个数 , 求二叉树结点总数 , 求度为 1 或度 为 2 的结点总数, 复制二 叉 树,建立 二叉树, 交换 左右子 树, 查找值为n 的某个指定结点, 删除 值为 n 的某个指定结 点,诸如此类等等等等。如果你可以熟练掌

19、握二叉树的递归和非递归遍历算法, 那么解决以上问题就是小菜一碟了。4 线索二叉树 : 线索二叉树的引出, 是 为避免如二叉树 遍历时的递 归求解。众所周知 ,递归虽然形式上比精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 31 页较好理解 , 但是消耗了大量的内存资源, 如果递归层次一多 , 势必带来资源耗尽的危险 , 为了避免此类情况 , 线索二叉树便堂而皇之地出现了。 对于线索二叉树 ,应该掌握 : 线索 化的实质 , 三种线索化的算法 , 线 索化后二叉树的遍历算法, 基本线索二叉树的其它算法问题 (如: 查 找某一类线索二叉树中

20、指定结 点的 前驱或后继结点就是一类常考题)。 5 最优二叉树 ( 哈 夫 曼树): 最优二叉树是为了解决特定问题引出的特殊二叉树结构 , 它的前提是给二叉树的每条边赋予了权值 , 这样 形成的 二叉 树按权相加之和是最小 的。最优二叉树一节 ,直接考查算法源码的很少, 一般是给你一组数据, 要求你建立基于这组数据的最优二叉树, 并求出其最小权值之和 , 此类题目不难 , 属送分题。 6 树与森林 : 二叉树是一种特殊的树,这种特殊不仅仅在于其分 支最多为 2 以及其它特征 , 一个最重要的特殊之处是在于: 二叉树是有序的 ! 即: 二叉 树的左右孩子是 不可交换的 , 如果 交换了就成了另外

21、一棵二叉树。树与森林的遍历, 不像二叉树那样丰富,他们只 有两种 遍历算法 : 先 根与后根 ( 对于森 林而言 称作: 先序与后序遍历 ) 。 此二者的先根与 后根遍历与二 叉树 中的遍历算法是有对应关系的: 先 根遍历对应二叉树的先序遍历 , 而精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 31 页后根遍历对应二叉树的 中序 遍历。 二叉树 、树与森林之所以能有以 上的 对应关系 , 全 拜二叉 链表所赐。 二 叉树使 用二叉 链表分 别存放他的左右孩子 , 树利 用二叉链表存储孩子及兄弟 ( 称孩 子兄弟链表) , 而森 林也

22、是利用二 叉链表存储孩子及兄弟。 7 、图 1. 图的基本概念 : 图的定义和特点 , 无向 图, 有 向图, 入度,出度, 完全图 , 生 成子图, 路径长度, 回路,( 强)连 通图,( 强) 连通分 量等概念。2. 图的几种存储形式 : 邻接矩阵, (逆 ) 邻接表, 十字链表及邻接多重表。在考查时 ,有的学校是给出一种存储形式, 要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。3. 考查图的两种遍历算法 : 深 度遍历和广度遍历深度遍历和广度遍历是图的两种基本的遍历算法, 这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。 在考查时 ,图一

23、章的算法设计题常常是基于这两种基本的遍历算法而设计的, 比如:“求最 长的 最短路径问题”和“判断两 顶点间是否存在长为 K 的简单 路径问 题” , 就分别用到了广度遍历和深度遍历算法。 4. 生成树、最小生成 树的概念以及最小生成树的 构造:PRIM 算法和 KRUSKAL 算法。考查时 , 一般不要求写出算法源码,精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 31 页而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。5. 拓扑排序问题 : 拓扑排序有两种方法 , 一是无前趋的顶点优先算法 , 二是无后

24、继的顶点优先算法。换句话说, 一种是“从前向后”的排序, 一种是“从后向前”排。当然,后一种排序出来的结果是“逆拓扑有序”的。 6. 关键路径问题 : 这个问题是图一章的难点问题。理解关键路径的关键有三个方面: 一是何谓关键路 径; 二是最早时间是什么意思、如何求; 三是最晚时间是什么意思、如何求。简单地说 ,最早时间是通过 “从前向后” 的方法求的 , 而最晚时间是通过“从后向前”的方法求解的, 并且, 要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。在实际设计关键路径的算法时, 还应该注意以下这一点 : 采 用邻接 表的存储结 构, 求最 早时间和最晚时间要采用 不同 的处理

25、方法, 即 : 在算 法初始时, 应 该首先将所有 顶点 的最早时间全部置为 0 。 关键路径问题是工程进度控制的重要方法, 具有很强的实用性。7. 最短路径问题 : 与关键路径问题并称为图一章的两只拦路虎。 概念 理解是比 较容易的, 关 键是 算法的理解。最短路径问题分为两种:一是求从某一点出 发到其余各 点的精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 31 页最短 路径( 单源最短路径 ); 二是求图中每一对顶点 之间的 最短 路径。这个问题也具有非常实用的背景特色 , 一个典型的应该就是旅游景点及旅游路 线的选 择问题。解

26、决第一个问题用 DIJSKTRA 算法, 解决第二个问题用 FLOYD 算法, 注意区分。8 、查找 (search ) 先弄清楚以下几个概念: 关 键字、 主关键 字、 次 关键字的含义; 静态 查找与 动态查 找的含义及区别; 平均 查找长度 ASL 的概念及在各种查找算法中的计算方法和计算结果 ,特别是一些典型结构的 ASL 值, 应该记住。一般将 search 分为三类 : 在顺序表上的查找; 在 树表 上的查找; 在哈 希表上 的查 找。(1) 线性表上的查找 : 主要分为三种线性 结构: 顺序表 ?传统查找方法 :逐个比较 ; 有序顺序表?二分查找法 (注意适 用条件以及其递归 实

27、现方法 ); 索引顺序表?对索引结构 , 采用索引查找算法。 注意这三种表下的 ASL 值以及 三种算法的实现。 (2) 树表上的查找 : 树表主要分为以下几种: 二叉排序树( 即二叉 查找 树), 平 衡二叉查找树 (AVL 树),B 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 31 页树, 键树。其中, 尤以前两种结构为重 , 也有部分名校偏爱考 B 树的。由于二叉排 序树与平 衡二叉树是一种特 殊的二 叉树。二叉排序树, 简言之 , 就是“左小右大” , 它的 中序遍 历结果是 一个递 增的有 序序 列。 平 衡二叉排序树是

28、二叉排序树的 优化 , 其本质也是一 种二叉排序树, 只不 过, 平 衡排序 二叉 树对左右子树的深度有了限定 : 深度之差 的绝对值不得大 于 1 。对于二叉排序树 , “判 断某棵 二 叉树是否二叉排序树”这一算法经常被考到 , 可用递归 , 也可以用非递归。 平衡二叉 树的建 立也是一个常考点 , 但该知识点归根结底还是关注的平衡二叉树的四种调整 算法, 调整的 一个参 照是 : 调整前后的中序遍历结果相同。 B 树是二叉排序树的进一步改进, 也可以把B 树理 解为三叉、四叉. 排序树。除 B 树的查找算法外 ,应该特别注意一下 B 树的插入和删除算法 , 因为这两种算法涉及到 B 树

29、结点的分 裂和合并 , 是一个难点。键树(keywordtree),又称数字搜索树(digitalsearch tree)或字符树。 trie 树也可说等同于键树或属于键树的一种。键 树特别适 用于查找英文 单词 的场合。一般不要求能完整描述算法源码, 多是根据算法思想建立键树及描述精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 31 页其大致查找过程。 (3) 基于哈希表的查找算法 : 哈希译自“ hash”一词, 意为“散列”或“杂凑” 。哈希 表查找 的基本 思想是 :根据 当前待查找数据的特征, 以记录 关键字为自变量 , 设

30、计一个function , 该函数对关键字 进行转换后, 其解释结果为待 查的地 址。 基于哈希表的考查点有 : 哈 希函数的 设计, 冲突解 决方 法的选择及冲突处理过程的描 述。9 、内部排序考查你对书本上的各种排序 算法及其思想以及其优缺点和性能指 标 ( 时间复杂度 ) 能否了如指掌。排序方法分类有 : 插入、选择、交换、归并、计数等五种排序方法。 (1) 插入排序中又可分为 : 直接插 入、折 半插入、2 路插 入( ?) 、 希尔排序。这几种插入排序算法的最根本的不同点, 说到底就是根据什么规 则寻找新 元素的 插入点。直接插入是依次寻找, 折半插入是折半寻找 , 希尔排序 , 是

31、通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。(2) 交换排序, 又称冒泡排序 , 在交换排序的基础上改进又可以得到快速排序。快速排序的思想, 一语以敝之 : 用中 间数 将待排数据组一 分为二。(3) 选择精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 31 页排序可以分为 : 简 单选择、 树选择、 堆 排序。选择排序相对于前面几种排序算法来说, 难度大一点。这三种方法的不同点是 , 根据 什么 规则选取最小的 数。简单选择 ,是通过简单的数组遍历方案确定最小数; 树选择 , 是通过“锦标赛”类似的思

32、想 , 让两数相比 , 不断淘汰较大 ( 小) 者, 最终选出最小 ( 大) 数; 而堆排序 ,是利用堆这种数据结构的性质, 通过堆元素的删除、 调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建 立、堆调整是重要考点。(4) 归 并排序, 是 通过 “ 归并” 这 种操作 完成排 序的 目的,既然是归并就必须是两者以上的数据集合才可能实现归并。所以, 在归并排序中 , 关注 最 多的就是 2 路归并。算法思想比较简单, 有一点 , 要铭记在心 : 归并 排序是稳定排序。 (5) 基数排序 ,是一种很特别的排序方法, 也正是由于它的特殊 , 所以, 基数排序就比较适合于一些特别的场合,比如扑

33、克牌排序问题等。 基数排序 , 又分为 两种: 多关键字的排序 ( 扑克牌排序 ), 链式排 序 ( 整 数排序 ) 。基数排序的核心思想也是 利用“基数空 间” 这个概念将问精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 31 页题规模规范、变小, 并 且, 在排序的过程中 , 只要 按照 基排的思 想, 是 不用进行关 键字比较的, 这样得出的最终序列就是一个有序序列。本章各种排序算法的思 想以及伪代码实 现, 及其时 间复杂度都是必须掌握的。/ 稳定 性分 析/ 排序算法的稳定性, 通俗地讲就是能保证排序前 2 个 相 等的数其

34、 在序列 的前后 位置 顺序和排序后它们两个的前 后位置 顺序 相同。稳定性的好处 : 若排 序算法如果是稳定的 , 那么 从一个键上排序 , 然 后再从 另一个键上排序 , 第一个键排序的结果可以 为第 二个键排序所用。基数排序就是这样 , 先按低位排序 , 逐次按高位排序, 低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定 ,对基于比较的排序算法而言, 元素交换的次数可能会少一些个人感觉, 没有证实。分析一下常见的排序算法的稳定性, 每个都给出简单的理由。 1 冒泡排序冒泡排序就是把小的 元素往前调或者 把大的元素 往后调。比较是 相邻的两个 元素比较 , 交换也发生

35、在这两 个元素 之间 。 所以, 如果两个元素相等 , 我想你是不会再无聊地把他们俩交换一精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 31 页下的; 如果两个相等的元素没有相邻, 那么即使通过前面的两两交换把两个相邻起来 , 这时候也不会交换 , 所以相同元素的前后顺序并没有改变, 所以 冒泡排序是一种稳定排 序算 法。 2 选择排序选择排序是给每个位置选择当前元素最小的 , 比如给第一个位置选择最小的, 在剩余元素里面给第二个元素选择第二小的, 依次类推 , 直到第 n-1 个元素 ,第 n 个元素不用选择了 , 因为只剩下它一

36、个最大的元素了。 那么, 在一趟选择 , 如果当前元素比一个元素小 , 而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口 ,举个例子 , 序列 5 8 5 2 9 ,我 们知道第一遍选择第 1 个 元素 5 会和2 交换, 那么原序列中 2 个 5 的相对前后顺序就被破 坏了 , 所以 选择排序不是一 个稳定 的排 序算法。 3 插入排序插入排序是在一个已经有序的小序列的基础上, 一次插入一个元素。当然 , 刚开始这个有序的小序列只有 1 个元素 , 就是第一个元素。比较是从有序序列的末尾开始 , 也就是想要插入的元素和已经有序的最大者开始比起, 如果比它

37、大则直接插入在其后面 , 否则一直往前找直到找到它该插入的位置。如果碰 见一个和插入元素相等 的, 那么插入 元素把 想插入 的元 素放在相等元精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 31 页素的后面。所以, 相等元素的前后顺序没有改变, 从原无序序列出去的顺序就是排好序后的顺序, 所以插入排序是稳定的。 4 快速排序快速排序有两个方向,左边的 i 下标一直往右走 , 当 ai acenter_index,其中center_index 是中枢元素的数组下标, 一般取为数组第 0 个元素。 而右边的 j 下标一直往左走 , 当

38、aj acenter_index。如果 i 和 j 都走不动了 ,i j, 交换 ai和 aj,重复上面的过程 , 直到 ij。交换 aj和 acenter_index,完成一趟快速排序。在中枢元素和 aj交换的时候 , 很有可能把前面的元素的稳定性打乱, 比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素 5 和 3 第 5 个元素 , 下标从 1 开始计交换就会把元素 3 的稳定性打乱 , 所以快速 排序是 一个 不稳定的排序算法, 不 稳定发 生在中 枢元 素和 aj 交换的 时刻。 5 归并排序归并排序是把序列递归地分成短序列, 递归出口是短序列只有 1 个元素认为直接

39、有序或者 2 个序列 1 次比较和交换 , 然后把各个有序的段序列合并成一个有序的长序列 , 不断合并直到原序列全部排好序。可以发现 ,在 1 个或 2 个元素时 ,1 个元素不会交换,2 个元素如果大小相等也没有人故意交换 , 这不会破坏稳定性。 那么, 在短的有序序列合并精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 31 页的过程中 , 稳定是是否受到破坏?没有, 合并过程中我们可以保证如果两个当前元素相等时, 我们把处在前面的序列的元素保存在结果序列的前面 , 这样就保证了稳定性。 所以, 归并排序也是稳定的排序算法。 6 基

40、数排序基数排序是按照低位先排序, 然后收集; 再按照高位排序 , 然后再收集 ; 依次类推 , 直到最高位。有时候有些属性是有优先级顺序的, 先按低优先级排序,再按高优先级排序 ,最后的次序就是高优先级高的在前, 高优先级相同的低优先级高的在前。基数排 序基于 分别排 序, 分 别收集 , 所以其是稳定的 排序算 法。 7 希尔排序 shell希尔排序是按照不同步长对元素进行插入排序, 当刚开始元素很无序的时候, 步长最大 , 所以插入排序的元素个数很少, 速度很快 ; 当元素基本有序了, 步长很 小, 插 入排序 对于有序的序列效率很高。所以 , 希尔排序的时间复杂度会比 on2 好一些。由

41、于多次插入排序 ,我们知道一次插入排序是稳定的, 不会改变相同元素的相对顺序, 但在不同的插入排序过程中 , 相同的元素可能在各自的插入排序中移动, 最后其稳定性就会被打乱, 所以 shell 排序是不稳定的。 8 堆排序我们知道堆的结构是节点i 的孩子为 2*i 和 2*i+1 节点, 大顶堆要求父节点大于等于其 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 31 页个子节点, 小顶堆要求父节点小于等于其 2 个子节点。在一个长为 n 的序列 , 堆排序的过程是从第n/2 开始和其子节点共 3 个值选择最大大顶堆或者最小小顶堆

42、,这 3 个元素之间的选择当然不会破坏稳定性。但当为 n /2-1, n/2-2,.1 这些个父节点选择元素时, 就会破坏稳定性。有可能第 n/2 个父节点交换把后面一个元素交换过去了, 而第 n/2-1 个父节点把后面一个相同的元素没有交换 ,那么这 2 个相同的元素之间的稳定性就被破坏了。所以, 堆 排序不 是稳 定的排序算法。/ / 冒泡排序插 入排序二 路 插入排序希 尔排序快速排序选择排 序 归并排 序堆排序算法的C/C+实现/ / 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 31 页#includeusing name

43、space std; / 交换两个数的值void swapint &a,int &b int tmp;tmpa;ab;btmp; / 屏幕输出数组void displayint array,int len coutthe resultis:endl;for int i 0 ;i len;i+ coutarrayi ;coutendl; /* 冒泡排序算法思想 : 将被排序的记录数组 R1.n垂直排列 , 每个记录Ri 看作是重量为 Ri.key 的气泡。根据轻气泡不能在重气泡之下的原则 , 从下往上扫描数组 R: 凡扫描到违反本原则的轻气泡, 就使其向上 飘浮 。如此反复进行 , 直到最后任何

44、两个气泡都是轻者在上,重者在下为止。时间复杂度 on2 空间复杂度 o1 比较次数 nn+1/2 */ void bubble_sortint array,int len for int i len-1 ;i 0;i- forint j 0;j i;j+ ifarrayj arrayj+1swaparrayj,arrayj+1; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 31 页/* 直接插入排序算法思想 : 把 n 个待排序的元素看成为一个有序表和一个无序表, 开始时有序表中只包含一个元素, 无序表中包含有 n-1 个元素 ,

45、 排序过程中每次从无序表中取出第一个元素 , 将它插入到有序表中的适当位置, 使之成为新的有序表, 重复 n-1 次可完成排序过程。时间复杂度 on2 空间复杂度 o1 比较次数 nn+1/2 */ void insert_sortint array,int len int tmp,i,j;fori 1;i len;i+ if arrayi arrayi-1 tmp arrayi; arrayi arrayi-1; / 插入 到相 应位 置for j i-2;j 0;j- /往后移 if arrayj tmp arrayj+1 arrayj; else arrayj+1 tmp; break;

46、 ifj -1 arrayj+1 tmp; /* 2- 路插入排序算法思想 : 增加一个辅助空间 d, 把 r1赋值给 d1,并将 d1看成是排好序后处于中间位置的记录。然后从 r2开始依次插入到d1 之前或之后的有序序列中。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 31 页时间复杂度 on2 空间复杂度 o1 比较次数 nn+1/2 */ void bi_insert_sortint array,int len int* arr_d int*mallocsizeofint * len;arr_d0 array0;int hea

47、d 0,tail 0;for int i 1;i len; i+ if arrayi arr_d0 int j; for j tail;j0;j- if arrayi arr_dj arr_dj+1 arr_dj;else break; arr_dj+1 arrayi; tail + 1; else if head 0 arr_dlen-1 arrayi;head len-1; else int j;for j head;j len-1;j+ if arrayi arr_dj arr_dj-1 arr_dj; else break;arr_dj-1 arrayi;head - 1; for i

48、nt i 0;i len; i+ int pos i + head ; ifpos len pos - len; arrayi arr_dpos; freearr_d; /* 希尔排序算法思想 : 先将整个待排序记录分割成若干子序列分别进行直接插入排序 , 待整个序列中的记录基本有序时, 再对全体记录进行一次直接插入排序时间复杂度 on2 空间复杂度 o1 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 31 页比较次数*/ void shell_insertint array,int d,int len int tmp,j;for

49、int i d;i len;i+ ifarrayi arrayi-d tmp arrayi; j i - d; doarrayj+d arrayj;j j - d; while j 0 &tmp arrayj; arrayj+d tmp; void shell_sortint array,int len int inc len;do inc inc/2; shell_insertarray,inc,len; while inc 1; /* 快速排序算法思想 : 将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题 , 然后将这些子问题的解组合成为原问题的解。时间复杂度 o

50、nlogn 空间复杂度 ologn 比较次数*/ void quick_sortint array,int low,int high if low high int pivotloc partitionarray,low,high; quick_sortarray,low,pivotloc-1;quick_sortarray,pivotloc+1,h精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 25 页，共 31 页igh; int partitionint array,int low,int high int pivotkey arraylow

51、;while low highwhilelow high &arrayhigh pivotkey -high; swaparraylow,arrayhigh; whilelow high &arraylow pivotkey +low; swaparraylow,arrayhigh;arraylow pivotkey;return low; /* 直接选择排序算法思想 : 每一趟在 n-i+1 个记录中选取关键字最小的记录作为有序序列中的第 i 个记录时间复杂度 on2 空间复杂度 o1 比较次数 nn+1/2 */ int SelectMinKeyint array,int iPos,int

52、 len int ret 0;for int i iPos; i len; i+ if arrayret arrayi ret i; return ret; void select_sortint array,int len for int i 0; i len; i+ int j SelectMinKeyarray,i,len; if i ! j swaparrayi,arrayj; /* 归并排序精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 26 页，共 31 页算法思想 : 设两个有序的子文件相当于输入堆放在同一向量中相邻的位置上 :Rlo

53、w.m, Rm+1.high,先将它们合并到一个局部的暂存向量 R1 相当于输出堆中 , 待合并完成后将 R1 复制回 Rlow.high中。时间复杂度 onlogn 空间复杂度 on 比较次数*/ void mergeint array,int i,int m, int n int j, k;int iStart i, iEnd n;int arrayDest256;for j m + 1,k i; i m& j n; +k if arrayi arrayj arrayDestk arrayi+; else arrayDestk arrayj+;if i m for ;k n; k+,i+

54、arrayDestk arrayi;ifj n for ;k n; k+,j+ arrayDestk arrayj;forj iStart; j iEnd; j+ arrayj arrayDestj; void merge_sortint array,int s,int t int m;if s t m s + t /2; merge_sortarray,s,m; merge_sortarray,m+1,t; mergearray,s,m,t; /* 堆排序算法思想 : 堆排序 (Heap Sort) 是指利用堆 (heaps) 这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构,

55、并同时满足精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 27 页，共 31 页堆属性 : 即子节点的键值或索引总是小于( 或者大于 )它的父节点。时间复杂度 onlogn 空间复杂度 o1 比较次数 : 较多*/ void heap_adjustint array,int i,int len int rc arrayi;forint j 2 * i; j len; j * 2 ifj len & arrayj arrayj+1 j+; ifrc arrayj break; arrayi arrayj; i j;arrayi rc; void he

56、ap_sortint array,int len int i;fori len-1/2; i 0; i- heap_adjustarray,i,len;for i len-1; i 0; i- swaparray0,arrayi;/弹出最大值 , 重新对 i-1 个元素建堆 heap_adjustarray,0,i-1; int main int array 45, 56, 76, 234, 1, 34,23, 2, 3, 55, 88, 100;int len sizeofarray/sizeofint;/bubble_sortarray,len; /冒 泡排序 /*insert_sorta

57、rray,len;*/ /插 入排 序/*bi_insert_sortarray,len;*/ /二路插入排序/*shell_sortarray,len;*/ /希尔排序/*quick_sortarray,0,len-1;*/ /快速排序/*select_sortarray,len;*/ /选择排序/*merge_sortarray,0,len-1;*/ /归并排序 heap_sortarray,len; / 堆排序 displayarray,len;return 0; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 28 页，共 31 页| 对排

58、序 算法的 总结按平均时间将排 序分为 四类: (1) 平方阶 On2排序 一般称为简单排序 , 例如直接插入、直接选择和冒泡排序 ; (2) 线性对数阶 Onlgn 排序 如快速、堆和归并排序 ; (3)On1+阶排序是介于 0 和 1 之间的常数 , 即 01, 如希尔排序 ; (4) 线性阶 On排序 如桶、箱和基数排序。各种排序方法比较 简单排序中直接插入最好, 快速排序最快 ,当文件为正序时 , 直接插入和冒泡均最佳。影响排序效果的因素 因为不同的排序方法适应不同的应用环境和要求 , 所以选择合适的排序方法应综合考虑下列因素 : 待排序的记录数目 n; 记录的大小规模 ; 关键字的结

59、构及其初始状态; 对稳定性的要求; 语言工具的条件; 存储结构 ; 时间和辅助空间复杂度等。不同条件下, 排 序方法 的选 择1 若 n 较小如 n 50, 可采用直接插入或直接选择排序。当记录规模较小时 , 直接插入排序较好; 否则因为直接选择移动的记录数少于直接插人 , 应选直接选择排序为宜。2 若文件初始状态基本有序指正序, 则应选用直接插人、冒泡或随机的快速排序为宜 ; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 29 页，共 31 页3 若 n 较大, 则应采用时间复杂度为 Onlgn 的排序方法 : 快速排序、堆排序或归并排序。 快

60、速排序是目前基于比较的内部排序中被认为是最好的方法 , 当待排序的关键字是随机分布时, 快速排序的平均时间最短; 堆排序所需的辅助空间少于快速排序 , 并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。若要求排序稳定 , 则可选用归并排序。 但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡 ,通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件 , 然后再两两归并之。因为直接插入排序是稳定的, 所以改进后的归并排序仍是稳定的。10 、OSI 模型 7 层结 构,TCP/IP 模型结构 ? osi 参考模型osi 参考模型中的数据封装过程下面的

61、图表试图显示不同的 TCP/IP 和其他的协议在最初 OSI 模型中的位置 : 例如 HTTP 、SMTP 、SNMP 、FTP 、Telnet 、SIP、SSH 、NFS 、RTSP 、XMPP 、Whois、7 应用层ENRP 6 表示层 例如 XDR 、ASN.1、SMB 、AFP 、NCP 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 30 页，共 31 页例如 ASAP 、TLS 、SSH 、ISO 8327 / CCITT X.225、RPC 、NetBIOS 、ASP 、Winsock、5 会话层BSD sockets 4 传输层

62、例如 TCP、UDP 、RTP 、SCTP 、SPX 、ATP 、IL 3 网络层 例如 IP 、ICMP 、IGMP 、IPX、BGP 、OSPF 、RIP、IGRP 、EIGRP 、ARP 、RARP 、 X.25 例如 Ethernet 、Token ring 、HDLC 、Frame relay 、ISDN 、ATM 、802.11 WiFi 、FDDI、2 数据链路层PPP 1 物理层 例如 wire 、radio 、fiber optic、Carrier pigeon tcp/ip 参考模型tcp/ip 参考模型分为四个层次 : 应用层、传输层、网络互连层和主机到网络层 : tcp/ip 参考模型的层次结构通常人们认为 OSI 模型的精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 31 页，共 31 页