目录
第一章 绪论
第二章 线性表
顺序表
单链表
循环链表
第三章 栈和队列
栈
队列
矩阵的压缩存储
第四章 树与二叉树
树
二叉树
线索二叉树
树、森林
树和二叉树的应用
平衡二叉树
哈夫曼树
第五章 图
图的存储和基本操作
第六章 排序
直接插入排序
希尔排序
冒泡排序
快速排序
简单选择排序
归并排序
1、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。
2、抽象数据类型（Abstract Data Type, ADT）是指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论内部结构如何变化，只要它的数学属性不变，都不影响其外部使用。
ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT抽象数据类型名3、算法特性
有穷性、确定性（无二义性）、可行性、输入、输出
4、算法设计要求：
正确性、可读性、健壮性、效率与低存储量需求
5、复杂度
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n*n)<O(n*n*n)<O(2^n)
1、线性表是n个数据元素的有限集合
2、typedef与define的区别：摘自
typedef：可以按照自己的习惯定义数据类型名称
define：#define命令是C语言中的一个宏定义命令，它用来将一个标识符定义为一个字符串，该标识符被称为宏名，被定义的字符串称为替换文本。eg，#define PI 3.1415926
（1）原理不同
#define是C语言中定义的语法，是预处理指令，在预处理时进行简单而机械的字符串替换，不作正确性检查，只有在编译已被展开的源程序时才会发现可能的错误并报错。
typedef是关键字，在编译时处理，有类型检查功能。它在自己的作用域内给一个已经存在的类型一个别名，但不能在一个函数定义里面使用typedef。用typedef定义数组、指针、结构等类型会带来很大的方便，不仅使程序书写简单，也使意义明确，增强可读性。
（2）功能不同
typedef用来定义类型的别名，起到类型易于记忆的功能。另一个功能是定义机器无关的类型。如定义一个REAL的浮点类型，在目标机器上它可以获得最高的精度：typedef long double REAL， 在不支持long double的机器上，看起来是这样的，typedef double REAL，在不支持double的机器上，是这样的，typedef float REAL
#define不只是可以为类型取别名，还可以定义常量、变量、编译开关等。
（3）作用域不同
#define没有作用域的限制，只要是之前预定义过的宏，在以后的程序中都可以使用，而typedef有自己的作用域。
3、new与malloc的区别：摘自
（1）属性
new/delete是C++关键字，需要编译器支持。malloc/free是库函数，需要头文件支持。
（2）参数
使用new操作符申请内存分配时无须指定内存块的大小，编译器会根据类型信息自行计算。而malloc则需要显式地指出所需内存的尺寸。
（3）返回类型
new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无须进行类型转换，故new是符合类型安全性的操作符。而malloc内存分配成功则是返回void * ，需要通过强制类型转换将void*指针转换成我们需要的类型。
（4）分配失败
new内存分配失败时，会抛出bac_alloc异常。malloc分配内存失败时返回NULL。
（5） 自定义类型
new会先调用operator new函数，申请足够的内存（通常底层使用malloc实现）。然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用析构函数，然后调用operator delete函数释放内存（通常底层使用free实现）。malloc/free是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对象构造和析构工作。
（6）重载
C++允许重载new/delete操作符，特别的，布局new的就不需要为对象分配内存，而是指定了一个地址作为内存起始区域，new在这段内存上为对象调用构造函数完成初始化工作，并返回此地址。而malloc不允许重载。
（7）内存区域
new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数从堆上动态分配内存。自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。自由存储区不等于堆，如上所述，布局new就可以不位于堆中。
1、定义：用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
2、特点：
（1）随机访问，O(1)时间找到制定元素
（2）存储密度高，每个节点只存储数据元素
（3）顺序表逻辑上相邻的元素物理上也相邻，插入删除需要移动。
//顺序表的构建、插入、删除、查找
#include<iostream> #include<cstdio> #include<malloc.h> using namespace std; #define List_size 10 #define maxL 50 typedef struct LNode{ int *data; int len; }List; void init(List &L){ L.data=(int*)malloc(List_size*sizeof(int)); for(int i=0;i<10;i++){ L.data[i]=i+1; } L.len=10; } bool Insert(List &L,int pos,int e){//在第pos个位置出插入e if(pos<1||pos>L.len+1){ return false; } if(L.len>=maxL){ return false; } for(int i=L.len;i>=pos;i--){ L.data[i]=L.data[i-1]; } L.data[pos-1]=e; L.len++; return true; } bool Delete(List &L,int pos,int &e){//删除pos位置上的数，并赋给e if(pos<1||pos>L.len){ return false; } e=L.data[pos-1]; for(int i=pos;i<L.len;i++){ L.data[i-1]=L.data[i]; } L.len--; return true; } int Locate(List L,int e){ for(int i=0;i<L.len;i++){ if(L.data[i]==e){ return i+1; } } return 0; } void print(List L){ for(int i=0;i<L.len;i++){ printf("%d ",L.data[i]); } printf("\n"); } int main(){ List L; init(L); print(L); //插入 Insert(L,3,8); print(L); //删除 int e; Delete(L,3,e); printf("删除了%d\n",e); print(L); //查找 int k=Locate(L,3); printf("第3个位置上的元素是：%d\n",k); }单链表（线性表的链式存储）：
插入删除不需要移动元素，只需要修改指针
是非随机存取的存储结构，查找节点时要遍历
//单链表的构建、插入、删除、查找
#include<iostream> #include<cstdio> #include<malloc.h> using namespace std; #define List_size 10 #define maxL 50 typedef struct LNode{ int data; struct LNode *next; }LNode,*List; void init(List &L){//尾插 L=(List)malloc(sizeof(LNode)); LNode *s,*r=L; for(int i=1;i<=10;i++){ s=(LNode*)malloc(sizeof(LNode)); s->data=i; r->next=s; r=s; } r->next=NULL; } LNode *GetElem(List L,int i){//找第i个位置上的节点 int j=1; LNode *p=L->next; if(i==0)return L; if(i<1)return NULL; while(p&&j<i){ p=p->next; j++; } return p; } void Insert(List &L,int i,int e){//在第i个位置插入元素e LNode *p=GetElem(L,i-1); LNode *s=(LNode*)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; } void Delete(List &L,int i){//删除第i个位置上的元素 LNode *p=GetElem(L,i-1); LNode *q=p->next; p->next=q->next; printf("删除了%d\n",q->data); free(q); } void print(List L){ LNode *p=L->next; while(p!=NULL){ printf("%d ",p->data); p=p->next; } printf("\n"); } int main(){ List L; init(L); print(L); //插入 Insert(L,3,8); print(L); //删除 Delete(L,3); print(L); //查找 LNode *p=GetElem(L,3); printf("第3个位置上的元素是：%d\n",p->data); }//循环链表的构建、插入、删除、查找
#include<iostream> #include<cstdio> #include<malloc.h> using namespace std; #define List_size 10 #define maxL 50 typedef struct LNode{ int data; struct LNode *next,*pre; }LNode,*List; void init(List &L){//尾插 L=(List)malloc(sizeof(LNode)); LNode *s,*r=L; for(int i=1;i<=10;i++){ s=(LNode*)malloc(sizeof(LNode)); s->data=i; r->next=s; s->pre=r; r=s; } r->next=NULL; } LNode *GetElem(List L,int i){//找第i个位置上的节点 int j=1; LNode *p=L->next; if(i==0)return L; if(i<1)return NULL; while(p&&j<i){ p=p->next; j++; } return p; } void Insert(List &L,int i,int e){//在第i个位置插入元素e LNode *p=GetElem(L,i-1); LNode *s=(LNode*)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next->pre=s; p->next=s; s->pre=p; } void Delete(List &L,int i){//删除第i个位置上的元素 LNode *p=GetElem(L,i-1); LNode *q=p->next; p->next=q->next; q->next->pre=p; printf("删除了%d\n",q->data); free(q); } void print(List L){ LNode *p=L->next; while(p!=NULL){ printf("%d ",p->data); p=p->next; } printf("\n"); } int main(){ List L; init(L); print(L); //插入 Insert(L,3,8); print(L); //删除 Delete(L,3); print(L); //查找 LNode *p=GetElem(L,3); printf("第3个位置上的元素是：%d\n",p->data); printf("第2个位置的元素是：%d\n",p->pre->data); }顺序表和链表的比较：
（1）存取方式
顺序表可以顺序存取，也可以随机存取。链表只能从表头存取元素
（2）逻辑结构与物理结构
顺序表：逻辑上相邻的元素，其对应物理存储位置也相邻。
链表：逻辑上相邻的元素，其对应物理存储位置不一定相邻。
（3）查找、插入、删除操作
链表
顺序表
按值查找
O(n)
O(n)（有序的话二分O(log2n)）
按序号查找
O(n)
O(1)
（4）空间分配
顺序存储：
静态存储：满则不能装，要预先分配足够大内存
动态存储：存储空间可扩充，但需要移动大量元素，效率低，且内存无足够大的连续存储空间会导致分配失败
链式存储：
需要时分配，有内存空间就可分配，操作灵活高效。
栈：只允许在一端（栈顶）进行插入或删除操作的线性表
//顺序栈的基操
顺序栈的入栈操作收到数组上界的约束，当栈的最大空间不够时，可能出现上溢。
#include<iostream> #include<cstdio> #include<malloc.h> using namespace std; #define List_size 10 #define maxL 50 typedef struct{ int data[maxL]; int top; }sta; void initStack(sta &S){ S.top=-1; } bool Push(sta &S,int i){ if(S.top==maxL-1){ return false; } S.data[++S.top]=i; return true; } bool getTop(sta &S){ if(S.top==-1)return false; int x=S.data[S.top]; printf("栈顶元素是：%d\n",x); return true; } bool Pop(sta &S){ printf("出栈：\n"); if(S.top==-1)return false; while(S.top!=-1){ int x=S.data[S.top--]; printf("%d ",x); } return true; } int main(){ sta S; initStack(S); for(int i=1;i<=10;i++){//进栈 Push(S,i); } getTop(S); Pop(S); }//链栈的基操
链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常用单链表实现，并规定所有操作都是在单链表的表头进行（头插法）
注意：
链栈没有头指针，S指针指向栈顶元素，S初始化为NULL，最后栈底元素的next是NULL
#include<iostream> #include<cstdio> #include<malloc.h> using namespace std; #define List_size 10 #define maxL 50 typedef struct LNode{ int data; struct LNode *next; }LNode,*sta; void initStack(sta &S){ S=NULL; } void Push(sta &S,int e){//无头结点 LNode *p; p=(LNode*)malloc(sizeof(LNode)); p->data=e; p->next=S; S=p; } bool getTop(sta &S){ printf("栈顶元素是：%d\n",S->data); } bool Pop(sta &S){ printf("出栈：\n"); LNode *p=S; while(p!=NULL){ printf("%d ",p->data); p=p->next; } printf("\n"); } int main(){ sta S; initStack(S); for(int i=1;i<=10;i++){//进栈 Push(S,i); } getTop(S); Pop(S); }栈的应用
括号匹配
表达式求值
队列：也是一种操作受限的线性表，在表的一端进行插入（队尾），在另一端进行删除（队头）
当Q.rear==MaxSize的时候，不能说明队列已满，因为，会有出队的元素，这时候，队列中依然可以存放元素，但却出现了“上溢出”，这是一种“假溢出”
==》解决方法：循环队列
初始化：Q.front=Q.rear=0
出 队：Q.front=(Q.front+1)%MaxSize
入 队：Q.rear=(Q.rear+1)%MaxSize
队 长：(Q.rear+MaxSize-Q.front)%MaxSize
区分满或空：
（1）牺牲一个单元：
队满：(Q.rear+1)%MaxSize=Q.front
队空：Q.front==Q.rear
//顺序队列顺序存储基操（牺牲一个单元）
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<stack> using namespace std; #define MaxSize 10 typedef struct{ int data[MaxSize]; int f,r; }Q; void init(Q &q){ q.f=q.r=0; } void EnQ(Q &q,int e){ if((q.r+1)%MaxSize==q.f){ printf("the queue is full, and %d hasn't been inserted to it.\n",e); return ; } q.data[q.r]=e; q.r=(q.r+1)%MaxSize; printf("%d is successfully inserted to the queue!\n",e); } void DeQ(Q &q){ if(q.r==q.f){ printf("the queue is empty, you cannot delete an element!\n"); return ; } printf("%d is removed.\n",q.data[q.f]); q.f=(q.f+1)%MaxSize; } void print(Q q){ if(q.f==q.r){ printf("Empty!\n"); } else { int p=q.f; while(p!=q.r){ printf("%d ",q.data[p]); p=(p+1)%MaxSize; } printf("\n"); } } int main(){ Q q; init(q); for(int i=1;i<=10;i++){ EnQ(q,i); } print(q); for(int i=1;i<=5;i++){ DeQ(q); } print(q); for(int i=1;i<=3;i++){ EnQ(q,i); } print(q); }//队列的链式存储基操
不带头结点的链式队列操作比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<stack> using namespace std; typedef struct LNode{//队列节点 int data; struct LNode *next; }LNode; typedef struct{//队列 LNode *f,*r; }LinkQ; void init(LinkQ &q){ q.f=q.r=(LNode*)malloc(sizeof(LNode)); q.f->next=NULL; } void EnQ(LinkQ &q,int e){ if(q.f==q.r){ init(q); } LNode *s=(LNode*)malloc(sizeof(LNode)); s->data=e; s->next=NULL; q.r->next=s; q.r=s; } void DeQ(LinkQ &q){ if(q.r==q.f){ printf("cannot dequeue!\n"); return ; } LNode *p=q.f->next; q.f->next=p->next; if(q.r==p){//队列中只有一个元素 q.r=q.f; } free(p); } void print(LinkQ q){ if(q.r==q.f){ printf("Empty!\n"); return ; } LNode *p=q.f->next; while(1){ printf("%d ",p->data); if(p==q.r)break; p=p->next; } printf("\n"); } int main(){ LinkQ q; init(q); for(int i=1;i<=10;i++){ EnQ(q,i); } print(q); for(int i=1;i<=11;i++){ DeQ(q); } print(q); for(int i=1;i<=3;i++){ EnQ(q,i); } print(q); }1、压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是为了节省存储空间。
2、特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。eg、对称矩阵、上（下）三角矩阵，对角矩阵等。
3、特殊矩阵压缩存储方法：找到特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵压缩存储到一个存储空间。
对称矩阵（沿矩阵对角线对称）
把A[1...n][1...n]存到B[n(1+n)/2]里，从0开始存
Aij在B中对应的下标k为：
k=i*(i-1)/2+j-1 (i>=j)
k=j*(j-1)/2+i-1 (i<j)
三角矩阵
（1）下三角矩阵：上三角区所有的元素均为同一常量
把A[1...n][1...n]存到B[n(1+n)/2+1]里，从0开始存
Aij在B中对应的下标k为：
k=i*(i-1)/2+j-1 (i>=j)
k=n*(1+n)/2 (i<j)
（2）上三角矩阵：下三角区所有的元素均为同一常量
把A[1...n][1...n]存到B[n(1+n)/2+1]里，从0开始存
Aij在B中对应的下标k为：
k=(n-i+2+n)*(n-(n-i+2)+1)/2+j-i+1-1=(2n-i+2)*(i-1)/2+(j-i) (i<=j)
k=n*(1+n)/2 (i>j)
（3）三对角矩阵
对角矩阵也称带状矩阵。对于n阶方阵A中的任一元素aij，当|i-j|>1时，有aij=0（1<=i,j<=n）,则称为三对角矩阵。在三对角矩阵中，所有非零元素都集中在以主对角线为中心的3条对角线区域，其他区域的元素都为零。
把A[1...n][1...n]存到B[]里，从0开始存
则aij对应在B中的元素下标是：k=3*(i-1)-1+(j-i+2)-1=2i+j-3
反之，知道k，可推：i=floor((k+1)/3+1) ; j=k-2*i+3
（4）稀疏矩阵
矩阵元素个数s相对于矩阵中非零元素的个数t来说非常多，即s>>t的矩阵成为稀疏矩阵。
通常非零元素的行列分布还没有规律，所以用(i,j,v)这样一个三元组来存储
很显然，稀疏矩阵压缩存储后便时期了随机存取特性。
1、树的定义：
树是n(n>=0)个节点的有限集合，n=0时，是空树。任意一棵非空树中应满足：
（1）有且仅有一个特定的成为根的结点。 （2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集合T1,T2…Tm，其中每个集合本身又是一棵树，并称为根结点的子树。
（树中的某个结点（除根结点外）最多只和上一层的一个结点（父结点）有直接关系，根节点没有直接上层结点，因此在n个结点中的树，有n-1条边，而树中的每个结点与其下一层的零个或多个结点（子结点）有直接关系）
2、基本术语
（1）树中一个结点的子结点个数称为该结点的度，树中结点最大度数称为数的度。
（2）结点的层次：根为1，向下+1
结点的深度：根开始自顶向下累加
结点的高度：从叶子结点开始向上累加
树的高度：树中结点的最大层数
（3）有序树：结点的子结点从左到右的顺序出现是有关联的。反之，无序树
（4）路径和路径长度：两个结点的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边数。
注意：由于树中的分支是有向的，即从双亲结点指向孩子结点，所以树中的路径是从上到小的，同一双亲结点的孩子结点之间不存在路径。
（5）森林：是m(m>=0)棵互不相交的树的集合。
3、树的性质
（1）树中结点数等于所有结点的度数+1
（2）度为m的树中第i层上至多有m^(i-1)个结点
假设，1到i-1层的每个结点的度都为m，则1，m，m*m，m*m*m……m^(i-1)
（3）高度为h的m叉树至多有(m^h-1)/(m-1)个结点
1，m，m*m，m*m*m……m^(h-1)
1*(1-m^h)/(1-m)=(m^h-1)/(m-1)
（4）具有n个结点的m叉树的最小高度为
1，m，m*m，m*m*m……m^(h-1)
1*(1-m^h)/(1-m)=(m^h-1)/(m-1)=n
m^h=(m-1)*n+1
h=
1、定义：二叉树的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。
（即使二叉树一个结点只有一个孩子结点也要区分左右）
2、特殊的二叉树
（1）满二叉树：高度为h，有2^h-1个结点
（2）完全二叉树：所有结点与相对应的满二叉树相对应（无空隙）
（3）二叉排序树：一棵二叉树或是空二叉树，或是具有如下性质的二叉树：左子树上所有结点的关键字均小于根节点的关键字，右子树上所有结点的关键字均大于根节点的关键字。左右子树又各是一棵二叉排序树
（4）平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1
3、二叉树的性质
（1）非空二叉树上的叶子结点数等于度为2的结点数+1，即n0=n2+1
二叉树结点的度可能为：0,1,2。
设度为0,1,2的节点个数有n0，n1，n2个，则节点总数n=n0+n1+n2
二叉树的边有：n-1条，n-1=n1+2*n2
即n0+n1+n2-1=n1+2*n2
n0=n2+1
（2）非空二叉树上第k层上至多有2^(k-1)个结点(k>=1)
（3）高度为h的二叉树至多有2^h-1个结点(h>=1)
（4）对完全二叉树从上到下、从左到右编号1,2，……，n则有下面关系：
a.当i>1时，双亲结点编号：floor(i/2) 左孩子：i*2（i*2<=n） 右孩子：i*2+1（i*2+1<=n）
b.结点i所在的层次（深度）为：
（5）具有n个（n>0）结点的完全二叉树高度为或
4、二叉树的存储结构
（1）顺序存储
满二叉树和完全二叉树比较适用，反之要在空结点位置上存0，造成空间效率低下。
（2）链式存储
一般都采用链式存储。
在含有n个结点的二叉链表中，含有n+1个空链域
n个结点，共2n个链域
n-1条边，每条边占2个域（1个链域，1个数据域）
所以2n-(n-1)=n+1
二叉树的遍历
（1）先、中、后序的递归算法
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<stack> using namespace std; typedef pair<char,int> P; typedef struct BiNode{ char data; struct BiNode *lc,*rc; }BiNode,*BiTree; void init(BiTree &T){ char ch; scanf("%c",&ch); if(ch=='#')T=NULL; else{ T=new BiNode; T->data=ch; init(T->lc); init(T->rc); } } void pre_O(BiTree T){ if(T==NULL)return ; printf("%c",T->data); pre_O(T->lc); pre_O(T->rc); } void in_O(BiTree T){ if(T==NULL)return ; in_O(T->lc); printf("%c",T->data); in_O(T->rc); } void post_O(BiTree T){ if(T==NULL)return ; post_O(T->lc); post_O(T->rc); printf("%c",T->data); } int main(){ BiTree T; init(T); printf("先序遍历为：\n"); pre_O(T); printf("\n中序遍历为：\n"); in_O(T); printf("\n后序遍历为：\n"); post_O(T); } /* ABC##DE#G##F### */（2）先、中、后序的非递归算法（思路源自）
先序遍历：因为每次都最先访问其根节点，所以根节点不用存储，只用栈存右结点
（用栈就是为了帮我们保存还没有被访问的地址，以便将来我们能找到返回的地址）。
中序遍历：扫描根节点将其入栈，然后一直入栈其左子结点，直到入栈了叶子结点（其左结点为空）
出栈一个结点，并访问，然后扫描其右子结点，将其入栈，再扫描其右子结点的左节点并入栈，如此继续，直到栈空。
后序遍历：对于一个结点，可以访问它的条件是：左右子树已经遍历完
所以要一个标志位tag，tag=0表示结点不能访问；tag=1表示结点可以访问
若这次返回是从左结点返回的，就不能访问根节点，反之，能。
（1）搜索到p结点时，先把其左子树结点全部入栈，（结点地址p和tag）
（2）出栈一个最靠下的左结点，然后访问它，再遍历其右结点，tag置为1
（3）当右结点遍历完毕后，便可对p结点访问。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<stack> using namespace std; typedef struct BiNode{ char data; struct BiNode *lc,*rc; }BiNode,*BiTree; typedef pair<BiNode*,int> P; void init(BiTree &T){ char ch; scanf("%c",&ch); if(ch=='#')T=NULL; else{ T=new BiNode; T->data=ch; init(T->lc); init(T->rc); } } void pre_O(BiTree T){ stack<BiNode*>S; BiNode *p=T; S.push(p); while(S.size()){//当栈不为空时 p=S.top();S.pop(); while(p){ printf("%c",p->data); if(p->rc){ S.push(p->rc);//把右节点入栈 } p=p->lc; } } } void in_O(BiTree T){ stack<BiNode*>S; BiNode *p=T; S.push(p); while(S.size()){//当栈不为空时 p=S.top(); while(p){//把左结点都入栈 S.push(p->lc); p=p->lc; } S.pop();//出栈一个空结点 if(S.size()){ p=S.top();S.pop(); printf("%c",p->data);//访问 S.push(p->rc);//把右节点入栈 } } } void post_O(BiTree T){ int tag; BiNode *p=T; P t; stack<P>S; while(p||(S.size())){ while(p){ t.first=p; t.second=0; S.push(t); p=p->lc; } t=S.top();S.pop(); p=t.first; tag=t.second; if(tag==0){ t.first=p; t.second=1; S.push(t); p=p->rc; } else{ printf("%c",p->data); p=NULL; } } } int main(){ BiTree T; init(T); printf("先序遍历为：\n"); pre_O(T); printf("\n中序遍历为：\n"); in_O(T); printf("\n后序遍历为：\n"); post_O(T); } /* ABC##DE#G##F### */（3）层序遍历：
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> using namespace std; typedef struct BiNode{ char data; struct BiNode *lc,*rc; }BiNode,*BiTree; void init(BiTree &T){ char ch; scanf("%c",&ch); if(ch=='#')T=NULL; else{ T=new BiNode; T->data=ch; init(T->lc); init(T->rc); } } void ceng(BiTree T){ queue<BiNode*>Q; BiNode *q=T,*t; Q.push(q); while(Q.size()){ t=Q.front();Q.pop(); if(t){ printf("%c",t->data); } if(t->lc)Q.push(t->lc); if(t->rc)Q.push(t->rc); } } int main(){ BiTree T; init(T); printf("层序遍历为：\n"); ceng(T); } /* ABC##DE#G##F### */ 由遍历序列构造二叉树：先、中=>唯一确定一棵二叉树：戳我(*╹▽╹*)
后、中=>唯一确定一棵二叉树：戳我(*╹▽╹*)
层、中=>唯一确定一棵二叉树：戳我(*╹▽╹*)
先、后不能唯一确定一棵二叉树
传统的链式存储仅能一线一种父子关系，不能直接得到结点在遍历中的前驱和后继。通过观察我们发现二叉链表表示的二叉树中存在大量的空指针，若利用这些空链域存放指向其直接前驱或后继的指针，则可以更方便地运用某些二叉操作算法。引入线索二叉树是为了加快查找节点前驱和后继的速度。
（传统的链式存储，比如中序遍历，递归遍历完左子树后，向上一层一层返回，到根节点，再遍历根节点，
用线索二叉树，可以直接返回到根节点）
前面提到过，在有n个节点的二叉树中，有n+1个空指针。
（ps,记得初始化tag的值为0鸭，QwQ）
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> using namespace std; typedef struct TNode{ char data; int rtag=0,ltag=0; struct TNode *lc,*rc; }TNode,*ThreadTree; void init(ThreadTree &T){ char ch; scanf("%c",&ch); if(ch=='#')T=NULL; else{ T=new TNode; T->data=ch; init(T->lc); init(T->rc); } } void InThread(ThreadTree &p,ThreadTree &pre){ if(p){ InThread(p->lc,pre); if(p->lc==NULL){ p->lc=pre; p->ltag=1; } if(pre!=NULL&&pre->rc==NULL){ pre->rc=p; pre->rtag=1; } pre=p; InThread(p->rc,pre); } else return ; } void CreateInThread(ThreadTree &T){ ThreadTree pre=NULL; if(T){ InThread(T,pre); pre->rc=NULL; pre->rtag=1; } } TNode *Firstnode(TNode *p){//求中序搜索二叉树中中序序列下的第一个结点 while(p->ltag==0)p=p->lc; return p; } TNode *NextNode(TNode *p){//求中序搜索二叉树中结点p在中序序列下的后一个结点 if(p->rtag==0){ return Firstnode(p->rc); } else return p->rc; } void In_O(TNode *T){ for(TNode *p=Firstnode(T);p!=NULL;p=NextNode(p)){ printf("%c",p->data); } printf("\n"); } int main(){ ThreadTree T; init(T); CreateInThread(T); In_O(T); } /* ABC##DE#G##F### */树的存储结构：
（1）双亲表示法
利用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。
该存储利用了每个结点（除根节点）只有唯一双亲的性质，可以很快得到每个结点的双亲结点，但是求结点的子结点需要遍历整个结构。
#define MAX_TREE_SIZE 100 typedef struct{ int data; int pra; }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE] int n;//结点数 }PTree;（2）孩子表示法
将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表（叶子结点的孩子链表为空）
该存储可以很快得到每个结点的孩子结点，但是求结点的双亲结点需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。
（3）孩子兄弟表示法（又称二叉树表示法）
即以二叉链表作为树的存储结构。孩子兄弟表示法使得每个结点包括3部分：结点值，指向结点第一个孩子结点的指针，指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）
typedef struct CSNode{ int data; struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree;
树、森林与二叉树的转换
树转换为二叉树的规则：
每个结点左指针指向它的第一个孩子结点，右指针指向它在树中的相邻兄弟结点，可表示为：“左孩子右兄弟”。由于根节点没兄弟结点，所以由树转换得到的二叉树没有右子树。
森林转换为二叉树的规则：
把森林中每棵树转换为二叉树，再将第一棵树的根作为转换后二叉树的根，第二棵树作为其右子树，第三棵树作为第二棵树的右子树……依次类推
二叉树转换为森林的规则：
若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，二叉树的根的右子树也看成是要转成森林的一棵二叉树，重复上述操作，直到最后产生一棵没有右子树的二叉树为止。
树和森林的遍历：
树的遍历无中根遍历，因为一个结点的子结点可能有n(n>2)个
这里有一点需要注意的！表格里树的后根遍历等于二叉树的中序遍历，指的是：
树的后根遍历=该树转为二叉树后，对二叉树进行的中序遍历。
二叉排序树（BST）
1、定义二叉排序树，也称二叉搜索树：
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）它的左、右子树也分别为二叉搜索树。
2、删除操作（删除的是z结点）
（1）若z是叶子结点，直接删掉
（2）若z只有一棵左子树，或一棵右子树，删除后，把子树提上来
（3）若z有左、右子树
则找到z节点的右子树的最左的节点，把它替换删除结点。（若z结点右子树无左结点，则用其右子树根节点代替）
3、二叉排序树查找效率
二叉排序树查找算法的平均查找长度取决于树的高度，即与二叉树的形态有关。若其为只有右（左）孩子的单支树，平均查找长度为O(n)。若二叉排序树左右子树的高度只差的绝对值不超过1，这样的二叉排序树称为平衡二叉树。平均查找长度达到O(log2n)
嘻嘻，然后来快乐的水两道题：
LeetCode450 删除二叉搜索树中的结点
hdu3791二叉树的建立遍历
平衡二叉树（Balancing Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
定义结点左子树右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是：-1,0,1
平衡二叉树插入删除
给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度（WPL）达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
构造：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
（思路就是：把权值较大的点放在上面~）
哈弗曼编码：
（1）对于待处理的一个字符串序列， 若对每个字符用同样长度的二进制位表示，则称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示，则这种方式称为可变长度编码。可变长度编码比固定长度编码好得多，其特点是对频率高的字符赋以短编码，而对频率低的字符赋以较长一些的编码，从而可以使字符平均长度减短，起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。
（2）若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。
eg、0、101、100是前缀编码，因为没有一个码是其他码的前缀。所以，可以识别出第一个编码，将它翻译为原码，再对余下的编码文件重复同样的解码操作。eg、00101100可被唯一地分析为0、0、101、100
由哈夫曼树得到哈夫曼编码是很自然的过程。首先，将每个出现的字符当作一个独立的节点，其权值为它出现的频度（次数），构造出哈弗曼树。显然，所有结点都出现在叶子结点。我们可以将字符的编码结束为从根至该字符的路径上边标记的序列，其中边标记为0表示“转向左孩子”，标记为1表示“转向右孩子”。
1、简单图：满足
（1）不存在重复边
（2）不存在顶点到自身的边
2、多重图
若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己相联，则G为多重图。多重图的定义和简单图是相对的。
3、完全图
在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。在有向图中，若任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条有向边。
4、连通：若顶点v到w有路径存在，则成v,w是连通的
连通图：若图中任意两个顶点都是联通的，则称图为连通图。
强连通：有向图中，若从顶点v到w和从顶点w到v之间都有路径，则称这两个顶点是强连通的。
有向图中的极大强连通子图称为有向图的强连通分量。
5、稀疏图：|E|<|V|log|V|
图的存储
1.邻接矩阵法，用矩阵表示，a[i][j]=1有边
2.邻接表法
3.十字链表
裸最短路
dijk：
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> using namespace std; const int N=105; const int INF=0x3f3f3f3f; int cost[N][N]; int d[N],vis[N],n,m; void dijk(){ d[1]=0; for(int j=1;j<=n;j++){ int v=-1; //每次选一个到源点最近的点 for(int i=1;i<=n;i++){ if(!vis[i]&&(v==-1||d[i]<d[v])){ v=i; } } vis[v]=1; for(int i=1;i<=n;i++){ if(d[i]>d[v]+cost[v][i]){ d[i]=d[v]+cost[v][i]; } } } } void init(){ memset(d,INF,sizeof(d)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cost[i][j]=INF; } } } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ if(m+n==0)break; init(); int a,b,c; while(m--){ scanf("%d%d%d",&a,&b,&c); if(cost[a][b]>c){ cost[a][b]=c; cost[b][a]=c; } } dijk(); printf("%d\n",d[n]); } }bellman：
检查是否存在负环：如果在进行过n-1次松弛操作后还存在可以松弛的边，那么说明有负环。
（如果没有负环的话松弛操作完后，d[i]就表示点i到原点最小的长度，还能再松弛说明有一个边是负的）
时间复杂度：O(VE)，用队列优化复杂度为O(kE)，k为每个节点入队次数，也就是SPFA算法。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> #define ll long long using namespace std; const int N=105,M=10005; const int INF=0x3f3f3f3f; struct A{ int from,to,cost,nex; }edge[2*M]; int n,m,cnt=0,head[N],d[N]; void add(int from,int to,int cost){ edge[cnt].from=from; edge[cnt].to=to; edge[cnt].cost=cost; edge[cnt].nex=head[from]; head[from]=cnt++; } int bellman(){ int flag; d[1]=0; for(int i=1;i<=n;i++){ flag=0; for(int j=0;j<cnt;j++){ if(d[edge[j].to]>d[edge[j].from]+edge[j].cost){ d[edge[j].to]=d[edge[j].from]+edge[j].cost; flag=1; } } if(!flag)break; } for(int i=0;i<cnt;i++){//判负环 if(d[edge[i].to]>d[edge[i].from]+edge[i].cost){ return 1; } } return 0; } void init(){ cnt=0; memset(head,-1,sizeof(head)); memset(edge,0,sizeof(0)); memset(d,INF,sizeof(d)); } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ if(m+n==0)break; init(); int a,b,c; while(m--){ scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } bellman(); printf("%d\n",d[n]); } }裸最小生成树
prim：
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> using namespace std; const int N=105; const int INF=0x3f3f3f3f; int cost[N][N]; int d[N],vis[N],n; int prim(){ for(int i=1;i<=n;i++){ d[i]=INF; vis[i]=0; } d[1]=0; int res=0; for(int j=1;j<=n;j++){ int v=-1; for(int i=1;i<=n;i++){ if(!vis[i]&&(v==-1||d[v]>d[i]))v=i; } vis[v]=1; res+=d[v]; for(int i=1;i<=n;i++){ d[i]=min(d[i],cost[v][i]); } } return res; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&cost[i][j]); } } int res=prim(); printf("%d\n",res); }kruskal：
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> #include<algorithm> using namespace std; const int N=105; const int INF=0x3f3f3f3f; int cost[N][N]; struct A{ int from,to,cost; }edge[N*N]; int n,cnt=0,pre[N]; void add(int from,int to,int cost){ edge[cnt].from=from; edge[cnt].to=to; edge[cnt++].cost=cost; } int f(int x){ if(x==pre[x])return x; pre[x]=f(pre[x]); return pre[x]; } int cmp(A a,A b){ return a.cost<b.cost; } int main(){ scanf("%d",&n); int c; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&c); add(i,j,c); } } for(int i=1;i<=n;i++)pre[i]=i; sort(edge,edge+cnt,cmp); int ans=0,flag=0; for(int i=0;i<cnt;i++){ int fx=f(edge[i].from); int fy=f(edge[i].to); if(fx!=fy){ pre[fx]=fy; ans+=edge[i].cost; flag++; } if(flag==n-1)break; } printf("%d\n",ans); }排序分类：
内部排序：指待排序记录存放在计算机随机存储器中进行的排序过程。
外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中需对外存进行访问的排序过程。
思想：
有序序列L[1..i-1]把L[i]插入到其中，无序序列L[i+1]
（1）查找出L[i]在L[1..i-1]中的位置k
（2）L[k..i-1]中的元素全部后移
（3）L[i]复制到L[k]
时间复杂度：
（1）有序情况下：
进行n-1次比较，不移动。
（2）无序情况下：
比较次数：(n+2)(n-1)/2 即，
移动次数：(n+4)(n-1)/2 即，
（3）总的来说时间复杂度是O(n^2)
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> #include<algorithm> using namespace std; const int N=105; int a[11]={0,10,9,8,7,6,5,4,3,2,1}; void insert_sort(int a[]){//a[0]空着不用 for(int i=2;i<=10;i++){ if(a[i]<a[i-1]){//与有序表中的最大的元素比较 a[0]=a[i]; int j; for(j=i-1;a[0]<a[j];j--){ a[j+1]=a[j]; } a[j+1]=a[0]; } } } int main(){ insert_sort(a); for(int i=1;i<=10;i++){ printf("%d ",a[i]); } printf("\n"); }希尔排序（Shell's Sort），又称“缩小增量排序”，也是一种插入类排序方法，但是时间效率上有较大改进。
插入排序在数据规模小且基本有序时效率高。
希尔排序在数据规模大且无序时效率高。
学习博客
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> #include<algorithm> using namespace std; const int N=105; int a[10]={10,9,8,7,6,5,4,3,2,1}; int n=10; /* 将a[i]插到所在分组的正确位置上 */ void insertI(int a[],int gap,int i){ int inserted=a[i]; int j=i-gap; for(;j>=0&&inserted<a[j];j-=gap){ a[j+gap]=a[j]; } a[j+gap]=inserted; } void Shell_sort(int a[]){ int n=10; for(int gap=n/2;gap>0;gap/=2){ for(int i=gap;i<n;i++){ insertI(a,gap,i); } } } int main(){ Shell_sort(a); for(int i=0;i<10;i++){ printf("%d ",a[i]); } printf("\n"); }思想：
假设表长为n，从后往前两两比较，若a[i-1]<a[i]则交换，没一趟冒泡，是把最小的元素交换到序列的正确的位置。
时间复杂度：
（1）有序情况下，进行n-1次比较，不移动。
（2）无序情况下，进行 次比较和移动。
（3）总的来说时间复杂度是O(n^2)
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> #include<algorithm> using namespace std; const int N=105; int a[10]={10,9,8,7,6,5,4,3,2,1}; int n=10; void bubble_sort(int a[]){ for(int i=0;i<n-1;i++){//进行n-1次冒泡 int flag=0; for(int j=n-1;j>i;j--){ if(a[j-1]>a[j]){ swap(a[j-1],a[j]); flag=1; } } if(!flag)break; } } int main(){ bubble_sort(a); for(int i=0;i<10;i++){ printf("%d ",a[i]); } printf("\n"); }是对冒泡排序的一种改进。
思想：
通过一趟排序将待排记录分成独立的两部分，其中一部分记录的关键字比另一部分记录的关键字小，这个分别对这两部分记录继续进行排序，以达整个序列有效。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> #include<algorithm> using namespace std; const int N=105; int a[10]={10,9,8,7,6,5,4,3,2,1}; int n=10; int Partition(int a[],int s,int e){ int i=s,j=e+1; int x=a[s]; while(1){ while(a[++i]<x&&i<e); while(a[--j]>x); if(i>=j)break; swap(a[i],a[j]); } a[s]=a[j]; a[j]=x; return j; } void quick_sort(int a[],int s,int e){ if(s<e){ int pos=Partition(a,s,e); quick_sort(a,s,pos-1); quick_sort(a,pos+1,e); } } int main(){ quick_sort(a,0,9); for(int i=0;i<10;i++){ printf("%d ",a[i]); } printf("\n"); }思想：
第i趟选择L[i..n]中最小的元素和L[i]交换，每趟排序可以确定一个元素的最终位置。
一共是n-1趟就可以排好序。
时间复杂度：
记录移动的次数：最少为0，最大为3(n-1)
比较次数均为：n(n-1)/2
总的时间复杂度是：O(n^2)
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> #include<algorithm> using namespace std; const int N=105; int a[10]={10,9,8,7,6,5,4,3,2,1}; int n=10; void select_sort(int a[]){ for(int i=0;i<n-1;i++){//第i趟排序，选择[i,n]最小的元素,并与a[i]交换 int pos=i; for(int j=i+1;j<n;j++){ if(a[j]<a[pos]){ pos=j; } } if(pos!=i)swap(a[i],a[pos]); } } int main(){ select_sort(a); for(int i=0;i<10;i++){ printf("%d ",a[i]); } printf("\n"); }递归到终点时，是单个元素，然后向上，两两有序数组合并到temp数组，然后把temp数组的值，复制到原数组中。
此外在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn).
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> #include<algorithm> using namespace std; const int N=105; int a[10]={10,9,8,7,6,5,4,3,2,1}; int temp[10]; int n=10; void Merge(int s[],int t[],int b,int m,int e){ int i=b,j=m+1,k=0; while(i<=m&&j<=e){ if(s[i]<=s[j])t[k++]=s[i++]; else t[k++]=s[j++]; } while(i<=m){ t[k++]=s[i++]; } while(j<=e){ t[k++]=s[j++]; } for(int i=0;i<k;i++){ s[b+i]=t[i]; } } int Msort(int s[],int t[],int b,int e){ if(b<e){ int m=(b+e)>>1; Msort(s,t,b,m); Msort(s,t,m+1,e); Merge(s,t,b,m,e); } } int main(){ Msort(a,temp,0,9); for(int i=0;i<10;i++){ printf("%d ",a[i]); } printf("\n"); }