逻辑结构：线性结构，树形结构，图形结构

线性数据结构：线性数据结构是指数据元素之间存在一对一的线性关系的数据结构。常见的线性数据结构包括数组、广义表，链表、栈和队列

存储结构：顺序结构（开辟连续空间，通过地址），链式存储（指针域存放下一个地址，不连续），散列存储，索引存储

顺序表

连续顺序存储，可以快速定位，但是插入和删除需要移动大量元素

创建，取值，插入，删除（暂存）

（略）

链式

• 单链表：数据域，指针域

创建：头插法，尾插法

L->next =s->next;

L->next = s;

查找：定义一个指针p，比较p->data =e

删除：实际上就是把这个节点(i)跳过去，找到第i-1个节点

while((p->next)&&(j<i-1)){

p=p->next;

j++;

}
q=p->next;//暂时保存节点
p->next=q->next;
delete q;

• 双向链表：两个指针域

插入：前后两个方向操作

//p的前驱
p->prior
p->prior->next =s;
s->prior=p->prior;
s->next=p;
p->prior=s;

先处理p->prior和s的链接，再处理p和s的链接

线性表的应用

• 合并有序顺序表，将两个有序顺序表La和Lb合并为一个新的有序顺序表

创建Lc，从两个顺序表中选择较小的数据放入Lc

void mergelist(sqlist la,sqlist lb,sqlist &lc){
    int i,j,k;
    i=j=k=0;
    lc.length=la.length+lb.length;
    lc.element = new int[lc.length];
}
while(i<la.length&&j<lb.length){
    if(la.elem[i]<lb.elem[j]){
    lc.elem[k++]=la.elem[i++];
    }else{
    lc.elem[k++]=lb.elem[j++];
    }
}
while(i<la.length){
lc.elem[k++]=la.elem[i++];
}
while(j<lb.length){
lc.elem[k++]=lb.elem[j++];
}

• 合并有序链表：不需要开辟新空间，穿针引线,p,q指向链表的第一个节点,r指向尾部

void mergelinklist(linklist la,linklist,lb,linklist& lc){
    linklist p,q,r;
    p=la->next;
    q=lb->next;
    lc=la;
    r=lc;//r指向lc的尾部
    while(p&&q){
    if(p->data <= q->data){
    r->next =p;
    r=p;
    p=p->next;
    }else{
    r->next=q;
    r=q;
    q=q->next;
    }
    }
    r->next = p?p:q;
}

• 就地逆置单链表

断开指针，记录断点，插入

void reverselinklist(linklist& l){
   linklist p,q;
   p=l->next;
   l->next=null;
   while(p){
       q=p->next;
       p->next=l->next;
       l->next=p;
       p=q;
   }
}

• 查找链表的中间节点

快指针走两步，慢指针走一步，这样，快指针走到空时，慢指针正好走到中间

Linklist findmiddle(Linklist L){
    Linklist p,q;
    p=l;//p为快指针，指向L
    q=l;//q为慢指针
    while(p !=nullptr && p->next!=next){
    p=p->next->next;
    q=q->next;
    }
    return q;
}

• 删除链表中的重复元素

设置一个辅助数组，用1或0标注数据是否出现

void delerep(linklist& l){
    linklist p,q;
    int x;
    int* flag = new int[n+1];
    for(int i=0;i<=n;i++) flag[i]=0;
    p=l;//指向头结点
    while(p->next!=null){
    x=abs(p->next->data);
    flag[x]++;
    }
    
    if(flag[x]=0){
    p=p->next;
    }else{//删除操作
    q=p->next;
    p->next=q->next;
    delete q;
    }
}

栈

顺序栈

• 初始化

base指向栈底，top指向栈顶

动态分配

typedef struct stack{
    elemtype *base;
    elemtype *top;
}stack
#define maxsize

静态分配

typedef struct stack{
     elemtype data[maxsize];
     int top;
}stack

