7.图的存储
图线性表中,数据元素是一对一的关系,除了第一个和最后一个元素外,每个元素有唯一的前驱和后继。
树形结构中,数据元素是一对多的关系,除了根之外,每个结点有唯一的双亲结点,可以有多个孩子。
图形结构是多对多的关系,任何两个数据元素都有可能有关系,每个结点可以有多个前驱和后继。
图通常用一个二元组表示:$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)$表示无序对
即不含平行边,也不含自环的图称为简单图。含有平行边或自环的图称为多重图。
无向图 ...
6.哈夫曼树与哈夫曼编码
哈夫曼树通常的编码方法有固定长度和不等长度编码两种。最优编码方案的目的是使总码长度最短。利用字符的使用频率来编码,是不等长编码方法,使得经常使用的字符编码较短,不常使用的字符编码较长。如果采用等长的编码方案,假设所有字符的编码都等长,则表示n个不同的字符需要位。例如三个不同的字符a,b,c,至少需要2位二进制数表示:a:00,b:01,c:10。如果每个字符的使用频率相等的话,固定长度编码是空间效率最高的方法。
不等长编码方法需要解决两个关键问题:
编码尽可能的短。使用频率高的字符编码较短,使用频率低的编码较长,可提高压缩率,节省空间,也能提高运算和通信速度。即频率越高,编码越短。
不能有二义性。解决的办法是:任何一个字符的编码不能是另一个字符编码的前缀,即前缀码特性。
设二叉树具有n个带权值的叶节点,那么从根节点到各个节点的路径长度与相应节点权值的乘积的和,叫做二叉树的带权路径长度WPL(Weighted Path Length)
$$WPL = \sum_{i=1}^nW_il_i$$
具有最小带权路径的二叉树称为哈夫曼树(也称最优树)哈夫曼算法采取的贪心 ...
跳表SkipList以及实现
跳表普通链表查找需要顺序比较,复杂度较高,而折半查找可以将复杂度降到$O(\log n)$,跳表就是利用折半的思想,建立索引,以空间换时间,优化后的空间约为原来所占空间的2倍。
跳表的结构类似:
C语言实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716 ...
5.二叉树
树树(Tree)是n(n≥0)个结点的有限集合,当n=0时,为空树;n>0时,为非空树。任意一棵非空树,满足:
有且仅有一个称之为根的结点;
除根结点以外的其余结点可分为$m(m>0)$个互不相交的有限集$T1, T2, …, Tm$, 其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。
节点:节点包含数据元素以及若干子树的分支信息
节点的度:节点拥有的子树个数
树的度:树中节点的最大度数
终端节点:度为0的结点,又称为叶子
分支节点:度大于0的节点。除了叶子都是分支结点
内部节点:除了树根和叶子都是内部节点
节点的层次:从根到该节点的层数(根节点为第一层)
树的深度(高度):所有节点中的最大层数
路径:树中两个结点之间的所经过的结点序列。
路径长度:两结点之间路径上经过的边数。
双亲、孩子:结点的子树的根称为该结点的孩子
兄弟:双亲相同的结点互称兄弟。
堂兄弟:双亲是兄弟的结点互称堂兄弟。小
祖先:即从该结点到树根经过的所有结点,称为该结点的祖先。
子孙:结点的子树中的所有结点都称为该结点的子孙。
有序树:结点的各子树从左至右有序,不能互 ...
4.字符串
字符串
串:字符串,有零个或者多个字符组成的有限序列
串长:串中字符的个数
空串:零个字符的串
子串:串中任意个连续字符组成的子序列。原串称为主串
字符串的存储可以使用顺序存储和链式存储两种方式。
顺序存储用一段连续的空间存储字符串。可以预先分配一个固定长度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;}
链式存储顺序存储的串在插入和删除操作时,需要移动大量元素,因此也可以采用链表的形式存储。
模 ...
3.队列和栈
栈后进先出(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 ...
2.链表
线性表线性表是由n(n≥0)个相同类型的数据元素组成的有限序列,它是最基本、最常用的一种线性结构。顾名思义,线性表就像是一条线,不会分叉。线性表有唯一的开始和结束,除了第一个元素外,每个元素都有唯一的直接前驱,除了最后一个元素外,每个元素都有唯一的直接后继。
前驱和后继
顺序表顺序表是顺序存储方式,即逻辑上相邻的数据在计算机内的存储位置也是相邻的。顺序存储方式,元素存储是连续的,中间不允许有空,可以快速定位第几个元素,所以插入、删除时需要移动大量元素。
链表链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻
单链表
添加操作头插法
尾插法
中间添加
删除操作
数组实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include <stdio.h>#def ...
1.算法基础
算法特性
有穷性:算法是由若干条指令组成的有穷序列,总是在执行若干次后结束,不可能永不停止。
确定性:每条语句有确定的含义,无歧义。
可行性:算法在当前环境条件下可以通过有限次运算实现。
输入输出:有零个或多个输入,一个或多个输出。
衡量算法
时间复杂度: 算法运行需要的时间,一般将算法的执行次数作为时间复杂度的度量标准。
空间复杂度: 算法占用空间的大小。一般将算法的辅助空间作为衡量空间复杂度的标准。
算法占用的存储空间包括:
输入/输出数据;
算法本身;
额外需要的辅助空间
常见的算法复杂度
常数阶。常数阶算法运行的次数是一个常数,如 5、20、100。
多项式阶。很多算法时间复杂度是多项式,通常用 О(n)、О(n )、 О(n )等表示
指数阶。指数阶时间复杂度运行效率极差。
对数阶。对数阶时间复杂度运行效率较高,常见的有 О(logn)、О(nlogn)等
$$О(1)< О(logn)< О(n)< О(nlogn) < О(n2)< О(n3)< О(2n) < О(n!)< О(nn)$$
兔子数列 ...
C语言-字符串操作
字符测试函数字符测试函数,由头文件"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 ...





