《2022年《数据结构》知识点总结 .pdf》由会员分享，可在线阅读，更多相关《2022年《数据结构》知识点总结 .pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构知识点概括第一章概 论数据就就是指能够被计算机识别 、 存储 与加工处理 得信息得载体 。数据元素就是数据得基本单位 ，可以由若干个数据项 组成。 数据项 就是具有独立含义得最小标识 单位。数据结构得定义：逻辑结构：从逻辑结构上描述数据，独立于计算机。线性结构：一对一关系 。线性结构：多对多关系。存储结构 ：就是逻辑结构用计算机语言得实现。顺序存储结构：如数组。链式存储结构 ：如链表。索引存储结构 ： 稠密索引：每个结点都有索引项。稀疏索引 ：每 组结点都有索引项。散列存储结构 ：如散列表。数据运算。对数据得操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用得有：检索 、插入、
2、删除、更新、排序。数据类型：就是一个值得集合以及在这些值上定义得一组操作 得总称。结构类型：由用户借助于描述机制定义，就是导出类型。抽象数据类型ADT ： 就是抽象数据得组织与与之得操作。相当于在概念层上描述问题。优点就是将数据与操作封装在一起实现了信息隐藏。程序设计得实质就是对实际问题选择一种好得数据结构，设计一个好得算法。算法取决于数据结构。算法就是一个良定义得计算过程，以一个或多个值输入，并以一个或多个值输出。评价算法得好坏得因素：算法就是正确得；执行算法得时间；执行算法得存储空间（主要就是辅助存储空间）；算法易于理解、编码、调试。时间复杂度：就是某个算法得时间耗费，它就是该算法所求解问
3、题规模n 得函数。渐近时间复杂度：就是指当问题规模趋向无穷大时，该算法时间复杂度得数量级。评价一个算法得时间性能时，主要标准就就是算法得渐近时间复杂度。算法中语句得频度不仅与问题规模有关，还与输入实例中各元素得取值相关。时间复杂度按数量级递增排列依次为：常数阶 O （1） 、 对数阶 O （log2n） 、 线性阶 O （n） 、 线性对数阶O （nlog2n） 、平方阶 O（n2） 、立方阶O（n3） 、 k 次方阶 O（nk ） 、指数阶O（ 2n） 。空间复杂度：就是某个算法得空间耗费，它就是该算法所求解问题规模n 得函数。算法得时间复杂度与空间复杂度合称算法复杂度。第二章线性表线性表就
4、是由n0 个数据元素组成得有限序列。n=0 就是空表；非空表，只能有一个开始结点，有且只能有一个终端结点。线性表上定义得基本运算：构造空表：Initlist （L）求表长： Listlength （L）取结点： GetNode（L， i）查找： LocateNode（L，x）插入： InsertList （L，x，i）删除： Delete（L，i）顺序表就是按线性表得逻辑结构次序依次存放 在一组 地址连续 得存储单元中。 在存储单元中得各元素得物理位置与逻辑结构 中各结点相邻关系就是一致得。地址计算：LOCa（i）=LOCa （1）+（i-1）*d； （首地址为1）在顺序表中实现得基本运算：插
5、入：平均移动结点次数为n/2；平均时间复杂度均为O（n） 。删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O（n） 。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 16 页 - - - - - - - - - - 线性表得链式存储结构中结点得逻辑次序与物理次序不一定相同，为了能正确表示结点间得逻辑关系，在存储每个结点值得同时，还存储了其后继结点得地址信息（即指针或链 ） 。这两部分信息组成链表中得结点结构。一个单链表由头指针得名字来命名。单链表运算：建立单链表头插法：s-next
6、=head；head=s；生成得顺序与输入顺序相反。平均时间复杂度均为O（n） 。尾插法： head=rear=null ；if（head=null） head=s；else r-next=s； r=s； 平均时间复杂度均为O（n）加头结点得算法：对开始结点得操作无需特殊处理，统一了空表与非空表。查找按序号：与查找位置有关，平均时间复杂度均为O（ n） 。按值：与输入实例有关，平均时间复杂度均为O（n） 。插入运算：p=GetNode（L，i-1） ；s-next=p-next ；p-next=s；平均时间复杂度均为O（n）删除运算： p=GetNode（L， i-1） ； r=p-next；
7、p-next=r-next ；free（r） ；平均时间复杂度均为O（n）单循环链表就是一种首尾相接得单链表，终端结点得指针域指向开始结点或头结点。链表终止条件就是以指针等于头指针或尾指针。采用单循环链表在实用中多采用尾指针表示单循环链表。优点就是查找头指针与尾指针得时间都就是O（1） ，不用遍历整个链表。双链表就就是双向链表，就就是在单链表得每个结点里再增加一个指向其直接前趋得指针域prior，形成两条不同方向得链。由头指针head惟一确定。双链表也可以头尾相链接构成双（向）循环链表。双链表上得插入与删除时间复杂度均为O （1） 。顺序表与链表得比较：基于空间：顺序表得存储空间就是静态分配，
8、存储密度为1；适于线性表事先确定其大小时采用。链表得存储空间就是动态分配，存储密度1；适于线性表长度变化大时采用。基于时间：顺序表就是随机存储结构，当线性表得操作主要就是查找时，宜采用。以插入与删除操作为主得线性表宜采用链表做存储结构。若 插入 与删除 主要发生在表得首尾两端 ，则宜采用 尾指针 表示得 单循环链表 。第三章栈与队列栈（ Stack）就是仅限制在表得一端进行插入与删除运算得线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈得修改就是按后进先出得原则进行得，我们又称栈为LIFO 表（ Last In First Out ） 。通常栈有顺序栈与链栈两种存储结构
9、。栈得基本运算有六种：构造空栈： InitStack （S）判栈空：StackEmpty（S）判栈满：StackFull（ S）进栈：Push（S，x）退栈：Pop（S）取栈顶元素：StackTop（S）在顺序栈中有“上溢”与“下溢”得现象。 “上溢”就是栈顶指针指出栈得外面就是出错状态。 “下溢”可以表示栈为空栈，因此用来作为控制转移得条件。顺序栈中得基本操作有六种：构造空栈判栈空判栈满进栈退栈取栈顶元素链栈则没有上溢得限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有 链表得头指针 就可以了。链栈中得基本操作有五种：构造空栈判栈空进栈退栈取栈顶元素队列 （Queue）就是一种运算
10、受限得线性表，插入在表得一端进行，而删除在表得另一端进行，允许删除得一端称为队头（ front） ，允许插入得一端称为队尾（rear） ，队列得操作原则就是先进先出得，又称作FIFO 表（ First In First Out ） 、队列也有顺序存储与链式存储两种存储结构。队列得基本运算有六种：置空队： InitQueue（Q）判队空： QueueEmpty（Q）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 16 页 - - - - - - - - - - 判队满： QueueFull（Q）
11、入队： EnQueue（ Q， x）出队： DeQueue（ Q）取队头元素：QueueFront（Q）顺序队列得“假上溢”现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列就是空得却产生了“上溢”现象。为了克服 “假上溢” 现象引入循环向量得概念，就是把向量空间形成一个头尾相接得环形，这时队列称循环队列。判定循环队列就是空还就是满，方法有三种：一种就是另设一个布尔变量来判断；第二种就是少用一个元素空间，入队时先测试（rear+1）%m = front ）？满：空；第三种就就是用一个计数器记录队列中得元素得总数。队列得链式存储结构称为链队列，一个链队列就就是一个操作受限得单链表。
12、为了便于在表尾进行插入（入队）得操作，在表尾增加一个尾指针，一个链队列就由一个头指针与一个尾指针唯一地确定。链队列不存在队满与上溢得问题。在链队列得出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。第四章串串就是 零个 或 多个字符 组成得 有限序列 。空串：就是指长度为零得串，也就就是串中不包含任何字符（结点） 。空白串：指串中包含一个 或 多个 空格字符得串。在一个串中任意个连续字符组成得子序列称为该串得子串，包含子串得串就称为主串。子串在主串中得序号就就是指子串在主串中首次出现得位置。空串就是任意串得子串，任意串就是自身得子串。串分为两种：串常量在程序中只能
13、引用不能改变；串变量得值可以改变。串得基本运算有：求串长strlen（char*s）串复制strcpy（char*to ，char*from ）串联接 strcat（char*to， char*from ）串比较 charcmp（char*s1，char*s2）字符定位strchr（char*s，charc）串就是特殊得线性表（结点就是字符），所以串得存储结构与线性表得存储结构类似。串得顺序存储结构简称为顺序串。顺序串又可按存储分配得不同分为：静态存储分配：直接用定长得字符数组来定义。优点就是涉及串长得操作速度快，但不适合插入、链接操作。动态存储分配：就是在定义串时不分配存储空间，需要使用时按
14、所需串得长度分配存储单元。串得链式存储就就是用单链表得方式存储串值，串得这种链式存储结构简称为链串。链串与单链表得差异只就是它得结点数据域为单个字符。为了解决“存储密度”低得状况，可以让一个结点存储多个字符，即结点得大小。顺序串上子串定位得运算：又称串得“模式匹配”或“串匹配”，就是在主串中查找出子串出现得位置。在串匹配中，将主串称为目标（串），子串称为模式（串） 。这就是比较容易理解得，串匹配问题就就是找出给定模式串P在给定目标串T 中首次出现得有效位移或者就是全部有效位移。最坏得情况下时间复杂度就是O（ （n-m+1） m） ，假如 m 与 n 同阶得话则它就是O（n2） 。链串上得子串定
15、位运算位移就是结点地址而不就是整数第五章多维数组数组一般用顺序存储得方式表示。存储得方式有：行优先顺序，也就就是把数组逐行依次排列。PASCAL、 C 列优先顺序，就就是把数组逐列依次排列。FORTRAN 地址得计算方法：按行优先顺序排列得数组：LOCa（ij ）=LOCa （11）+（ （i-1 ）*n+ （j-1） ） *d、按列优先顺序排列得数组：LOCa（ij ）=LOCa （11）+（ （j-1 ）*n+ （i-1） ） *d、精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 16 页
16、 - - - - - - - - - - 矩阵得压缩存储：为多个相同得非零元素分配一个存储空间；对零元素不分配空间。特殊矩阵得概念：所谓特殊矩阵就是指非零元素或零元素分布有一定规律得矩阵。稀疏矩阵得概念：一个矩阵中若其非零元素得个数远远小于零元素得个数，则该矩阵称为稀疏矩阵。特殊矩阵得类型：对称矩阵：满足a（ij ）=a（ji ） 。元素总数n（n+1）/2、I=max（ i，j） ，J=min（i，j） ，LOCa（ij ）=LOC （sa0）+（I* （ I+1）/2+J）*d 、三角矩阵：上三角阵： k=i* （2n-i+1） /2+j-i ，LOCa（ij ）=LOC （sa0）+k*
17、d 、下三角阵：k=i* （i+1 ）/2+j ，LOCa（ij ）=LOC （sa0）+k*d 、对角矩阵：k=2i+j ，LOCa（ij）=LOC （ sa0）+k*d 、稀疏矩阵得压缩存储方式用三元组表把非零元素得值与它所在得行号列号做为一个结点存放在一起，用这些结点组成得一个线性表来表示。但这种压缩存储方式将失去随机存储功能。加入行表记录每行得非零元素在三元组表中得起始位置，即带行表得三元组表。第六章树树就是 n 个结点得有限集合，非空时必须满足：只有一个称为根得结点；其余结点形成m 个不相交得子集，并称根得子树。根就是开始结点；结点得子树数称度；度为0 得结点称叶子（终端结点）；度不
18、为0 得结点称分支结点（非终端结点） ；除根外得分支结点称内部结点；有序树就是子树有左，右之分得树；无序树就是子树没有左，右之分得树；森林就是m 个互不相交得树得集合；树得四种不同表示方法：树形表示法； 嵌套集合表示法； 凹入表示法广义表表示法。二叉树得定义：就是n0 个结点得有限集，它就是空集（n=0）或由一个根结点及两棵互不相交得分别称作这个根得左子树与右子树得二叉树组成。二叉树不就是树得特殊情形，与度数为2 得有序树不同。二叉树得4 个重要性质：二叉树上第i 层上得结点数目最多为2（i-1） （i1） 。 ；深度为k 得二叉树至多有（2k）-1 个结点（ k1） ；在任意一棵二叉树中，若
19、终端结点得个数为n0，度为 2 得结点数为n2，则 n0=n2+1；具有 n 个结点得完全二叉树得深度为int （log2n） +1、满二叉树就是一棵深度为k，结点数为 （2k）-1 得二叉树；完全二叉树就是满二叉树在最下层自右向左去处部分结点；二叉树得顺序存储结构就就是把二叉树得所有结点按照层次顺序存储到连续得存储单元中。（存储前先将其画成完全二叉树）树得存储结构多用得就是链式存储。BinTNode 得结构为 lchild|data|rchild ，把所有 BinTNode 类型得结点，加上一个指向根结点得BinTree 型头指针就构成了二叉树得链式存储结构，称为二叉链表。它就就是由根指针r
20、oot 唯一确定得。共有 2n 个指针域， n+1 个空指针。根据访问结点得次序不同可得三种遍历：先序遍历 （前序遍历或先根遍历），中序遍历 （或中根遍历） 、后序遍历 （或后根遍历）。时间复杂度为O（n） 。利用二叉链表中得n+1 个空指针域来存放指向某种遍历次序下得前趋结点与后继结点得指针，这些附加得指针就称为“线索”，加上线索得二叉链表就称为线索链表。线索使得查找中序前趋与中序后继变得简单有效，但对于查找指定结点得前序前趋与后序后继并没有什么作用。树与森林及二叉树得转换就是唯一对应得。转换方法：树变二叉树：兄弟相连，保留长子得连线。二叉树变树：结点得右孩子与其双亲连。森林变二叉树：树变二
21、叉树，各个树得根相连。树得存储结构： 有双亲链表表示法：结点data | parent，对于求指定结点得双亲或祖先十分方便，但不适于求指定精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 16 页 - - - - - - - - - - 结点得孩子及后代。孩子链表表示法：为树中每个结点data | next 设置一个孩子链表firstchild ，并将 data | firstchild 存放在一个向量中。双亲孩子链表表示法：将双亲链表与孩子链表结合。孩子兄弟链表表示法：结点结构leftmost
22、child |data | rightsibing ，附加两个分别指向该结点得最左孩子与右邻兄弟得指针域。树得前序遍历与相对应得二叉树得前序遍历一致；树得后序遍历与相对应得二叉树得中序遍历一致。树得带权路径长度就是树中所有叶结点得带权路径长度之与。树得带权路径长度最小得二叉树就称为最优二叉树（即哈夫曼树） 。在叶子得权值相同得二叉树中，完全二叉树得路径长度最短。哈夫曼树有n 个叶结点，共有2n-1 个结点，没有度为1 得结点，这类树又称为严格二叉树。变长编码技术可以使频度高得字符编码短，而频度低得字符编码长，但就是变长编码可能使解码产生二义性。如 00、01、 0001 这三个码无法在解码时确
23、定就是哪一个，所以要求在字符编码时任一字符得编码都不就是其她字符编码得前缀，这种码称为前缀码（其实就是非前缀码）。哈夫曼树得应用最广泛地就是在编码技术上，它能够容易地求出给定字符集及其概率分布得最优前缀码。哈夫曼编码得构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点得相应路径上得代码得序列就就是该结点得最优前缀码。第七章图图得逻辑结构特征就就是其结点（顶点）得前趋与后继得个数都就是没有限制得，即任意两个结点之间之间都可能相关。图 GraphG=（V，E） ，V 就是顶点得有穷非空集合，E 就是顶点偶对得有穷集。有向图 Digraph：每条边有
24、方向；无向图Undigraph：每条边没有方向。有向完全图：具有n*（n-1）条边得有向图；无向完全图：具有n*（ n-1）/2 条边得无向图；有根图：有一个顶点有路径到达其它顶点得有向图；简单路径：就是经过顶点不同得路径；简单回路就是开始与终端重得简单路径；网络：就是带权得图。图得存储结构：邻接矩阵表示法：用一个n 阶方阵来表示图得结构就是唯一得，适合稠密图。无向图：邻接矩阵就是对称得。有向图：行就是出度，列就是入度。建立邻接矩阵算法得时间就是O（ n+n2+e） ，其时间复杂度为O（n2）邻接表表示法：用顶点表与邻接表构成不就是唯一得，适合稀疏图。顶点表结构vertex | firsted
25、ge ，指针域存放邻接表头指针。邻接表：用头指针确定。无向图称边表；有向图又分出边表与逆邻接表；邻接表结点结构为adjvex | next，时间复杂度为O（n+e） 。 ，空间复杂度为O（n+e） 。 。图得遍历：深度优先遍历：借助于邻接矩阵得列。使用栈保存已访问结点。广度优先遍历：借助于邻接矩阵得行。使用队列保存已访问结点。生成树得定义：若从图得某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过得边与图得所有顶点构成得子图称作该图得生成树。最小生成树：图得生成树不唯一，从不同得顶点出发可得到不同得生成树，把权值最小得生成树称为最小生成树精品资料 - - - 欢迎下载 - - - - -
26、 - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 16 页 - - - - - - - - - - （MST ） 。构造最小生成树得算法：Prim 算法得时间复杂度为O（n2）与边数无关适于稠密图。Kruskal 算法得时间复杂度为O（lge） ，主要取决于边数，较适合于稀疏图。最短路径得算法： Dijkstra 算法，时间复杂度为O（n2） 。 类似于 prim 算法。拓扑排序： 就是将有向无环图G 中所有顶点排成一个线性序列，若E（G） ，则在线性序列u 在 v 之前，这种线性序列称为拓扑序列。拓扑排序也有两种方法：无前趋得顶点优先，每次输
27、出一个无前趋得结点并删去此结点及其出边，最后得到得序列即拓扑序列。无后继得结点优先：每次输出一个无后继得结点并删去此结点及其入边，最后得到得序列就是逆拓扑序列。第八章排序记录中可用某一项来标识一个记录，则称为关键字项，该数据项得值称为关键字。排序就是使文件中得记录按关键字递增（或递减）次序排列起来。基本操作：比较关键字大小；改变指向记录得指针或移动记录。存储结构：顺序结构、链表结构、索引结构。经过排序后这些具有相同关键字得记录之间得相对次序保持不变，则称这种排序方法就是稳定得，否则排序算法就是不稳定得。排序过程中不涉及数据得内、外存交换则称之为“内部排序”（内排序），反之，若存在数据得内外存交
28、换，则称之为外排序。内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序与分配排序。评价排序算法好坏得标准主要有两条：执行时间与所需得辅助空间，另外算法得复杂程序也就是要考虑得一个因素。插入排序：直接插入排序：逐个向前插入到合适位置。哨兵（监视哨）有两个作用：作为临变量存放Ri 就是在查找循环中用来监视下标变量j 就是否越界。直接插入排序就是就地得稳定排序。时间复杂度为O（n2） ，比较次数为 （n+2） （n-1）/2；移动次数为 （n+4）（n-1）/2；希尔排序：等间隔得数据比较并按要求顺序排列，最后间隔为1、希尔排序就是就地得不稳定排序。时间复杂度为O（ n1、25） ，比较次
29、数为（n1、25） ；移动次数为（1、6n1、25） ；交换排序：冒泡排序： 自下向上确定最轻得一个。自上向下确定最重得一个。自下向上确定最轻得一个，后自上向下确定最重得一个。冒泡排序就是就地得稳定排序。时间复杂度为O（n2） ，比较次数为n（n-1）/2；移动次数为3n（n-1）/2；快速排序： 以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。快速排序就是非就地得不稳定排序。时间复杂度为O（nlog2n） ，比较次数为n（n-1） /2；选择排序：直接选择排序：选择最小得放在比较区前。直接选择排序就地得不稳定排序。时间复杂度为O（n2） 。比
30、较次数为n（n-1）/2；堆排序建堆：按层次将数据填入完全二叉树，从int（ n/2）处向前逐个调整位置。然后将树根与最后一个叶子交换值并断开与树得连接并重建堆，直到全断开。堆排序就是就地不稳定得排序，时间复杂度为O（nlog2n） ，不适宜于记录数较少得文件。归并排序：先两个一组排序，形成（n+1）/2 组，再将两组并一组，直到剩下一组为止。归并排序就是非就地稳定排序，时间复杂度就是O（nlog2n） ，分配排序：箱排序：按关键字得取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。箱排序得平均时间复杂度就是线性得O（n） 。基数排序： 从低位到高位依次对关键字进行箱排序。基数排序就是非就
31、稳定得排序，时间复杂度就是O（d*n+d*rd ） 。各种排序方法得比较与选择：待排序得记录数目n；n 较大得要用时间复杂度为O（nlog2n）得排序方法；记录得大小（规模） ；记录大最好用链表作为存储结构，而快速排序与堆排序在链表上难于实现；关键字得结构及其初始状态；对稳定性得要求；精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 16 页 - - - - - - - - - - 语言工具得条件；存储结构；时间与辅助空间复杂度。第九章查找查找得同时对表做修改操作（如插入或删除）则相应得表称之为
32、动态查找表，否则称之为静态查找表。衡量查找算法效率优劣得标准就是在查找过程中对关键字需要执行得平均比较次数（即平均查找长度ASL ） 。线性表查找得方法：顺序查找：逐个查找，ASL= （n+1）/2；二分查找：取中点int（ n/2）比较，若小就比左区间，大就比右区间。用二叉判定树表示。ASL= （每层结点数 *层数） ）/N 、分块查找。要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中得最大关键字及其位置建立有序索引表。二叉排序树（ BST）定义就是：二叉排序树就是空树或者满足如下性质得二叉树：若它得左子树非空，则左子树上所有结点得值均小于根结点得值；若它得右子树非空，则右子树上
33、所有结点得值均大于根结点得值；左、右子树本身又就是一棵二叉排序树。二叉排序树得插入、建立、删除得算法平均时间性能就是O（ nlog2n） 。二叉排序树得删除操作可分三种情况进行处理：*P 就是叶子，则直接删除*P ，即将 *P 得双亲 *parent 中指向*P 得指针域置空即可。*P 只有一个孩子 *child ，此时只需将*child 与*p 得双亲直接连接就可删去*p、*p 有两个孩子，则先将*p 结点得中序后继结点得数据到*p，删除中序后继结点。关于 B-树（多路平衡查找树） 。它适合在磁盘等直接存取设备上组织动态得查找表，就是一种外查找算法。建立得方式就是从下向上拱起。散列技术：将结
34、点按其关键字得散列地址存储到散列表得过程称为散列。散列函数得选择有两条标准：简单与均匀。常见得散列函数构得造方法：平方取中法：hash=int（ （x2）%100）除余法：表长为m，hash=x%m 相乘取整法：hash=int（m*（x*A-int （x*A ） ） ；A=0、 618 随机数法： hash=random（x） 。处理冲突得方法： 开放定址法：一般形式为hi=（h（key）+di） %m1im-1，开放定址法要求散列表得装填因子 1、开放定址法类型：线性探查法：address=（hash（x）+i）%m；二次探查法：address=（hash（x） +i2 ）%m；双重散列法
35、：address=（ hash（x）+i*hash （y） ） %m；拉链法：就是将所有关键字为同义词得结点链接在同一个单链表中。拉链法得优点：拉链法处理冲突简单，且无堆积现象；链表上得结点空间就是动态申请得适于无法确定表长得情况；拉链法中可以大于1，结点较大时其指针域可忽略，因此节省空间；拉链法构造得散列表删除结点易实现。拉链法也有缺点：当结点规模较小时，用拉链法中得指针域也要占用额外空间，还就是开放定址法省空间。第十章排序10、1 排序得基本概念10、2 插入排序10、3 选择排序10、4 交换排序本章主要知识点：排序得基本概念与衡量排序算法优劣得标准，其中衡量标准有算法得时间复杂度、空间
36、复杂度与稳定性直接插入排序，希尔排序直接选择排序，堆排序冒泡排序，快速排序10、1 排序得基本概念精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 16 页 - - - - - - - - - - 1、排序就是对数据元素序列建立某种有序排列得过程。2、排序得目得：便于查找。3、关键字就是要排序得数据元素集合中得一个域，排序就是以关键字为基准进行得。关键字分主关键字与次关键字两种。对要排序得数据元素集合来说，如果关键字满足数据元素值不同时该关键字得值也一定不同，这样得关键字称为主关键字。不满足主关
37、键字定义得关键字称为次关键字。4、排序得种类：分为内部排序与外部排序两大类。若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序。注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。5、排序算法好坏得衡量标准：(1)时间复杂度 它主要就是分析记录关键字得比较次数与记录得移动次数。(2)空间复杂度 算法中使用得内存辅助空间得多少。(3)稳定性 若两个记录A 与 B 得关键字值相等，但排序后A、B 得先后次序保持不变，则称这种排序算法就是稳定得。10、2 插入排序插入排序得基本思想就是：每步将一个待排序得对象，按其关
38、键字大小，插入到前面已经排好序得一组对象得适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都就是排好序得。常用得插入排序有：直接插入排序与希尔排序两种。10、2、1 直接插入排序1、其基本思想就是：顺序地把待排序得数据元素按其关键字值得大小插入到已排序数据元素子集合得适当位置。例 1：关键字序列T=（13，6，3，31，9，27，5，11） ，请写出直接插入排序得中间过程序列。初始关键字序列： 【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序：【6, 13】, 3, 31, 9, 27, 5, 11 第二次排序：【3, 6, 13】 , 31, 9,
39、 27, 5, 11 第三次排序：【3, 6, 13， 31】, 9, 27, 5, 11 第四次排序：【3, 6, 9, 13，31】, 27, 5, 11 第五次排序：【3, 6, 9, 13，27, 31】, 5, 11 第六次排序：【3, 5, 6, 9, 13，27, 31】, 11 第七次排序：【3, 5, 6, 9, 11，13，27, 31】注：方括号 中为已排序记录得关键字，下划横线得关键字表示它对应得记录后移一个位置。2、直接插入排序算法public static void insertSort(int a) int i, j, temp; int n = a、Length
40、; for(i = 0; i -1 & temp aj) aj + 1 = aj; j -; aj + 1 = temp; 初始关键字序列： 【13】, 6, 3, 31, 9, 27, 5, 11 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 16 页 - - - - - - - - - - 第一次排序：【6, 13】, 3, 31, 9, 27, 5, 11 第二次排序：【3, 6, 13】 , 31, 9, 27, 5, 11 3、直接插入排序算法分析(1)时间效率：当数据有序时，执行
41、效率最好，此时得时间复杂度为O(n)；当数据基本反序时，执行效率最差，此时得时间复杂度为O(n2)。所以当数据越接近有序，直接插入排序算法得性能越好。(2)空间效率：仅占用1 个缓冲单元 O（1）(3)算法得稳定性：稳定8、2、2 希尔（ shell）排序（又称缩小增量排序）1、基本思想：把整个待排序得数据元素分成若干个小组，对同一小组内得数据元素用直接插入法排序；小组得个数逐次缩小，当完成了所有数据元素都在一个组内得排序后排序过程结束。2、技巧：小组得构成不就是简单地“ 逐段分割 ” ， 而就是将相隔某个增量d得记录组成一个小组,让增量 d逐趟缩短（例如依次取5,3,1） ，直到 d1 为止
42、。3、优点：让关键字值小得元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。例 2：设待排序得序列中有12 个记录，它们得关键字序列T=(65 ，34，25，87，12，38，56，46，14，77，92，23） ，请写出希尔排序得具体实现过程。public static void shellSort(int a, int d, int numOfD) int i, j, k, m, span; int temp; int n = a、 Length; for(m = 0; m numOfD; m +) /共 numOfD 次循环span = dm; /取本次得增量值
43、for(k = 0; k span; k +) /共 span个小组for(i = k; i -1 & temp aj) aj + span = aj; j = j - span; aj + span = temp; 算法分析：开始时d 得值较大，子序列中得对象较少，排序速度较快；随着排序进展，d 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作得基础，大多数记录已基本有序，所以排序速度仍然很快。时间效率： O(n(log2n)2) 空间效率： O（ 1） 因为仅占用1 个缓冲单元算法得稳定性：不稳定练习：1、欲将序列（ Q, H, C, Y, P, A, M, S, R, D, F, X
44、）中得关键码按字母升序重排，则初始d 为 4 得希尔排序一趟得结果就是？答：原始序列：Q, H, C, Y, P, A, M, S, R, D, F, X shell 一趟后：P,A,C,S,Q,D,F,X,R,H,M,Y 2、 以关键字序列（ 256，301，751，129，937，863，742，694，076，438）为例，写出执行希尔排序（取d=5,3,1）算法得各趟排序结束时，关键字序列得状态。解：原始序列 : 256，301， 751， 129，937，863，742，694，076，438 希尔排序第一趟d=5 256 301 694 076 438 863 742 751 12
45、9 937 第二趟 d=3 076 301 129 256 438 694 742 751 863 937 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 16 页 - - - - - - - - - - 第三趟 d=1 076 129 256 301 438 694 742 751 863 937 10、3 选择排序选择排序得基本思想就是：每次从待排序得数据元素集合中选取关键字最小（或最大）得数据元素放到数据元素集合得最前（或最后），数据元素集合不断缩小，当数据元素集合为空时选择排序结束。常
46、用得选择排序算法：（1）直接选择排序（2）堆排序10、3、1 直接选择排序1、其基本思想每经过一趟比较就找出一个最小值，与待排序列最前面得位置互换即可。（即从待排序得数据元素集合中选取关键字最小得数据元素并将它与原始数据元素集合中得第一个数据元素交换位置； 然后从不包括第一个位置得数据元素集合中选取关键字最小得数据元素并将它与原始数据集合中得第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。）2、优缺点优点：实现简单缺点：每趟只能确定一个元素，表长为n 时需要 n-1 趟例 3：关键字序列T= （ 21，25，49，25*，16，08） ，请给出直接选择排序得具体实现过
47、程。原始序列：21，25，49， 25*，16，08 第 1 趟08，25，49，25*，16， 21 第 2 趟08，16, 49，25*，25，21 第 3 趟08，16, 21，25*，25，49 第 4 趟08，16, 21，25*，25，49 第 5 趟08，16, 21，25*，25，49 public static void selectSort(int a) int i, j, small; int temp; int n = a、 Length; for(i = 0; i n - 1; i +) small = i; /设第 i 个数据元素最小for(j = i + 1; j
48、 n; j +) /寻找最小得数据元素if(aj asmall) small = j; /记住最小元素得下标if(small != i) /当最小元素得下标不为i 时交换位置temp = ai; ai = asmall; asmall = temp; 3、算法分析时间效率：O(n2) 虽移动次数较少，但比较次数仍多。空间效率： O（1） 没有附加单元（仅用到1 个 temp) 算法得稳定性：不稳定4、稳定得直接选择排序算法例：关键字序列T= （21，25，49，25*， 16，08） ，请给出稳定得直接选择排序得具体实现过程。原始序列：21，25，49， 25*，16，08 第 1 趟 08,
49、 21 , 25 , 49 , 25 *, 16 第 2 趟 08，16, 21，25，49 ，25 * 第 3 趟 08，16, 21，25，49 ，25 * 第 4 趟 08，16, 21，25，49 ，25 * 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 16 页 - - - - - - - - - - 第 5 趟 08，16, 21，25，25 * ，49 public static void selectSort2(int a) int i,j,small; int temp;
50、 int n = a、 Length; for(i = 0; i n-1; i+) small = i; for(j = i+1; j n; j+) /寻找最小得数据元素if(aj i; j-) /把该区段尚未排序元素依次后移aj = aj-1; ai = temp; /插入找出得最小元素 8、3、2 堆排序1、 什么就是堆？2、 怎样建堆？3、 怎样堆排序？堆得定义：设有n 个数据元素得序列k0， k1，kn-1，当且仅当满足下述关系之一时，称之为堆。解释：如果让满足以上条件得元素序列（k， k， ， kn）顺次排成一棵完全二叉树，则此树得特点就是：树中所有结点得值均大于（或小于）其左右孩子