数据结构是重中之重，但是由于我在练习或比赛时一直对stl的频繁使用，似乎让我越来越对基础数据结构的代码能力越来越薄弱，由此重新开始练习基础。
以《数据结构C（第二版）》严蔚敏、李冬梅老师书为训练基础。
复杂度
时间复杂度
其实就是找循环和n有关的执行次数。
logn2的时间复杂度：
for(int i=0;i<=n;i=i*2){
x++;
}
//2^n<=n f(n)=log2n
空间复杂度
其实就是找需要借助的大小n的复杂度
例如逆序交换时只用一个数，与n的规模无关，则为O1。
若是要用n大小数组，则为On。
程序设计要点
1.不允许使用stl库，所以所有的数据结构都要自己编写所以基本用C来完成。
2.对异常情况的处理，由于数据结构的书中会考虑许多不满足条件的情况以增加程序健壮性，所以基本上函数都是有int型返回值的，虽然不一定接受，可能这样更严谨吧。
//常用的返回值大概有三类
#define ok 1
#define error 0
#define overflow -2
线性表
线性表中主要有两种结构：顺序表和链表。
顺序表
顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。
顺序表的存储结构
线性表可以根据需要增长或缩短，所以并不是简单的数组可以用来表示（在C语言中数组的给定需要提前给出长度，所以这里的感觉更像是stl中的vector）。
struct sqlist{
node *elem; //当前空间的基地址
int length; //当前长度
};
顺序表的初始化
完成两件事：
1.为顺序表L分配一个预定大小的数组空间maxn（涉及内存分配的问题需要使用if来判断一下是否分配失败），用elem指向这段空间的基地址。
2.将长度length设为0。
int InitList(sqlist &L){
L.elem = new node[Mansize]; //为顺序表分配存储空间
if(!L.elem) return overflow;
L.length = 0;
return ok;
};
顺序表的取值
完成两件事：
1.判断指定的位置序号是否合理（1<=i<=L.length）;
2.若i合理则返回给一个&数;
int GetElem(sqlist &L,int i,node &e){
if(i<1 || L.length) return error;
e = L.elem[i-1];
return ok;
}
顺序表的查找
返回查找到的序号
完成两件事：
1.依次比较，相等则返回序号
2.找不到返回0
int find(sqlist &L,node e){
for(int i=0;i<L.length;i++)
if(L.elem[i] == e) return i+1;
return 0;
}
顺序表的插入
返回查找到的序号
完成五件事：
1.判断插入位置是否合法。
2.判断存储空间是否已满。
3.将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置。
4.放入元素在第i个位置。
5.表长加1。
int LisrInsert(sqlist &L,int i,node e){
if((i<1)||(i>L.length+1)) return error;
if(L.length == Mansize) return error;
for (int j = L.length-1; j > i-1 ; j--)
{
/* code */
L.elem[j+1]=L.elem[j];
}
L.elem[i-1]=e;
L.length++;
return ok;
}
顺序表的删除
返回查找到的序号
完成三件事：
1.删除位置是否合法。
2.i+1个往前移。
3.表长减1。
int LisrDelete(sqlist &L,int i){
if (i<1||i>L.length) return ERROR;
for (int j = i; j<= L.length-1; i++)
{
L.elem[j-1]=L.elem[j];
}
L.length--;
return ok;
}
求两个升序序列的中位数的优秀算法
之前我想的是使用链表存储以后，进行一次合并的操作，再进行n次->next的操作即可，但是合并操作的时间复杂度是O（n）,这里学会一种自由O(log2n)的写法。
画图更加明晰
想法：
（1）还是使用顺序表来做，分别求出两个序列的中位数记为a，b。这里需要说明的是求法就是(startIndex+endIndex)/2，因为整数除法会取小的那个。
（2）比较a和b有三种情况：
1.a=b:a即为中位数。
2.a<b:舍弃a之前的元素，即调整as。 舍弃b之后的元素，即调整be； 3.a>b:舍弃a之后的元素，即调整ae。 舍弃b之前的元素，即调整bs；
tip:需要注意的是，调整并不是简单的像二分查找一样划等号，因为当是偶数个数量的时候，如果要的是后半段的数据那其实as会等于mid+1，所以一定要画图找准位置。
链表
顺序表指的是用一组地址任意的（可连续，可不连续）存储单元依次存储线性表的数据元素。
链表的存储结构
线性表可以根据需要增长或缩短，所以并不是简单的数组可以用来表示（在C语言中数组的给定需要提前给出长度，所以这里的感觉更像是stl中的vector）。
const int
typedef struct Lnode{
elem data; //当前空间的基地址
Lnode *next; //当前长度
}Lnode,*LinkList;
单链表的初始化
其实就是完成对头结点的初始化。
void InitList(LinkList &l){
l = new Lnode;
l->next = NULL;
}
单链表的取值
1.用指针p指向首元结点。计数器j=1.
2.只要p不为NULL并且未到达i，p就指向下一个结点，并且计数器+1.
3.若p为NULL或j大于i这失败，若成功则改变参数e.
int GetElem(LinkList &l,int i,elem &e){
LinkList p;
p = l->next;j=1;
while(p && j<i){
p=p->next;
j++;
}
if(!p||j>i) return error;
e = p->data;
return ok;
}
单链表的查找
1.p指向首元结点.
2.只要p不为NULL并且不等于e，p就指向下一个结点.
3.若p为NULL或j大于i这失败，若成功则改变参数e.
int GetElem(LinkList l,int i,elem e){
LinkList p;
p = l->next;
while(p && p->data != e){
p=p->next;
}
return p;
}
单链表的插入
1.查找结点i-1并让p指向.
2.生成一个新结点s.
3.将数据域设为e.
4.将新结点的指针域指向i.
5.将p指向s.
int GetElem(LinkList &l,int i,elem &e){
LinkList p,s;
p = l->next;j=0;
while(p && j<i-1){
p=p->next;
j++;
}
if(!p||j>i-1) return error;
s = new Lnode;
s->node = e;
s->next = p->next;
p->next = s;
return ok;
}
单链表的删除
1.查找结点i-1并让p指向.
2.临时保存待删结点i的地址在q中，以备释放.
3.将结点p的指针域指向i的直接后继结点.
4.将新结点的指针域指向i.
int GetElem(LinkList &l,int i){
LinkList p,q;
p = l->next;j=0;
while(p && j<i-1){
p=p->next;
j++;
}
if(!p||j>i-1) return error;
q=p->next;
p->next = q->next;
delete q;
return ok;
}
单链表的创建
之前顺序表的创建是可以直接赋值的，但是链表的创建一般是靠两种方法。
（1）前插法
将结点插入头结点之后来创建链表的方法。
1.首先初始化，得到一个只有头结点的空链表。
2.循环n次：生成一个新结点p，输入数据域，将p插入到头结点之后。
ps：需要注意的是，由于每次插入是在头部，所以需要逆序输入数据。
void creat_h(LinkList &l,int n){
l = new Lnode;
l->next = NULL;
for (int i = 0; i < n; ++i)
{
p = new Lnode;
cin >> p->data;
p->next = l->next;
l->next = p;
}
}
(2)后插法
为了使每次都插到最后需要一个尾指针。
1.首先初始化，得到一个只有头结点的空链表。
2.尾指针r初始化，指向头结点。
3.循环n次：生成一个新结点p，输入数据域，指针域为空，将新结点p插入到尾结点r之后，指针r指向尾结点p。
void creat_r(LinkList &l,int n){
l = new Lnode;
l->next = NULL;
LinkList r,p;
r = l;
for (int i = 0; i < n; ++i)
{
p = new Lnode;
cin >> p->data;
p->next = NULL;
r->next = p;
r=p;
}
}
链表的排序
总的来说还是冒泡排序，但是不能像顺序表那样直接选择这时候就需要再使用一个指针来代替。
for(int i=0; i<l.length-1 ;i++){
//i、j次数不变，但是需要用指针指到第一个数据
LinkList p = l->next;
for (int j = 0; j < l.length-i-1 ; j++)
{
if (p->data.price < p->next->data.price) {
//并不需要复杂的换位置，直接交换结点数据内容即可
book t = p->data;
p->data = p->next->data;
p->next->data = t;
}
p=p->next;
//通过指向下一个来完成一次循环中的向后迁移
}
}
两个链表的合并
比较过程比较简单就不再赘述，但是有一个最后的点需要注意一一下，就是当q或p有一个为NULL之后的处理：
c->next = x1?x1:x2;
//好简洁牛逼的写法哈哈哈
单链表的逆序
单链表的逆序最少需要用到四个指针，头指针l，h=l，t=h->next,s=t->next;
完成指针指向的逆转，而不仅仅还是data的换位，逆转后把头指针移到末尾，头结点还在原来的位置，所以当输出时要提前判定一个node位。
一定要画图梳理清楚。
查找两个单词链表共同后缀的起始结点
使用前插法得到倒序的单词序列，在遍历时需要提前一个节点进行检查，若不想等则现在指向的节点就是答案。
循环链表
最后一个结点的指针指向头结点，也就意味着头节点其实背两个指针共同指向（头指针、最后一个结点的指针），也可以发现没有结点的next为NULL。
没有结点时头节点的next也指向本身。
循环链表在操作上与单链表差不多，但是遍历时需要判定的是p！=L。
双向链表
为了克服链表的单项性，设计双向链表，存储结构如下，多了直接前驱：
typedef struct Lnode
{
elem data;
Lnode *prior; //直接前驱
Lnode *next;
}*LinkList;
顺序表和链表比较
空间性能
1.存储空间的分配
顺序表存储空间需要先分配，扩充受限制，而且易造成空间浪费。当线性表长度变化大、难以预估存储规模时，宜采用链表作为存储结构。
2.存储密度的大小
链表的结点处了设置数据与用来存储元素外还需设置指针域，所以顺序表密度等于1，链表密度小于1。当线性表长度变化不大、事先确定大小时，为了节约空间适合采用顺序表作为存储结构。
时间性能
1.存取效率
顺序表由数组实现，是一种随机存储结构，取值效率高。链表是一种顺序存储结构，存取元素时只能依次遍历，效率比较低。若需多次存取操作，最好选择顺序表。
2.插入删除效率
对于链表，在确定插入删除位置后，插入删除操作无需移动数据，只需修改指针。而顺序表的插入删除操作平均需要移动一半的节点，时间复杂度较高。因此若线性表需要频繁的进行插入删除操作，宜采用链表作为存储结构。
线性表应用
线性表的合并
算法步骤：
1.分别获取A表长m，B表长n。
2.从B中第一个元素开始，循环n次执行以下操作：
将B中的第i个元素赋给e。
将A中查找元素e，如果不存在就插在A的最后。
相当于以一个链表为基准去遍历另一个链表一次，时间复杂度为O(nm)。
有序表的合并
1.顺序表的合并
创建一个m+n的空表C
pc初始化，指向C的第一个元素
pa、pb也初始化，指向A、B的第一个元素
当指针pa、pb均为到达相应表尾时，则依次比较pa和pb的元素值，从A、B中选择较小的插入到C最后
如果pb/pa到达尾部，将LA/LB的剩余元素插入LC之后
不是很常用，因为空间复杂度较高。要点就是要重新创建一个顺序表。
2.链表的合并
算法步骤：
指针pa、pb分别指向A、B的第一个结点。
C的节点取值为LA的头结点。
pc初始化，指向C的头结点。
当指针pa合pb均未到达相应表尾时，依次比较pa、pb说指向元素的值，选择较小的元素值插入到C的最后。
将非空表剩余段插入到pc所指的结点之后。
释放B的头结点。
void MergeList(LinkList &a,LinkList &b,LinkList &c){
LinkList pa = a->next,pb = b->next,pc;
c = a;
pc = c;
while(pa && pb){
if (pa->data <= pb->data)
{
pc->next = pa;
pc=pa;
pa=pa->next;
}
else{
pc->next = pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
delete b;
}
案例分析
一元多项式
一元线性表可以用数组来表示，数组分量下标i即对应每项的系数，再运算时只要把两个数组对应的分量相加即可。
稀疏多项式
稀疏多项式的相加过程和归并两个有序表的过程及其类似，此过程常用链式存储结构更加灵活，(有点类似于稀疏图使用邻接表，而不是用邻接矩阵来描述一样)更适合表示一般的多项式，其中结点要进行一些变化。
typedef struct PNode{
float c; //系数
int e; //指数
Pnode *next;
}*LinkList;
由此，在稀疏多项式相加时可以模拟链表归并的过程，因为稀疏多项式的项顺序是以系数递增或递减排列的，
OJ练习
栈和队列
顺序栈
仅能在表尾进行插入和删除操作的线性表。栈可以进栈和出栈的一端称为栈顶，最里面的一端称为栈底。
顺序栈的表示和实现
顺序栈是指利用顺序存储结构实现的栈，结构体的创建类似于顺序表，里面存在指针变量，代表地址。顺序栈定义如下：
#define MAXSIZE 100
typedef struct
{
ElemType *base; //栈底指针，初始化完成后，base始终指向栈底为止
ElemType *top; //栈顶指针，初值指向栈底
int stacksize; //栈最大容量,s.top-s.base就可以得到容量
}SqStack;
顺序栈的初始化
1.为顺序栈分配一个MAXSIZE的数组空间,并判断内存分配情况。
2.使base指向这段空间的基地址，即栈底。
3.top指向base，表示栈空。
4.stacksize表示为最大容量MAXSIZE。
int InitStack(SqStack &s){
s.base = new ElemType[MAXSIZE];
if(!s.base) exit(error);
s.top=s.base; //top指针指向刚刚开辟的空间
s.stacksize = MAXSIZE; //stacksize保存的是最大容量
return ok;
}
顺序栈的入栈
1.判断栈是否满
2.将元素压入栈顶，栈顶指针加1
ps：指针变量支持自增和自减操作，例如指针变量p+1代表p所指的int型变量的下一个int型变量地址，所以由此也可以完成类似数组遍历的操作。
int Push(SqStack &s,ElemType e){
if(s.top-s.base == s.stacksize) return error;
*s.top++ = e; //自增运算符的优先级高于*，此表达式等价于*(s.top++)=e;
return ok;
}
顺序栈的出栈
1.判断栈是否为空
2.栈顶指针减1，栈顶元素出栈
int Pop(SqStack &s,ElemType &e){
if(s.top == s.base) return error;
e = *--s.top;
return ok;
}
取栈顶元素
需判断非空情况。
ElemType Top(SqStack s){
if (s.top!=s.base)
{
return *(s.top-1);
}
}
链栈
链栈是指采用链式存储结构实现的栈。通常链栈用单链表来表示。
链栈的表示和实现
为了方便栈的插入和删除，一般以链表的头部作为栈顶，所以没必要附加一个头结点。
typedef struct StackNode{
ElemType data;
StackNode *next;
}*LinkStack;
链栈初始化
其实就是让指针指空即可，可以不用写为一个函数。
void InitStack(LinkStack &s){
s = null;
}
链栈的入栈
void Push(LinkStack &s,ElemType e){
LinkStack p;
p->data=e;
p->next=s;
s = n;
}
取栈顶元素
ElemType Top(LinkStack s){
if (s!=NULL)
return s->data;
}
案例分析
数制的转换
由于数制转换的输出是需要从前至后遍历，所以可以借助栈结构来表示。
//10进制转8进制
void conversion(int N){
InitStack(s);
while(N){
Push(s,N%8);
N /= 8；
}
while(!stackEmpty(s)){
Pop(S,e);
cout<<e;
}
}
括号匹配
1.初始化一个空栈
2.设置一标记性变量flag，用来标记匹配结果
3.依次读入字符，若是’[‘或者’(‘则入栈。若是右括号，栈内非空且为相应的左括号则匹配成功
bool matching(){
InitStack(s);
bool flag = true;
cin >> ch;
while(ch!='#' && flag){
switch(ch){
case'['||'(':
Push(s,ch);
break;
case']':
if(!stackEmpty(s)&&Top(s)=='[')
Pop(s,x);
else
flag = false;
break;
case')':
if(!stackEmpty(s)&&Top(s)=='(')
Pop(s,x);
else
flag = false;
break;
}
cin >> ch;
}
return flag;
}
表达式求值
表达式由操作数、运算符和界限符组成。
归纳运算规则为：
1.先乘除，后加减。
2.从左算到右。
3.先括号内，后括号外。
OPTR寄存运算符。
OPND寄存操作数及运算结果。
算法步骤：
1.初始化OPTR和OPND栈，将表达式起始符“#”，压入OPTR栈。
2.扫描表达式：读取第一个字符ch，如果表达式没有扫描完毕至“#”或OPTR的栈顶元素不为“#”时，则循环执行以下操作：
若ch不是运算符，压入OPND栈，读如下一字符ch；
若ch是运算符，根据OPTR的栈顶元素和ch的优先级比较结果做不同处理：
若小于，则ch压入OPTR栈，读入下一字符ch；
若大于，则弹出OPTR栈顶元素，从OPND栈弹出两个数，进行相应运算，结果压入OPND栈。
若等于，则OPTR的栈顶元素是“（”且ch是“）”，这时弹出OPTR栈顶的“（”，相当于括号匹配成功，然后读入下一字符ch。
3.OPND栈顶元素即为表达式求值的结果。
//需要记下来
char Precede(char a,char b){
if ((a =='(' && b == ')')||(a == '='&&b == '='))
return '='; //括号和等号的情况为等于
else if (a=='(' || a=='=' || b=='(' || ((a=='+'||a=='-') && (b=='*'||b=='/')))
return '<'; //共四种小于情况：a、b的左括号情况，a的=情况，还有先乘除后加减的情况
else
return '>';
}
char EvaluateExpression(){
InitStack(OPND);
InitStack(OPTR);
Push(OPTR,'#');
cin >> ch;
while(ch!='#'||getTop(OPTR)!='#')
{
if (!In(ch)) {Push(OPTR,ch);cin>>ch;}
else
switch(Precede(Top(OPTR),ch))
{
case '<':
Push(OPTR,ch);cin>>ch;
break;
case '>':
Pop(OPTR,theta);
Pop(OPND,b);Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
case '=':
Pop(OPTR,x); cin>>ch;
break;
}
}
return Top(OPND);
}
数学知识
后缀表达式：又称逆波兰表达式。运算方法为数字入栈，有运算符则出栈两个数运算。
循环队列
队列的实现
#define MAXSIZE 100
typedef struct
{
ElemType *base; //存储空间的基地址
int front; //头元素的位置（后称头指针
int rear; //尾元素的位置（后称尾指针
}SqQueue;
初始化空队列时，front = rear = 0，每当插入一个元素时rear增1，每当删除队列头元素时候front就增加一。
为了解决“假溢出”问题，需要巧妙的将顺序队列变为一个环状空间，称为循环队列。具体的运算时通过“模运算”来完成。
由上图b发现若是所有元素都占满，那么队列的状态是q.front == q.rear，与空队相同，所以为了区分两种状态，队满时会少用一个空间来认为是队满。
由此可以得到两个判断队列起始和终止状态的条件：
队空：q.front == q.rear
队满：(q.rear+1)%MAXQSIZE == q.front
由于队列是队尾入队、队头出队，可能会导致“假溢出”现象，所以选择使用循环队列的方法来顺序表示和实现队列。
队列的初始化
1.分配数组空间，base指向首地址
2.首尾指针相等且为0
int InitQueue(SqQueue &q){
q.base = new ElemType[MAXQSIZE];
if(!q.base) return error;
q.front = q.rear = 0;
return ok;
}
求队列长度
int QueueLength(SqQueue q){
return (q.rear-q.front+MAXQSIZE)%MAXQSIZE;
}
循环队列的入队
1.判断队列是否满
2.将新元素插入队尾
3.队尾指针加1
int EnQueue(SqQueue &q,ElemType e){
if((q.rear+1)%MAXQSIZE == q.front) return error;
q.base[q.rear] = e;
q.rear = (q.rear+1)%MAXQSIZE;
return ok;
}
循环队列的出队
1.判断队列是否为空
2.保存队头元素
3.队头指针加1
int DeQueue(SqQueue &q,ElemType &e){
if(q.rear == q.front) return error;
e = q.base[q.front];
q.front = (q.front+1)%MAXQSIZE;
return ok;
}
循环队列的头元素获取
只需先判断队列是否为空
int DeQueue(SqQueue &q,ElemType &e){
if(q.front != q.rear){
return q.base[q.front];
}
}
链队
链队需要两个分别指向头尾的指针，线性表和单链表一样需要头节点（目前也就链栈不需要头节点）。
链队的存储结构
//节点
typedef struct QNode{
ElemType data;
QNode *next;
}*QueuePtr;
//链队
typedef struct
{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkList;
链队的初始化
1.生成一个头结点，队头和队尾指针都指向此节点。
2.头节点的指针域置空。
void InitQueue(LinkList &q){
q.front = q.rear = new QNode;
q.front->next = NULL;
}
链队的入队
void EnQueue(LinkList &q,ElemType e){
QueuePtr p;
p = new QNode;
p->data = e;
p->next = NULL;
q.rear->next = p;
q.rear = p;
}
链队的出队
int DeQueue(LinkList &q,ElemType &e){
if(q.front == q.rear) return error;
QueuePtr p;
p = q.front->next;
e = p->data;
q.front->next = p->next;
if(q.rear == p) q.rear = q.front; //最后一个元素被删，队尾指向头结点
delete p;
return ok;
}
链队的出队
int DeQueue(LinkList &q,ElemType &e){
if(q.front == q.rear) return error;
QueuePtr p;
p = q.front->next;
e = q->data;
q->front->next = p->next;
if(q.rear == p) q.rear = q.front;
delete p;
return ok;
}
链队的头元素
void Top(LinkList q){
if (q.rear == q.front)
return q.front->next->data;
}
案例分析
舞伴问题
对于伴舞配对问题，设置两个队列分别存放男士和女士，依次出队来配成舞伴，直至某队列变空为止。
typedef struct
{
char name[20];
char sex;
}Person;
//------队列的顺序结构-------
#define MAXQSIZE 100
typedef struct
{
Person *base;
int front;
int rear;
}SqQueue;
SqQueue Mdancers,Fdancers;
void DancePartner(Person dance[],int num){
InitQueue(Mdancers);
InitQueue(Fdancers);
for (int i = 0; i < num; ++i)
{
p=dancer[i];
if(p.sex=='F') EnQueue(Fdancers,p);
else EnQueue(Mdancers,p);
}
cout<<"The patners are:\n";
while(!queueEmpty(Fdancers)&&!queueEmpty(Mdancers)){
DeQueue(Fdancers,p);
cout<<p.name<<" ";
DeQueue(Mdancers,p);
cout<<p.name<<endl;
}
if (!queueEmpty(Fdancers))
{
p=getTop(Fdancers)
cout<<"The first women to get a partener is:"<<endl;
}
else if(!queueEmpty(Mdancers)){
p=getTop(Mdancers);
cout<<"The first man to get a partener is:"<<p.name<<endl;
}
}
串、数组和广义表
串的顺序存储
串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串和线性表的主要差别是在于基本操作中，线性表大多以单个元素为操作对象，例如在线性表中增删改查某个元素，串的基本操作中一般以串的整体作为操作对象，例如查找子串等。
串一般采用顺序存储，进行如下描述：
typedef struct{
char ch[MAXQSIZE+1];
int length;
}sstring;
BF算法：
这个算法理解起来简单，写起来有点裹，最好还是使用while结构，用i、j赋初值来写。
bool Judge(string x,string b){
int i,j,temp;
i = j = temp = 0;
while (i<x.length() && j<b.length()) {
if (x[i] == b[j]) {
i++ ;
j++ ;
}
else{
i = 0; //小的串回到起点
j = ++temp; //大的串从下一个开始匹配
}
}
if(i == x.length()) return true;
return false;
}
树和二叉树
二叉树性质
对所有二叉树都成立：
1.在第i层上至多有2^(i-1)个节点。
2.深度为k的二叉树最大节点数为2^i-1个。
3.对任意一棵二叉树T，如果其终端节点数为n0，度为2的节点数n2，n0=n2+1。
对完全二叉树（每个节点都和自己的位置对应，每层都满叫满二叉树）成立：
4.n个节点的完全二叉树的深度（层数）为 」log2n」+1.
5.如果对有一棵n个节点的完全二叉树的节点按层序编号从第一层开始编号，有如下性质：
（1）如果i=1，为根；如果i>1,其双亲是 」i/2」.
（2）如果2i>n，则无左孩子，否则左孩子为2i.
（3）如果2i+1>n，这无右孩子，否则右孩子是2i+1.
二叉树的顺序存储结构
顺序存储结构最大的特点就是使用一组地址连续的存储单元来存储数据元素，写的复杂其实就是用一个数组来表示，数组的大小就是节点的个数。
#define maxsize 100
typedef ElemType SqBiTree[MAXSIZE]; //maxsize代表结点个数
SqBiTree bt;
二叉树节点会依照一定的规律存储进单元中：
1.对于完全二叉树只需要考虑编号为i的节点按层序存储进结构中。
2.一般二叉树的存储类似于完全二叉树，用0来表示不存在的节点。
由此也可以看出顺序存储结构仅适用于完全二叉树。
二叉树的链式存储结构
最常见的二叉树链表的存储表示。
typedef struct BiTNode{
TElemType data;
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
二叉树创建
oj题目就是那种给一个序列让你用规定方式创建的，我感觉我写的时候脑子不清楚，记录一下，要记住的是每次都是在新地方操作，不是NULL就是创建新结点。
void createPre(linklist &t,char str[],int &index){
if (str[index] == '#') {
t = NULL;
}
else{
t = new node;
t->data = str[index];
t->left = NULL;t->right = NULL;
index++;
createPre(t->left,str,index);
index++;
createPre(t->right,str,index);
}
}
遍历二叉树
先序遍历： 根->左->右
中序遍历： 左->根->右
后序遍历： 左->右->根
以中序遍历为例，与先序遍历和后序遍历相比就是位置调换了。
```c++ //递归表示 void InOrder(BiTree t){ InOrder(t->left); cout«t->data; InOrder(t->right); }
//非递归表示 void InOrder(BiTree t){ InitStack(S); p=T; q=new BiTNode; while(p||!stackEmpty(s)){ if(p){ Push(S,p); p=p->left; } else{ Pop(S,q); cout«q->data; p=q->right; } } }
### 根据遍历确定二叉树
之前的遍历是在已有二叉树的结构上遍历获取值，该过程是针对已有的遍历结果来创建二叉树，由于此过程需要说明为空的节点，所以可以用一个#自负表示空树。
```c++
void CreateBiTree(BiTree &T){
cin >> ch;
if(ch == '#') T=NULL;
else{
T = new BiTNode;
T->data = ch; //复制二叉树也是同理，只是此处的值来源是树
CreateBiTree(T->left);
CreateBiTree(T->right);
}
}
计算二叉树的深度
采用递归的思想来完成，二叉树的深度为左右子树深度较大者加1.
int Depth(BiTree T){
if(T == NULL) return 0;
else{
int m = Depth(T->left);
int n = Depth(T->right);
if(m>n) return m+1;
else return n+1;
}
}
统计二叉树中节点的个数
如果是空树放回0，否则就放回左子树+右子树+1（该节点）。
int NodeCount(BiTree t){
if(t == NULL) return 0;
else return NodeCount(t->left) + NodeCount(t->right)+1;
}
线索二叉树
线索二叉树是什么？解决什么问题？
在以二叉链表作为存储结构时，只能找到节点的左、右孩子信息，而不能直接得到节点在任一序列（前、中、后）中的前驱和后继信息，这种信息只有在便利的动态过程才能得到，引入线索二叉树就是为了保存在动态便利过程中得到的前驱和后继信息。
表示方式？
由于每个节点中再增加两个指针域来表示前驱和后继会使得存储密度大大降低，而其实n个节点的二叉链表中必定存在n+1个空链域，因此利用空链域来存放节点的前驱和后继信息。
如何规定？
typedef struct BiTreeNode{ Elem data; BiThrTree *left,*right; int LTag,RTag; //LTag = 0 left指向左孩子 LTag = 1 left指向前驱 //RTag = 0 right指向右孩子 RTag = 1 right指向后继 }BiTNode,*BiThrTree;若节点有左子树，left就是指左孩子，否则令left指向前驱；若节点有右子树，则其right域指右孩子，否则令right域指向后继。 同时为了避免混淆，增加两个标志域LTag,RTag。
哈夫曼树
- 存储表示
哈夫曼树又称最优树，是一类带权路径长度最短的树。根据给定的n个权值{w1,w2,···,wn},其实就是一直找最小的节点然后组成树（小的在左边，大的在右边）。
typedef struct{
int weight;
int parent,left,right;
}HTNode,*HuffmanTree;
哈夫曼树的各节点存储在定义的动态分配的数组中，为了实现翻倍，数组的0号单元不适用，从1号单元开始使用，所以数组的大小为2n。 其中叶子节点在1～n个位置，后面的n-1个位置存储非叶子节点。
- 构造哈夫曼树
构造哈夫曼树分为两部分(其实就是一个填写二维数组的过程)：
（1）初始化：首先动态申请2n个单元；然后循环2n-1次，从1号单元开始，依次将1至2n-1所有单元中的父节点、左孩子、右孩子的下标都初始化为0；最后再循环n次，输入前n个单元中叶子结点的权值。
（2）创建树：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。选择是从当前森林中选择父亲节点为0且权值最小的两个树根节点s1和s2；删除是指将节点s1和s2的父节点改为非0；合并就是将s1和s2的权值和作为一个新节点的权值一次存储到数组的第n+1之后的单元中，同时记录这个新节点左孩子下标为s1，右孩子的下标为s2。
//select函数用来查找哈夫曼数组里面最小的两个数
void select(ht t,int n,int &s1,int &s2){
//找最小的两个数，我之前的思路都是初始化后比较，但是如果第二个数在第一个数找到前就随意初始化会导致出现一定问题找不到，所以还是得一个个找，然后用不等于第一个数的思路来解决
int i;
for (i=1; i<=n; i++) {
if (!t[i].parent) {
break;
}
}
s1 = i;
for (int j=s1+1; j<=n; j++) {
if (!t[j].parent && t[j].data < t[s1].data) {
s1 = j;
}
}
int k;
for (k=1; k<=n; k++) {
if (!t[k].parent && k!=s1) {
break;
}
}
s2 = k;
for (int j=s2+1; j<=n; j++) {
if (!t[j].parent && t[j].data < t[s2].data && j!=s1) {
s2 = j;
}
}
}
void CreateHuffmanTree(HuffmanTree &HT,int n){
//构造哈夫曼树HT
if(n<=1) return;
HT=new HTNode[2*n];
for (int i = 1; i <= 2*n; ++i)
{
HT[i].parent = 0;
HT[i].left = 0;
HT[i].right = 0;
}
for (int i = 1; i <= n; ++i)
{
cin >> HT[i].weight;
}
//创建哈夫曼树
for (int i = n+1; i < 2*n; ++i)
{
//通过n-1次的选择、删除、合并来创建哈夫曼树
Select(HT,i-1,s1,s2);
//在HT[k]（1<=k<=i-1）中选择两个其双亲域为0且权值最小的节点，并返回她们在HT中的序号s1和s2
HT[s1].parent=i;HT[s2].parent=i;
HT[i].left=s1;HT[i].right=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
- 哈夫曼编码
主要是想：为了使压缩后的数据文件尽可能短，采用不定长编码。基本思想是：为出现次数比较多的字符赋予较短的编码。采用二进制编码，在构造的哈夫曼树中，左分支记为0，右分支记为1，根节点到每个叶子节点路径上的0、1序列即为相应字符的编码。
利用二叉树求解表达式的值
中缀表达式创建表达式树的方法：
假设运算符均为双目运算符，表达式树中的叶子节点为操作数，分支节点均为运算符。表达式树需要准确的表达运算次序，因此在表达式树的创建过程中不能直接创建节点，而应将其与前面的运算符进行优先级比较，根据比较的结果再进行处理。（所以需要用到一个运算符栈）
最后完成表达式树的创建：
void InitExpTree(){
InitStack(EXPT);
InitStack(OPTR);
Push(OPTR,'#');
cin >> ch;
while(ch!='#' || GetTop(OPTR)!='#'){
if (!In(ch)) //ch不是运算符
{
CreateExpTree(T，NULL，NULL,ch);
//以ch为根创建一颗只有根结点的二叉树
Push(EXPT,T);
//二叉树根节点T进EXPT栈
cin >> ch;
}
else{
switch(Precede(GetTop(OPTR),ch))
{
case '<':
Push(OPTR,ch);cin>>ch;
break;
case '>':
Pop(OPTR,theta); //弹出运算符
Pop(EXPT,b);Pop(EXPT,a); //弹出栈顶的两个运算数
CreateExpTree(T,a,b,theta);
//以theta为根，a为左子树，b为右子树，创建一颗二叉树
Push(EXPT,T);
break;
case '=':
Pop(OPTR,x);cin>>ch;
break;
}
}
}
}
小结：
1.需要两个栈，一个用来存储节点（只可能是运算符号），一个用来存储二叉树（二叉树表示一个一个运算数字或者是一个结果）。
2.扫描整个字符串，如果是数字就生成一个左右孩子为空的二叉树，让二叉树入栈。
3.如果不是数字就比较节点顶端的字符和现在这个字符的优先级
（ = 的情况有两种，一个是a是左括号，b是右括号；一个是两个都是等号）
弹出字符栈即可。
（ < 的情况有四种，a、b都是左括号；a是等号；a是加减b是乘除）
字符入栈即可。
（ > 其余均是大于情况）
弹出两个数字树和一个运算符组合成新的树，并让新数入栈。
表达式树的求值：
在构造好表达式树后要求值，需要走到最末端节点才能算，一个值要想计算就要先算出其左子树和右子树为多少才能进行接下来的计算。
int value(tree t){
int l,r;
l = 0;r = 0;
if (!t->left && !t->right) {
return t->data-'0';
}
else{
l = value(t->left);
r = value(t->right);
if (t->data == '+') return l+r;
else if(t->data == '-') return l-r;
else if(t->data == '*') return l*r;
else{
return l/r;
}
}
}
整个过程其实和直接用栈的类似。
图
图的存储结构
1.邻接矩阵表示法
#define maxint 32767
#define maxnum 100
typedef struct{
char vexs[maxnum]; //一个顶点表
int arcs[maxnum][maxnum]; //一个邻接矩阵
int nodenum,sidenum;
//节点数和边数
}graph;
构造的过程其实就是不断的输入，注意区分是否有向即可。
不适合稀疏图。
2.邻接表表示法
说白了就是一个指针数组，数据域代表顶点号，若是网（即带权图），则需要另一个数据域用来存储权值，需要注意的是若是无向图则需要创造两次节点赋值。
#define maxnum 100
typedef struct Lnode{
int data;
//若有权值还需要加权值
Lnode *next;
}Lnode,*LinkList;
typedef struct {
int vernum;
int arcnum;
LinkList v[maxn];
}graph;
构造过程输入即可，用于稀疏图的创建。
图的搜索
在大佬室友的帮助下我知道了一份方法可以避免搜索增加效率并减少代码量：
由于有时候图中的节点使用字母表示的，但是在不允许使用map的情况下我还需要用一个子函数来找到字母在顶点集合中的位置然后返回，但是其实，ascii码表上的字符一共只有128个，这也就意味着当表示顶点的字符是确定的时候，可以使用：
v['c'] = 1;
这种形式来表达，编译器就会进行强制类型转换，则达到类似于map的效果！
厉害厉害。
DFS
bool visit[maxnum];
void DFS(graph g,int v){
visit[v] = true;
for (w = firstAdjvex(G,VertexNode); w>=0; w=nextAdjVex(G,v,w))
//遍历相连接的所有节点
if (!visit[w])
dfs(g,w);
}
一般我是用dfs都是针对邻接矩阵，今天在做要求使用邻接表的dfs时突然不太会了，原因在于我在构建邻接表的时候使用的尾插法，会导致顺序乱这一问题，这里记录一下邻接矩阵的写法。
int visit[maxn];
int Stack[maxn];
int top = 0;
//就不一定非要递归调用dfs才叫dfs，只要遵循栈的思想，甚至这是一个最简单的模拟栈。
void dfs(graph g,int x){
visit[x] = true;
Stack[top++] = x;
while(top > 0){
LinkList t = g.v[Stack[top-1]];
int y = -1;
while (t) {
if (!visit[t->data]) {
y = t->data;
}
t=t->next;
}
if (y == -1) {
top--;
}
else{
Stack[top++] = y;
cout<<" "<<y;
visit[y] = true;
}
}
cout<<endl;
}
今天试了一下，不用数组代替栈也能写滴嘿嘿。
//其中 需要g、nmk是全局变量。
void dfs(linklist t,char end,int num){
visit[t->data] = true;
if (t->data == end && k == num) {
flag = true;
}
linklist p = g.v[t->data]->next;
while (p) {
if (!visit[p->data]) {
dfs(p,end,num+1);
}
p = p->next;
}
visit[t->data] = false;
}
BFS
bool visit[maxnum];
void BFS(graph g,int v){
visit[v] = true;
InitQueue(q);
EnQueue(q,v);
while(!queueEmpty(q)){
DeQueue(q,u);
for (w = firstAdjvex(G,VertexNode); w>=0; w=nextAdjVex(G,v,w))
if (!visit[w])
{
visit[w] = true;
EnQueue(Q,w);
}
}
}
Dijkstra
经典的最短路算法，首先先归纳一下大概的书写过程：
涉及数据结构：
int n,G[maxv][maxv];
//n 表示图中node个数
//G 表示领阶矩阵
int d[maxv];
//d 表示从一个起始点开始到d[i]的最短路径
bool vis[maxv];
//表示这个点已经访问过
第一步，初始化，常用数组初始化方法：
//对于要初始化为0、-1的数组，可以使用memset来处理：
memset(a,0,sizeof(a))；
memset(g,0,sizeof(g));
//对于其他值的初始化
fill(a,a+n;INF);
fill(G[0],G[0]+n*n;INF);
操作中主要对d[]数组进行初始化操作：
//初始化d均为最大距离
fill(d,d+N,INF);
//起点到自己距离是0
d[s] = 0;
第二步，过程梳理：
首先构想伪代码。
第一层要循环n次，因为每一个点都需要找到一个最短路径d[j]，一切都是在该循环中处理；
第二层循环中要对现在的每个点都进行遍历，要找到现在d[j]最小的一个点，找最短路我必须保证之前的已经是最小的了再往后找；
与第二层并列的还有一层循环，当我找到了最小的d[j]对应的点后，我还需要对所有点进行一次遍历，这时候我是为了找到在图中与之前到的点连通，并且没有被访问过，并且之前找到的点与这条路求和的值小于现在的这个目标点，此时我就对这个点的d进行更新。
完整邻接矩阵代码：
int n,G[maxv][maxv];
int d[maxv];
bool vis[maxv] = {false};
void Dijkstra(int s){
fill(d,d+maxv,INF); //fill函数将整个d数组赋为INF
d[s] = 0;
for(int i=0;i<n;i++){
int u = -1,MIN = INF;
for(int j = 0; j < n; j++){
if(!vis[j] && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if(u == -1) return; //不联通
vis[u] = true;
for(int v=0; v<n; v++){
if(!vis[v] && G[u][v]!=INF && d[u]+G[u][v]<d[v]){
//三个条件缺一不可，通常可以再起一个if写第三个条件用于Dij+dfs的情况
d[v] = d[u] + G[u][v];
}
}
}
}
最小生成树
图类问题大概有两种，一种是最短路径问题，可以考虑使用Dijkstra与算法解决。第二种就是最小生成树的问题，一般采用prim和kruskal算法。
prim是针对点生成最小生成树，kruskal是针对边生成最小生成树。
prim
中心思想：每次从点中选取一个与集合S距离最小的变加入最小生成树。过程类似Dijkstra算法。区别在于：d[]含义不同，在prim中表示点到以访问集合S的距离，所以最后选择时不用考虑+的情况，直接用Guj与dj做比较。
kruskal
中心思想：每次选择图中最小的边，如果边两端的顶点在不同的连通块中，就把这条边加入最小生成树中。
对于如何判断两个端点处于不同的连通块，采用并查集的方法。
int father[N]; //并查集数组
int findFather(int x){//返回父亲值
while(x!=father[x]){
x = father[x]; //获得自己的父亲节点
}
return x;
}
//定义边
struct edge
{
int u,v;
int cost;
}E[maxe];
//n个顶点，m条边
int kruskal(int n,int m){
int ans = 0,Num_edge = 0;
for (int i = 1; i <= n; ++i) //并查集初始化
{
father[i] = i;
}
sort(E,E+m,cmp);//从小到大排序边
for(int i = 0;i < m;i++){
int faU = findFather(E[i].u);
int faV = findFather(E[i].v);
if(faU != faV){
father[faU] = faV;
ans += E[i].cost;
Num_edge++;
if(Num_edge == n-1) break;
}
}
if(Num_edge != n-1) -1;//无法连通时返回-1
else return ans;
}
查找
顺序查找
折半查找
使用要求：
1.必须采用顺序存储结构。
2.元素按关键字有序排列。（多为递增有序）
使用步骤：
1.置查找区间初值，low为1，high为表长。
2.当low小于等于high时，循环执行以下操作：
mid为low和high的中间值
将给定值key与中间位置记录的关键字进行比较，若相等则查找成功，返回中间位置mid
若不相等，则利用中间位置分成子表。
int low = 1,high = length;
while(low <= high){
mid = (low+high)/2;
if(key == a[mid]) return mid;
else if(key<a[mid].key) high = mid - 1;
else
low = mid + 1;
}
tips:需要注意的是循环条件是low<=high.
分块查找
建立过程：
1.建立一个索引表，长度其实并没有规定，但是有两个关键字：最大关键字和其实地址，将主表分为几个子表。
//主表
int a[10]={0,1,2,3,4,5,6,7,8,9};
//索引表
struct index
{
//定义块的结构
int key;
int start;
} newIndex[3]; //定义结构体数组
2.确认模块的起始值和最大值
for (i=0; i<3; i++)
{
newIndex[i].start = j+1; //确定每个块范围的起始值
j += 6;
for (int k=newIndex[i].start; k<=j; k++) //找出最大值
{
if (newIndex[i].key<a[k])
{
newIndex[i].key = a[k];
}
}
}
3.对结构体index索引表进行排序,机试最好通过直接写冒泡来吧。
4.输入一个key，遍历索引表，确定key可能在的子表。
5.检查是否能查到。
树表的查找
线性表的查找适用于静态表的查找，若要对动态查找表进行高效的查找，可采用几种特殊的二叉树作为查找表的组织形式。在此统称树表。
二叉排序树
二叉排序树又称二叉查找树、二叉搜索树，定义如下：
1.若左子树不空，则左子树上所有节点的值均小于它的根节点的值。
2.若右子树不空，则右子树上所有节点的值均大于它的根节点的值。
3.左右子树也为二叉排序树。
所以，当中序遍历二叉树时，可以得到一个递增的序列。 这也是来判断一个二叉树是否是二叉排序树的重要依据。例子如下：
//用一个数组来保存中序遍历的结果
int b[maxn];
//top用来控制数组下标
int top = 0;
void InOrder(LinkList t){
if (t)
{
InOrder(t->left);
b[top++] = t->data;
if (top>2 && top[top-2]>top[top-1])
{
flag = false;
return;
}
InOrder(t->right);
}
}
存储结构：（其实就是普通的二叉树吧…可能有多项数据，所以可能设计两个结构体？但是一般就一个结构体就够用了）
typedef struct node{
int data;
node *right,*left;
}node,*LinkList;
二叉树的高度计算：
int GetHeight(linklist t){
if (!t) //空节点
return 0;
else if(!t->left && !t->right) //叶子节点
return 1;
else
return GetHeight(t->left)>=GetHeight(t->right)?(GetHeight(t->left)+1):(GetHeight(t->right)+1);
}
二叉查找树的查找：
bool flag = false;
void search(linklist t,int target){
if(t->data == target) flag = true;
else{
if t->data > target? search(t->left,target):search(t->right,target);
}
flag = false;
}
二叉排序树和折半查找差不多，但是如果需要经常进行插入、删除和查找运算的表，采用二叉排序树比较好。
二叉排序树的插入：
其实和查找过程差不多…
void Insert(linklist t,int target){
if (!t)
{
t = new node;
t->data = target;
t->left = NULL;
t->right = NULL;
}
else{
t->data > target ? Insert(t->left,target):Insert(t->right,target);
}
}
二叉树的创建其实就是逐个读入然后创建的过程。
二叉排序树的删除：
从二叉树的根节点开始查找关键字为key的待删节点，如果树中不存在此节点，则不做任何操作；
否则，假设被删节点为p，父节点为f，l、r分别为左孩子和右孩子。
不失一般性，共有三种情况会出现：
1.若p为叶子节点，直接删除即可，不会破坏树的结构。
2.若p节点只有左或右孩子，则此时需要另左、右孩子占p现在的位置即可。
3.若p节点的左子树和右子树均不空：首先记住一个宗旨，变换完之后中序其他元素不能变。共有两种处理方法：
(1)令p的左孩子为f的左子树，而p的右子树为s（位置在最右下角）的右子树。
f->left = p->left; //(假设p是f的左子树) s->right = p->right;
(2)令p的直接前驱代替p，然后再从二叉排序树中删去它的直接前驱，由于直接前驱肯定是1、2两种情况中的一种，方便处理，即可完成。
二叉排序树的非递归构造：
之前在构造二叉排序树的时候都是如果不是t不是NULL就递归，看看去左边还是右边，今天遇到一个要求非递归的，比较不熟练，过程如下。
//x是要插入的值
void Create(linklist &t,int x){
//只要是插入肯定要先生成一个节点（若有重复的之后特判）
linklist s;
s = new node;
s->data = x;
s->left = s->right = NULL;
if (!t)
{
t = s;
return;
}
linklist p=t,q;
while(p){
if(p->data == x){
p->count++;
return;
}
q = p;
if (p->data < x)
p = p->right;
else
p = p->left;
}
if (q->data < x)
q->left = s;
else
q->right = s;
}
平衡二叉树
平衡二叉树又称平衡二叉搜索树，又被称为AVL树。
左子树和右子树的深度之差绝对值不超过过1的树。
平衡二叉树的平衡调整方法：
找到力插入节点最近切平衡因子绝对值超过1的祖先节点，以该节点为根的子树成为最小不平衡子树。
散列表的查找
散列表的思想：如果能在元素的存储位置和其关键字之间建立某种直接关系，那么在进行查找时，就无需做比较或做少量比较。
概念：
散列查找法又叫杂凑法或散列法。
p = H(key) H叫散列函数 p叫散列地址。
散列表是一个有限连续的地址空间（一维数组），散列地址就是数组的下标。
key1!=key2 但是 H(key1)=H(key2)这种现象叫冲突。key1和key2叫同义词。
冲突处理方法：
1.开放地址法：这是一种h1不行就在h1基础上对应找h2的基本思想。有三种方法：
（1）线性探测法：如果h1冲突了就从冲突地址的下一单元顺序寻找空单元，使用循环队列的思想。
(2) 二次探测法：找的是冲突后的1，-1，4，-4，9，-9…这样的单元。
(3) 伪随机探测法：生成一个随机数来确定下一个位置…玄学。
2.链地址法：把具有相同散列地址的记录放在同一个单链表中，相当于一个指针数组，同时用HT[0…m-1]存放各个链表的头指针。
有几个需要注意的点在代码中说明：
//基础存储结构
typedef struct node{
int data;
node *next;
}node,*linklist;
//初始化给出头节点
void Init(){
for (int i=0; i<maxn; i++) {
Hash[i] = new node;
Hash[i]->data = i;
Hash[i]->next = NULL;
}
}
排序
插入排序
直接插入排序
是一种最简单的排序方法，其基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的、记录数量增1的有虚表。
void InsertSort(sqlist &l){
for (int i = 2; i < l.length; ++i) //不需要另开数组，从本数组第二个元素开始遍历
{
if (L.r[i].key < L.r[i-1].ley) //如果检测的元素值比已排序的开头还大就摆那
{
L.r[0] = L.r[i]; //用0号位置存储i号节点
L.r[i] = L.r[i-1]; //先把最大的放在i号节点
int j;
for(j=i-2;L.r[0].key<L.r[j].key;j--){ //如果j位置的元素大于0号要插入进来的值，这个元素的后一个值就等于这个值
L.r[j+1] = L.r[j];
}
//当找到一个值后插到他前面
L.r[j+1] = L.r[0];
}
}
}
折半插入排序
相比直接插入，其找插入位置不是属于一一比对，是用二分查找来比对后插入。
void InsertSort(sqlist &l){
for (int i = 2; i < l.length; ++i) //不需要另开数组，从本数组第二个元素开始遍历
{
L.r[0] = L.r[i];
low = 1;hight = i-1;
while(low <= high){
mid = (low+high)/2;
if(L.r[0].key < L.r[mid].key)
high = mid - 1;
else
low = mid + 1;
}
for(j=i-1;j>=high+1;j--) //high前面的就是全部要挪格子的
L.r[j+1] = L.r[0];
L.r[high+1] = L.r[0];
}
}
希尔排序（缩小增量排序）
希尔排序实质上是采用分组插入的方法。
希尔对记录的分组，不是简单地“逐段分割”，而是将相隔某个“增量”的记录分成一组，在各组中直接进行排序。
【49，38，65，97，76，13，27，49，55，04】
执行过程：
1.分组，第一次分组一般为数组总长度的一半左右，所以d1 = 5，间隔为5的记录分在同一组全部的记录分在一组。
2.组内排序，注意并不是拎出来排，组内使用直接插入排序，就是说组内原本占用着哪些位置还是占用着。
3.再设立间隔分组，间隔一般为上一次的一般，所以d2 = 3，分组后再进行组内排序。
…..
n.直到间隔为1。
void ShellInsert(sqlist &l,int dk){
//对顺序表L做一趟增量为dk的希尔插入排序
for(i=dk+1;i<L.length;i++){
//进行直接插入排序
if (L.r[i].key<L.r[i-dk].key)
{
L.r[0]=L.r[i];
int j;
for (j = i-dk;j>0 && L.r[0].key<L.r[j].key;j-=dk)
{
L.r[j+dk] = L.r[j];
}
L.r[j+dk] = L.r[0];
}
}
}
void ShellSort(sqlist &l,int dt[],int t){
for (int k = 0; k < t; ++i)
{
ShellInsert(L,dt[k]);
}
}
交换排序
冒泡排序
经典的冒泡排序是选择从一端开始，通过比较相邻元素大小并交换次序的。实际上对冒泡排序加以改进，从两端进行排序，也就是所谓的“双向冒泡排序”，可以有更好的效率。如果按照排序结果从小到大输出，可以按照“较大气泡从左到右移动，较小气泡从右到左移动”来实现双向冒泡排序的效果；
想法：链表的话先用一个指针指到最后面。
linklist head,tail;
head = l->next;
tail = head;
while (tail->next) {
tail = tail->next;
}
while(head!=tail){
for (linklist i = head; i != tail; i=i->next)
{
if (i->data > i->next->data) {
int temp = i->next->data;
i->next->data = i->data;
i->data = temp;
}
}
tail = tail->pre;
//这是双向的，如果不是双向的应该需要多一个指针指在head的后面，然后用tail指向这个指针
}
在这里介绍一种刷题时遇到的双向冒泡排序：
即：我每次循环的时候考虑从tail再到head，把最小的换到末尾，然后head = head->next.
快速排序
对冒泡排序的一种改进。
int Partition(int &a[],int left,int right){
int temp = a[left];//temp作为指标，左边都是比temp小的，右边都是比temp大的
//必需先从左开始看不能搞反
while(left<right){ //在while内部也要检测left<right
while(a[right]>temp && left<right){right--;}
a[left] = a[right];
while(a[left]<temp && left<right){left++;}
a[right] = a[left];
}
a[left] = temp;
return left;
}
void quickSort(int a[],int left,int right){
if(left<right){
int pos = Partition(a,left,right);
quickSort(a,left,pos-1); //不需要考虑主元pos
quickSort(a,pos+1,right);
}
}
今天遇到一个基于快排思想的查找，其实快排思想就是所谓的双指针思想。
选择排序
简单选择排序
也称直接选择排序。有点忘记做法了，记录一下，前半部分有点像简单插入排序，这个是每次选择一个最小的放在指定位置。
void SelectSort(sqlist &l){
for (int i = 1; i < length; i++)
{
k = i;
for (int j = i+1; i <= length; j++)
{
if(L.r[j].key < L.r[k].key) k=j;
}
//交换r[i]与r[k]
if(k!=i)
{t=L.r[i];L.r[i]=L.r[k];L.r[k]=t;}
}
}
堆排序（Heap Sort）
堆这种数据结构的条件：
1.完全二叉树。（生成顺序从上到下从左到右，不要和满二叉树混淆！）
2.父节点的值大于子节点的值。
首先要知道一个完全二叉树如何变成堆：
//制定某一个节点调整
void Heapify(int tree[],int n,int i){
//递归出口，超过节点数量即退出
if (i>=n){
return;
}
//由于堆就是要孩子比自己小（大根堆），所以找出孩子，根是1和0的公式略有差异
int c1 = 2*i+1;
int c2 = 2*i+2;
//用maxn表示最大的节点的编号
int maxn = i;
if (c1<n && tree[maxn]<tree[c1]){
maxn = c1;
}
if (c2<n && tree[maxn]<tree[c2]){
maxn = c2;
}
if (maxn != i){
//交换
int temp = tree[max]; tree[max] = tree[i]; tree[i]=temp;
Heapify(tree,n,maxn);
}
}
//要明确的是，只有根节点调用Heapify是不能让整个树变成堆的，因为只对交换的一个分支进行检查。
//接下来创建堆：
void CreateHeap(int tree[],int n){
int last_node = n-1;
int parent = (last_node-1)/2;
//从第一个非叶子节点开始到根进行heapify
for (int i = n/2-1; i >=0; i--)
{
Heapify(tree,n,i)
}
}
//堆排序：
//步骤：
//1. 先把根节点和最后一个节点交换
//2. 把最后一位砍断，单独拎出来
//3. 根节点做heapify，
//4. 循环1-3步骤，直到只剩下一个点。
void HeapSort(int tree[],int n){
CreateHeap(tree,n);
for (int i = n-1; i >=0 ; i--){
int temp = tree[i]; tree[i] = tree[0]; tree[0]=temp;
Heapify(tree,i,0);
}
}
//此时如果进行层序遍历 会发现已经排序完成。
归并排序
归并排序的思想是：
假设有n个记录，则可看成是n个有序的子序列，每个子序列长度为1，然后两两归并，得到[n/2]个长度为2或1的子序列，然后再两两归并。直到得到一个长度为n的有序序列为止。
核心算法 相邻两个有序子序列的合并：
void Merge(int R[],int &T[],int low,int mid,int high){
i = low;j=mid+1;k=low;
while(i<=mid && j<=high){
if(i<=mid && j<=high){
if (R[i].key<=R[j].key){
T[k]=R[i++];
}
else{
T[K]=R[j++];
}
k++;
}
while(i<=mid){
T[k++] = R[i++];
}
while(j<=mid){
T[k++] = R[j++];
}
}
}
归并排序，其实就是递归到n值为1的过程：
void MSort(int R[],int &T[],int low,int high){
if(low == high) T[low]=R[low];
else{
mid=(low+high)/2;
MSort(R,S,low,mid);
MSort(R,S,mid+1,high);
Merge(S,T,low,mid,high);
}
}