文章目录

• 自述
• 第一章绪论
• • 基本概念
  • 算法的时间空间复杂度：
• 线性表：
• • 线性表的顺序存储结构
  • • 顺序存储结构定义：
    • 1.初始化：
    • 2.插入：
  • 线性表的链式存储结构：
  • • 定义：
    • 1.初始化
    • 2.单链表的插入
  • 双向链表
  • 线性表的应用：
  • • • 1.线性表的合并（LB合并到LA中）：
    • 2.有序表的合并(LA,LB合并到LC)：
    • 3.一元多项式的表示及相加：
• 栈：
• • 顺序栈的存储结构定义：
  • • 1.初始化
    • 2.进栈
    • 3.出栈
  • 链栈：
  • • 存储结构定义：
  • 栈的应用：
  • • 1.数制转换：
    • 2.括号匹配检验：
    • 3.表达式求值：
  • 栈与递归：
• 队列：
• • 顺序队列
  • • 假溢出：
    • 2.入队
    • 3.出队
  • 队列的应用：
  • • 打印二项式系数表
• 数组：
• • 数组的定义：
  • 数组取地址：
  • 特殊矩阵的压缩：
  • • 对称矩阵：
    • 上三角矩阵存储：
    • 下三角矩阵：
  • 稀疏矩阵：
  • • 三元组表法：
    • 伪地址表示法：
  • 稀疏矩阵的转置：
  • • 1按三元组表的列转置：
    • 2快速转置:
    • 2.十字链表：
• 树：
• • 1.树的基本概念
  • 2二叉树
  • • 二叉树的存储结构：
    • 二叉树的遍历方法和实现：
  • 二叉树遍历的应用，究其本质使用了递归算法：
  • • 建立二叉链表：
    • 复制二叉树：
  • 树的存储结构：
  • 森林，树，二叉树的转换
  • • 树转化成二叉树：
    • 将二叉树还原成树就表示成：
    • 二叉树还原成森林：
    • 树的遍历：
    • 森林的遍历：
  • 哈夫曼树：
  • • 基本概念：
    • 哈夫曼树的构造：
    • 哈夫曼编码：
• 图：
• • 基本概念：
  • 图的存储结构：
  • • 1.邻接矩阵表示法又称数组表示法：
    • 邻接表表示法：
    • • 结构特点：
  • 图的遍历：
  • • 1深度优先遍历：
    • 广度优先遍历：
  • 最小生成树一些性质：
  • 最小生成树的构造方法：
  • • 1prim方法：
    • 克鲁斯卡尔算法：
  • 拓扑排序：
  • • 拓扑排序过程：
    • 拓扑排序算法实现：
  • 最短路径问题：
  • • 迪杰斯特拉算法：
    • 弗洛伊德算法：
• 查找：
• • 基本概念：
  • 静态查找表：
  • • 顺序查找：
    • 折半查找：
    • 折半查找的判定树：
    • 索引表查找：
  • 动态查找表：
  • • 二叉排序树:
    • 二叉排序树的删除：
  • 哈希表：
  • • 哈希函数的构造：
    • • 1数字分析法：
      • 2平方取中法：
      • 3折叠法：
      • 4除留余数法：
    • 哈希表的冲突：
    • • 1开放地址法：
      • • 线性探测法：
        • 二次探测法：
        • 伪随机法：
      • 2再哈希法
      • • 3链地址法：
• 排序：
• • 排序算法的评价标准：
  • • 插入排序：
    • • 直接插入排序；r[i]跟前面排好的i-1个元素进行比较后插入
      • 折半插入排序：
      • 希尔排序：
  • 交换排序：
  • • 冒泡排序：
    • 快速排序：
  • 选择排序
  • • 简单选择排序：
    • 堆排序：
    • • 筛选：
  • 2-路归并排序
  • 基数排序：

自述

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，
《数据结构》让读者认识到了各种数据结构在处理数据上的优缺点，
理解掌握相关数据结构的具体操作，在结构的基础上添加好的算法，就能够更好的处理和利用数据。

第一章绪论

基本概念

数据：所有能输入到计算机中并被计算机程序处理的符号的总称
数据元素：数据的基本单位，也称为元素，结点，记录等
数据项：组成数据元素的最小单位
数据对象：数据元素的集合
数据结构：相互之间存在一种或多种特定关系的数据元素的集合
逻辑结构：集合结构，线性结构，树结构，图结构
存储结构：顺序存储结构，链式存储结构
数据类型：一个值的集合和定义在这个值集上的一组操作的总称
抽象数据类型：一般指由用户定义的，表示应用问题的数学模型，
以及定义在这个模型上的一组操作的总称，具体包括数据对象，数据对象上关系的集合，以及对数据对象的基本操作的集合。
1
2
3
4
5
6
7
8
9
10

算法的时间空间复杂度：

算法特性：有穷性，确定性，可行性，输入，输出
评判标准：正确性，可读性，健壮性，高效性
时间空间复杂度
即评判算法是否高效。
语句的频度：一个语句的重复执行次数
算法的执行时间T(n)：所有语句频度的和
算法的时间复杂度：$当lim_{x
ightarrow infty}T(n)/n^k=c(c为常数)$有T(n)的数量级T(n)=O(n^k)称为 算法的渐进时间复杂度，$简称时间复杂度。n^k一般由最深层次循环内的语句频度确定$
算法时间复杂度就是求最内层循环的语句频度，往往可以从内向外求。
时间复杂度数量级递增排列：$常数阶O(1),对数阶O(log_{2}n),线性阶O(n),线性对数阶O(nlog_{2}n)及以上的k次方阶$算法的空间复杂度：所用的辅助存储空间对问题规模n的数量级
1
2
3
4
5
6
7
8
9
10

线性表：

线性表的顺序存储结构

用一组连续的存储单元依次存储线性表的数据元素。
特点：线性表的顺序存储是一种随机存取的存储结构。
随机存取：即读写存储的消息的时间与存储的位置无关

顺序存储结构定义：

#define MAXSIZE 100
typedef struct{
	ElemType *elem;//存储空间的基地址
	int MAXSIZE//容量
	int length;//当前长度
	}SqList