• 入栈

判断栈是否满，如果栈满，入栈是啊比，否则放入栈顶，栈顶指针向上移动一个位置

• 出栈

判断栈是否空，如果空，出栈失败，否则将栈顶元素暂存给一个变量，栈顶指针向下移动

• 取栈顶元素

不动栈顶指针，只是把栈顶元素复制一份

链栈

把链栈看作一个不带头节点的单链表，只能在头部操作，只需要一个栈顶指针

• 入栈

生成新的节点，修改栈顶指针指向新节点

P=new Snode;
p->data =e;//将e存入新节点数据域
p->next=S;//S指向的是旧的头节点地址域
S=p;//修改新栈顶指针为p

• 出栈

删除栈顶元素，让栈顶指针指向下一个节点

e=S->data;//保存栈顶元素
p=S;//保存栈顶元素地址
S=S->next;修改栈顶指针
Delete p;

• 取栈顶元素

把栈顶元素复制一遍

return S->data;

队列

进的一端称为队尾，出的一段称为队头

顺序队列

typedef struct sqQueue{
    Elemtype *base;
    int front,rear;
}sqQueue
#define maxsize 100

• 入队列

Q.base[Q.rear]=x;
Q.rear++;

• 出队列

e=Q.base[Q.front];
Q.rear++;

循环队列

判断队空？只要Q.rear和Q.front指向同一个位置

判断队满？当Q.rea的下一个位置是Q.front，（Q.rear+1）%Maxsize = Q.front

• 入队

将元素放入Q.rear所指空间，然后Q.rear后移一位

Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)%MaxSize;

• 出队

先用变量保存队头元素，然后队头Q.front后移一位

e=Q.base[Q.front];
Q.front=(Q.front+1)%MaxSize;

链队列

• 入队

先创建新结点并且将数据插入到data域

p=new Node;
p->data=e
Q.rear->next = S;
Q.raer=S;//移动

• 出队

相当于删除第一个数据元素，将第一个数据元素结点跳过去，p指针指向第一个数据节点

Q.front->next=p->next;

栈的应用

• 数制的转换，将一个十进制数转换成一个二进制数

思路：辗转相除法

Initstack(s);//初始化一个栈
while(n){
    s.push(n%2);//余数入栈
    n=n/2;
}
while(n!=empty){
    s.pop();
}

• 判断回文字符串

初始化栈S，求字符串长度，把前一半字符放入到栈中，再取出来与后半部分比较是否相同，注意奇书偶数的处理，如果是奇数，先要把中间的字符取出来

bool palimarome(char* str){
    sqstack s;
    int len,i;
    char e;
    len=strlen(str);
    Initstack(s);//初始化栈
    for(i=0;i<len/2;i++){
    s.push(str[i]);
    if(len%2 == 1) i=i+1;
    while(!empty(s)){
        pop(s,e);
    }
    if(e!=str[i]) {return False;}
    else {i=i+1;}
    return True;
    }
   
}

串

存储方式

• 顺序存储

1.以‘\0’表示字符串长度，不算字符串长度，但是占空间

2.在0空间存储字符串长度，下标为0的空间存储字符串长度

3.结构体变量存储字符串长度

静态

Typedef struct{
    char ch[Maxsize];
    int length;
}String

动态

Typedef struct{
    char *ch;
    int length;
}String

• 链式存储

改进，一个节点存储多个字符

串的模式匹配算法

求字串在主串的位置(BF)，T在S中的位置

从S的第一个字符开始，T的第一个字符开始，i=1，j=1,i++,j++，如果遇到不匹配，i回退到i-j+2，j回退到1，重新开始匹配，如果匹配成功，则返回字串T在主串S中第一个字符出现的位置

