ClancyCC

5.6 树和森林 5.6.1 树的存储结构 结合起来： 5.6.2 树和二叉树的转换 由子树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系。给定一棵树，可以找到唯一的一棵二叉树与之对应。 5.6.3 森林和二叉树的转换 5.6.4 树和森林的遍历 5.7 哈夫曼树（最优二叉树）Huffman Tree 5.7.1 哈夫曼树的基本概念 满二叉树不一定是哈夫曼树 权值越大的叶子距离根节点越近 具有相同带权结点的哈夫曼树不唯一 5.7.2 哈夫曼树的构造算法 因为哈夫曼树中权越大的叶子离根越近，所以采用贪心算法，即构造时首先选择权值小的叶子节点 包含n个叶子结点的哈夫曼树共有2n-1个结点，因为包含n棵树的森林要经过n-1次合并才能幸成哈夫曼树，也就产生了n-1个新结点。 哈夫曼树的结点度数为0或2，没有度为1的结点。 算法实现： 5.7.3 哈夫曼编码 若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。 关键:要设计长 ...

5.1 树形结构 为何要重点研究每结点最多只有两个“叉”的树? √二叉树的结构最简单，规律性最强; √可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 二叉树是n (n≥0)个结点的有限集，它或者是空集(n = 0)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。 特点： 1、每个结点最多有俩孩子(二叉树中不存在度大于2的结点)。 2、子树有左右之分，其次序不能颠倒。 3、二叉树可以是空集合，根订以有空的左子树或空的右子树。 二叉树不是树的特殊情况，二叉树结点的字数要区分左子树和右子树，即使只有一个子结点 5.2 案例引入 5.3 树和二叉树的抽象数据类型定义 5.4 二叉树的性质和存储结构 5.4.1 性质 在二叉树的第i层最多由2^(i-1)个结点，最少一个 深度为k的二叉树最多有2^k-1个结点，最少k个 对某一棵二叉树，如果其叶子树为n0，度为2的节点数为n2，则n0=n2+1; 证明：设总边数B，总结点数n，度为1的节点数为n1 从下往上看：B=n-1 从上往下看：B=n22+n11 又n=n0+n1+n2 可得n0= ...

4.1 串：内容受限的线性表 串（String）——零个或多个任意字符组成的有限序列 4.1.1串的顺序存储结构（更常用） 4.1.2串的链式存储结构——块链结构 4.1.4 串的模式匹配算法 目的：确定主串中所含子串第一次出现的位置 Brute—Force算法，亦称简单匹配算法：穷举 BF算法的时间复杂度 最好的情况是比较m次，最差为(n-m+1)*m次，效率低 KMP算法设计思想 此时主串的指针i不必回溯！ 假设某时刻已经比较到子串的前(j-1)位和主串第i位前面的(j-1)位已经相等了，但是i，j本身不相等； 此时寻找主串第i位前面有没有(k-1)位和子串从头开始的前(k-1)位正好相等； 如果没有，子串第一位和主串第i位继续往后比； 如果有，那么主串的第i位和子串的第k位继续往后比； 如此做直到找到或者主串比完了； 📌 第三步中，因为主串前(j-1)位已经和子串前(j-1)位相等了，所以要确定下一次从子串的哪一位开始继续比，只要看子串的前(k-1)位和第j位前的(k-1)位就可以了。则定义了next[j]这样一个函数处理子串 强调一下1<k& ...

