大学数据结构期末知识点重点总结(考试专用).doc

第一章 概论1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系可以用一组数据（结点集合K）以及这些数据之间的 一组二元关系（关系集合R）来表示：(K, R)结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据关系集R是定义在集合K上的一组关系，其中每个关系r（rR）都是KK上的二元关系3.数据类型a.基本数据类型整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char）、指针类型（pointer） b.复合数据类型复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多）5.四种基本存储映射方法：顺序、链接、索引、散列6.算法的特性：通用性、有效性、确定性、有穷性7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化8.渐进算法分析a大分析法：上限，表明最坏情况b分析法：下限，表明最好情况c分析法：当上限和下限相同时，表明平均情况第二章 线性表1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性3.顺序表a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L（设每个元素需占用L个存储单元）c. 线性表的优缺点：优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样缺点：空间难以扩充d.检索：ASL=【（1）】e.插入：插入前检查是否满了，插入时插入处后的表需要复制【（n）】f.删除：删除前检查是否是空的，删除时直接覆盖就行了【（n）】4.链表4.1单链表a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等b.带头结点的怎么判定空表：head和tail指向单链表的头结点c.链表的插入（q-next=p-next; p-next=q;）【（n）】d.链表的删除（q=p-next; p-next = q-next; delete q;）【（n）】e.不足：next仅指向后继，不能有效找到前驱4.2双链表a.增加前驱指针，弥补单链表的不足b.带头结点的怎么判定空表:head和tail指向单链表的头结点c.插入：（q-next = p-next; q-prev = p; p-next = q; q-next-prev = q;）d.删除：（p-prev-next = p-next; p-next-prev = p-prev; p-prev = p-next = NULL; delete p;）4.3顺序表和链表的比较4.3.1主要优点a.顺序表的主要优点没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利b.链表的主要优点无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相 比其比例较大时，应该慎重选择第三章 栈与队列1.栈a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种b.应用：1）数制转换while (N) N%8入栈； N=N/8; while (栈非空) 出栈；输出；2）括号匹配检验不匹配情况：各类括号数量不同；嵌套关系不正确算法：逐一处理表达式中的每个字符ch： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else 出栈，检查匹配情况， if (不匹配) return false 如果结束后，栈非空，返回false3）表达式求值3.1中缀表达式：计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右3.2后缀表达式： := + | | := * |/| := := | = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 93.3中缀表达式转换为后缀表达式InfixExp为中缀表达式，PostfixExp为后缀表达式 初始化操作数栈OP，运算符栈OPND；OPND.push(#); 读取InfixExp表达式的一项操作数：直接输出到PostfixExp中； 操作符： 当（：入OPND; 当）：OPND此时若空，则出错；OPND若非空，栈中元 素依次弹出，输入PostfixExpz中，直到遇到（为止；若 为（，弹出即可 当四则运算符：循环（当栈非空且栈顶不是（& 当前运算符优先级栈顶运算符优先级），反复弹出栈顶运 算符并输入到PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP；while （表达式没有处理完) item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈c.递归使用的场合：定义是递归的；数据结构是递归的；解决问题的方法是递归的2.队列a.若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为队列b.循环队列判断队满对空：队空：front=rear；队满：(rear+1)%n=front第五章 二叉树1.概念a. 一个结点的子树的个数称为度数b.二叉树的高度定义为二叉树中层数最大的叶结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶结点的层数d.如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树 f.当二叉树里出现空的子树时，就增加新的、特殊的结点空树叶组成扩充二叉树，扩充二叉树是满二叉树外部路径长度E：从扩充的二叉树的根到每个外部结点（新增的空树叶）的路径长度之和内部路径长度I：扩充的二叉树中从根到每个内部结点（原来二叉树结点）的路径长度之和2.性质a. 二叉树的第i层（根为第0层，i0）最多有2i个结点b. 深度为k的二叉树至多有2k+1-1个结点c. 任何一颗二叉树，度为0的结点比度为2的结点多一个。n0 = n2 + 1d. 满二叉树定理：非空满二叉树树叶数等于其分支结点数加1e. 满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1f. 有n个结点（n0）的完全二叉树的高度为log2(n+1)，深度为log2(n+1)𝟏g. 对于具有n个结点的完全二叉树，结点按层次由左到右编号，则有： 1) 如果i = 0为根结点；如果i0，其父结点编号是 (i-1)/2 2) 当2i+1n，i结点的左子结点是2i+1；否则i结点没有左子结点 3) 当2i+2n，i结点的右子结点是2i+2；否则i结点没有右子结点3.周游（重点为由前序中序/中序后序求得二叉树）a.深度优先周游二叉树，可以有下列三种周游顺序：（实现：栈）1) 前序周游(tLR次序)：访问根结点；前序周游左子树；前序周游右子树 2) 中序周游(LtR次序)：中序周游左子树；访问根结点；中序周游右子树 3) 后序周游(LRt次序)：后序周游左子树；后序周游右子树；访问根结点b. 广度周游二叉树：从二叉树的顶层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问（实现：队列）4.存储链式存储结构，顺序存储结构（仅限完全二叉树：因为完全二叉树排列紧凑）5.二叉搜索树（BST）a.判定：是一颗空树；或者是具有下列性质的二叉树： 对于任何一个结点，设其值为K，则该结点的 左子树(若不空)的所有结点的值都小于K； 右子树(若不空)的所有结点的值都大于K；它的左右子树也分别为二叉搜索树b.性质：按照中序周游将各结点打印出来，得到的排列按照由小到大有序c.检索：从根结点开始，在二叉搜索树中检索值K 如果根结点储存的值为K，则检索结束 如果K小于根结点的值，则只需检索左子树 如果K大于根结点的值，则只检索右子树该过程一直持续到找到K或者遇上叶子结点 如果遇上叶子结点仍没有发现K，则查找失败*查找关键码：把查找时所经过的点一次写出d.插入：用待插入结点与树根比较，若待插入的关键值小于树根的关键值，就进入左子树，否则进入右子树；在子树中，按照同样的方式沿检索路径直到叶结点，将新结点插入到二叉搜索树的叶子结点位置e.创建：从空的BST开始，将关键码按BST定义一次插入f.删除：与插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性，删除过程分为如下情况：1）被删除的结点是叶子：直接将其删除即可2）被删除的结点只有左子树或只有右子树：直接将要删除的点删除后，将该点的左（右）孩子和上面结点相连3）被删除结点有左、右子树：若p有左右子树，则在左子树里找中序周游的最后一个结点r，将r的右指针置成指向p的右子树的根，用结点p的左子树的根去代替被删除的结点p6.堆a.最小/大堆定义：最小堆：是个关键码序列k0, k1kn-1，具有如下特性(i=0,1,n/2-1)k i k 2i+1（左孩子） k i k 2i+2（右孩子）（即父2个孩子）类似可以定义最大堆k i k 2i+1k i k 2i+2 （即父2个孩子）b.建“初堆”：按序列建立完全二叉树，从其中最后一个有孩子的结点开始按堆的定义调整c.插入：插入点追加到最后，自下而上依次比较父与子，直到满足堆的定义d.删除：用最后结点替换被删结点，自上至下调整成堆e.移出最小/大值：可以将堆中最后一个位置上的元素(数组中实际的最后一个元素)移到根的位置上，利用从左开始向下筛选对堆重新调整 7.Huffman树a.概念路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径结点路径长度：从根结点到该结点的路径上分支的数目树的路径长度：树中每个结点的路径长度之和b.带权的路径长度树中所有叶子结点的带权路径长度之和 =其中： 𝒘𝒌：权值 𝒍𝒌 ：结点到根的路径长度c.编码：左0右1d.如何构建：选取序列中最小的相加生成树如此反复第六章 树1.概念若N，则称k是k的父结 点，k是k的子结点若有序对及N， 则称k和k互为兄弟若有一条由 k到达ks的路径，则 称k是ks的祖先，ks是k的子孙2.树/森林与二叉树的相互转换a.树转换成二叉树加线: 在树中所有兄弟结点之间加一连线 抹线: 对每个结点，除了其最左孩子外，去除其与其余孩 子之间的连线 旋转: 以树的根结点为轴心，将整树顺时针转45b.二叉树转化成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构 c.森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 d.二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到 的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树3.周游a.先根(次序)周游若树不空，则先访问根结点，然后依次先根周游各棵子树b.后根(次序)周游若树不空，则先依次后根周游各棵子树，然后访问根结点c.按层次周游若树不空，则自上而下自左至右访问树中每个结点4.存储结构“左子/右兄”二叉链表表示法：结点左指针指向孩子，右结点指向右兄弟，按树结构存储，无孩子或无右兄弟则置空5. “UNION/FIND算法”（等价类）判断两个结点是否在同一个集合中，查找一个给定结点的根结点的过程称为FIND归并两个集合，这个归并过程常常被称为UNION“UNION/FIND”算法用一棵树代表一个集合，如果两个结点在同一棵树中，则认为它们在同一个集合中；树中的每个结点（除根结点以外）有仅且有一个父结点；结点中仅需保存父指针信息，树本身可以 存储为一个以其结点为元素的数组6.树的顺序存储结构a. 带右链的先根次序表示法 在带右链的先根次序表示中，结点按先根次序顺序存储在一片连续的存储单元中每个结点除包括结点本身数据外，还附加两个表示结构的信息字段，结点的形式为: info是结点的数据；rlink是右指针，指向结点的下一个兄弟；ltag是一个左标记，当结点没有子结点（即对应二 叉树中结点没有左子结点时），ltag为 1，否则为 0 b. 带双标记位的先根次序表示法规定当结点没有下一个兄弟（即对应的二叉树中结点没有右子结点时）rtag为1，否则为0c. 带双标记位的层次次序表示法结点按层次次序顺序存储在一片连续的存储单元中第七章 图1.定义a.假设图中有n个顶点，e条边：含有e=n(n-1)/2条边的无向图称作完全图含有e=n(n-1) 条弧的有向图称作有向完全图若边或弧的个数e nlogn，则称作稀疏图，否则称作稠密图b. 顶点的度(TD)=出度(OD)+入度(ID)顶点的出度: 以顶点v为弧尾的弧的数目顶点的入度: 以顶点v为弧头的弧的数目c.连通图、连通分量 若图G中任意两个顶点之间都有路径相通，则称此图为连通图 若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量 d.强连通图、强连通分量 对于有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图 否则，其各个极大强连通子图称作它的强连通分量 e.生成树、生成森林假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树 对非连通图，则将由各个连通分量构成的生成树集合称做此非连通图的生成森林 2.存储结构a.相邻矩阵表示法表示顶点间相邻关系的矩阵若G是一个具有n个顶点的图，则G的相邻矩阵是如下定义的nn矩阵： Ai,j=1，若(Vi, Vj)(或)是图G的边Ai,j=0，若(Vi, Vj)(或)不是图G的边b.邻接表表示法为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）（建立单链表时按结点顺序建立）3.周游a. 深度优先周游：从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发，深度优先搜索遍历图中的其余顶点，直至图中所有与V0有路径相通的顶点都被访问到为止b. 广度优先周游：从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，随后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有与V0有路径相通的顶点都被访问到为止，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止4.拓扑排序拓扑排序的方法是：1）选择一个入度为0的顶点且输出之2）从图中删掉此顶点及所有的出边3）回到第1步继续执行，直至图空或者图不空但找不到无前驱（入度为0）的顶点为止5.单源最短路径（Dijkstra算法）6.每对顶点间的最短路径（Floyd算法）7.最小生成树a.Prim算法b.Kruskal算法c.两种算法比较：Prim算法适合稠密图，Kruskal算法适合稀疏图第八章 内排序算法 最大时间 平均时间 直接插入排序 (n2) (n2) 冒泡排序 (n2) (n2) 直接选择排序 (n2) (n2) Shell排序 (n3/2) (n3/2) 快速排序 (n2) (nlog n) 归并排序 (nlog n) (nlog n) 堆排序 (nlog n) (nlog n) 桶式排序 (n+m) (n+m) 基数排序 (d(n+r) (d(n+r) 最小时间 S(n) 稳定性 (n) (1) 稳定 (n) (1) 稳定 (n2) (1) 不稳定 (n3/2) (1) 不稳定 (nlog n) (log n) 不稳定 (nlog n) (n) 稳定 (nlog n) (1) 不稳定 (n+m) (n+m) 稳定 (d(n+r) (n+r) 稳定 第十章 检索1.平均检索长度（ASL）是待检索记录集合中元素规模n的函数， 其定义为：ASL=Pi为检索第i个元素的概率;Ci为找到第i个元素所需的比较次数2.散列a.除余法用关键码key除以M(取散列表长度)，并取余数作为散列地址散列函数为：hash(key) key mod M b.解决冲突的方法 开散列方法：把发生冲突的关键码存储在散列表主表之外（在主表外拉出单链表） 闭散列方法：把发生冲突的关键码存储在表中另一个位置上c.线性探查 基本思想：如果记录的基位置存储位置被占用，就在表中下移，直到找到一个空存储位置；依次探查下述地址单元：d0+1，d0+2，.，m-1，0， 1，.， d0-1；用于简单线性探查的探查函数是:p(K, i) = i d.散列表的检索1.假设给定的值为K，根据所设定的散列函数h，计算出散列地址h(K) 2. 如果表中该地址对应的空间未被占用，则检索失败，否则将该地址中的值与K比较3. 若相等则检索成功；否则，按建表时设定的处理冲突方法查找探查序列的下一个地址，如此反复下去，直到某个地址空间未被占用（可以插入），或者关键码比较相等（有重复记录，不需插入）为止e.散列表的删除：删除后在删除地点应加上墓碑（被删除标记）f.散列表的插入：遇到墓碑不停止，知道找到真正的空位置第十一章 索引技术1.概念：a.主码：数据库中的每条记录的唯一标识b.辅码：数据库中可以出现重复值的码2.B树a.定义：B树定义：一个m阶B树满足下列条件： (1) 每个结点至多有m个子结点；(2) 除根和叶外其它每个结点至少有个子结点；(3) 根结点至少有两个子结点例外(空树，or独根)(4) 所有的叶在同一层,可以有- 1到m-1个关键码(5) 有k个子结点的非根结点恰好包含k-1个关键码 b.查找在根结点所包含的关键码K1，Kj中查找给定的关键码值(用顺序检索(key少)/二分检索(key多)；找到：则检索成功;否则，确定要查的关键码值是在某个Ki和Ki+1之间，于是取pi所指结点继续查找;如果pi指向外部结点，表示检索失败. c.插入找到的叶是插入位置，若插入后该叶中关键码个数m,插入完成；否则分裂,中间为分界码(插入到父结点),若父结点上溢则继续向上分裂d.删除删除的关键码不在叶结点层：先把此关键码与它在B树里的后继对换位置，然后再删除该关键码(叶中删)删除的关键码在叶结点层：删除后关键码个数不小于- 1直接删除关键码个数小于- 1，如果兄弟结点关键码个数不等于- 1从兄弟结点移若干个关键码到该结点中来(父结点中的一个关键码要做相应变化)如果兄弟结点关键码个数等于- 1合并