提纲形式：
图
邻接矩阵(key)
邻接矩阵的存储表示
#define MaxInt 32767
#define MVNumn 100
typedef char
typedef int ArcType;
typedef struct
{
char vexs[MVNum];
int arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
浪费存储空间
无向图的邻接矩阵表示
int CreateUDN(AMGraph &G)
{
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;i++)
cin>>G.vexs[i];
for(i=0;i<G.vexnum;i++)
for(j=0;j<vexnum;j++)
arcs[i][j]=MaxInt;
for(k=0;k<vexnum;k++)
{
cin>>v1>>v2>>w;
i=LocateVex(G,v1);
j=LocateVex(G.v2);
G.arcs[i][j]=w;
G.arcs[j][i]=G.arcs[i][j];
}
retutn 1;
}
主对角线对称
顶点i的度等于第i行/列中1的个数
有向图的邻接矩阵表示
int CreateUDN(AMGraph &G)
{
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;i++)
cin>>G.vexs[i];
for(i=0;i<G.vexnum;i++)
for(j=0;j<vexnum;j++)
arcs[i][j]=MaxInt;
for(k=0;k<vexnum;k++)
{
cin>>v1>>v2>>w;
i=LocateVex(G,v1);
j=LocateVex(G.v2);
G.arcs[i][j]=w;
//G.arcs[j][i]=G.arcs[i][j];只需要删去此语句即可变为有向
}
retutn 1;
}
不对称
行：出度
列：入度
度：行+列
邻接表(key)
图的邻接表存储表示
#define MVNum 100
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
OtherInfo info;
}ArcNode;
typedef struct VNode
{
VerTexType data;
ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct {
AdjList vertices;
int vernum,arcnum;
}ALGraph;
表头结点表
数据域（顶点名称）
链域
边表
邻接点域（顶点位置）
数据域（权值）
链域
无向图的邻接表表示
int CreateUDG(ALGraph &G)
{
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;i++)
{
cin>>G.veetices[i].data;
G.vertices[i].firstarc=NULL;
}
for(k=0;k<arcnum;k++)
{
cin>>v1>>v2;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p1=new ArcNode;
p1->adjvex=j;
p1->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p1;
p2=new ArcNode;
p2->adjvex=i;
p2->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p2;
}
return 1;
}
有向图的邻接表表示？
邻接表与逆邻接表
邻：由顶点指出
逆：指向该结点的点
图的遍历
辅助数组 Visited[N]
搜索(key)
深度优先 DFS
遍历连通图？
遍历非联通图
void DFSTraverse(Graph G)
{
for(v=0;v<G.vexnum;v++)
visited[v]=false;
for(v=0;v<G.vexnum;v++)
if(!visited[v]) DFS(G,v);
}
邻接矩阵表示的深度优先搜索（key）
void DFS_AM(AMGraph G,int v)
{
cout<<v;
visted[v]=true;
for(w=0;w<G.vexnum;w++)
{
if(G.arcs[v][w]!=0 && (!visited[w]))
DFS_AM(G,w);
}
}
邻接表表示的深度优先搜索？
一条路走到头，再回退
广度优先 BFS
算法实现（key）
void BFS(Graph G,int v)
{
cout<<v;
visited[v]=true;
InitQueue(Q);
EnQueue(Q,v);
while(!QueueEmpty(Q))
{
DeQueue(Q,v);
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
{
if(!visited[w])
{
cout<<w;
visited[w]=true;
EnQueue(Q,w);
}
}
}
}
一层一层
权重优先
图的应用(要求会做题)
生成树
由邻接矩阵画DFS生成树
类似于先序遍历
一条路走到头，后面有1不管，到头再回退
由邻接矩阵画BFS生成树
类似于层次遍历
一层一层
求最小生成树
普里姆Prim归并点，稠密
对起点u0，初始化closedge[]
选择其余n-1个顶点，生成n-1条边
克鲁斯卡尔Kruskal归并边，稀疏
图的最小生成树不唯一，存储结构一定才唯一
求最短路径
迪杰斯特拉Dijkstra（key）
单源最短路径
按路径长度递增次序求解
步骤
初始化
寻找v0到v1.. vk的直达路径
选择
找出一条长度最短的路径
更新
矢量三角形化简，基于已经求得的点，用两条短的边替代长的边
实现
S[]顶点在S集合就是Ture，不在False
D[]源点到顶点路径长度
path[]记录前驱,否则为-1
O(n^2)
弗洛伊德Floyd
任意两点最短路径
拓扑排序
树
二叉树的性质
每层有2的i-1次方个结点
至多有2的k次方-1个结点
n0=n2+1
完全二叉树
n个结点，深度为[log2(n)]+1
[x]表示不大于x的最大整数
对于一个结点i
LC左孩子 2i
RC右孩子 2i+1
PA父亲结点 [i/2]
二叉树的存储结构
顺序存储
typedef MAXSIZE 100
typedef TElemType SqBiTree[MAXSIZE];
SqBiTree bt;
完全二叉树按顺序存储
一般二叉树空位补0
链式存储
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
遍历二叉树
先序遍历
中序遍历
后序遍历
遍历的递归算法
void Traverse(BiTree T)
{
if(T)
{
Traverse(T->lchild);
cout<<T->data;//中序遍历
Traverse(T->rchild);
}
}
遍历的非递归算法
void Traverse(BiTree T)
{
InitStack(S);
p=T;
q=new BiTNode;
while(p||!StackEmpty(S))
{
if(p)
{
Push(S,p);
p=p->lchild;
}
else
{
Pop(S,q);
cout<<q->data;
p=q->rchild;
}
}
}
先序遍历建立二叉链表
void CreateBiTree(BiTree &T)
{
cin>>ch;
if(ch=='#')T=NULL;
else
{
T=new BiTNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
区别
cout的时机不同
线索化二叉树
二叉线索存储表示
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;
以结点p为根的子树中序线索化
带头节点的二叉树中序线索化
遍历中序线索二叉树
哈夫曼树
基本概念
路径
权
带权路径长度 WPL
哈夫曼树的存储表示
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
构造哈夫曼树（算法 课本P138）
使权大的结点靠近根
选取权最小的两个结点/子树，形成一颗二叉树
栈和队列
表达式求值
链表
串，数组，广义表
BF O(m*n）
KMP O(m+n)
线性表
初始化
new
length=0
取值
查找
插入
数据运算
插入
删除
修改
查找
排序
排序
ASL==ACN(平均比较次数)
衡量好坏
时间
比较次数
移动次数
简单排序 先进排序
空间
稳定性
外部排序 内部排序
插入排序
直接插入
void InsertSort(SqList ＆L)
{int i,j;
for(i=2;i<=L.length;++i)
if( L.r[i].key<L.r[i-1].key)//将L.r[i]插入有序子表
{ L.r[0]=L.r[i]; // 复制为哨兵
L.r[i]=L.r[i-1];
for(j=i-2; L.r[0].key<L.r[j].key;--j)
L.r[j+1]=L.r[j]; // 记录后移
L.r[j+1]=L.r[0]; //插入到正确位置
}
}
•平均情况比较次数和移动次数为n2/4
•时间复杂度为 o(n2)
•空间复杂度为 o(1)
•是一种稳定的排序方法
最简单
n个数做n-1趟
最好情况
数据基本有序，待排序序列小，效率比较高
最坏情况
折半插入
•在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少
void BInsertSort ( SqList &L )
{ for ( i = 2; i <= L.length ; ++i )
{ L.r[0] = L.r[i]; low = 1 ; high = i-1 ;
while ( low <= high )
{ m = ( low + high ) / 2 ;
if ( L.r[0].key < L.r[m]. key ) high = m -1 ;
else low = m + 1;
}
for ( j=i-1; j>=high+1; - - j ) L.r[j+1] = L.r[j];
L.r[high+1] = L.r[0];
}
} // BInsertSort
•时间复杂度为 o(n2)
•空间复杂度为 o(1)
•是一种稳定的排序方法
无需折半，数据移动次数和直接插入排序一样，只是比较次数减少（key）
脑子里不用折半，但实际做的时候是折半的
希尔排序
如何选择最佳d序列，目前尚未解决
最后一个增量值必须为1，无除1以外的公因子
不宜在链式存储结构上实现
逐趟缩小增量
类似于分块查找，分割成多个子序列，然后子序列中直接插入排序，然后对整体再进行一次直接插入排序
交换排序
快速排序
先进排序
冒泡排序
简单排序
o(n2)
快速排序
•快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的low和high）。
•最大递归调用层次数与递归树的深度一致，因此，要求存储开销为 O(log2n) 。
平均计算时间最好，是O(nlog2n)
不稳定
步骤
取第一个元素存放在界点r[0]
小的放前，大的放后，形成左右两个子表
对子表重新选择中心元素并递归，直到每个子表的元素只剩一个
选择排序
避开稳定性
可稳定可不稳定
堆排序
时间效率：O(nlog2n)
n趟，每趟log2n
空间效率：O（1）
稳 定 性：不稳定
适用于n 较大的情况（先进排序）
堆的定义
用树的形式描述堆
满足一个这样的条件的完全二叉树：ki<=(或>=)k2i/k2i+1
大根堆
根结点大于左右孩子，左右孩子没有区别
小根堆
如果将序列看成一个完全二叉树，非终端结点的值均小于或大于左右子结点的值
堆是完全二叉树的顺序存储结构
完全二叉树中最后一个子树的根结点的标号就是n/2取下界
筛选法调整堆 算法8.7
调整
建堆就是不断地调整
建初堆
从最后一颗子树，反复调用筛选法
过程一定要掌握（不要求代码）
归并排序
两两合并
基数排序（不考）
不需要关键字之间的比较
多关键字排序
高位优先法
最低位优先法
不需要分组
链式基数排序
知道主次关系
知道取值范围
查找
查找效率
ASL
求和：pi*ci
顺序查找
改进
哨兵
查找概率大放前面
ASL=1/2(n+1)
O（n)
折半查找
•设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值
•初始时，令low=1,high=n,mid=ë(low+high)/2û
•让k与mid指向的记录比较
–若k==R[mid].key，查找成功
–若k<R[mid].key，则high=mid-1
–若k>R[mid].key，则low=mid+1
重复上述操作，直至low>high时，查找失败
不宜用于链式结构
非递归算法
int Search_Bin(SSTable ST,KeyType key){
//若找到，则函数值为该元素在表中的位置，否则为0
low=1;high=ST.length; while(low<=high){
mid=(low+high)/2;
if(key==ST.R[mid].key) return mid;
else if(key<ST.R[mid].key) high=mid-1;//前一子表查找
else low=mid+1; //后一子表查找
} return 0; //表中不存在待查元素
}
递归算法
int Search_Bin (SSTable ST, keyType key, int low, int high)
{
if(low>high) return 0; //查找不到时返回0
mid=(low+high)/2;
if(key==ST.elem[mid].key) return mid;
else if(key>ST.elem[mid].key) return Search_Bin(ST.key,mid+1,high);
else if(key<ST.elem[mid].key) return Search_Bin(ST.key,low,mid-1);
}
不超过判定树的深度 d = [log2 n]+ 1
O(log2[n])
ASL:（求和:比较次数*个数）/总数
不宜用于链式结构
折半查找判定树（不会）
关键：mid+1或mid-1
ASL不乱用公式
分块查找
折半+顺序
性能介于两者之间
块之间有序，块内无序
插入删除比较容易，无需进行大量移动
只需要移动索性表的数据
树表的查找
动态查找表
表结构在查找中动态生成，如果已存在，就返回值，不存在就插入
B-,B+树不考
二叉排序树（key）
平均查找长度和二叉树的形态有关，即，
最好：log2n（形态匀称，与二分查找的判定树相似）
最坏: （n+1)/2（单支树）
左子树所有小于根，右子树所有大于根
求二叉排序树的中序遍历
直接投影法
常考，非常常用
插入
先查找，直至叶子结点为空
二叉排序树插入的元素一定在叶子结点上
元素要么比根小，要么比根大
不同插入次序的元素形成不同的二叉排序树
影响查找的性能
算ASL
假设概率相等，比较一次有几个，两次有几个...
平均查找长度和二叉树的形态有关，即，
最好：log2n（形态匀称，与二分查找的判定树相似）
最坏: （n+1)/2（单支树）
删除（知道过程就ok，代码不要求）
缺右子树用左子女替代
缺左子树用右子女替代
在右子树中序遍历第一个结点替代
左子树中序遍历最后一个结点
平衡二叉树
形状均衡
左右子树深度之差的绝对值小于等于1
左右子树都是平衡二叉树
平衡因子:该结点左子树与右子树的高度差
任一结点的平衡因子只能取：-1、0 或 1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；
需要不断调整
旋转
LL
RR
LR
RL
保证是一颗二叉排序树即可
红黑树
二叉排序树的变种
要求没有那么严格，使用更广泛
哈希表的查找
记录存储位置与关键字之间的关系
根据数据的特征进行查找
根据关键字的特征构造一个哈希函数
理想状态O（1)
冲突
不同的关键码映射到同一个哈希地址
同义词
具有相同函数值的两个关键字
MD5
不冲突
不可逆
密码学
数字签名
除留余数法
Hash(key)=key mod p
优于其他类型函数
如何选取合适的p
表长为m，取p≤m且为质数
必考
其余方法了解就好
处理冲突的方法
开放地址法
线性探测法
有冲突的时候就寻找下一个哈希地址，数组下标+1
Hi=(Hash[key]+di)mod m，mod m可以从最后一个单元转到开头
缺点：聚集，降低查找效率
一直往后查到空表，查找失败
二次探测法
伪随机探测法
链地址法
把哈希地址相同的做成一个单链表
优于开地址法
装填因子=记录数/长度，越大越容易冲突，ASL取决于装填因子
ASL既不是O（1）也不是O(n),与装填因子有关
考试
选择题都好好做一遍
一定会考一个链表的算法
理解算法
第二章链表非常重要
背都要背出来
ppt里凡是有算法都考代码
方法只考过程
链表一定画图
算法：先看文字描述，再数据验证，再看动画
不会写不要空着
根据算法步骤理解着背，不要死记硬背
53 1234 67
80 3.2
第三章一般不会考代码 考选择题 90%考递归
表达式求值要会这个表格
特殊矩阵不考
ppt没有的不考
表达式求值 应用题
二叉树递归
概念术语性质
写算法掌握到代码
去ftp下考纲