3.1 栈和队列的定义和特点 栈和队列是限定插入和删除只能在表的端点进行的线性表，是线性表的子集 3.1.1 栈：Stack 栈就像手电筒装电池、手枪弹夹里装子弹：有**后进先出（Last In First Out）**的特性 栈是仅在表尾进行插入删除操作的线性表，简称LIFO结构 它与一般线性表的区别：仅在于运算规则不同 案例1：进制转换 括号匹配的检验 表达式求值 3.1.2 队列Queue 队列就像排队，有**先进先出（First In First Out）**的特性，插入仅在表尾，删除仅在表头 舞伴问题 3.3 栈的定义和实现：顺序栈和链栈 3.3.2 顺序栈的实现 上溢(overflow):栈已经满，又要压入元素，使问题的处理无法进行 下溢(underflow):栈已经空，还要弹出元素，只认为是一种结束条件 顺序栈的长度=S.top-S.base，这里可以对指针加减，他会自动除以元素长度 删除时，删除base对应空间，长度设为0，两个指针设为空 入栈：先判断是否上溢，满则报错(也可以加空间），否则压入元素并让top ...

2.5 线性表的链式表示和实现 2.5.3 下面介绍循环链表： 最大的优点是：从表中任一结点出发均可找到表中其他结点 终止条件： 判断指针是否等于头指针 对循环链表进行优化，更方便寻找首尾位置 两个带尾指针的循环链表的合并：时间复杂度是O(1) 2.5.4 下面介绍双向链表： 双向列表中仅插入和删除时，因为需要同时修改两个方向上的指针，两者的操作时间复杂度均为O(n)。和单链略有不同。 双向链表的插入： 双向列表的删除，仅删除O(1)，但是查找O(n) 2.5.5 链表的比较 2.6 顺序表和链表的比较 2.7 线性表的应用 2.8 顺序表和链表的应用 多项式相加适合用顺序表 稀疏多项式适合用链表 图书管理系统

2.5 线性表的链式表示和实现 2.5.1 基本概念 线性表的链式表示又称为非顺序映像或链式映像，逻辑次序和物理次序可能并不一致。 下图为带头结点的单链表示意图： 结点只有一个指针域的链表，称为单链表或线性链表 结点有两个指针域的链表，称为双链表 首尾相接的链表称为循环链表（可分单循环和双循环） 头指针:是指向链表中第一个结点的指针 首元结点:是指链表中存储第一个数据元素a,的结点 头结点:是在链表的首元结点之前附设的一个结点; 头结点的好处：便于首元结点的处理，空表和非空表可以统一处理（头指针都是指向头结点的非空指针） 链表（链式存储结构)的特点： (1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。 (2）访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等（顺序存取） 2.5.2 下面建立单链表： 建立链表时，通常采用LinkList L而不是Lnode L 更常用的定义方式 基本操作： 单链表的初始化： 判断链表是否为空（空表无元素，但是头指针和 ...

2.1 线性表的定义和特点 线性表(Linear List)是具有相同特性的数据元素的一个有限序列 同一线性表中的元素必具有相同的特征，且互为线性关系 有且仅有一个开始结点、一个终端结点，内部结点均有且仅有一个直接前趋和一个直接后继 2.2 案例引入 多项式可以用数组的形式来表示，但对于稀疏多项式将会造成存储空间很大的浪费，可以每一条元素记录多个数据项 顺序存储结构存在问题：存储空间分配不灵活，运算的空间复杂度高 此处对于多项式的加法可以采用链式结构 选择适当的存储结构，实现此存储结构上的基本操作并利用基本操作完成功能 线性表中数据元素的类型可以是简单类型，也可以是复杂类型 基本操作有很大相似性，不必一对一写程序 2.3 线性表的类型定义 基本操作有： InitList(&L), DestroyList(&L), Clear(&L) ListEmpty(L), ListLength(L) GetElem(L,i,&e), LocateElem(L,e,compare()) PriorElem(L,cur_e,&pre_e), N ...

1.1 数据结构的研究内容： 数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及他们之间的关系和操作的学科。 人事管理系统：增、删、改、查、排序，线性关系 人机对弈问题、文件系统的系统结构图：树形结构 最短路径：网状结构 1.2 基本概念和术语： 数据data ≥数据对象>数据元素data element（数值型，非数值型）>数据项data item 一个学生信息表可称为数据，里面一个学生可以看作一个数据元素，一个学生有姓名性别学号等多个数据项，其中所有男生可以组成一个数据对象 数据结构data structure =逻辑结构+储存结构+数据的运算和实现（增、删、改、查、排序） 逻辑结构包括线性结构（最多只有一个直接前趋和一个后继，线性表、栈、队列、串）和非线性结构（多个前后，树、图） 存储结构包括：顺序存储结构、链接存储结构（用指针连接，当前元素的值和下一个元素的地址）、索引存储结构index、散列存储结构 1.3 数据类型和抽象数据类型 数据类型data type 是一组性质相同的值的几何以及定义于这个值集合上的一组操作的总称 数据类型=值的几何+值 ...

❀❀❀❀完结撒花❀❀❀❀ 本书为北航蔡国飙先生团队的《液体火箭发动机设计》，其系统讲述液体火箭发动机系统、推力室、燃气发生器、涡轮泵及阀门和调节器的设计，理论联系实际，反映了当前液体火箭发动机设计的新技术和新成就。 从十一月十八日至今，已完成全部的更新。有很多不足的地方，也有不少地方笔者自己也没有看懂，选择了跳过。后续可能会查漏补缺，再添加一些内容。该系列之作自己学习纪念之用，希望未来能有长足进步。 以下为相关复习思考题： 6-1 发动机阀门的定义及其功能是什么？ 在液体火箭发动机系统中，将控制工质流动或调节工质参数的组件称为阀门（简称阀），其主要作用是保障发动机启动前的准备工作、过渡过程（启动、转级、关机）和调节过程等都能顺利进行。 6-2 阀门按功能可分为哪几类？ 液体火箭发动机上使用的阀门就其功能可分为：用来控制发动机工作过程，具有导流、截止、止回、溢流和卸压等作用的阀门，如启动阀、断流阀、单向阀、泄出阀和卸压阀等；用来调节发动机主要性能参数的阀门，通常称为调节器或调节阀，如减压器、压力调节器和节流圈等。 6-3 简述发动机控制系统设计的基本步骤。 ①选择控制方法。包括开环控 ...

本章无论是内容的量、难度还是强度都很高，需要多投入时间。下面第五章涡轮泵设计的下半部分： 以下为相关复习思考题： 5-7 什么是转子的平衡与不平衡？如何对涡轮泵转子进行平衡？ 在高速旋转的涡轮泵转子系统中，当没有大小和方向改变的离心力或由此产生的力矩外传时，这一转子系统称为平衡;反之,称为不平衡。 转子的静不平衡是指如果将转子放在水平位置的刀架上,则转子质心将会自动位于最低位置的现象。转子的静平衡是指转子在刀架上能实现“随遇平衡”。为了做到这一点，可在质心的同侧，半径为丁处去除质量为由名的材料;也可在重心的对侧，半径为了处加上质量为m g的配重。动不平衡是转子的一般不平衡状态，它由静不平衡和力偶不平衡叠加而成。经过静平衡的转子已能“随遇平衡”，但依然可能存在力偶不平衡的作用。动平衡是把转子放在动平衡机上进行旋转,通过在指定位置上添加配重，以消除不平衡力矩。 影响涡轮泵转子平衡的因素很多，也很复杂。高速旋转的零件，在设计时力求其形状对称于旋转轴线，同时保持必要的精度和较小的形状误差，对轴颈及轴承的要求应更高些. 组成转子的各零件的连接应能保持相互良好的定心。 一般转子的动平衡在普通的动 ...