Ansore

图线性表中，数据元素是一对一的关系，除了第一个和最后一个元素外，每个元素有唯一的前驱和后继。 树形结构中，数据元素是一对多的关系，除了根之外，每个结点有唯一的双亲结点，可以有多个孩子。 图形结构是多对多的关系，任何两个数据元素都有可能有关系，每个结点可以有多个前驱和后继。 图通常用一个二元组表示：$G=<V,E>$，V表示顶点集，E表示边集。$|V|$表示顶点集中元素的个数，即顶点数，也成为图G的阶，如n阶图，表示图中有n个顶点。$|E|$表示边集中元素的个数，即边数。 V和E均为有限集合，E可以为空集，V不可以为空，也就是说图至少有一个顶点 无向图。图中每条边都没有方向，则称为无向图。如顶点$v_1$和$v_3$可记为$(v_1, v_3)$或$(v_2, v_1)$。 有向图。图中每条边都是有方向的，则称为有向图。有向边也称为弧，每条弧都是由来嗯个顶点组成的有序对。 尖括号$<v_i, v_j>$表示有序对，圆括号$(v_i, v_j)$表示无序对 即不含平行边，也不含自环的图称为简单图。含有平行边或自环的图称为多重图。 无向图 ...

哈夫曼树通常的编码方法有固定长度和不等长度编码两种。最优编码方案的目的是使总码长度最短。利用字符的使用频率来编码，是不等长编码方法，使得经常使用的字符编码较短，不常使用的字符编码较长。如果采用等长的编码方案，假设所有字符的编码都等长，则表示n个不同的字符需要位。例如三个不同的字符a,b,c，至少需要2位二进制数表示：a:00，b:01，c:10。如果每个字符的使用频率相等的话，固定长度编码是空间效率最高的方法。 不等长编码方法需要解决两个关键问题： 编码尽可能的短。使用频率高的字符编码较短，使用频率低的编码较长，可提高压缩率，节省空间，也能提高运算和通信速度。即频率越高，编码越短。 不能有二义性。解决的办法是：任何一个字符的编码不能是另一个字符编码的前缀，即前缀码特性。 设二叉树具有n个带权值的叶节点，那么从根节点到各个节点的路径长度与相应节点权值的乘积的和，叫做二叉树的带权路径长度WPL(Weighted Path Length) $$WPL = \sum_{i=1}^nW_il_i$$ 具有最小带权路径的二叉树称为哈夫曼树（也称最优树）哈夫曼算法采取的贪心 ...

跳表普通链表查找需要顺序比较，复杂度较高，而折半查找可以将复杂度降到$O(\log n)$，跳表就是利用折半的思想，建立索引，以空间换时间，优化后的空间约为原来所占空间的2倍。 跳表的结构类似： C语言实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716 ...

树树（Tree）是n（n≥0）个结点的有限集合，当n=0时，为空树；n>0时，为非空树。任意一棵非空树，满足： 有且仅有一个称之为根的结点； 除根结点以外的其余结点可分为$m（m＞0）$个互不相交的有限集$T1, T2, …, Tm$, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。 节点：节点包含数据元素以及若干子树的分支信息 节点的度：节点拥有的子树个数 树的度：树中节点的最大度数 终端节点：度为0的结点，又称为叶子 分支节点：度大于0的节点。除了叶子都是分支结点 内部节点：除了树根和叶子都是内部节点 节点的层次：从根到该节点的层数（根节点为第一层） 树的深度（高度）：所有节点中的最大层数 路径：树中两个结点之间的所经过的结点序列。 路径长度：两结点之间路径上经过的边数。 双亲、孩子：结点的子树的根称为该结点的孩子 兄弟：双亲相同的结点互称兄弟。 堂兄弟：双亲是兄弟的结点互称堂兄弟。小 祖先：即从该结点到树根经过的所有结点，称为该结点的祖先。 子孙：结点的子树中的所有结点都称为该结点的子孙。 有序树：结点的各子树从左至右有序，不能互 ...

