数据结构复习
目录
第一章 绪论
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###
*/- 先序遍历：
因为每次都最先访问其根节点，所以根节点不用存储，只用栈存右结点
（用栈就是为了帮我们保存还没有被访问的地址，以便将来我们能找到返回的地址）。
- 中序遍历：
扫描根节点将其入栈，然后一直入栈其左子结点，直到入栈了叶子结点（其左结点为空）
出栈一个结点，并访问，然后扫描其右子结点，将其入栈，再扫描其右子结点的左节点并入栈，如此继续，直到栈空。
- 后序遍历：
对于一个结点，可以访问它的条件是：左右子树已经遍历完
所以要一个标志位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)
嘻嘻，然后来快乐的水两道题：
平衡二叉树
平衡二叉树（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");
}