int Index_BF(String S,String T,int pos){
    int i=pos,j=1,sum=0;
    while(i<=s[0]&&j<=T[0]){
    sum+=1;
    if(s[i]=s[j]){
    j+=1;
    i+=1;
    }else{
    i=i-j+2;
    j=1;
    }
    if(j>T[0]) return i-T[0];
    else return 0;
    }
}

树

注意定义，体现递归的思想：有且仅有一个称为根的节点，除根节点以外，其余节点可分为m个互不相交的有限集T1,T2,T3,T4……，其中每一个集合本身又是一棵树，称为根的子树

度与节点的关系：结点的个数=总度数+1

存储方式

• 顺序存储

双亲表示法：每个节点有两个域，数据域data和双亲域parent

孩子表示法：除了存储数据元素之外，还存储所有孩子的存储位置下标

双亲孩子表示法：存储双亲和所有孩子的存储位置下标

• 链式存储

孩子表示法：

孩子兄弟表示法：二叉链表，节点除了存储数据元素之外，还有两个指针域lchild和rchild，lchild存储第一个孩子地址，rchild存储右兄弟地址

二叉树

有且仅有一个称为根的节点，除根节点以外，其余节点分为两个互不相交的子集T1,T2

最多有两个子树

满二叉树

完全二叉树

二叉树的性质

QA1：第i层最多有几个节点？

QA2：深度为k的二叉树最多有多少个节点？2^k-1

QA3：叶子数（2^n）和度为2的节点数(2^0+2^1+2^2+2^3……+2^n-1)的关系？

二叉树的遍历

• 先序遍历DLR

void preorder(Btree){
if(T){
cout<<T->data<<" ";
preorder(T->lchild);
preorder(T->rchild);
}
}

• 中序遍历LDR

• 后序遍历LRD

• 层次遍历

树和森林及其应用

树转二叉树：长子作为左孩子，兄弟关系向右倾斜

森林转树：把每棵树跟看作兄弟

哈夫曼树

构造一棵二叉树，若该树的带权路径长度达到最小，成这样的二叉树为最优二叉树，即哈夫曼树，权值较大的节点离根很近

树的带权路径长度：树中所有叶节点的带权路径长度之和

哈夫曼编码：左边标0，右边标1

二叉排序树：左<中<右

图的概念和存储结构

G=<V,E>顶点，边集

无向图

有向图：每条胡都是有序对，<V1,V3>从顶点v1指向顶点v3，v1弧尾，v3弧头

简单图：既不含平行边也不含环的图

完全图：任意两个点都有一条边；若任意两个点都有两条方向相反的弧，则该图为有向完全图

顶点的度：指与该顶点相关联的边的数目

握手定理：度数之和等于边数的两倍

子图：1=<V1,E1>，V1包含于V，E1包含于E

生成子图：从图中选择所有顶点，若干条边构成的图

邻接矩阵：表示顶点之间关系。先要用一个一维数组把所有顶点保存下来。如果vi到vj有边，则邻接矩阵M[i] [j]=M[j] [i]=1，否则为0。so，无向图的邻接矩阵应该是对称的。有向图中，第i行元素之和就是顶点i的出度，第i列元素之和就是顶点i的入度（散度）

邻接表：链式存储方式

邻接表和邻接矩阵的区别和优缺点

图的遍历和应用

BFS:先被访问的顶点，其邻接点先被访问

DFS：无法行进时，回退到刚刚访问的节点。后被访问的节点，其邻接点先被访问

Dijkstra最短路径

最小生成树——prim：需要n-1条边保证图连通不含回路，且要权值最小

最小生成树——kruskal：按权值从小到大排序连接，其中不能生成回路

拓扑排序：先选一个入度为零的节点，开始排序，删除，在删除后再找入度为零的，排序，删除……

AOE网：弧上的权值表示活动持续的时间，从源点到汇点的带权路径长度最大的路径称为关键路径，关键路径上的活动称为关键活动

查找

• 顺序查找

int sqsearch(int r[],int n,int x){
for(int i=0;i<=n;i++){
    if(r[i]==x){
    return i;
    }else{return -1;}
}
}

