1 数据
2 算法
3 线性表
4 栈
5 队列
6 串
朴素模式匹配算法 -子串的定位操作:从主串中找到子串
KMP模式匹配算法(大大避免重复遍历的情况)
7 树
8 二叉树
二叉树的遍历(前序,中序,后序,层序)
赫夫曼树(最优二叉树)
9 图
10 最小生成树
普里姆算法,克鲁斯卡尔算法
11 最短路径
迪杰斯特拉算法,弗洛伊德算法
拓扑排序 -一个工程能否顺序进行
关键路径 -起点到终点最长路径
12 表
静态查找表,动态查找表,散列表(哈希表)
折半查找,插值查找,斐波那契查找
13 索引
二叉排序树,平衡二叉树(AVL树),多路查找树(B树),B+树
1 数据
数据--是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合 电影
数据元素--是组成数据的,有一定意义的基本单位 电影角色
数据项--几个数据项组成一个数据元素,是数据不可分割的最小单位 电影角色的脸
数据对象--是性质相同的数据元素的集合 反派电影角色
数据结构--是相互之间存在一种或多种特定关系的数据元素的集合
意义:我们要分析待处理对象的特性,及各对象之间的关系,才能写出一个好的程序
数据结构分为逻辑结构和物理结构
逻辑结构--是指数据对象中数据元素之间的相互关系
分为集合结构:数据元素之间的关系仅仅为同属于一个集合 数组
线性结构:数据元素之间为一对一关系 铁链
树形结构:数据元素之间为一对多关系
图形结构:数据元素之间为多对多关系
物理结构--是指数据的逻辑结构在计算机中的存储形式(指内存,外部存储器数据组织通常用文件结构)
分为顺序存储结构:把数据元素存放在地址连续的存储单元里,逻辑关系和物理关系一致 数组
链式存储结构:把数据元素存放在任意的存储单元里,用指针存放下个数据元素的地址
数据类型--是指一些性质相同的值的集合,及对值一些操作的总称
比如在C中,分为原子类型:int float char...
结构类型:数组
抽象--抽取出事物具有的普遍本质,共同特征
抽象数据类型--是指一个数学模型,及对该模型的一些操作的总称 类
比如int 与 NSInteger 都叫整型
描述抽象数据类型的标准格式:
ADT 抽象数据类型名
Data
数据元素之间逻辑关系的定义
Operation
操作1
初始条件
操作结果描述
操作n
...
endADT
2 算法
算法--是解决特定问题步骤的描述,在计算机中表现为指令的有限序列,每条指令表示一个或多个操作
算法的特性:
输入输出--可以没有输入,但必须至少一个输出
有穷性--在执行有限的步骤后自动结束,且时间要尽量短
确定性--每个步骤都要精确无歧义
可行性--每个步骤可以转换为程序上机执行
好的算法,应该有正确性,可读性,健壮性,高效率,低存储量
算法效率的度量方法:
事后统计方法--设计测试数据,在计算机上运行算法,看时间(不采用,因为硬件差距大)
事前分析估算方法--依据统计方法对算法进行估算,消耗时间的基本操作的执行次数(输入规模)
函数的渐近增长:
两个函数f1(n)与f2(n),如果在一个取值区间内,f1(n)总是大于f2(n),那就说f1(n)的增长渐近快于f2(n)
算法时间复杂度:(算法的时间量度/算法的渐近时间复杂度)
T(n) = O(f(n)) n输入规模 T(n)语句总的执行次数 f(n)运行次数函数 O()体现算法时间复杂度
表示随输入规模n的增大,算法执行时间的增长率与f(n)的增长率相同
随着n的增大,T(n)增长最慢的算法为最优算法
整体用的storyboard做的布局,Controller之间跳转也是加载stroyboard中的Controller
控制器之间跳转用的
登录界面用的coredata查询sqlite数据库中用户信息
注册界面也是用coredata存储用户信息至sqlite数据库
推导大O阶:
1.用常数1取代运行时间中的所有加法常数
2.在运行次数函数中,只保留最高阶项
3.如果最高阶项存在且不是1,去掉该项相乘的常数
加法常数不重要,与最高次项相乘的常数不重要,更该关注最高阶项的阶数
运行三次的函数,f(n) = 3; 时间复杂度为O(1) 叫常数阶
一个for循环n次的函数,f(n) = n; 时间复杂度为O(n) 叫线性阶
还有x次2相乘大于n的函数,f(n) = log2n; 时间复杂度为O(logn) 叫对数阶
两个for循环嵌套的函数,f(n) = n * n; 时间复杂度为O(n*n) 叫平方阶
运行次数函数f(n) = 4n²+2n+8; 时间复杂度为:4与2n与8可忽略,为O(n²)
算法空间复杂度:
S(n) = O(f(n)) n输入规模 f(n)语句关于n所占存储空间的函数
计算算法所需的存储空间
3 线性表
线性表是有序的,有限的
a1...ai-1,ai,ai+1...an
ai-1为ai的前驱元素,ai+1为ai的后继元素,i为位序,且只有一个前驱和后继
ADT 线性表 List
Data
线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType.除第一个元素外,每个元素有且只有一个直接前驱元素,除了最后一个元素,每个元素有且只有一个直接后继元素.数据元素之间的关系是一对一的关系
Operation
InitList(*L) 初始化操作,建立一个空的线性表L
ListEmpty(L) 判断线性表是否为空
ClearList(*L) 将线性表清空
GetElem(L,i,*e) 将线性表L中的第i个位置元素值返回给e
LocateElem(L,e) 在线性表L中查找与e相等的元素,成功返回该元素在表中序号,失败返回0
ListInsert(*L,i,e) 在线性表L中的第i个位置插入新元素e
ListDelete(*L,i,*e) 删除线性表L中第i个位置元素,并用e返回这个值
ListLength(L) 返回线性表L的元素个数
endADT
怎么这么像NSArray?是的,NSArray就是一个OC定义的数据结构啊
//struct->protype==(*struct).protype
//malloc (size) 功能：在内存的动态存储区中分配一块长度为"size" 字节的连续区域
//calloc(n,size) 功能：在内存动态存储区中分配n块长度为“size”字节的连续区域。
//strlen指字符的长度
//sizeof指文件或者数据占的内存(字节)
线性表顺序存储结构: 类似不能移动的数组
插入和删除需要移动大量数据O(n),适合读取操作O(1)
线性表的链式存储结构: 链表,单链表,是动态结构,即时生成
每一个存储映象称为结点,分为存储数据元素信息的数据域 与下一个数据元素地址的指针域,n个结点链接成一个链表
每个结点只包含一个指针域的叫单链表
头结点可以有可以没有,一般设置一个,数据域存储线性表的长度,指针域存储第一个结点的指针,即头指针,在第一个结点之前
单链表存储结构:
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList;
插入和删除越频繁,效率优势越来越明显,可以一段一段操作数据O(1)
头插法和尾插法动态生成新的链表
静态链表--用数组描述的链表--游标实现法(因为某些语言没有指针)
#define MAXSIZE 1000 //链表长度
typedef struct{
ELemType data; //链表元素
int cur; //游标
}Component,StaticLinkList[MAXSIZE];
//理解即可
循环链表
将单链表中终端结点的指针端由空指针改为指向头结点,形成个头尾相接的环
双向链表
在单链表的每个结点中,再设置一个指向前驱结点的指针域
typedef struct DulNode{
ElemType data;
struct DulNode *prior; //直接前驱指针
struct DulNode *next; //直接后继指针
}
双向链表也可以是循环表
4 栈
栈--是限定仅在表尾进行插入和删除操作的线性表
后进先出 LIFO结构(Last In First Out) 弹夹 网页后退功能
栈顶--允许插入和删除的那一端
ADT 栈(stack)
Data
同线性表,元素具有相同的类型,相邻元素具有前驱和后继关系
Operation
InitStack(*S):初始化操作,建立一个空栈S
DestroyStack(*S):若栈存在,则销毁它
ClearStack(*S):将栈清空
StackEmpty(S):若栈为空,返回true,否则返回false
GetTop(S,*e):若栈存在且非空,用e返回S的栈顶元素
Push(*S,e):若栈存在,插入新元素e到栈S中并成为栈顶元素
Pop(*S,*e):删除栈S中栈顶元素,并用e返回其值
StackLength(S):返回栈S的元素个数
endADT
顺序栈--栈的顺序存储结构
有一种有趣的两栈共享空间,两端为栈底
链栈--栈的链式存储结构 不需要头结点
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LickStack{
LinkStackPtr top;
int count;
}LinkStack;
//说明在声明变量的时候可以直接StackNode stack1,而不是struct StackNode stack1,不写第一个StackNode也可以
//说明此结构体类的结构体指针为LinkStackPtr
如果栈中的元素变化不可预料,时大时小,用链栈
如果在可控范围内的变化,用顺序栈
迭代--常规for循环
递归--调用自己的函数称为递归函数
菲波那切数列兔子问题--前面相邻两项之和,一年后144只兔子
栈的应用:
逆波兰表示法:定义后缀表达式,计算四则运算 9+(3-1)*3+10/2 --> 9 3 1-3*+10 2/+
后缀表达式运算规则:
从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算后的结果再进栈,一直到获得结果
中缀表达式转后缀表达式规则:
从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右符号或优先级低于栈顶符号(*/优先+-),则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止
5 队列
队列--是只允许在一端进行插入操作,而在另一端进行删除操作的线性表
是一种先进先出的线性表(First In First Out)简称FIFO
允许插入的一端称为队尾,允许删除的一端称为队头
ADT 队列(Queue)
Data
同线性表.元素具有相同的类型,相邻元素具有前驱和后继关系
Operation
InitQueue(*Q):初始化操作,建立一个空队列Q
DestroyQueue(*Q):若队列Q存在,则销毁它
ClearQueue(*Q):将队列Q清空
QueueEmpty(Q):若队列Q为空,返回true,否则返回false
GetHead(Q,*e):若队列Q存在且非空,用e返回队列Q的队头元素
EnQueue(*Q,e):若队列Q存在,插入新元素e到队列Q中并成为队尾元素
DeQueue(*Q,*e):删除队列Q中队头元素,并用e返回其值
QueueLength(Q)返回队列Q的元素个数
endADT
循环队列的顺序存储结构
typedef int QElemType;
typedef struct{
QElemType data[MAXSIZE];
int front; //头指针
int rear; //尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出,简称为链队列
6 串
串--是由零个或多个字符组成的有限序列,又名字符串
空格串:只包含空格的串
子串:串中任意个数的连续字符组成的子序列
主串:包含子串的串
ADT 串(string)
Data
串中元素仅由一个字符组成,相邻元素具有前驱和后继关系
Operation
StrAssign(T,*chars) 生成一个其值等于字符串常量chars的串T
StrCopy(T,S) 串S存在,由串S复制得到串T
ClearString(S) 串S存在,将串清空
StringEmpty(S) 若串S为空,返回true,否则返回false
StrLength(S) 返回串S的元素个数,即串的长度
StrCompare(S,T) 若S>T,返回值大于0,若S=T,返回0,若S<T,返回值<0
Concat(T,S1,S2) 用T返回由S1和S2联接而成的新串
SubString(Sub,S,index,len) 串S存在,1<=index<=StrLength(S),且0<=index<=StrLength(S)-index+1,用Sub返回串S的第index个字符起长度为len的子串
Index(S,T,index) 串S和T存在,T是非空串,1<=index<=StrLength(S),若主串S中存在串T值相同的子串,则返回它在主串S中第index个字符之后第一次出现的位置,否则返回0
Replace(S,T,V) 串S,T,V存在,T是非空串.用V替换主串S中出现的所有与T相等的不重叠的子串
StrInsert(S,index,T) 串S和T存在,1<=index<=StrLength(S)+1,在串S的第index个字符之前插入串T
StrDelete(S,index,len) 串S存在,1<=index<=StrLength(S)-len+1,从串S中删除第index个字符起长度为len的子串
endADT
朴素模式匹配算法:子串的定位操作(从主串中找到子串) 挨个遍历
KMP模式匹配算法:根据子串中字符是否重复,可以减少比较次数,大大避免重复遍历的情况
把T串各个位置的j值得变化定义为一个数组next,next的长度就是T串的长度
next[j] = 0 (当j=1时)
= k ("P1...P(k-1)" = "P(j-k+1)...P(j-1)")
= 1 (其他情况)
j 123456
T abcdex
next[j] 011111
j 123456
T abcabx
next[j] 011123
j 123456789
T ababaaaba
next[j] 011234223
优化KMP模式匹配算法:
在计算next值时,判断T[next]的值与当前位置T[j]的值是否相等,如果相等,nextval[j]的值就等于nextval[next]的值
j 123456789
T ababaaaba
next[j] 011234223
nextval[j] 010104210
7 树
树--是n个节点的有限集.n=0时为空树
在任意一棵非空树中:
1>有且仅有一个特定的称为根(root)的结点
2>当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2...Tm,其中每一个集合本身又是一棵树,并且称为根的子树
结点拥有的子树数称为结点的度,度为0的结点称为叶结点或终端结点,度不为0的称为非终端结点或分支结点,除根结点外,也称为内部结点
结点的层次从根开始定义起,根为第一层,树中结点的最大层次称为树的深度或高度
如果将树中结点的各子树看成从左至右有次序的,不能互换的,则称该树为有序树
ADT 树(tree)
Data
树由一个根结点和若干棵子树构成,树中结点具有相同数据类型及层次关系
Operation
InitTree(*T) 构造空树T
DestroyTree(*T) 销毁树T
CreateTree(*T,definition) 按definition中给出的树的定义来构造树
ClearTree(*T) 若树T存在,则将树T清为空树
TreeDepth(T) 返回T的深度
Root(T) 返回T的根结点
Value(T,cur_e) cur_e是树T中一个结点,返回此结点的值
Assign(T,cur_e,value) 给树T中结点cur_e赋值为value
Parent(T,cur_e) 若cur_e是树T的非根结点,则返回它的双亲,否则返回空
LeftChild(T,cur_e) 若cur_e是树T的非根结点,则返回它的最左孩子,否则返回空
RightSibling(T,cur_e) 若cur_e有右兄弟,则返回它的右兄弟,否则返回空
InsertChild(*T,*p,i,c) 其中p指向树T的某个结点,i为所指结点p的度加上1,非空树c与T不相交,操作结果为插入c为树T中p指结点的第i棵子树
DeleteChild(*T,*p,i) 其中p指向树T的某个结点,i为所指结点p的度,操作结果为删除T中所指节点的第i棵子树
endADT
树的存储结构:
1 双亲表示法:
#define MAX_TREE_SIZE 100
typedef int TElemType; //树结点的数据类型
typedef struct PTNode{ //结点结构
TElemType data; //结点数据
int parent; //双亲位置
}PTNode;
typedef struct{ //树结构
PTNode nodes[MAX_TREE_SIZE]; //结点数组
int r,n; //根的位置和结点数
}PTree;
可以扩展域,增加双亲域,长子域,兄弟域
2 孩子表示法:
多重链表,每个结点有多个指针域,每个指针指向一棵子树的根节点
2.1 每个结点指针域的个数等于树的度 牺牲空间
2.2 每个结点指针域的个数等于该结点的度 牺牲时间
2.3 每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,然后n个头指针又组成一个线性表,顺序存储结构,存放进一个一维数组中
#define MAX_TREE_SIZE 100
typedef struct CTNode{ //孩子结点
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct{ //表头结构
TElemType data;
ChildPtr firstchild;
}CTBox;
typedef struct{ //树结构
CTBox nodes[MAX_TREE_SIZE]; //结点数组
int r,n; //根的位置和结点数
}CTree;
3 孩子兄弟表示法
typedef struct CSNode{
TElemType data;
struct CSNode *firstChild,*rightSib;
}CSNode,*CSTree;
8 二叉树
二叉树--是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的,分别称为根结点的左子树和右子树的二叉树组成
每个结点最多有两棵子树,左子树和右子树是有顺序的,即使只有一棵子树,也要区分左还是右,且次序不能颠倒
线性表结构可以理解为是树的一种极其特殊的表现形式
左斜树,右斜树,满二叉树,完全二叉树(按层序顺序编号)
二叉树性质:
1.在二叉树的第i层上至多有2^(i-1)个结点
2.深度为k的二叉树至多有2^k -1个结点
3.对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0 = n2 + 1
4.具有n个结点的完全二叉树的深度为[log2^n]+1
5.寻找双亲为i/2等
二叉树的顺序存储结构
适用于完全二叉树,按顺序存入数组中 ABCDEFGHI
二叉链表
二叉树每个结点最多有两个孩子,即一个数据域和两个指针域
typedef struct BiTNode{ //结点结构
TElemType data; //结点数据
struct BiTNode *lChild,*rChild; //左右孩子指针
}BiTNode,*BiTree;
二叉树的遍历
是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次
1>前序遍历
先访问根节点,然后前序遍历左子树,再前序遍历右子树 ABDGHCEIF
void PreOrderTraverse(BiTree T){
if(T==NULL){
return;
}
printf("%c",T->data);
PreOrderTraverse(T->lCHild);//先遍历左子树
PreOrderTraverse(T->rChild);//然后遍历右子树
}
2>中序遍历
从根结点开始,中序遍历根结点的左子树,然后访问根结点,最后中序遍历右子树 GDHBAEICF
void PreOrderTraverse(BiTree T){
if(T==NULL){
return;
}
PreOrderTraverse(T->lCHild);//先遍历左子树
printf("%c",T->data);
PreOrderTraverse(T->rChild);//然后遍历右子树
}
3>后序遍历
从左到右先叶子后结点遍历左右子树,最后访问根结点 GHDBIEFCA
void PreOrderTraverse(BiTree T){
if(T==NULL){
return;
}
PreOrderTraverse(T->lCHild);//先遍历左子树
PreOrderTraverse(T->rChild);//然后遍历右子树
printf("%c",T->data);
}
4>层序遍历
从根结点开始访问,从上而下逐层遍历,在同一层中,从左到右对结点逐个访问 ABCDEFGHI
建立二叉树:
将二叉树中每个结点的空指针引出一个虚结点,其值为"#",称为扩展二叉树 AB#D##C##
线索二叉树:
把空余的指针域指向前驱后继元素,指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树
并且除了两个左右指针域,再增加两个标识BOOL值,lTag与rTag,lTag为0时指向左孩子,为1时指向前驱,rTag为0时指向右孩子,为1时指向后继
typedef enum(Link,Thread) PointerTag; //Link==0表示指向左右孩子指针 Thread==1表示指向前驱或后继的线索
typedef struct BiTNode{ //结点结构
TElemType data; //结点数据
struct BiTNode *lChild,*rChild; //左右孩子指针
PointerTag lTag; //左标识
PointerTag rTag; //右标识
}BiTNode,*BiTree;
树转换为二叉树:
1.加线.在所有兄弟结点之间加一条连线
2.去线.每个结点只保留与第一个孩子结点的连线,删除它与其他孩子结点之间的连线
3.第一个孩子是二叉树结点的左孩子,兄弟转换过来的孩子是结点的右孩子
森林转换为二叉树:
1.把每个树转换为二叉树
2.把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子
二叉树转换为树:
1.加线.将子级与孙子级的右孩子结点都作为此结点的孩子连接
2.去线.删除所有结点与其右孩子结点的连线
二叉树转换为森林:
1.把所有右孩子分离出来
2.把分离出来的二叉树转换为树
森林的前序遍历和二叉树的前序遍历结果相同,森林的后序遍历和二叉树的中序遍历结果相同
赫夫曼树
是压缩文件时用的最基本的压缩编码方法
树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称为路径长度
结点的带权路径长度为从该结点到树根之间的路径长度与结点上权(值比例)的乘积
带权路径长度WPL最小的二叉树称作赫夫曼树.最优二叉树.
构造方法:
1.把各结点按照权值从小到大排列
2.取最小权值的两个结点作为新结点N1的两个子结点,新结点N1的权值为两个叶子权值得和
3.将N1替换两个结点重新排列
4.重复以上三步
传递时,构造好赫夫曼树,双方约定好赫夫曼编码规则,按照路径寻找数据
一般规定赫夫曼树的左分支代表0,右分支代表1,从根结点到叶子结点经过的路径分支组成的0和1的序列便为该结点对应字符的编码,这就是赫夫曼编码
9 图
图--是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边集合
顶点(元素)之间的边没有方向,则称这条边为无向边(),全是无向边的图称为无向图
G(V,{E}) V={A,B,C,D} E={(A,D),(B,A),(C,A),(B,C)}
有方向则为有向边<>,也称为弧,弧头,弧尾,有向图
G(V,{E}) V={A,B,C,D} E={<A,D>,<B,A>,<C,A>,<B,C>}
简单图:无重复边与指向自身的边
稀疏图,稠密图,连通图,子图,
权:与图的边或弧相关的数
网:带权的图
无向完全图:任意两个顶点之间都存在边 n(n-1)/2条边
有向完全图:任意两个顶点之间都存在方向互为相反的两条弧 n(n-1)条边
无向图的度,有向图的入度,出度
ADT 图
Data
顶点的有穷非空集合和边的集合
Operation
CreateGraph(*G,V,VR) 按照顶点集V和边弧VR的定义构造图G
DestroyGraph(*G) 图G存在则销毁
LocateVex(G,u) 若图G中存在顶点u,则返回图中的位置
GetVex(G,v) 返回图G中顶点v的值
PutVex(G,v,value) 将图G中顶点v赋值value
FirstAdjVex(G,*v) 返回顶点v的一个邻接顶点,若顶点在G中无邻接顶点返回空
NextAdjVex(G,v,*w) 返回顶点v相对于顶点w的下一个邻接顶点,若w是v的最后一个邻接点则返回空
InsertVex(*G,v) 在图G中增添新顶点v
DeleteVex(*G,v) 删除图G中顶点v及其相关的弧
InsertArc(*G,v,w) 在图G中增添弧<v,w>,若G是无向图,还需添加对称弧<w,v>
DeleteArc(*G,v,w) 在图G中删除弧<v,w>,若G是无向图,还需删除对称弧<w,v>
DFSTraverse(G) 对图G中进行深度优先遍历,在遍历过程对每个顶点调用
HFSTraverse(G) 对图G中进行广度优先遍历,在遍历过程对每个顶点调用
endADT
存储方式
1>邻接矩阵
用两个数组,一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息
无向图的边数组是一个对称矩阵
2>邻接表
针对有向图,用数组与链表结合,一个一维数组存储图中顶点信息,每个顶点的所有邻接点构成一个线性表(入度)
逆邻接表(出度)
3>十字链表
把邻接表和逆邻接表整合在了一起
4>邻接多重表
针对无向图,根据十字链表设计
5>边集数组
由两个一维数组构成,一个存储顶点的信息,另一个存储边的信息,这个边数组每个数据元素包括起点下标,终点下标,权
图的遍历
1>深度优先遍历 DFS
2>广度优先遍历 BFS
10 最小生成树
一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边.
最小生成树--构造连通网的最小代价生成树
普里姆算法
假设N=(P,{E})是连通网,TE是N上最小生成树中边的集合.算法从U={u0}(u0属于V),TE={}开始.
在所有u属于U,v属于V-U的边(u,v)属于E中,找出一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止.此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树.
时间复杂度为O(n²)
针对顶点展开,边数多的情况下更好一些
克鲁斯卡尔算法
假设N=(V,{E})是连通网,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}},图中每个顶点自成一个连通分量.在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边选择下一条代价最小的边.直至T中所有的顶点都在同一连通分量上为止
时间复杂度为O(eloge)
针对边来展开,边数少时效率会非常高
11 最短路径
非网图指的是两顶点之间经过的边数最少的路径,
网图指的是两顶点之间经过的边上权值之和最少的路径
迪杰斯特拉算法
按路径长度递增的次序产生最短路径的算法
时间复杂度为O(n²)
弗洛伊德算法
列出两个矩阵,一个是顶点到顶点的最短路径权值和的矩阵,一个是对应顶点的最小路径的前驱矩阵(初始化为P[i][j]=j存储路径)
通过修改初始矩阵的值,最终得到可以找出最短路径的矩阵
时间复杂度为O(n³)
拓扑排序
针对表示工程的有向图,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,称为AOV网
设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列v1,v2...vn,满足若从顶点vi到vj有一条路径,顶点vi必在vj之前,该顶点序列为一个拓扑序列
拓扑排序,对有向图构造拓扑序列的过程,解决一个工程能否顺序进行的问题
从AOV网中选择入度为0的顶点入栈,选择栈顶的顶点输出,然后删去此顶点,并删除此顶点为尾的弧,出现了入度为0的顶点就继续入栈,直到输出全部顶点或者AOV网中不存在入度为0的顶点,这个顺序就是拓扑排序方案
关键路径
在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,称为AOE网
其实就是从起点到终点找最长路径
12 表
静态查找表:只做查找操作的查找表
动态查找表:在查找过程中有增删操作的
顺序查找:从第一个查找到最后一个,直到查找到为止
有序表查找
折半查找:
二分查找,线性表中的数据必须是有序的,采用顺序存储.取中间数据作为比较对象,若小于中间数据,再左半区继续查找,若大于中间数据,在右半区继续查找
下标mid = low + 1/2 * (high-low)
插值查找:
根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法
mid = (key-a[low]) / (a[high]-a[low]) * (high-low)
表长较大,关键字分布较均匀的表,平均性能比折半查找好得多
斐波那契查找:
根据要查找表的长度n处于斐波那契数列F={0,1,1,2,3,5,8,13,21...}中位置,计算出k值(n=10,F[6]<n<F[7],得出k=7)
key<a[mid]时,新范围是low到mid-1,个数为F[k-1]-1个
key>a[mid]时,新范围是mid+1到high,个数为F[k-2]-1个
mid = low + F[k-1] - 1
13索引
加快查找速度设计的一种数据结构,把一个关键字与它对应的数据相关联的过程
分为线性索引,树形索引,多级索引
线性索引:
索引表,将索引项集合组织为线性结构
分为稠密索引,分块索引,倒排索引
稠密索引
在线性索引中将数据集中的每个记录对应一个索引项
索引表索引项是按照关键码有序的排列
索引项有序,在查找关键字时,可以使用有序查找算法
分块索引
对数据进行分段,每个分块有序,每一个块建立一个索引项,减少索引项的个数,块内无序,块间有序
一个分块索引表分为三部分,最大key值,块长,块首指针
倒排索引
记录号表存储具有相同次关键字的所有记录的记录号
二叉排序树
又称二叉查找树,左子树的值<根结点的值<右子树的值
中序查找时,就如同顺序查找了
平衡二叉树 AVL树
一种二叉排序树,每一个节点的左子树和右子树的 高度差 至多为1
看起来是对称的,可以提供比较高效的查找效率
多路查找树 B树
每个结点的孩子数可以多于两个,每个结点处可以存储多个元素
对数据的处理不断从硬盘等存储设备中调入或调出内存页面
2-3树 3阶B树
每个结点都有两个孩子或三个孩子
一个2结点包含一个元素和两个孩子
一个3结点包含一大一小两个元素和三个孩子
2-3-4树 4阶B树
一个4结点包含小中大三个元素和四个孩子
B树
平衡的多路查找树,2-3树和2-3-4树都是B树的特例,结点最大的孩子数目称为B树的阶
为内外存的数据交互准备的
调整B树结点的元素与硬盘存储页面大小相匹配,把根结点持久地保留在内存中,在这棵树上,寻找某一个关键字至多需要两次硬盘的读取
由于B树每个结点的元素比二叉树多得多,减少了必须访问结点和数据块的数量,从而提高了性能
B+树
出现在分支结点中的元素,会在叶子结点中再次列出,每一个结点都会保存一个指向后一叶子结点的指针
应文件系统所需而出
散列表(哈希表)查找
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)
f称为散列函数,哈希函数
关键字对应的记录存储位置称为散列地址
采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表
是面向查找的存储结构,散列技术的数据之间不存在什么逻辑关系,只与关键字有关
解决查找与给定值相等的记录
设计哈希表
直接定址法,数字分析法,平方取中法,折叠法,除留余数法,随机数法
关键在于解决key冲突：
1、开放地址法：一旦发生了冲突，就再进行一次哈希函数，计算出下一个散列地址，直到该散列地址是空的，只要散列表足够大，空的散列地址总能找到，并将记录存入，也叫线性探测法。
如果哈希函数计算的结果总是出现地址相同的情况，就称为堆积。
2、准备多个散列函数
3、链地址法：将同地址的存储在一个单链表中，好处是不会产生堆积
4、公共溢出区：设立一个区域存储地址冲突的元素，溢出表