字符串 串：字符串，有零个或者多个字符组成的有限序列 串长：串中字符的个数 空串：零个字符的串 子串：串中任意个连续字符组成的子序列。原串称为主串 字符串的存储可以使用顺序存储和链式存储两种方式。 顺序存储用一段连续的空间存储字符串。可以预先分配一个固定长度Maxsize的空间在这个空间中存储字符串。 以**’\0’**表示字符串的结束（C/C++、Java）。 在0空间存储字符串的长度。下标0的空间不使用，因此可以预先分配Maxsize+1的空间，在下标为0的空间存储字符串长度。 结构体变量存储字符串长度。 1234567891011121314typedef struct Str { // 存储数组 char ch[Maxsize]; // 字符串的长度 int length;}// 或typedef struct Str { // 字符串指针 char *ch; // 字符串的长度 int length;} 链式存储顺序存储的串在插入和删除操作时，需要移动大量元素，因此也可以采用链表的形式存储。 模 ...

栈后进先出（Last In First Out，LIFO）的线性序列，称为“栈”。栈也是一种线性表，只不过它是操作受限的线性表，只能在一端进出操作。进出的一端称为栈顶（top），另一端称为栈底（base）。栈可以用顺序存储，也可以用链式存储，分别称为顺序栈和链栈。 静态分配 初始化 入栈 出栈 取栈顶 链栈 入栈 出栈 取栈顶 栈实现（数组）123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include <stdio.h>#define MAXSIZE 100// 数组实现栈typedef struct Stack { // 保存数据 int data[MAXSIZE]; // 指向栈顶的下标 int top;} Stack;int isEmpty(Stack *qstack) { if(qstack->to ...

线性表线性表是由n（n≥0）个相同类型的数据元素组成的有限序列，它是最基本、最常用的一种线性结构。顾名思义，线性表就像是一条线，不会分叉。线性表有唯一的开始和结束，除了第一个元素外，每个元素都有唯一的直接前驱，除了最后一个元素外，每个元素都有唯一的直接后继。 前驱和后继 顺序表顺序表是顺序存储方式，即逻辑上相邻的数据在计算机内的存储位置也是相邻的。顺序存储方式，元素存储是连续的，中间不允许有空，可以快速定位第几个元素，所以插入、删除时需要移动大量元素。 链表链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻 单链表 添加操作头插法 尾插法 中间添加 删除操作 数组实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include <stdio.h>#def ...

算法特性 有穷性:算法是由若干条指令组成的有穷序列,总是在执行若干次后结束,不可能永不停止。 确定性:每条语句有确定的含义,无歧义。 可行性:算法在当前环境条件下可以通过有限次运算实现。 输入输出:有零个或多个输入,一个或多个输出。 衡量算法 时间复杂度: 算法运行需要的时间,一般将算法的执行次数作为时间复杂度的度量标准。 空间复杂度: 算法占用空间的大小。一般将算法的辅助空间作为衡量空间复杂度的标准。 算法占用的存储空间包括: 输入/输出数据; 算法本身; 额外需要的辅助空间 常见的算法复杂度 常数阶。常数阶算法运行的次数是一个常数，如 5、20、100。 多项式阶。很多算法时间复杂度是多项式，通常用 О(n)、О(n )、 О(n )等表示 指数阶。指数阶时间复杂度运行效率极差。 对数阶。对数阶时间复杂度运行效率较高,常见的有 О(logn)、О(nlogn)等 $$О(1)< О(logn)< О(n)< О(nlogn) < О(n2)< О(n3)< О(2n) < О(n!)< О(nn)$$ 兔子数列 ...

字符测试函数字符测试函数，由头文件"ctype.h"定义 数字或字母测试函数isalnum1int isalnum(int c) 检查c是否为英文或者阿拉伯数字，若是返回真，否则返回假 字母测试函数isalpha1int isalpha(int c) 测试一个字符是不是英文字母，包括大小写 可打印字符测试函数isgraph1int isgrath(int c) 不可打印指的是转义字符、格式控制或特殊作用的字符 大小写测试函数islower和isupper12int islower(int c)int isupper(int c) islower用于测试一个字符是不是小写字符，isupper用于测试是不是大写字符 数字测试函数isxdigit1int isdigit(int c) 测试一个字母是不是0~9之间的阿拉伯数字 符号测试函数ispunct1int ispunct(int c) 测试一个字符是否为标点符号作者特殊符号 12345678910111213141516171819202122232425262728#include <stdio. ...

悲观锁悲观锁是利用数据库本身的锁机制来实现，会锁记录。 以一种预防的姿态在修改数据之前先把数据锁住，然后再对数据进行操作，在它释放锁之前任何人都不能对其数据进行操作，知道前面一个释放锁，后面才能对数据进行加锁，然后才可以对苏话剧进行操作。 特点：可以保证数据的独占性和正确性，因为每次请求都会先对数据进行加锁，然后再进行操作，最后再解锁，然而加锁释放锁的过程会造成消耗，所以性能不高。 实现方式： 1select * from t_table where id = 1 for update 要使用悲观锁，我们必须关闭MySQL数据库的自动提交属性。因为MySQL默认使用autocommit模式，也就是说，当我们执行一个更新操作后，MySQL会立刻将结果进行提交。（sql语句：set autocommit=0） 以下单过程为例： 12345678// 开始事务begin;// 查询商品库存信息select quantity from items where id = 1 for update;// 修改商品库存为2update items set quantity = 2 whe ...