大学数据结构期末知识点重点总结

第一章概论1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系可以用一组数据（结点集合K）以及这些数据之间的一组二元关系（关系集合R）来表示：(K,R)结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系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;deleteq;）【Ο（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;deletep;）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(栈空)returnfalseelse{出栈，检查匹配情况，if(不匹配)returnfalse}如果结束后，栈非空，返回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.二叉树的高度定义为二叉树中层数最大的叶结点的层数加1c.二叉树的深度定义为二叉树中层数最大的叶结点的层数d.如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树f.当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶组成扩充二叉树，扩充二叉树是满二叉树外部路径长度E：从扩充的二叉树的根到每个外部结点（新增的空树叶）的路径长度之和内部路径长度I：扩充的二叉树中从根到每个内部结点（原来二叉树结点）的路径长度之和2.性质a.二叉树的第i层（根为第0层，i≥0）最多有2^i个结点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)/22)当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,k1…kn-1}，具有如下特性(i=0,1,…,⌊n/2⌋-1)ki≤k2i+1（左孩子）ki≤k2i+2（右孩子）（即父≤2个孩子）类似可以定义最大堆ki≥k2i+1ki≥k2i+2（即父≥2个孩子）b.建“初堆”：按序列建立完全二叉树，从其中最后一个有孩子的结点开始按堆的定义调整c.插入：插入点追加到最后，自下而上依次比较父与子，直到满足堆的定义d.删除：用最后结点替换被删结点，自上至下调整成堆e.移出最小/大值：可以将堆中最后一个位置上的元素(数组中实际的最后一个元素)移到根的位置上，利用从左开始向下筛选对堆重新调整7.Huffman树a.概念路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径结点路径长度：从根结点到该结点的路径上分支的数目树的路径长度：树中每个结点的路径长度之和b.带权的路径长度树中所有叶子结点的带权路径长度之和=其中：��：权值��：结点到根的路径长度c.编码：左0右1d.如何构建：选取序列中最小的相加生成树如此反复第六章树1.概念若k，k'∈N，则称k是k'的父结点，k'是k的子结点若有序对k，k'及k，k″∈N，则称k'和k″互为兄弟若有一条由k到达ks的路径，则称k是ks的祖先，ks是k的子孙2.树/森林与二叉树的相互转换a.树转换成二叉树加线:在树中所有兄弟结点之间加一连线抹线:对每个结点，除了其最左孩子外，去除其与其余孩子之间的连线旋转:以树的根结点为轴心，将整树顺时针转45°b.二叉树转化成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构c.森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构d.二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树3.周游a.先根(次序)周游若树不空