• 二分/折半查找

非递归算法

int BinarySearch(int s[],int n,int x){
int low=0,high=n-1;
while(low<=high){
int middle=(high+low)/2;
if(x==s[middle]) return middle;
else if(x>s[middle]) low=middle+1;
else high=middle1;
}
return 0;
}

递归算法

int recursion(int s[],int x,int low,high){
if(low>high) return -1;
int middle=(low+high)/2;
if(x=s[middle]) return middle;
else if(x<s[middle]) return recursion(s,x,low,middle-1);
else return recursion(s,c,middle+1,high);
}

• 二叉查找树

前提：线性表必须是有序的

BsTree searchBST(BsTree T,ElemType key){
if((!T)||key=T->data) return T;
else if(key<T->data ) return searchBST(T->lchild,key);
else return searchBST(T->rchild,key);
}

二叉查找树的插入：小的放左边，大的放右边

二叉查找树的删除

• 平衡二叉树（AVL树）：1.左右子树高度差（平衡因子）的绝对值不超过1，2.左右子树也是平衡二叉树

插入操作，调整平衡四种（结合图）

1.LL型：最近不平衡节点到新节点的路径前两个都是左子树L。LL旋转

2.RR型

3.LR型：两次旋转。从下往上第一个不平衡节点逆时针旋转，调整成LL型，第二个节点LL旋转

4.RR型：先顺时针后RR旋转

创建操作：按序调整，再调整平衡

哈希表

哈希函数：散列函数，将关键字一ing射到存储地址的函数，hash(key)=Addr

设计散列函数原则:1.尽可能简单，能快速找到 2.均匀分布整个地址，避免聚集，减少冲突

设计哈希函数

1.直接定址法 hash(key)=a*key+b

2.除留余数法 hash(key)=key%p

处理冲突：1.开放地址法：再线性存储空间上探测其他地址（通常往后移）2.链地址法

排序

有序性

稳定性：关键字相同时（比如出现两个2），在排序前后，这两个关键字相对位置在排序后是否发生变化

内部排序：

• 插入排序

1.直接插入，把第一个元素看作有序序列，将之后的元素插入已经排好序的序列中，保持有序性

例：非递减排序

时间复杂度

最好：O(n)

最坏：O(n^2)