1
2
3
4
5
6

相关操作：

1.初始化：

Status InitList_Sq(SqList &L){
//构造一个空顺序表L
L.elem=(int*)malloc(MAXSIZE*sizeof(int));//分配int类型指针数组空间,成功返回首地址，失败返回NULL
if(!L.elem)  exit(-1）//exit除0外的其它值为异常退出
L.length=0;
return Ok;//#define OK 1
1
2
3
4
5
6

2.插入：

Status ListInsert_Sq(SqList &L,int i，ElemType e)
//在顺序表第i个元素前插入e
//通过插入函数建立顺序表
if(i<1||i>L.length+1) return ERROR;
if(L.length==MAXSIZE) return ERROR;
for(j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j];//i之后元素后移
L.elem(i-1)=e;//插入e
++L.length;
return Ok;
}
1
2
3
4
5
6
7
8
9
10
11

3.查找
4.删除

线性表的链式存储结构：

定义：

//链表就是定义结
//单链表结点的定义
typedef struct Lnode{
Elem data;
struct Lnode *next;//双向链表需要再加上前指针
}LNode,*LinkListt
1
2
3
4
5
6

1.初始化

Status InitList_L(LinkList &L){
//构造一个空的单链表
//使用头结点有益于单链表的操作，插入时头结点不移动
L=(LinkList) malloc(sizeof(LNode));//生成头结点
L->next=Null;//头结点置空
return OK;
}
1
2
3
4
5
6
7

2.单链表的插入

Status ListInsert_L(LinkList &L,int i,ElemTyoe e){
//在带头结点的单链表L的第i个位置之前插入元素e
//以此创造单链表，前插法即是插入到第一个元素前，后插法即增加尾指针插入链表尾部
p=L;j=0;
while(p&&j<i-1){p=p->next;++j;}//寻找第i-1个结点
if(!p||j>i-1) return ERROR;
s=(LinkList) malloc(sizeof(LNode));//生成新的结点
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12

3.查找
4.删除

双向链表

插入：即在单链表插入的基础上增加对前指针的修改
循环链表：即将尾部结点的next从NULL改为指向头指针

线性表的应用：

1.线性表的合并（LB合并到LA中）：

将LB中元素逐个取出，在LA中进行逐个查访，不存在就插入。

2.有序表的合并(LA,LB合并到LC)：

对LA,LB中元素依次比大小后插入。
链式有序表的合并则在LA的基础上比较插入即可。

3.一元多项式的表示及相加：

多项式链表结点，有两个数据，系数和指数
多项式链表的创建：通过查找计较指数，找到插入位置进行插入
多项式相加：通过查找比较指数，若没有相同的则插入，若有相同的，则系数相加。

栈：

是限定仅在表位进行插入或删除操作的线性表如果需要按照保存数据相反的顺序来使用数据，则可以利用栈来实现。

顺序栈的存储结构定义：

typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SpStack;
1
2
3
4
5

1.初始化

Status InitStack(SqStack &S){
//构造一个空栈
S.base=(SElemType*) malloca(MAXSIZE*sizeof(SElemType));
if(!S.base) exit(-1);
S.top=S.base;
S.stacksize=MAXSIZE;//初始容量即设为满容量
return OK;
}
1
2
3
4
5
6
7
8

2.进栈

Status Push(SqStack &S,SElemType e){
if(S.top-S.base==S.stacksize) return ERROR;
*S.top++=e;
return OK;
}
1
2
3
4
5

3.出栈

Status Pop(SqStack &S,SElemType &e){
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}
1
2
3
4
5

4.取栈顶元素则不用top–

链栈：

存储结构定义：

typedef struct StackNode{
ElemType data;
struct StackNode *next;
}StackNode,*LinkStack;
1
2
3
4

1.初始化
栈顶指针置空；
2.入栈
生成新的结点替换至替换为栈顶结点；
3.出栈：类似

栈的应用：

1.数制转换：

void conversion(){
InitStack(S);
cin>>N;
while(N){
Push(S,N%8);//得到低位
N=N/8
}
while(!StackEmpty(S)){
//通过栈的后入先出得到从高位到低位输出
Pop(S,e);
cout<<e;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.括号匹配检验：

对（[)]四种括号进行分类：
（，[压入栈，），]则依据栈顶进行匹配。

3.表达式求值：

为运算符设置优先权即写入优先权比较函数。
#表达式#，#代表开始和结束
设置两个栈，一个储存运算符一个储存数字
操作：
1.开始的#压入运算符栈
2.每次从左至右提取一个字符，如果是数字，压入数字栈；如果是运算符和运算符栈顶元素比较，若大于，则压入栈；若小于，则将栈顶运算符取出，并取出数字栈顶两个元素进行运算；
3.当两个#碰到时，操作结束，

栈与递归：

采用递归解决的问题涉及到：
1.定义是递归的或2.数据结构是递归的或3.问题的解法是递归的
递归工作栈：调用函数类似于增加栈顶元素，而栈的元素就是保存调用函数信息的单元；
当被调用函数返回时，就是从栈顶不断向栈底出栈；
递归在算法应用中的个人理解：
1使用递归调用函数时默认该函数正确在第一层中能够完成任务。
2该函数有一个明确的调用出口，即最后一层，最小的单元中能够正确返回（只需要得到比它稍大的能够想到的那一层，那一单元能够正确返回就行）。
将递归转化成非递归：
1使用循环语句
2利用栈消除递归：直接设置栈模仿递归方式，栈顶储存调用函数信息模仿递归操作。

队列：

先进先出的受限制的线性表,插入的一端叫队尾，删除的一端叫对头。

顺序队列

#define MAXSIZE 100
typedef struct{
QElemType *base;
int front;
int rear;
}SqQueue;
1
2
3
4
5
6

插入：队尾指针加一，赋值。
删除：删除对头元素，指针加一；

假溢出：

队尾指针到末尾，有删除后的空间未利用。
解决方法：
使用循环队列：使用求余赋值的方式使尾指针和头指针能够访问前面的空间。

Q.rear=(Q.rear+1)%MAXSIZE;Q.front=(Q.front+1)%MAXSIZE;
队空判断：Q.rear==Q.front; 队满判断：Q.front==Q.rear+1
1
2

1.初始化，同上：分配内存，指针置零；并且定义存储头尾指针的空间Q；
链队：
存储结构定义：结点定义同上；
1.初始化：

Q.front=Q.rear=(*QNode) malloc(sizeof(LNode))//生成第一个结点头结点
if(!Q.front) exit(-1);
Q.front->next=NULL;
return OK;
1
2
3
4

2.入队

Status EnQueue (LinkQueue &Q,QElemType e){
//插入元素e为Q的新的对位元素,Q.front->next这个第一个结点是空的，是头结点
P=(*QNode) malloc(sizeof(LNode))//生成一个结点
if(!P) exit(-1);
P->date=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
1
2
3
4
5
6
7
8
9

3.出队

Status DeQueue(LinkQueue &Q,QElemType &e){
//删除Q的对头元素，用e返回其值，并返回OK
if(Q.front==Q.rear) return ERROR;
p=Q.front->next;//Q.front->next这个第一个结点是空的
e=p->date;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;//如果最后一个元素删除，队尾指针指向头结点
delete p;
return OK;
}
1
2
3
4
5
6
7
8
9
10

队列的应用：

打印二项式系数表

数组：

由类型相同的数据元素构成的有序集合，每个数据元素可以是某种结构但是相同的数据，是线性表的推广。
由于数组只有存取和修改元素的功能，初始化就确定了空间大小，一般只使用顺序存储，那么数组与顺序表就同样是随机存储的结构。

数组的定义：

typedef ElemType Array2[m][n];//直接定义二维数组
typedef ElemType Array1[n];//一维数组的定义
typedef Array1 Array2[m];//借组一维数组定义二维数组
1
2
3

数组取地址：

LOC(i,j)=LOC(0,0)+(n*i+j)L
1

n维的地址如下
L O C ( j 1 , j 2 , . . . , j n ) = L O C ( 0 , 0 , . . . , 0 ) + ( ∑ i = 1 n 1 j i k = i + 1 n b k + j n ) L LOC(j_1,j_2,…,j_n)=LOC(0,0,…,0)+(sum_{i=1}^{{n-1}j_icoprod_{k=i+1}}{n}b_k+j_n)L LOC(j1,j2,…,jn)=LOC(0,0,…,0)+(i=1∑n1jik=i+1nbk+jn)L

特殊矩阵的压缩：

对多个相同的值只分配一个空间，对零元不分配空间

对称矩阵：

以sa[n(n+1)/2]作为存储空间，sa[k]和矩阵元 a i j 有 着 如 下 一 一 对 应 关 系 k = { i ( i 1 ) 2 + j 1 if i ≥ j j ( j 1 ) 2 + i 1 if i ≤ j a_{ij}有着如下一一对应关系k=egin{cases} rac{i(i-1)}{2}+j-1 & ext{ if } igeq j \ rac{j(j-1)}{2}+i-1 & ext{ if } ileq j end{cases} aij有着如下一一对应关系k={2i(i1)+j12j(j1)+i1ifi≥jifi≤j

这就表示除了对角线上的矩阵元，其余两个矩阵元对应一个数组元素sa[k].

上三角矩阵存储：

k = { ( i 1 ) ( 2 n i + 2 ) 2 + ( j i ) if i ≤ j n ( n 1 ) 2 if i > j k=egin{cases} rac{(i-1)(2n-i+2)}{2}+(j-i) & ext{ if } ileq j \ rac{n(n-1)}{2} & ext{ if } i> j end{cases} k={2(i1)(2ni+2)+(ji)2n(n1)ifi≤jifi>j

下三角矩阵：

k = { i ( i 1 ) 2 + ( j 1 ) if i ≥ j n ( n 1 ) 2 if i < j k=egin{cases} rac{i(i-1)}{2}+(j-1) & ext{ if } igeq j\ rac{n(n-1)}{2} & ext{ if } i< j end{cases} k={2i(i1)+(j1)2n(n1)ifi≥jifi<j

出对角线上和直接在对角线上，下方若干对角线上的元之外，所有其他的元皆为0.对于只有三条斜线需要算的对角矩阵： L O C ( a i j ) = L O C ( a 11 ) + [ 2 ( i 1 ) + j 1 ] L ( ∣ i j ∣ ≤ 1 ) LOC(a_{ij})=LOC(a_{11})+[2(i-1)+j-1]*L (left | i-j ight |leq 1) LOC(aij)=LOC(a11)+[2(i1)+j1]L(∣ij∣≤1)

稀疏矩阵：

非零元较零元少且没有一定规律的矩阵；
稀疏因子: δ = t m + n delta = rac{t}{m+n} δ=m+ntt为非零元个数，m为矩阵行数，n为矩阵列数；
稀疏矩阵的顺序压缩存储：

三元组表法：

三元组数组元素结构定义：

typedef struct
{ int i, j; //非零元的行、列下标 非零元的行、列下标
ElemType e; //非零元的值 非零元的值
} Triple;
1
2
3
4

稀疏矩阵结构：

#define MAXSIZE 100 //非零元最大个数 非零元最大个数
typedef struct
{ Triple data[MAXSIZE + 1];
// 三元组表，data[0]未用 未用
int mu, nu, tu; //矩阵行、列数、非零元个数 矩阵行、列数、非零元个数，用于三元组第一个数据
} TSMatrix;
1
2
3
4
5
6

三元组表存取需要从头至尾查找不能随机存取；
带行链接的三元组表，创建一个数组rpos[maxline+1]来使三元组表元素的搜索操作事件减少。
rpos[i]=第i行开始计算的第一个非零元素指向三元组表中的下表//其中rpos[0]不存储或只存储行数。

伪地址表示法：

与三元组表表示类似，但将行列信息糅合成一个数值（伪地址x=m*i+j);

稀疏矩阵的转置：

1按三元组表的列转置：

1按矩阵T中三元组表T.data的顺序，依次在矩阵M的三元组
表M.data中找到相应三元组进行转置
2为找到M.data中第i列所有非零元素，需对M.data扫描一遍
3由于M.data以M行序为主序，所以得到的恰是T.data中应有
的顺序

2快速转置:

稀疏矩阵的链式压缩存储:
与顺序压缩存储的比较：顺序压缩存储在存储转置之类的运算下既节省空间速度也快，但是矩阵进行相加，矩阵元增加减少时，要移动大量元素，十分不利，因此采用链式存储的方式能够较好的解决此类问题；
1.带行指针的单链表表示：构造M.head单链表结点指针数组M.head[i-1]存储指向
第i行中第一个非零元素（不能计算到i+1行），第i行中后面的非零元素接在第一个结点之后。

typedef struct RLNode
{//结点信息包括列数j，元素数值e，下一个指针right
 int j;
ElemType e;
struct RLNode *right;
}RLNode,* RLink ;


//数组结构
typedef struct
{ RLink rhead[M];//指针数组
int mu, nu, tu;
}RowList;
1
2
3
4
5
6
7
8
9
10
11
12
13

2.十字链表：

十字链表在只有行指针的单链表之上还加入了列指针都已数组方式进行存储，并且每一个结点不仅存储行，列，数值，还存储了一个指向同列中下一个元素的指针down和指向同行中下一个元素的指针right。

//结点结构
typedef struct OLNode
{ int row, col; //非零元所在行、列 非零元所在行、列
ElemType val; //非零元的值 非零元的值
struct OLNode *right, *down;
//同行、同列的下一个非零元的指针 同行、同列的下一个非零元的指针
}OLNode,* OLink;


//十字链表结构
typedef struct
{ OLink rhead[M],chead[N]; //行、列指针数组 行、列指针数组
int mu, nu, tu; //行、列数及非零元个数 行、列数及非零元个数
}CrossList;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

树：

1.树的基本概念

树的定义：有且仅有一个根结点，除根结点之外的其余结点可分为m个互不相交的有限集，每一个集合又是一棵树，并称为根的子树。
树的基本术语：
结点的度：结点拥有的子树的数量
树的度：树内各节点度的最大值
祖先：从根到该结点所经分支上的所有结点
层次：根称为第一层，根的孩子称为第二层，以此类推
树的深度：树中结点的最大层次
有序树和无序树：树中结点从左至右不能调换顺序的树称为有序树；反之，称为无序树
森林：m棵不相交的子树的集合

2二叉树

二叉树：每一个结点至多只有两个孩子的树，二叉树是有序树；
二叉树的一些性质：
1二叉树的第i层至多有 2 i 1 2^{i-1} 2i1结点
2深度为k的二叉树至多有 2 k 1 2^k-1 2k1结点
3对任何一颗二叉树其叶子结点 n 0 n_0 n0度为2的结点 n 2 n_2 n2满足 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1

满二叉树：深度为k且含有 2 k 1 2^k-1 2k1个结点的二叉树。
完全二叉树：当其的结点全都能够与满二叉树序号对应时的二叉树；
完全二叉树的性质：
1具有n个结点的完全二叉树的深度为 [ l o g 2 n ] + 1 left [ log_2n ight ]+1 [log2n]+1
2设完全二叉树按顺序排列的任一结点i
i ≠ 1 i eq1 i=1,则其双亲为 [ i 2 ] left [ rac{i}{2} ight ] [2i]
2i<n，则i没有左孩子反之2i是其左孩子；
2i+1<n,则其没有右孩子反之2i+1是其右孩子；

二叉树的存储结构：

顺序存储：

#define MAXSIZE 100
typedef TElemType SqBiTree[MAXSIZE];//数组存储二叉树
SqBiTree bt;
1
2
3

这种存储结构只适用于完全二叉树，应为大量空结点将浪费；
链式存储结构：

//二叉树结点存储结构
typedef struct BitNode{
TElemType data;//任何种类的结点都需要数据域
Struct BitNode *lchild,*rchild,*parent;//三叉链表，找孩子和双亲都容易
}BitNode,*BitNode;
1
2
3
4
5

二叉树的遍历方法和实现：

1先序遍历：又称先根遍历，即根-左孩子-右孩子进行遍历
2中序遍历：又称中根遍历，即左孩子-根-右孩子进行遍历
3后序遍历：又称后根遍历，即左孩子-右孩子-根进行遍历
4按层次遍历：从上到下从左到右依次序遍历

void preordertraverse(BiTree T){//先序遍历的递归算法
printf("%d	",T->date);//把该语句放在第二行就是中序遍历，第三行就是后序遍历
preordertraverse(T->lchild);
preordertraverse(T->rchild);


void preordertraverse(BiTree T){//二叉树的非递归遍历算法
InitStack(s);p=T;
while(p!||!StackEmpty(S)){
if(p){
printf("%d	",p->date);
Push(S,p);
p=p->lchild;}
else{
Pop(S,p);//中序遍历将printf("%d	",p->date);移至该语句后
p=p->rchild;
}


//层次遍历的非递归算法
void LevelTrave(BiTree T)
{ int f=0,r=0;
BiTree p, q[M];
q[r++]=T;
while(f<r)
{ p=q[f++];
printf("%c	",p->data);
if(p->lchild)//左孩子入队
q[r++]=p->lchild;
if(p->rchild)//右孩子入队
q[r++]=p->rchild;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

根据遍历序列确定二叉树：
先序遍历和中序遍历，中序遍历和后序遍历，中序遍历和层次遍历都能够确定一棵二叉树：都能确定每颗子树的根结点。

二叉树遍历的应用，究其本质使用了递归算法：

建立二叉链表：

void CreateBiTree(BiTree &T){
scanf("%c	",&ch）；
if(ch=='#')T=NULL;
else{
T=(*BitNode)malloc(sizeof(BiTNode));
T->date=ch;//放中间就是中序遍历，后面就是后序遍历
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
1
2
3
4
5
6
7
8
9
10

复制二叉树：

void Copy(BiTree T,BiTree &NewT){
if(T==NULL){
NewT=NULL;
return;
}
else{
NewT=new BiTnODE;
nEWt->date=T->data;
Copy(T->lchild,NewT->lchild);//同样调整位置就变成了其它序遍历
Copy(T->rchild,NewT->rchild);
}}
1
2
3
4
5
6
7
8
9
10
11

计算二叉树深度和统计二叉树结点个数原理算法类似；

树的存储结构：

1双亲表示法：结点设置双亲指针；
2孩子表示法：结点设置多个孩子指针
3孩子兄弟表示法：结点设置第一个孩子和下一个兄弟指针；还可以加上双亲指针使用。
（3和二叉链表表示完全一样，便于将树结构转换成二叉树进行表示）

森林，树，二叉树的转换

树转化成二叉树：

使用孩子兄弟表示法的思想，第一个孩子作为左孩子(即根结点的first child指针），第二个孩子作为第一个孩子的兄弟（即第一个孩子的next brother指针），做为第一个孩子的右子树（右孩子）。
以上就可以表示成三步骤：
1连兄弟2断右孩子父子3将整棵树顺时针旋转45°

将二叉树还原成树就表示成：

1连祖孙（只是爷爷辈和孩子辈的）2断右孩子父子3调整成型
将森林表示成二叉树：将每棵树转换成二叉树，设定每棵树的根节点为兄弟，依照孩子兄弟表示法对森林进行连接；
以上表示成三步骤：
1将各棵树分别转换成二叉树；
2将每棵树的根结点用线相连；
3以第一棵树的根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树的结构.

二叉树还原成森林：

1先把根结点右分支线去掉，得到了原来各个树转化的二叉树。
2再依次将二叉树转换为树

树的遍历：

先根遍历：先访问根结点，再依次先根遍历访问根结点的各个子树=对应二叉树的先序遍历
后根遍历：先后根遍历根节点的各个子树再访问根结点=对应二叉树的后序遍历
按层次遍历

森林的遍历：

先序遍历：依次先序遍历每一棵树，又或者先序遍历对应的二叉树
中序遍历：后序遍历每一棵树，又或者中序遍历对应的二叉树

哈夫曼树：

基本概念：

路径：从树的一个结点到另一个结点之间的分支构成路径
路径长度：路径上的分支数目
树的路径长度：从树根到每一结点的路径长度之和
权：为结点或分支数值化，若结点带权，则就有带权树等概念
结点的带权路径长度：从该结点到树根之间的路径长度和结点上的权的乘积
树的带权路径长度：所有叶子结点的带权路径长度之和
基于上述概念有哈夫曼树：m个带权结点构造一棵带权路径长度最小的二叉树

哈夫曼树的构造：

1将m个结点中权最小的两个结点作为一棵二叉树的左右孩子，并以其权和为根结点构造一棵新的二叉树，舍去孩子。
2重复第一个过程得到一棵二叉树就是哈夫曼树；

哈夫曼编码：

构造一棵哈夫曼树，使其带权路径长度= ∑ ( w i l i ) sum (w_il_i) ∑(wili)wi为一个字母的出现频率即结点权值，依次构造哈夫曼树；li为路径长度，即当向左孩子走代表0，向有孩子走代表1，则li即译码一个字母的0和1的个数；由上述等式知道用哈夫曼树构造的电文长度最短；而又因为叶子结点路径唯一，所以所有编码都是前缀编码。
当编码时，则将每一个字母表示成哈夫曼树的叶子结点的0-1表示即可
当译码时，则根据0-1在哈夫曼树行走路径，得出叶子节点对应字母即可。

图：

基本概念：

1无向图，有向图：顶点之间无向连接的图称为无向图，顶点之间有向连接的图称为有向图；
2无向完全图：边数为n(n-1)/2的无向图；
有向完全图：边数为n(n-1)的有向图；
3权和网：为边赋予的一定含义的数值称为权，带权的图称为网；
4邻接点：对于无向图，两顶点构成一条边，则这两顶点互为邻接点；
5度，入度，出度：无向图的顶点的度即是和该顶点相关联的边的数目；有向图顶点的度分为入度和出度，入度即箭头指向个数，出度即箭头指出个数；
6路径：是从一个顶点到另一个顶点所经过的顶点序列。路径长度就是经过的边的数目；
7连通：如果两顶点之间有路径，则两顶点是连通的。（对于无向图而言）
8连通图：如果图中任意两个顶点都是连通的，则称为连通图；（对于无向图而言）
9连通分量：无向图中的最大连通子图。
10强连通图和强连通分量：对有向图，每一个顶点之间都存在路径的图是强连通图；有向图中的极大强连通子图称为有向图的强连通分量；
11连通图的生成树：一棵连通图有n个顶点但只有n-1条边就是对它连通后的连通图的生成树；
12:有向树和生成森林：一个顶点的入度为0，其余顶点的入度均为1的有向图成为有向树。一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点但只有足以构成若干棵不相交的有向树的弧。

图的存储结构：

1.邻接矩阵表示法又称数组表示法：

当图中不带权：有 A [ i ] [ j ] = { 1 if < v i , v j > o r ( v i , v j ) ∈ E 0 if o t h e r A[i][j]=egin{cases} 1 & ext{ if } <v_i,v_j> or(v_i,v_j)in E\ 0& ext{ if } other end{cases} A[i][j]={10if<vi,vj>or(vi,vj)∈Eifother
当图带权成为网： A [ i ] [ j ] = { w i , j if < v i , v j > o r ( v i , v j ) ∈ E ∞ if o t h e r A[i][j]=egin{cases} w_{i,j} & ext{ if } <v_i,v_j> or(v_i,v_j)in E\ infty & ext{ if } other end{cases} A[i][j]={wi,j∞if<vi,vj>or(vi,vj)∈Eifother

typedef char VertexType;//图的邻接矩阵存储表示
typedef int EdgeType;
#define M 20 //顶点最大数目 顶点最大数目
Typedef struct
{ VertexType vexs[M];
EdgeType arcs[M][M];
int vexnum, arcnum;
// 顶点数目、边数目
} MGraph;
1
2
3
4
5
6
7
8
9

邻接表表示法：

顶点信息使用一维数组进行存储，每一个顶点的邻接点用一个单链表表示

typedef struct Arcnode//单链表结点存储
{ int adjvex;
struct Arcnode *nextarc;//带权的邻接表即为结点多定义一个权的数据域
}ArcNode;
typedef struct Vnode//数组类型定义
{ VertexType data;
ArcNode *firstarc;
}VNode, AdjList[M];
typedef struct//图的邻接表存储
{ AdjList vertices; // // 顶点数组
int vexnum, arcnum; // // 顶点及弧的数目
}ALGraph
1
2
3
4
5
6
7
8
9
10
11
12

结构特点：

对于无向图：1 每条边对应2 个单链表结点
2单 链表结点总数= 边数*2
3它的度是第i 个单链表中的结点个数
对于有向图：1 每条弧对应1 个单链表结点
2 单 链表结点总数= 弧数
3 出度为第i 个单链表中
的结点个数
4 入度为所有单链表中
数据域为i的 的 结点 个数
逆邻接表：对于有向图而言，将所有顶点的逆邻接点存储到单链表中

图的遍历：

为了避免遍历的过程中对顶点重复遍历，所以需要设置一个数组对顶点遍历情况进行储存。

1深度优先遍历：

类似于属的先根遍历；遍历序列不唯一
步骤：
1先访问第一个顶点
2再访问第一个顶点的第一个邻接点，再访问该顶点的第一个邻接点，重复2至没有邻接点
3回退至上一个顶点，访问它的下一个邻接点重复23将图完全遍历；
深度遍历是一个递归过程：1先深度遍历

void DFS(ALGraph G, int i)
{ArcNode *w;int k;//深度优先遍历顶点i
printf("%d	",i);
visited[i]=1;
w=G.vertices[i].firstarc;
while(w!=NULL)
{k=w->adjvex;
if(visited[k]==0) DFS(G,k);//依旧使用递归算法遍历
w=w->nextarc;
}}
int visited[M];
void DFSTraver(ALGraph G)
{
//DFS只能便利和一个入度为0的顶点及其连接点，对于其它入度为0的顶点使用递归访问
int i;
for(i=1;i<=G.vexnum;i++)
if(visited[i]==0)
DFS(G,i);}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

广度优先遍历：

1访问顶点后访问其各个邻接点
2以1的方式访问各个临界点
采用队列实现广度优先遍历：
① 访问初始顶点并入队
②队列不为空时
出队一个顶点， 访问 其未
被访问过的邻接点并 入队

int visited[M];
void BFS( ALGraph G, int v)
{ int qu[MAX],f=0,r=0,x;//广度优先遍历一顶点,队列qu
ArcNode *w;
printf("%d	",v); visited[v]=1;
qu[r++]=v;
while(f<=r){//队列不空
x=qu[f++];//出队
w=G.vertices[x].firstarc ;//找出其第一个邻接点
while(w!=NULL)//有邻接点时，访问邻接点并入队
{
x=w->adjvex ;
if(visited[x]==0)
{ visited[x]=1;
printf("%d	",x);
qu[r++]=x; }
w=w->nextarc ;//求下一个邻接点
}
}}
void BFSTraver(ALGraph G)
{//递归算法遍历其它入度为0的邻接点
int i;
for(i=1;i<=G.vexnum;i++)
if(visited[i]==0)
BFS(G,i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

最小生成树一些性质：

1生成树中任意两个顶点间的路径是唯一的；
2在生成树中再加一条边必然形成回路。
3深度优先生成树和广度优先生成树

4生成森林：非连通图的每一个联通分量化成生成树组成的生成森林
5 最小生成树：在连通网(带权的连通图)中，所有边的权值之和最小的生成树，称为~

最小生成树的构造方法：

1prim方法：

从图中某顶点开始，每次选择权值最小的
边对应的顶点加入到最小生成树中，直到
加入所有顶点

struct
{ VertexType adjvex;//在U中对应的最小点
int lowcost;//距离U的点的最短距离
}closedge[M];
void MiniSpanTree_PRIM(MGraph G, VertexType u)//prim算法从顶点u出发求图的最小生成树
{inti,j,k=u-1;
for ( j=0; j<G.vexnum; ++j )//将数组closedge初始化
if (j!=k)
{ closedge[j].adjvex= u;
closedge[j].lowcost= G.arcs[k][j];
}
closedge[k].lowcost = 0;
for (i=0; i<G.vexnum-1; i++)
{
k = minimum( );//求出V-U中lowcost最小的顶点
printf(“%d%d
”,G.vexs[k],closedge[k].adjvex);//输出顶点k和对应边
closedge[k].lowcost = 0;//将k加入U，修改其lowcost
for (j=0; j<G.vexnum; j++)//修改其他顶点的lowcost
if (G.arcs[k][j] < closedge[j].lowcost)
{ closedge[j].lowcost= G.arcs[k][j];
closedge[j].adjvex= G.vexs[k];}}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

克鲁斯卡尔算法：

又称为加边法
设连通网为G=(V,E) ，构造的最小生成树为T=(U,TE)
1初始——令U=V ，TE为空集；
2加边——选择权值最小的边(u’,v’)加入TE，
若u’和v’是连通的，舍弃该边；
若u’和v’是非连通的，则将边(u’,v’) 加入TE；
3重复步骤2，直到T中所有顶点均连通

拓扑排序：

AOV网：用顶点表示活动，用弧表示活动间的优先顺序的网；（AOV网中不应该出现有向环；
所谓拓扑排序就是将AOV网中所有顶点排成一个线性序列，该序列满足：若在AOV网中由顶点vi到vj有一条路径，则vi排在vj之前。
拓扑排序检测是否有环：对有向图进行拓
扑排序，若网中所有顶点出现在拓扑序列中，则该AOV网不存在环。

拓扑排序过程：

1在AOV网中选择一个没有前驱(入度=0)的顶点并输出；
2从图中删除该顶点和所有以它为尾的弧；
3重复步骤12，直至全部顶点均被输出；或图中没有无前驱的顶点为止。

拓扑排序算法实现：

1采用邻接表作为存储结构(加入入度域)
2将所有入度为0的顶点入栈；
2当栈非空时，出栈栈顶元素V j 并输出到拓扑序列中；
查找V j 的所有直接后继V k ，将其入度-1；若V k 的入度为0则入栈；
3重复上述操作直至栈空为止。若拓扑序列中的顶点个数不是n，则图中有环存在

Status TopologicalSort(ALGraph G)
{ int i,j,k,count; ArcNode *p;
int S[max],top=0;
CountInDegree(G);
for(i=1; i<=G.vexnum; i++)
if(G.vertices[i].in==0)
S[top++]=i;
count=0;
while (top!=0)
j=S[--top]; count++;
printf("%d ",G.vertices[j].data);
for (p=G.vertices[j].firstarc; p; p=p->nextarc)
k=p->adjvex;
if ((--G.vertices[k].in)==0) S[top++]=k;
if (count<G.vexnum) return ERROR;
return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最短路径问题：

求从u0到ui的最短路径。

迪杰斯特拉算法：

从源点 v 0 出发，按 路径长度递增次序 求得v 0 到其它各顶点的最短路径。
一个分支路径的最小路径去更新两个分支路径的最小路径，以此类推。

弗洛伊德算法：

算法思想：逐个顶点 试探法
求最短路径步骤：
1初始时设置一个n阶方阵，令其对角线元 阶方阵，令其对角线元
素为 素为0 ，若存在弧<Vi,Vj>， ， 则对应元素为权
值；否则为 值；否则为 ——图的邻接矩阵 图的邻接矩阵
2 逐步 试着 在原直接路径中增加一个中间顶
点，若加入中间点后路径变短，则修改之；
否则，维持原值

查找：

基本概念：

静态查找表：仅仅查找，不改动查找表中的数据；
动态查找表：在查找过程中同时伴随着插入或删除操作。
平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键个数的期望值 A S L = ∑ p i C i ASL=sum p_iC_i ASL=∑piCi

静态查找表：

顺序查找：

从表的一端开始依次查找；既适用于顺序存储，也适用于链式存储。
A S L = n + 1 2 ASL= rac{n+1}{2} ASL=2n+1

折半查找：

从记录的中间位置二分查找；只适用于有序的顺序存储。

int Search_Bin( SSTable ST, KeyType k)
{ int low,high,mid;//设置三指针操作
low=1; high=ST.length;
while(low<=high)//循环条件
{ mid=(low+high)/2;
if(k>ST.elem[mid].key) low=mid+1;//low=mid+1
else if(k==ST.elem[mid].key) return mid;
else high=mid-1;//high=mid-1
}
return(0);
}
1
2
3
4
5
6
7
8
9
10
11

折半查找的判定树：

将有序表的元素进行位置序号排列，依据折半查找左右子表代替左右子树构建二叉树。
从判定树就可以得到查找各个元素需要比较的次数（即该结点所在的层次）
对于一个n元素顺序表，最大深度为 [ l o g 2 ( n ) ] + 1 left [ log_2(n) ight ]+1 [log2(n)]+1,这就是它的最大比较次数。
由此得一个一个元素为n的满二叉树的深度为 l o g 2 ( n + 1 ) log_2(n+1) log2(n+1),并有 A S L = n + 1 n l o g 2 ( n ) 1 ASL= rac{n+1}{n}log_2(n)-1 ASL=nn+1log2(n)1
当n较大时有 A S L = l o g 2 ( n + 1 ) 1 ASL=log_2(n+1)-1 ASL=log2(n+1)1.

索引表查找：

将线性表分成几块，块内无序，块间有序；
先确定待查记录所在块，再在块内查找。

typedef struct//索引表类型
{ KeyType MaxKey; //本块最大关键字
int FirstLink; //本块第一个结点下标
}IndexTable;
1
2
3
4

A S L = L b + L w ， L b ASL=L_b+L_w，L_b ASL=Lb+Lw，Lb块间查找，有序可用折半查找；

动态查找表：

查找过程中可以进行插入或删除

二叉排序树:

二叉排序树的左子树所有结点的数值小于根节点，右子树的所有结点数值大于根结点，根结点的左右子树也是二叉排序树；
对二叉排序树采用中序遍历，就可以得到递增的有序序列；
二叉排序树采用链表存储：
二叉排序树的查找采用递归的方式，比较后左右子树查找；
二叉树的插入：

void InsertBST(BiTree &T, Elemtype e)
{
T=(BiTree)malloc(sizeof(BiTNode));//节点空间
T->data=e;
T->lchild=T->rchild=NULL;
else if(e<T->data)
InsertBST(T->lchild,e);//递归
else
InsertBST(T->rchild,e);
1
2
3
4
5
6
7
8
9

二叉排序树的创建，读入结点信息插入排序树中即可。

二叉排序树的删除：

1删除的结点为叶子结点，改变其双亲指针即可；
2删除的结点只有左子树或者右子树，将其双亲指向其左子树或右子树即可
3删除的节结点既有左子树，又有右子树有两种方法
（1）令删除结点的左子树作为其双亲的左子树，其右子树作为其直接前驱的右子树
（2）直接令要删除结点的前去代替要删除的结点，直接前驱的左子树则作为直接前驱双亲的右子树。

哈希表：

在元素的存储位置何其关键字之间建立某种关系；
地址p，关键字key有 p = H ( k e y ) p=H(key) p=H(key)H称为哈希函数；

哈希函数的构造：

1数字分析法：

取变化较大的数字作为地址

2平方取中法：

对数据进行平方后取比较分散的几位作为地址

3折叠法：

移位叠加：将分割后的几部分低位对齐相加；
边界叠加：从一端沿分割界来回折送，并对齐相加。

4除留余数法：

H ( k e y ) = k e y H(key)=key%p H(key)=key

哈希表的冲突：

多个关键字对应一个地址
解决方法：

1开放地址法：

原来空间对所有元素都是开放的

线性探测法：

di=1，2，3…

二次探测法：

d i = 1 2 di=1^2 di=12, 1 2 -1^2 12 , 2 2 ,2^2 ,22…

伪随机法：

di=伪随机数序列

2再哈希法

构造若干个哈希函数，当发生冲突时，使用另外一个
哈希函数计算哈希地址，即：H i =Rh i (key) i=1,2,……k， ，
直到不发生冲突为止

3链地址法：

将所有关键字为同义词的记录存储在一个单链表中，
并用一维数组存放单链表的头指针

查找过程与冲突处理过程一致即可

排序：

按关键字的非递减或非递增顺序对异族记录重新进行排列的操作；
排序的稳定性：当存在多个相同记录时，排序结果唯一的稳定性好反之不稳定

排序算法的评价标准：

1执行时间即时间复杂度主要有关键字的比较和移动进行影响；
2辅助空间：除了存放待排序记录占用的空间之外执行算法所需要的其他存储空间。

插入排序：

直接插入排序；r[i]跟前面排好的i-1个元素进行比较后插入

最坏比较次数： K C N = ∑ i = 2 n i = ( n + 2 ) ( n 1 ) / 2 KCN=sum_{i=2}^{n}i=(n+2)(n-1)/2 KCN=∑i=2ni=(n+2)(n1)/2有一次跟哨兵比较
最坏移动次数： R M N = ∑ i = 2 n ( i + 1 ) = ( n + 4 ) ( n 1 ) / 2 RMN=sum_{i=2}^{n}(i+1)=(n+4)(n-1)/2 RMN=∑i=2n(i+1)=(n+4)(n1)/2其中两次为移入哨兵和移出哨兵
空间复杂度为O(1)

折半插入排序：

即查找的过程改为折半查找

希尔排序：

又叫缩小增量法排序 Diminishing Increment Sort
排序过程：先取一个正整数d 1 <n，把所有相隔d 1的记录放一组，组内进行直接插入排序；然后取d 2<d 1 ，重复上述分组和排序操作；直至d i =1，即所有记录放进一个组中排序为止。

空间复杂度：S(n)=O(1)
希尔排序是一种不稳定的排序方法

交换排序：

冒泡排序：

两两之间相互比较，使大值或小值移到下一个位置。是稳定排序
T ( n ) = O ( n 2 ) , S ( n ) = O ( 1 ) T(n)=O(n^2),S(n)=O(1) T(n)=O(n2),S(n)=O(1)

快速排序：

步骤：1设定枢轴（一般为需要排序的第一个元素）将其移入r[0]
2设置low，high指向数组首末，从high从后往前找比枢轴小的第一个元素，移入r[low],row后移
3再从low开始从前往后找比枢轴大第一个元素，移入r[high]，high前移
4row==high时，将令r[row]==r[0]
5对左右序列进行快速查找
最坏情况 T ( n ) = O ( n 2 ) , S ( n ) = O ( n ) T(n)=O(n^2),S(n)=O(n) T(n)=O(n2),S(n)=O(n)
最好情况 T ( n ) = O ( n l o g 2 ( n ) ) , S ( n ) = O ( l o g 2 ( n ) ) T(n)=O(nlog_2(n)),S(n)=O(log_2(n)) T(n)=O(nlog2(n)),S(n)=O(log2(n))//不稳定的排序方法

选择排序

简单选择排序：

1首先通过n-1次关键字比较，从n个记录中找出关键字最小
的记录，将它与第一个记录交换；
2再通过n-2次比较，从剩余的n-1个记录中找出关键字次小
的记录，将它与第二个记录交换；
3重复上述操作，共进行n-1趟排序后，排序结束
T ( n ) = O ( n 2 ) , S ( n ) = O ( 1 ) T(n)=O(n^2),S(n)=O(1) T(n)=O(n2),S(n)=O(1)

堆排序：

利用堆顶元素必为n 个元素的 最大或最小进行排序
堆的定义：n个元素的序列(k 1 , k 2 , … ,k n )，当且仅当满足
{ K i ≤ K 2 i K i ≤ K 2 i + 1 （ 小 根 堆 ） egin{cases} K_ileq K_{2i} &\ K_ileq K_{2i+1} & （小根堆） end{cases} {Ki≤K2iKi≤K2i+1（小根堆）
{ K i ≥ K 2 i K i ≥ K 2 i + 1 （ 大 根 堆 ） egin{cases} K_igeq K_{2i} &\ K_igeq K_{2i+1} & （大根堆） end{cases} {Ki≥K2iKi≥K2i+1（大根堆）

排序过程
1将无序序列建成堆，则堆顶是关键字最小/最大的记录；
2输出堆顶记录后，将剩余的记录重新调整成一个新堆，
则可得到剩余记录中的最小/最大值；
3重复执行2 ，直到得到一个有序序列。
输出堆顶后调整成堆：

筛选：

1输出堆顶记录之后，用堆中最后一个记录替代它；
2将根结点值与其左、右孩子进行比较，并与其中小/大的
孩子进行交换；
3 重复上述操作，直至叶子结点，即可得到新的堆。
将无序序列调整成堆：从无序序列的第 [ n 2 ] left [ rac{n}{2} ight ] [2n]个元素（即无序序列对应完全二叉树的最后一个非叶子结点）起，至第一个元素止，进行反复筛选。
堆排序的优点：即使在最坏情况下，其时间复杂度也
为 O(nlog 2 n) ；只需一个辅助空间

2-路归并排序

排序过程
1对于待排序的n个记录，初始时将其看作n个有序子序列，
每个子序列长度为1；
2两两合并子序列，得到 [ n 2 ] left [ rac{n}{2} ight ] [2n]个长度为2或1的有序子序列；
3重复执行2 ，直到得到1个长度为n的有序序列。
T ( n ) = O ( n l o g 2 ( n ) ) ， S ( n ) = O ( n ) T(n)=O(nlog_2(n))，S(n)=O(n) T(n)=O(nlog2(n))，S(n)=O(n)

基数排序：

最低位优先法(LSD-Least Significant Digit first)
1首先对最低位关键字k d 排序，再对高一位关键字排序；
2重复执行，最后对最高位关键字k 1 排序，得到有序序列。
LSD 可通过一系列分配- 收集 完成，不需要进行关键字的比较
链式基数排序：