void straightInsert(int r[],int n){
int i,j;
for(int i=2;i<=n;i++){
if(r[i]<r[i-1]){r[o]=r[i];//放到第一个位置
r[i]=r[i-1]；//往后移动一位
for(j=i-2;;j--) {if(r[j]>r[0]) {r[j+1]=r[j];}
else{r[j+1]=r[0];}}
}
}

2.希尔排序（缩小增量排序）

不稳定

将待排序记录按下标一定增量分组，对每组记录使用直接插入排序

• 交换排序：比较，不满足次序要求是交换位置

冒泡排序：两两比较，逆序则交换位置

稳定

void Bubblesort(int r[],int n){
    int i=n-1,temp;
    bool flag=true;
    while(i>=&&flag){
    flag= false;
    for(int j=0;j<i;i++){
    if(r[j]>r[j+1]){
    flag=true;
    temp=r[j];
    r[j]=r[j+1];
    r[j+1]=temp;
    }i--;
    }
    }
}

快速排序：目前最快的排序算法

int partition(int r[],int low,int high){
    int i=low.j=high,point=r[low];
    while(i<j){
    while(r[j]>point){
    j--;
    }
    if(i<j) swap(r[i++],r[j]);
    while(r[i]<point) i++;
    if(i<j) swap(r[i],r[j--];)
    }
    return i;
}

• 选择排序

简单选择排序：每次选一个最小的放在最前面

void simpleselect(int r[],int n){
     int i,j,temp;
     for(i=0;i<n-1;i++){
     k=i;
     for(j=i+1;j<n;j++){
     if(r[j]<r[k]){ k=j;//记录最小节点}
     if(k!=i){temp=r[i];//交换
     r[i]=r[k];
     r[k]=temp;}
     }
     }
}

• 堆排序

最大堆：如果每个节点大于等于左右子树

最小堆：如果每个节点小于等于左右子树

步骤：1.构建初始堆 2.堆顶和最后一个记录r[n]交换，把r[1,….,n]调整为堆 3.堆顶和最后一个交换，即r[n-1]，将r[1,…..,n-2]重新调整为堆 4.循环n-1次，得到一个有序序列

/*k是当前节点，j是左子树*/
void smk(int k,int n){
while(x*k<=n){//最后一层不用比较
    int j=2*k;
    if(j<n) j++；
    if(r[k]>r[j]) break;
    else swap(r[k],r[j])；k=j;//下一个节点是左子树
}
}

• 归并排序

桶排序

将待排序序列划分为若干个区间，每个区间可形象的看作一个桶，如果桶中的记录多余一个则使用较快的排序方法（可以选择），最后合并

注意：桶排序划分应该按照数据分布

基数排序

求出最大关键字的位数d，从低位开始，按个位分配，桶内排序，合并，按十位分配，桶内排序，合并…….直到最高位

分配

外部排序：数据很大，内存不能一次容纳全部的排序记录，需要访问外存。排序前后数据在外存，排序时将数据调入内存

• 如何判断一个算法的优劣性？

时间，空间

特点：有穷性，确定性，可行性，输入，输出

影响时间复杂性的因素：问题规模，输入序列，算法本身

渐进上界O：T(n)=O(f(n))

渐进下界Ω：T(n)=Ω(f(n))

渐进精确界记号Θ：c1f(n)<=T(n)<=c2f(n),T(n)=Θf(n)

分治算法

将一个规模为n的问题分解成k个规模较小的子问题

分解，递归，合并

• 主方法：T(n)=aT(n/b)+f(n) 时间复杂度：O(n^logb(a))

• 大整数乘法

给定两个都是2^k的大整数A，B，求A与B的乘积

推广：用分治法求两个十进制都是n位的A与B的乘积

优化前：T(n)=4*T(n/2)+O(n) O(n^2)

优化后：T(n)=3*T(n/2)+O(N) O(n^log2(3))

• Stassen矩阵乘法

给定矩阵A和B，均为n阶矩阵，n=2^k，求A*B

已知矩阵A和B，均为4阶矩阵，求A*B

划分矩阵:进行8次乘法，8个子问题

分解：将n阶矩阵，分成n/2矩阵

合并：赋值

优化前：T(n)=8T(n/2)+O(n^2) 时间复杂度：O（n^3）

优化后：T(n)=7T(n/2)+O(n^2)

• 二分法

log(n)

代码思路：1.中间值2.查找失败条件，low>high，返回0 3.查找成功key = 元素，返回mid+1 4.不然key<当前关键字，递归函数到low至mid-1中查找k 5.key>当前元素，递归函数到mid+1到high中查找

• 归并排序

T(n)=2T(n/2)+O(n)

时间复杂度：O(nlog(n))

分解：分为两个大小尽量相同的子序列（前提保证这两个子序列有序）

递归：用归并排序法对两个子序列递归地排序

合并：将排好序地有序子序列合并

代码思路：创建临时序列，双指针，依次比较前后子序列中关键字，将较小值依次复制到临时序列中，比较循环阶数后将前后子序列中剩余关键字（如果有剩余说明两个子序列长度不同）依次复制到临时序列中，再将临时序列是复制到原序列中，并释放原序列

//伪代码
int i=low,j=mid+1,k=0;//k是临时序列指针
while(i<=mid&&j<=high)//归并循环
if(R[i].key<=R[j].key){
   R1[k]=R[i];
   i++;
   j++
}else{
   R1[k]=R[j];
   i++;
   k++;
}
while(i<=mid){//复制剩余
    R1[k]=R[i];
    i++;
    k++;
}
while(j<=high){
    R1[k]=R1[j];
    j++;
    k++;
}
for(k=0,i=low;i<=high;k++,i++){//重置i
    R[i]=R1[k];
    }

• 快速排序

最好时间复杂度O(nlog(n))

最坏时间复杂度O(n^2)

平均时间复杂度O(nlog(n))

开始时将序列首元素定位基准，通过快速排序将表一分为二，关键字小于基准值放左边，大于基准值放右边(双指针)

最好的情况：每次循环基准值最终都能落在队中间的位置

代码思路：先用j从后往前找小于基准值的元素，将该元素前置，再用i从前往后找大于基准值的元素，将该元素后置，重复上述循环直到i=j位置，每次循环线移动j再移动i

int i=s,j=t,RecType tmp=R[i];//i从队首向后遍历，j从队尾向前遍历，将首元素设置位基准值
while(i<j){
    while(i<j&&R[j].key>=tmp.key) j--;
    R[i]=R[j];
    while(i<j&&R[i].key<=tmp.key) i++;
    R[j]=R[i];
}
R[i]=tmp;//i=j,循环结束，重置基准值的位置
return i;

• 循环赛日程表

分解前：1个n阶表格，分解后，4个n/2阶表格

T(n)=2T(n/2)+f(n)

int GameTable(int n,int k){
    if(n==2){
        a[k][0]=k+1;
        a[k][1]=k+2;
        a[k+1][0]=k+2;
        a[k+1][1]=k+1;
    }
}

动态规划

求解以时间划分阶段地动态规划的优化问题，经分解得到各个子问题不是相互独立的

三要素：最优子结构性质（有总体最优才有局部最优），子问题重叠性质，自底向上的求解方式

矩阵连乘

静态：穷举法/动态规划

A1A2矩阵相乘次数=A1行数*A1列数 *A2行数

1个矩阵连乘0种划分方式

2个矩阵连乘1种划分方式

3个矩阵连乘2种划分方式

最优质递归关系是:m[i] [j]=min{m[i] [k]+m[k+1] [j]+p(i-1)pkpj},i<j

自底向上求解

1.写出连乘矩阵

2.按顺序切割矩阵

3.算左右最少次数，合并最少次数，一共最少刺少

4.选择最少连乘次数

MatrixChain

/*一维数组p记录了矩阵的行列，n是总问题规模，二维数组m记录子问题的最少连乘次数，二维数组s激素子问题的最佳分割位置*/
void MatrixChain(int *p,int n,int **m,int *S){
    for(int i=1;i<=n;i++){
    m[i][j]=0;
    for(int r=2;r<=n;r++){
    for(int i=1;i<=n-r+1;i++){
    int j=i+r-1;
    m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
    s[i][j]=i;
    for(int k=i+1;k<j;k++){
    int t =m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
    if(t<m[i][j]){
    m[i][j]=t;
    s[i][j]=k;
    }
    }
    }
    }
    }
}

最长公共子序列

假设序列A长度为m，序列B长度为n，则时间消耗为O(mn)

定理：LCS最优子结构性质

两个序列的最长个公共子序列包含了这两个序列的前缀的最长公共子序列，因此具有最优子结构性质

递归方程

c[i] [j]={0 ,当i=0或j=0时；

c[i-1] [j-1]+1，当xi=yi时；

max(c[i] [j-1],c[i-1] [j],当xi!=yi时；)

}

分解子问题（填表）

自底向上计算LCS长度

void LCSlength(int m,int n,char *x,char *y,int **c,Type **b){
    int i,j;
    for(i=0;i<=m;i++) c[i][0]=0;
    for(j=0;j<=n;j++) c[0][j]=0;//第一行，第一列都填0
    for(i=0，i<=m;i++)
        for(j=1;j<=n;j++){
            if(x[i]=y[j]){
                c[i][j]=c[i-1][j-1]+1;
                b[i][j]="左上";
            }
            else if(c[i-1][j]>=c[i][j-1]){
                c[i][j]=c[i-1][j];
                b[i][j]="上";
            }else{
                c[i][j]=c[i][j-1];
                b[i][j]="左";
            }
        }
}

构造最长公共子序列

void LCS(int i,int j,char* x,Type **b){
    if((i==0)||(j==0)) return ;
    if(b[i][j]=="左上"){
        LCS(i-1,j-1,x,b);
        cout<<x[i];
    }else if(b[i][j]="上") LCS(i-1,j,x,b);
    else LCS(i,j-1,x,b);
}

贪心算法

初始解->当前最优->不能前进，终止

特点：不允许回溯，逐步，不稳定（有时无法求得最优解）

步骤：分解，局部最优，合并，证明

以局部最优解达到全局最优解

背包问题

描述：…….物品可以分割

按价值/重量最大的先装，降序排序

物品完全装入背包条件：背包剩余重量>某个物品重量

当甚于物品都无法完全装入背包时，考虑堆价值/重量较大的物品进行分割，尽量装满背包为止

• 时间复杂度

对物品放入背包操作，时间消耗O(n)

对价值/重量降序排序，默认使用堆排序，O(nlogn)

总时间消耗O(nlogn)

//假设已将各种物品依其单位重量的价值vi/wi从大到小排序了
void Knapsack(int n,float v[],float w[],float x[],float &value){
    float value =0;
    for(int i=1;i<=n;i++) x[i]=0;
    for(int i1;i<=n&&w[i]<=c;i++){
        x[i]==1;
        c-=w[i];//减少背包能装下的余下重量
        value+=v[i];//累计总价值
    }
    if(i<=n){
         x[i]=c/w[i];//将剩下的一部分装入
         value+=x[i]*v[i];
    }
}

会场安排问题

同一时间只能有一个活动使用资源，要求尽可能选择更多的活动来使用资源

用什么标准去安排？

• 开始时间最早

• 持续时间最短

• 结束时间最早

步骤

分解：按结束时间升序排序

解决：活动被安排，安排条件：下一个活动的开始时间晚于或等于前一个活动结束时间

时间复杂度：选择活动O(n)，对活动结束升序，堆排序，O(nlogn)

void GreedySelector(int n,Type s[],Type f[],bool A[]){
    A[1]=true;//活动1
    int j=1;//记录最近一次加入A[]的活动
    for(int i=2;i<=n;i++){
        if(s[i]>=f[j]){//找到一个相容活动，开始时间大于上一个结束时间
        A[i]=true;
        j=i;
        }else{A[i]=false;}
    }
}

最终结果A[]中true记录要加入的活动

最优装载问题

将尽可能多的集装箱装上轮船

分解：重量由小到大排序

解决：选择称重量较轻的装载。装载条件：轮船甚于重量>其中一个集装箱重量

合并：将选择装入轮船集装箱的号码列出

//假设集装箱已经按重量递增的次序排序
void Loading(int x[],Type w[],Type c,int n){
    for(int i=1;i<=n;i++){
        x[i]=0;//初始化为0
    for(int i=1;i<=n&&w[i]<=c;i++){
        x[i]=1;
        c-=w[i];
    }
    }
}

哈夫曼编码

构造哈夫曼树

• 为什么会出现重码现象？

编码位数不确定。通过以哈夫曼树为基础的哈夫曼编码完成需求，左树为0，右树为1.

时间复杂度：对字符出现频率排序，默认使用堆排序，O(nlogn)，构建哈夫曼树，O(n^2)，遍历字符集，注意给每个字符复制编码，时间O(n)。总时间消耗(n^2)

生成最小生成树——Prim算法

每次循环选择一个合适的顶点

时间复杂度O(n^2)，只与顶点数n有关

有n个顶点的图的生成树有n-1条边

最小生成树：权值之和最小的生成树

U生成树集合，V-U未生成树集合

在U和V-U中顶点的边选权值最小的边，将顶点加入U，直到V-U为空

生成最小树——Kruskal算法

每次循环选择一条适合的边

时间复杂度O(eloge) 只与边数e有关

有条件加入边，按从小到大的顺序选取，形成回路则舍弃，直到n-1条边

单源最短路径

Dijkstra算法：从一个顶点到其余各顶点的最短路径

如何存放最短路径长度：dist存储

如何存放最短路径长度：path存储

path[j]=w，表示从源点到j的最短路径中，j的前一个顶点式w

回溯法

通用的解题法：可以求出问题的所有解

深度优先策略

约束条件（constraint）：决定是否可以接受当前的部分解。

限界条件（bound）：用于剪枝，避免搜索不可能产生解的路径。

• 子集树

当所给的问题是从n个元素的集合S中找出满足某种性质的子集时

void Backtrack(int t){
if(t>n) Output(x);//已搜索至树叶
else for(int i=0;i<=1;i++){
x[t]=i;
if(Constraint(t)&&Bound(t)) Backtrack(t+1);
}
}

• 排列数

当所给的问题时确定n个元素的满足某种性质的排列时，相应的解空间树称为排列树

void BackTrack(int t){
if (t>n) Output(x);
else for(int i=t;t<=n;i++){
swap(x[t],x[i]);
if(Constraint(t)&&Bound(t)) Backtrack(t+1);
swap(x[t],x[i]);
}
}

n后问题

任何皇后不在同行同列同斜线上

约束条件：

x[i]!=x[k]（不在同一列）

|i-k|!=|x[i]-x[k]|(斜率不为1)

int n,x[N+1],sum=0;
bool Place(int k){
    for(int j=1;j<k;j++){
        if(abs(k-j)==abs(x[k]-x[j])||x[j]==x[k]) return False;
        else return True
    }
}
void Backtrack(int t){
if(t>n){//已经搜索到一叶节点，得到一个互不攻击的放置方案
sum++;
for(int i=1;i<=n;i++) cout<<x[i]<<" "
cout<<endl;
}
else
for(int i=1;i<=n;i++){
x[t]=i;
if(place(t)) Backtrack(t+1);
}
}

时间复杂度

共有结点

$$ \sum_{0}^{n-1} n^i $$

检查当前扩展结点每一个儿子是否可以放置该列O(n^2)

相乘，总时间耗费O(n^(n+1))

m图着色问题

若一个图最少需要m中颜色才能使途中任何一条边连接的2个顶点有不同颜色，则称这个数m为该图的色数。求一个图色数m的问题称为图的m可着色优化问题

用邻接矩阵表示无向连通图G=(V,E)，x[i]表示顶点i所着颜色，共有m种颜色，完全m叉树

void BackTrace(int t){
    if(t>n){
    sum++;
    for(int i=1;i<=n;i++) cout<<x[i]<<" ";
    cout<<endl;
    }else{
    for(int i=1;i<=m;i++){
        x[t]=i;
        if(ok(t)) Backtrace(t+1);
    }
    }
}
bool ok(int k){
for(int j=1;j<k;j++){
if(a[k][j]==1&&(x[j]=x[k]))//1代表相邻，0表示不相邻，相邻且颜色相同
{return Flase;}else{
return True;
}
}
}

分支限界法

找出T种使得某一目标函数达到极小或极大的解

分支限界法与回溯法的不同：

1.回溯法一广度优先的方式搜索解空间树T；分支限界法以广度优先或最小耗费优先的方式搜素空间树T

2.回溯法一般只通过约束条件，分支限界法不仅通过约束条件，还通过目标函数的限界减少无效搜索（在每一活结点处，计算一个函数值）