数据结构复习

算法复杂度

若两端算法分别由复杂度 $T_1(n)=O(f_1(n))$ $T_{1} (n) = O (f_{1} (n))$ 和 $T_2(n)=O(f_2(n))$ $T_{2} (n) = O (f_{2} (n))$ 则
- $T_1(n)+T_2(n)=max(O(f_1(n)),O(f_2(n))$
- $T_1(n)*T_2(n)=O(f_1(n)*f_2(n))$
若 $T(n)$ 是关于 n 的 k 阶多项式，那么 $T(n)=O(n^k)$
一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度

例题1 给定N个整数序列{A1，A2，……，An}；求函数 $f(i,j)=max(\sum_{i=0}^jA_k)$ 的最大值

//算法1 时间复杂度O(n^2)
int MaxSubseqSum1(int A[],int N){
    int ThisSum,MaxSum=0;
    int i,j,k;
    for(i=0;i<N;i++){
        for(j=0;j<N;k++){
            ThisSum+=A[j];
            if(ThisSum>MaxSum)
                MaxSum=ThisSum;
        }
    }
    return MaxSum;
}

1	//算法2 分而治之(递归) 时间复杂度O(nlogn) 见归并排序

//算法3 在线处理（动态规划） 时间复杂度O(n)
int MaxSubseqSum1(int A[],int N){
    int ThisSum=0,MaxSum=0;
    int i;
    for(i=0;i<N;i++){
        ThisSum+=A[i];//向右累加
        if(ThisSum>MaxSum)
            MaxSum=ThisSum;//发现更大和则更新当前结果
        else if(ThisSum<0)//如果发现当前子列和为负数
            ThisSum=0;//则不可能使后面的部分和增大，抛弃之
    }
    return MaxSum;
}

(考)线性表（查找，增加，删除）

定义：（对象集）一个线性表是n个数据元素的有限序列。由同类型元素构成有序序列的线性结构。

线性表**顺序存储,**抽象表示（考）

typedef struct LNode *List;
struct LNode{
    ElementType Data[MAXSIZE];
    int Last;
};
struct LNode L;
List Ptrl;
//访问下标i的元素：L.Data[i]或Ptrl->Data[i]
//线性表的长度：L.Last+1或Ptrl->last+1
//初始化（建立空表）
List MakeEmpty(){
    List PtrL;
    ptrL=(List)malloc(sizeof(struct LNode));
    PtrL->Last=-1;
    return PtrL;
}
int Find(ElementType X,List Ptrl){
    int i=0;
    while(i<=PtrL->Last && PtrL->Data[i]!=X) i++;
    if(i>PtrL->Last)return -1;
    else return i;
}//时间复杂度 O(n)
//插入从后往前先挪数，再插入到i-1下标，第i个元素下标0开始
void Insert(ElementType X,int i,List PtrL){
    int j;
    if(Ptrl->Last==MAXSIZE-1){
        printf("表满了，插不进去");
        return;
    }
    if(i<1||i>PtrL->Last+2){
        printf("位置不合法");
        return;
    }
    for(j=PtrL->Last;j>=i-1;j--)
        Ptrl->Data[j+1]=PtrL->Data[j];
    PtrL->Data[i-1]=X;
    PtrL->Last++;
    return;
}//O(n)
//删除,从i开始向前挪，覆盖前一个
void Delete(int i,List PtrL){
    int j;
   if(i<1||i>PtrL->Last+1){
        printf("位置不合法");
        return;
    }
    for(j=i;j<=PtrL->Last;j++)
         Ptrl->Data[j-1]=PtrL->Data[j];
    PtrL->Last--;
    return;
}//O(n)

//手写代码
# include <stdio.h>
# include <stdlib.h>
# define ElementType int
# define LIST_INIT_SIZE 10 //初始分配长度
# define LISTINCREMENT  5  //存储空间的分配增量 

//动态分配 
struct LNode{
	ElementType *data;
	int length;//当前长度 
	int listsize;//当前分配的储存容量(以sizeof(ELementType)为单位) 
};
//构造一个空的顺序表，返回指针 
struct LNode* InitList_Sq(){//初始化一个顺序表 
	struct LNode *q;
	q=(LNode*)malloc(sizeof(struct LNode));
	q->data=(ElementType*)malloc(LIST_INIT_SIZE*sizeof(ElementType));
	if(!q->data){
		printf("内存空间不足\n");
        return NULL;
	}
	q->length=0;
	q->listsize=LIST_INIT_SIZE;
	return q;
} 

//按值查找
int Find(ElementType X,struct LNode *p){
	int i =0;
	while(i<p->length && p->data[i]!=X) {i++;}
    if(i>=p->length)return -1;
	else return i+1;//返回下标要+1才是位置 
}

//删除 按位置删除 
void Delete(int i,struct LNode *p){
	int j;
	if(i<1||i>p->length){
		printf("位置不合法\n");
		//return ; 
	}else{
	for(j=i;j<=p->length;j++)//=将a[10]不存在转换到a[9] 
	p->data[j-1]=p->data[j];
	p->	length--;}
}

//插入 从后往前先挪数，再插入到i-1下标，第i个元素下标0开始 
struct LNode* Insert(ElementType X,int i,struct LNode *p){
	int j;
	if(p->length==p->listsize){
		printf("表满了，插不进去\n");
		return NULL;//跳出函数 
	} 
	if(i<1||i>=p->length+2){
        printf("位置不合法\n");
        return NULL;
    }
    for(j=p->length;j>=i-1;j--)
        p->data[j+1]=p->data[j];
    p->data[i-1]=X;
    p->length++;
    
	return p;

}  


int main(){
	struct LNode* InitList_Sq();
	int Find(ElementType X,struct LNode *p);
	struct LNode *q;
	q=InitList_Sq();
	for(int i=0;i<10;i++){
		q->data[i]=i;
		q->length+=1;
	}
	
	//查找 
	int g=Find(13,q);
	if(g==-1)printf("不在\n");
	else printf("在%d个位置\n",g);  
	for(int j=0;j<q->length;j++){
	printf("%d",q->data[j]);
	}
	printf("\n%d\n",q->length);
	
	//删除 
	Delete(6,q);
	for(int j=0;j<q->length;j++){
	printf("%d",q->data[j]);
	}
	printf("\n%d\n",q->length);
	
	//插入 
	q=Insert(10,11,q);
	if(q!=NULL){
	for(int j=0;j<q->length;j++){
	printf("%d",q->data[j]);
	}
	printf("\n%d\n",q->length);}
	
	return 0; 
}

链式存储，抽象表示

typedef struct LNode *List;
struct LNode{
    ElementType Data;
    List Next;
};
struct LNode L;
List PtrL;
//求表长
int Length(List PtrL){
    List p=PtrL;
    int j=0;
    while(p){
        p=p->Next;
        j++;
    }
    return j;
}//O(n)
//按序号查找
List FindKth(int K,List PtrL){
    List p=PtrL;
    int i=1;
    while(p!=NULL&&i<K){
        p=p->Next;
        i++;
    }
    if(i==K)return p;
    else return NULL;
}//O(n)
//按值查找
List Find(ElementType X,List Ptrl){
    List p=Ptrl;
    while(p!=NULL&&p->Data!=X)
        p=p->Next;
    return p;
}//O(n)
//插入结点，找i-1
List Insert(ElementType X,int i,List PtrL){
    List p,s;
    if(i==1){//新节点插入表头，将头指针改变，替换原来的头指针
        s=(List)malloc(sizeof(struct LNode));
        s->Data=X;
        s->Next=PtrL;
        return s;
    }
    p = FindKth(i-1,PtrL);
    if(p==NULL){
        printf("参数错误");
        return NULL;
    }else{
        s=(List)malloc(sizeof(struct LNode));
        s->Data=X;
        s->Next=p->Next;
        p->Next=s;
        return PtrL;
    }
}//O(n)
//删除结点，找i-1
List Delete(int i,List Ptrl){
    List p,s;
    if(i==1){
        s=PtrL;
        if(PtrL!=NULL)PtrL=PtrL->Next;
        else return NULL;
        free(s);
        return PtrL;
    }
    p=FindKth(i-1,PtrL);
    if(p==NULL){
        printf("结点不存在");
        return NULL;
    }else if(p->Next==NULL){
        printf("结点不存在");return NULL;
    }else{
        s=p->Next;
        p->Next=s->Next;
        free(s);
        return PtrL;
    }
}//O(n)

//单链表实现
# include<stdio.h> 
# include<stdlib.h>
typedef struct LNode *List;
struct LNode{
    int Data;
    List Next;
};
List FindKth(int K,List PtrL){
    List p=PtrL;
    	int i=1;//插入到第二个结点 
    while(p!=NULL && i<K){
        p=p->Next;
        i++;
    }
//    printf("第一%d\n 第二%d",i,K); 
    if(i==K)return p;
    else return NULL;
}//O(n)
List Insert(int X,int i,List PtrL){
    List p,s;//本身List就是指针类型，属于加*
    if(i==1){//新节点插入表头，将头指针改变，替换原来的头指针
        s=(List)malloc(sizeof(struct LNode));
        s->Data=X;
        s->Next=PtrL;
        return s;
    }
    p = FindKth(i-1,PtrL);
    if(p==NULL){
        printf("参数错误");
        return NULL;
    }else{
        s=(List)malloc(sizeof(struct LNode));
        s->Data=X;
        s->Next=p->Next;
        p->Next=s;
        return PtrL;
    }
}//O(n)

int main(){
List FindKth(int K,List PtrL);
List Insert(int X,int i,List PtrL);
LNode *head,*p,*q,*w;
w=(List)malloc(sizeof(struct LNode));
w->Data=3;
w->Next=NULL;
q=(List)malloc(sizeof(struct LNode));
q->Data=2;
q->Next=w;
p=(List)malloc(sizeof(struct LNode));
p->Data=1;
p->Next=q;

head=p;

p=Insert(4,3,p); 

p=Insert(5,3,p);
p=Insert(6,3,p);
p=Insert(7,3,p);
p=Insert(8,3,p);
while(head->Data!=NULL){//不要漏掉结点
	printf("%d\n",head->Data);
	head=head->Next;
}
return 0;	
};

(考)堆栈

插入数据：入栈(Push)
删除数据：出栈(Pop)
后入先出：Last In First Out(LIFO)

//！！！顺序存储实现，抽象
# define MaxSize<个数>
typedef struct SNode *Stack;
struct SNode{
    ElementType Data[MaxSize];
    int Top;//栈顶数组下标
};
//入栈
void Push(Stack PtrS,ElementType item){
    if(PtrS->Top==MaxSize-1){
        printf("堆栈满");return;
    }else{
        PtrS->Data[++(P->Top)]=item;
    }
}
//出栈
ElementType Pop(Stack PtrS){
    if(PtrS->Top==-1){
        printf("堆栈空");
        return ERROR;
    }else{
        return(PtrS->Data[(PrtS->Top)--]);
    }
}
//代码实现
#include<stdio.h>
#include<stdlib.h>
#define ElementType int
#define Maxsize 10

struct SNode{
	//ElementType *data;//如果使用动态分配需要指针 
	ElementType data[Maxsize];
	int top;//数组栈顶下标 
};

struct SNode* Init_Stack(){
	struct SNode *p=(SNode*)malloc(sizeof(struct SNode));
	//p->data =(ElementType*)malloc(Maxsize*sizeof(ElementType));
    if(p==NULL){
		printf("内存不足");
		return NULL; 
	}
	
	p->top=-1;
	return p;
}
//进栈 
void Push(ElementType k,struct SNode *p){
	if(p->top==Maxsize-1){//如果使用动态分配，Maxsize要传入
	printf("栈满"); 	
	}else{
	p->data[++(p->top)]=k;//先自增在进栈	
	}
} 

//出栈 
ElementType Pop(struct SNode *p){
	if(p->top==-1){//0可能有数 
		printf("堆栈空"); 
		exit(0); //抛出异常 退出 
	} else{
		return p->data[(p->top)--];//先弹出在自减 
	}
}


int main(){
	struct SNode *p;
	p=Init_Stack();
	Push(1,p);
	Push(2,p);
	int i=Pop(p);
	printf("%d\n",i);
	Push(3,p); 
	Push(4,p); 
	Push(5,p); 
	i=Pop(p);
    printf("%d\n",i);
    for(i=0;i<=p->top;i++)printf("栈内有：%d\n",p->data[i]);

	printf("%d",p->top);
	
	return 0;
}

使用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。(使这两个栈分别从数组的两头开始向中间生长，当两个栈的栈顶指针相遇时，表示两个栈都满了)

# define MaxSize<个数>
//typedef struct Dstack *S;
struct DStack{
    ElementType Data[MaxSize];
    int Top1;//栈顶数组下标
    int Top2;
}S;
S.Top1=-1;//数组两边下标，越界所以需要先自增或先自减
S.Top2=MaxSize;
//入栈
void Push(Stack Dstack *PtrS,ElementType item,int Tag){//当Tag=1为第一个堆栈，2为第二个堆栈
    if(PtrS->Top2-PtrS->Top1==1){//相邻右边减左边
        printf("堆栈满");return;
    }
    if(Tag==1)
        PtrS->Data[++(P->Top1)]=item;
    else
        PtrS->Data[--(P->Top2)]=item;
}

//出栈
ElementType Pop(Stack Dstack *PtrS,int Tag){
    if(Tag==1){
        if(PtrS->Top1==-1){
            printf("堆栈1空"); return NULL;
        }else return PtrS->Data[(PrtS->Top1)--];
    }else{
        if(PtrS->Top2==MaxSize){
            printf("堆栈2空");return NULL;
        }else return PtrS->Data[(PrtS->Top2)++];       
    }
}

表达式求值(中缀转后缀)
- 运算数：直接输出；
- 左括号：压入堆栈；
- 右括号：将栈顶的运算符弹出并输出，直到遇到左括号(出栈，不输出)；
- 运算符：
  - 若优先级大于栈顶运算符时，把它进行压栈；
  - 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
- 若各对象处理完毕，则把堆栈中留存的运算符一并输出。

//

队列

插入数据：入队列(AddQ)
删除数据：出队列(DeleteQ)
先来先服务
先进先出：FIFO

#define MaxSize<个数>
struct QNode{
    ElementType Data[MaxSize];
    int rear;//队头，插入
    int front;//队尾，删除
};
typedef struct QNode *Queue;
//循环队列 数组内只放放n-1个元素防止误判 满/空
void AddQ(Queue PtrQ,ElementType item){
    if((PtrQ->rear+1)%MaxSize==PtrQ->front){
        printf("队列满");
        return;
    }
    PtrQ->rear=(PtrQ->rear+1)%MaxSize;//最后一位会变零
    ptrQ->Data[PtrQ->rear]=item;
}
//出队列
ElementType DeleteQ(Queue PtrQ){
    if(PtrQ->front==PtrQ->rear){
        printf("队列空");
        return ERROR;
    }else{
        PtrQ->front=(PtrQ->front+1)%MaxSize;
        return  ptrQ->Data[PtrQ->front];
    }
}

//链表实现
#include<stdio.h>
#include<stdlib.h>
#define ElementType int
#define ERROR -99
//构建结点信息 
struct Node{
    ElementType Data;
    struct Node *Next;
};

struct QNode{//链队列结构
    struct Node *rear;//指向队尾
    struct Node *front;//指向队头
};


ElementType DeleteQ(struct QNode *PtrQ){
//    pNode FrontCell;
    struct Node *FrontCell;
    ElementType FrontElem;
    
    if(PtrQ->front==NULL){
        printf("队列空");return ERROR;
    }
    FrontCell=PtrQ->front;
    if(PtrQ->front==PtrQ->rear)//若队列只有一个元素
        PtrQ->front=PtrQ->rear=NULL;
    else 
        PtrQ->front=PtrQ->front->Next;
    FrontElem=FrontCell->Data;//将删除的元素返回
    free(FrontCell);
    return FrontElem;
}

void AddQ(struct QNode *q,ElementType i){
    struct Node *qNode;
    qNode=(Node*)malloc(sizeof(struct Node));
    
    if(!qNode){
        printf("内存空间不足\n");
        exit(-1);
    };
    
    qNode->Data=i;
    qNode->Next = NULL;
    if(q->front==NULL){
        q->front = qNode;
    }
    if(q->rear == NULL){
        q->rear = qNode;
    }
    else{//头尾不为null，则执行下列操作
        q->rear->Next=qNode;//连上上一个指针  
        q->rear=qNode;//队尾指针从新被定义
    }
}

int IsEmptyQ(struct QNode *q){
    return (q->front == NULL);
}

void PrientQueue(struct QNode *q){
    if(IsEmptyQ(q)){
        printf("空队列\n");
        return ;
    }
    printf("打印队列所有元素：\n");
    struct Node *qnode = q->front;
    while(qnode != NULL){
        printf("%d",qnode->Data);
        qnode= qnode->Next;
    }
    printf("\n");
}

int main(){
	ElementType DeleteQ(struct QNode *PtrQ);
	void AddQ(struct QNode *q,ElementType i);
	struct QNode *p;
	int w;
	p=(QNode*)malloc(sizeof(struct QNode));
	p->front=p->rear=NULL;
	AddQ(p,1);
	AddQ(p,2);
	AddQ(p,3);
	AddQ(p,4);
	AddQ(p,5);
	PrientQueue(p);
	DeleteQ(p);
	DeleteQ(p);

	PrientQueue(p);
		
	return 0;
}

树和二叉树

顺序查找

struct LNode{
    ElementType Element[MaxSize];
    int Length;
}
int SequentialSearch (struct LNode *Tb1,ElementType K){
    int i;
    Tb1->Element[0]=K;
    for(i =Tb1->Length; Tb1->Element[i]!=K;i--);//建立哨兵，返回数组下标没有返回0，哨兵坐标。
    return i;
}//O(n)

int SequentialSearch(ElementType A[],ElementType K,int N){//顺序查找 
	int i;
	for(i=0;i<N;i++){
		if(A[i]==K)return i;
	}
	return -1;
}

####二分查找

假设n个数据元素的关键字满足有序(比如：小到大)(k1<k2<····<kn)并且是连续存放**（数组）**，那么可以进行二分查找。
二叉排序树->动态查找问题

struct LNode{
    ElementType Element[MaxSize];
    int Length;
}

int BinarySearch(struct LNode *Tb1,ElementType K){
    int left,right,mid,NoFound=-1;
    left=1;//左边界
    right=Tb1->Length;//右边界
    while(left<=right){
        mid=(left+right)/2;//计算中间元素
        if(K<Tb1->Element[mid]) right=mid-1;//调整右边界
        else if(K>Tb1->Element[mid]) left=mid+1;//调整左边界
        else return mid;//查找成功，返回元素下标。
    }
    return NotFound;//查找失败，返回-1  
}//O(logN)

int BinarySearch(ElementType A[],ElementType K,int N){
	int left,right,mid,Nofound=-1;
	left=0;
	right=N-1;
	while(left<=right){
		mid=(left+right)/2;
		if(K<A[mid])right=mid-1;
		else if (K>A[mid])left=mid+1;
		else return mid;
	}
	return Nofound;
}

树

定义：n(n>=0)个结点的有限集合，n=0时，称为空树，这是一种情况。在任意一科非空树中应满足：

有且仅有一个特定的称为根的结点。
其余结点可分为m(m>0)个互不相交的有限集{T1,T2,…,Tm},其中每个集合本身又是一棵树，称为原来树的“子树”。

树与非树？

子树是不相交的；
出了根结点外，每个结点有且仅有一个父结点；
一棵N个结点的树有N-1条边。

一些基本定义：

结点的度：结点的子树个数；
树的度：树的所有结点中最大的度数；
叶结点： 度为0的结点；
**父结点：**有子树的结点是其子树的根结点的父结点；
**子结点：**子结点也称孩子结点；
**兄弟结点：**具有同一父结点的各结点彼此是兄弟结点。
路径和路径长度：从n1->nk的路径为一个结点序列，路径所包含边的个数为路径长度。
祖先结点：沿树根到某一结点路径上所有结点都是这个结点的祖先结点。
子孙结点：某结点的子树中所有结点都是这个结点的子孙结点。
**结点的层次：**根节点为1层，向下累加。
数的深度：树中所有结点最大层次是这棵树的深度。

基本性质：

树中的结点数等于所有结点的度+1；
度为m的树中第i层上至多有 $m^{i-1}$ 个结点(i>=1);
高度为h的m叉树至多有( $m^h$ -1)/(m-1)个结点。
具有n个结点的m叉树的最小高度为┌ $log_m(n(m-1)+1)$ ┐

二叉树

//儿子兄弟表示法
struct tree{
    ElementType Element;
    struct tree *firstChild;
    struct tree *NextSibling;
}

二叉树有左右之分，5中形态(空，根，根左，根左右，根右)，其中特殊的二叉树有，满二叉树，完全二叉树(不满但是结点序号和顺序必须一致)，二叉排序树(左小右大，二分查找)，平衡二叉树(任一结点左子树和右子树深度之差不超过1)。

操作集：

Boolean IsEmpty(struct tree *BT):判别BT是否为空；
Void Traversal(struct tree *BT):遍历，按某个顺序访问每个结点；
- void PreOrderTraversal(struct tree *BT):先序遍历— 根，左，右；
- void InOrderTraversal(struct tree *BT):中序遍历—左，根，右；
- void PostOrderTraversal(struct tree *BT):后序遍历—左，右，根；
- void LevelOrderTraversal(struct tree *BT):层次遍历，从上到下，从左到右
struct tree CreatBinTree():创建一个二叉树。

//链表存储
//儿子兄弟表示法
struct tree{
    ElementType Element;
    struct tree *Left;
    struct tree *Right;
}

(考)二叉树遍历

//先序遍历 
void PreOrderTraversal(struct tree *BT){
    if(BT){
        printf("%d",BT->Data);
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(BT->Right);
    }
}
//中序遍历
void InOrderTraversal(struct tree *BT){
if(BT){ 
        InOrderTraversal(BT->Left);
        printf("%d",BT->Data);
        InOrderTraversal(BT->Right);
    }
}
//后续遍历
void PostOrderTraversal(struct tree *BT){
    if(BT){ 
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%d",BT->Data);
    }
}
//中序遍历非递归算法
void InOrderTraversal1(struct tree *BT,int Maxsize){
	struct tree *T=BT;
	struct Stack *S=CreatStack(Maxsize);//创建并初始化堆栈S
	while(T || !IsEmpty(S)){
		while(T){//一直向左并将沿途压入堆栈
			Push(S,T);
			T=T->Left;
		}
		if(!IsEmpty(S)){
			T=Pop(S);//结点弹出堆栈
			printf("%d",T->Data);//访问打印结点
			T=T->Right; //转向右子树
		}
	}
}

//先序遍历非递归算法
void PreOrderTraversal1(struct tree *BT,int Maxsize){
	struct tree *T=BT;
	struct Stack *S=CreatStack(Maxsize);//创建并初始化堆栈S
	while(T || !IsEmpty(S)){
		while(T){//一直向左并将沿途压入堆栈
			Push(S,T);
			printf("%d",T->Data);//访问打印结点
			T=T->Left;
		}
		if(!IsEmpty(S)){
			T=Pop(S);//结点弹出堆栈	
			T=T->Right; //转向右子树
		}
	}
}

//层序遍历队列实现，每次出队时入队左右儿子结点
void LevelOrderTraversal(struct tree *BT){
    struct tree *T;
    struct QNode *Q;//数组
    if(!BT) return;
    Q = CreatQueue(MaxSize);
    AddQ(Q,BT);
    while(!IsEmptyQ(Q)){
        T=DeleteQ(Q);
        printf("%d",T->Data);
        if(T->Left) AddQ(Q,T->Left);
        if(T->Right) AddQ(Q,T->Right);
    }
}

//代码测试
#include<stdio.h>
#include<stdlib.h>
#define ElementType int
//儿子兄弟表示法
 struct tree{
 	ElementType Data;
 	struct tree *Left;
 	struct tree *Right;
 }; 

struct Stack{
	struct tree *data;
	int top;
	int Maxsize;
};

struct Stack* CreatStack(int Maxsize){
	struct Stack *p=(Stack*)malloc(sizeof(struct Stack));
	p->data=(tree*)malloc(Maxsize*sizeof(struct tree));
	if(p==NULL || p->data==NULL){
		printf("内存不足");
		return NULL;
		//exit(0); 
	}else{
		p->top=-1;
		p->Maxsize=Maxsize;
	}

}

void Push(struct Stack *s,struct tree *p){
	if(s->top==s->Maxsize-1){
		printf("堆栈满"); 		
	}else{
		s->data[++(s->top)]=*p; //※※※※※※※重点
	}
}

struct tree* Pop(struct Stack *s){
	if(s->top==-1){
		printf("堆栈空");
		return NULL;
	}else{
		return &(s->data[(s->top)--]);//※※※※※※重点
	} 
}

int IsEmpty(struct Stack *p){
	if(p->top==-1){
		return 1;
	}else{
		return 0;
	}
}
struct tree *add(struct tree *q,ElementType k,int n){
	if (n==1){
		struct tree *p=(tree*)malloc(sizeof(struct tree));
		p->Data=k;
		p->Left=NULL;
		p->Right=NULL;
		q->Left=p;
	}else{
		struct tree *p=(tree*)malloc(sizeof(struct tree));
		p->Data=k;
		p->Left=NULL;
		p->Right=NULL;
		q->Right=p;
	}
	
}

struct tree *creat(ElementType k){
	struct tree *q=(tree*)malloc(sizeof(struct tree));
	q->Data=k;
	q->Left=NULL;
	q->Right=NULL;
	return q;
}
int main(){
	struct Stack* CreatStack(int Maxsize);	
	void PreOrderTraversal(struct tree *BT);
	void InOrderTraversal(struct tree *BT);
	void PostOrderTraversal(struct tree *BT);
	void InOrderTraversal1(struct tree *BT,int Maxsize);
	void PreOrderTraversal1(struct tree *BT,int Maxsize);
	struct tree *add(struct tree *q,ElementType k,int n);
	struct tree *creat(ElementType k);
	
	struct tree *q,*w,*root;	
	struct Stack *p;
	//p=CreatStack(10);
	q=creat(1);
	q=add(q,2,1);
	q=add(q,3,2);
	root=w=q;
	w=w->Right;
	q=q->Left; 
	w=add(w,6,1);
	w=add(w,7,2);
	q=add(q,4,1);
	q=add(q,5,2);
	printf("先序遍历\n"); 
	PreOrderTraversal(root);
	printf("\n中序遍历\n");
	InOrderTraversal(root);
	printf("\n后序遍历\n");
	PostOrderTraversal(root);
	printf("\n中序遍历非递归算法\n");
	InOrderTraversal1(root,7);
	printf("\n先序遍历非递归算法\n");
	PreOrderTraversal1(root,7);
	return 0;
}

二叉树遍历应用：

//输出二叉树中叶子结点，先序遍历
void PreOrderTraversal(struct tree *BT){
    if(BT){
        if(!BT->Left && !BT->Right)//没有二子结点
            printf("%d",BT->Data);
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(BT->Right);
    }
}
//求树高度，左右子树最高高度+1
//使用后序遍历改
int PostOrderGetHeight(struct tree *BT){
    int HL,HR,MaxH;
    if(BT){ 
        HL=PreOrderGetHeight(BT->Left);//左子树深度
        HR=PreOrderGetHeight(BT->Right);//右子树深度
        MaxH=(HL>HR)?HL:HR;//取左右最大值
        return (MaxH+1);//返回树深度
    }else
        return 0;
}

二元运算表达式树及其遍历

通过两种序列(必须有中序遍历)就可以确定一个唯一的二叉树

//二叉树静态链表
# define MaxTree 10
# define ElementType char
# define Tree int
# define Null -1 //编译器定义Null（0）

struct TreeNode{
    ElementType Element;
    Tree Left;
    Tree Right;
}T1[MaxTree],T2[MaxTree];//数组中没有出现的下标就是根

(考)二叉搜索树/查找树/排序树

Position Find(ElementType X,struct tree *BST);//从二叉排序树BST中查找元素X，返回其所在结点的地址；
Position FindMin(struct tree *BST);//找出最小元素所在结点地址
Position FindMax(struct tree *BST);
struct tree Insert(ElementType X,struct tree *BST);
struct tree Delete(ElementType X,struct tree *BST);

插入操作

struct tree* Insert(ElementType k,struct tree *BST){
	if(!BST){
		//若原树为空，则生成一个结点得二叉排序树 
		BST=(tree*)malloc(sizeof(struct tree));////!!!!!!!!!!!!!!!!!!!!!!!!!不用结构体声明，直接申请，指针已经传进来了 
		BST->data=k;
		BST->Left=BST->Right=NULL;
	}else{//找插入元素得位置 
		if(k<BST->data){
			BST->Left=Insert(k,BST->Left);//递归插入左子树 
		}else if(k>BST->data){
			BST->Right=Insert(k,BST->Right);//递归插入右子树 
		}
		
		//else k已经存在，什么都不做 
	}
	
	return BST; 
}

删除操作

当为叶子结点直接删除
当删除结点只有一个儿子，用儿子代替
当左右都有儿子结点都有二子结点时
- 右子树最小元素代替
- 左子树的最大元素

//若为叶子结点直接删除
//若只有一个孩子结点则用孩子结点代替自己
//若 左右都有儿子结点且都有孙子结点
//用右子树最小元素 或左子树最大元素代替 
struct tree* Delete(ElementType k,struct tree *BST){
	struct 	tree *Tmp;
	if(!BST)printf("要删除的结点不存在");
	else if(k<BST->data)
		BST->Left=Delete(k,BST->Left);//左子树递归查找要删除的结点 
	else if(k>BST->data)
		BST->Right=Delete(k,BST->Right);//右子树递归查找要删除的结点 
	else //找到要删除的结点 
		if(BST->Left && BST->Right){
			Tmp=FindMin(BST->Right);//右子树最小结点 
			//Tmp=FindMax(BST->Left);//左子树最大结点 
			
			BST->data=Tmp->data;
			BST->Right=Delete(BST->data,BST->Right);//删除右子树中最小元素 
			//BST->Left=Delete(BST->data,BST->Left);
			
		} else{
			Tmp=BST;
			if(!BST->Left)//没有左节点，将右节点当自己 
				BST=BST->Right;
			else if(!BST->Right)//没有右节点，将左结点当自己 
				BST=BST->Left;
			//两个都没有直接释放自己 此时BST=NULL; 
			free(Tmp);//释放这个结点 释放的是结构体的空间，并不是指针变量，指针变量是临时的，用完就没了 
		}
		
	return BST;//返回的是当前结点
}

//代码实现
#include <stdio.h>
#include <stdlib.h>
#define ElementType int

//左小右大树 
struct tree{
	ElementType data;
	struct tree *Left;
 	struct tree *Right;
};

struct tree* FindMin(struct tree *BST){
	if(BST->Left){
		FindMin(BST->Left);
	}else{
		return BST;
	}
} 

struct tree* FindMax(struct tree *BST){
	if(BST->Right){
		FindMax(BST->Right);
	}else{
		return BST;
	}
} 


//中序遍历
void InOrderTraversal(struct tree *BT){
if(BT){ 
        InOrderTraversal(BT->Left);
        printf("%d",BT->data);
        InOrderTraversal(BT->Right);
    }
}

int main(){
	void InOrderTraversal(struct tree *BT);
	struct tree* FindMin(struct tree *BST);
	struct tree* FindMax(struct tree *BST);
	struct tree* Insert(ElementType k,struct tree *BST);
	
	struct tree *p=NULL,*w,*q;
	p=Insert(6,p);
	p=Insert(2,p);
	p=Insert(1,p);
	p=Insert(3,p);
	p=Insert(7,p);
	p=Insert(9,p);
	w=FindMin(p);
	printf("最小值%d\n",w->data);
	q=FindMax(p);
	printf("最大值%d\n",q->data);
	printf("中序遍历\n");
	InOrderTraversal(p);
	p=Delete(2,p); 
	printf("\n");
	InOrderTraversal(p);
	return 0;
}

平衡二叉树

任一结点左子树和右子树深度之差不超过1
搜索树结点不同插入次序，将导致不同的深度和平均查找长度ASL
斐波那契数列(1,1,2,3,5,…)，nh=n(h-1)+n(h-2)+1 =》给定结点数为n的平衡二叉树（AVL）最大高度为h=O(log2n).

调整：

RR旋转

LL旋转

LR旋转

(考)线索二叉树

线索化

若无左子树，则将左指针指向其前驱结点；
若无右子树，则将右指针指向其后继结点。

前驱结点

若左指针为线索，则其指向结点为前驱结点；
若左指针为左孩子，则其左子树的最右侧结点为前驱结点。

后继结点

若右指针为线索，则其指向结点为后继结点；
若右指针为右孩子，则其右子树的最左侧结点为后继结点。

中序线索二叉树，将中序序列中对应的结点结构中空指针设置前驱和后继，并设置头节点，指向根和尾结点，而左子树最后一个元素的前驱和右子树的尾结点元素的后继指向头节点。称为线索链表。

#include <stdio.h>
#include <stdlib.h>
#define ElementType int

struct ThreadNode{
	ElementType data;
	struct tree *Left;
	struct tree *Right;
	int Ltag;//0代表左孩子,1代表前驱 
	int Rtag; //0代表右孩子,1代表后继 
}; 
//中序线索二叉树线索化 
//&引用结构体得到的只是一个对象，不能当指针用，需要加*标记为指针才可以使用 ！！！！！！！！！！ 
void InThread(struct ThreadNode *&p,struct ThreadNode *&pre){
	if(p!=NULL){
		InThread(p->Left,pre);//递归左孩子
		
		 //对叶子节点的左孩子制作线索，线索为前驱结点 
		if(p->Left==NULL){
			p->Left=pre;
			p->Ltag=1;
		}
		//从第二个结点开始前驱结点的右孩子如果空则将其线索指向当前结点 
		if(pre!=NULL && pre->Right==NULL){
			pre->Right=p;
			pre->Rtag=1;
		}
		
		pre=p;//将前驱结点置为当前结点 
		
		InThread(p->Right,pre);//递归右孩子 
	} 
}

/*初始化和收尾工作，传入第一个NULL为前驱，
将最后一个结点右孩子后继设置为NULL，也可以设置一个头节点，
将第一个结点的左孩子和最后一个结点的右孩子指向头节点，
头节点中左孩子和右孩子指向根节点和最后一个结点*/ 
void createThread(struct ThreadNode *p){
struct ThreadNode *pre=NULL;
if (p!=NULL){
	InThread(p,pre);
	pre->Right=NULL;
	pre->Rtag=1;
	} 
} 

//线索二叉树的遍历
 struct ThreadNode *Firstnode(struct ThreadNode *p){
 	while(p->Ltag==0)
 		p=p->Left;		
 	return p;
 } 
 
 struct ThreadNode *Nextnode(struct ThreadNode *p){
 	if(p->Rtag==0)
 		return Firstnode(p->Right);
 	else 
 		return p->Right;
 }
 //遍历主函数
 void Inorder(struct ThreadNode *T){
 	for(struct ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
 		printf("%d",p->data);
 }
 
struct ThreadNode* Insert(ElementType k,struct ThreadNode *BST){
	if(!BST){
		//若原树为空，则生成一个结点得二叉排序树 
		BST=(ThreadNode*)malloc(sizeof(struct ThreadNode));////!!!!!!!!!!!!!!!!!!!!!!!!!不用结构体声明，直接申请，指针已经传进来了 
		BST->data=k;
		BST->Ltag=BST->Rtag=0;
		BST->Left=BST->Right=NULL;
	}else{//找插入元素得位置 
		if(k<BST->data){
			BST->Left=Insert(k,BST->Left);//递归插入左子树 
		}else if(k>BST->data){
			BST->Right=Insert(k,BST->Right);//递归插入右子树 
		}
		
		//else k已经存在，什么都不做 
	}
	
	return BST; 
}

//中序线索二叉树
int main(){
	struct ThreadNode* Insert(ElementType k,struct ThreadNode *BST);
	void createThread(struct ThreadNode *p);
	void Inorder(struct ThreadNode *T);
	void InOrderTraversal(struct ThreadNode *BT);
	
	
	struct ThreadNode *p=NULL;	
	p=Insert(6,p);
	p=Insert(2,p);
	p=Insert(1,p);
	p=Insert(3,p);
	p=Insert(7,p);
	p=Insert(9,p);
	createThread(p);
	Inorder(p);
	return 0;
}

完全二叉搜索树

完全二叉搜索树=二叉搜索树+完全二叉树

特点：不浪费空间，使用数组更加方便，使用层序遍历==直接输出

算法思想:首先从小到大排序，找根节点，分为左右子树，再递归将左右子树分别填入

####堆

**优先队列：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）**大小，而不是元素进入队列的先后顺序。

基本结构体及构建

struct HeapStruct{
	ElementType *data;//储存堆元素的数组
	int Size;//堆当前元素的个数 
	int Capacity; //堆的最大容量 
}; 
struct HeapStruct* Create(int Maxsize){
	struct HeapStruct *p=(HeapStruct*)malloc(sizeof(struct HeapStruct));
	p->data=(ElementType*)malloc((Maxsize+1) * sizeof(ElementType));//从1开始存 
	p->Size=0;
	p->Capacity=Maxsize;
	p->data[0]=Maxdata;
	//定义哨兵，大于堆中所有可能元素的值，便于以后更快操作；
	return p; 
}

堆的插入

/*保证插入后仍然是完全二叉树，且每个结点都是其子树所有结点的最大值 
1.按顺序插入到最后一个位置
2.调整整个树使其称为最大堆 */
void Insert(struct HeapStruct *p,ElementType k){
	//将元素k插入最大堆p，其中p->data[0]已经定义为哨兵 
	int i;
	if(IsFull(p)){
		printf("最大堆已满");
		return; 
	}
	i=++p->Size;//i指向插入堆中的最后一个元素的位置 
	for(;p->data[i/2]<k;i/=2)//如果不加哨兵，需要增加 && i>1  
		p->data[i]=p->data[i/2];//向下过滤结点i/2是父节点位置 
	p->data[i]=k; //将k插入 	
}

堆的删除

/*删除最大元素或某个元素用最后一个元素代替当前位置，
并调整堆为最大堆，向下比较，并交换位置 */
ElementType DeleteMax(struct HeapStruct *p){
	int parent,Child;
	ElementType Max,temp;
	if(IsEmpty(p)){
		printf("最大堆已空");
		return; 
	} 
	Max=p->data[1];//取出树根结点最大值；
	/*用最大堆中最后一个元素从根节点开始向上过滤下层结点*/
	temp=p->data[p->Size--];//取出最后一个元素并且将整体Size减一 
	for(Parent=1;Parent*2<=p->Size;Parent=Child);{//第三个函数在每一轮结束后执行 
		Child=Parent*2;
		if((Child!=p->Size) && (p->data[Child]<p->data[Child+1]))
			Child++;//Child 指向左右子结点较大者
		if(temp>=p->data[Child])break;
		else p->data[Parent]=p->data[Child]; 
	}
	p->data[Parent]=temp;
	return Max;	
}
//最小堆
ElementType DeleteMin(struct HeapStruct *p){
	int Parent,Child;
	ElementType Min,temp;
	if(IsEmpty(p)){
		printf("最小堆已空");
		return 0; 
	} 
	Min=p->data[1];//取出树根结点最小值；
	/*用最小堆中最后一个元素从根节点开始向上过滤下层结点*/
	temp=p->data[p->Size--];//取出最后一个元素并且将整体Size减一 
	for(Parent=1;Parent*2<=p->Size;Parent=Child){//第三个函数在每一轮结束后执行 
		Child=Parent*2;
		if((Child!=p->Size) && (p->data[Child]>p->data[Child+1]))
			Child++;//Child 指向左右子结点较小者
		if(temp<=p->data[Child])break;
		else p->data[Parent]=p->data[Child]; 
	}
	p->data[Parent]=temp;
	return Min;	
}

如何建立一个堆？
- 一个一个的插入(效率低)
- 在线性时间复杂度下建立最大堆。
  - 将N个元素按输入顺序存入，先满足完全二叉树的结构性；
  - 调整各结点位置，以满足最大堆的有序特性。
思路：从倒数第一个有儿子的父结点(size/2)开始一个一个调整(删除结点的思路)为堆

//调整为最大堆
struct HeapStruct* CreatMaxHeap(struct HeapStruct *p){
	int Parent,Child,Parent1,Child1;
	ElementType temp;
	if(IsEmpty(p)){
		printf("最大堆已空");
		return NULL; 
	} 
	/*用最后一个元素从倒数第一个父结点开始自下向上过滤结点*/
	for(Parent=p->Size/2;Parent>=1;Parent--){//从倒数第一个父结点开始依次递减 ， 
	Child=Parent*2;
	Parent1=Parent;
	Child1=Child;
		for(;Parent1*2<=p->Size;Parent1=Child1){
			Child1=Parent1*2;
			if((Parent1*2!=p->Size)&&(p->data[Child1]<p->data[Child1+1]))
				Child1++;
			if(p->data[Child1]>p->data[Parent1]){
				temp=p->data[Parent1];
				p->data[Parent1]=p->data[Child1];
				p->data[Child1]=temp; 
		    }		
	    }
	}
	return p;
} 
//调整为最小堆
struct HeapStruct* CreatMinHeap(struct HeapStruct *p){
	int Parent,Child,Parent1,Child1;
	ElementType temp;
	if(IsEmpty(p)){
		printf("最小堆已空");
		return NULL; 
	} 
	/*用最后一个元素从倒数第一个父结点开始自下向上过滤结点*/
	for(Parent=p->Size/2;Parent>=1;Parent--){//从倒数第一个父结点开始依次递减 ， 
	Child=Parent*2;
	Parent1=Parent;
	Child1=Child;
		for(;Parent1*2<=p->Size;Parent1=Child1){
			Child1=Parent1*2;
			if((Parent1*2!=p->Size)&&(p->data[Child1]>p->data[Child1+1]))
				Child1++;
			if(p->data[Child1]<p->data[Parent1]){
				temp=p->data[Parent1];
				p->data[Parent1]=p->data[Child1];
				p->data[Child1]=temp; 
		    }		
	    }
	}
	return p;
} 


int IsFull(struct HeapStruct *p){
	if (p->Capacity==p->Size)return 1;
	else return 0; 
}

int IsEmpty(struct HeapStruct *p){
	if (p->Size==0)return 1;
	else return 0; 
}

int main(){
	struct HeapStruct* CreatHeap(struct HeapStruct *p);
	ElementType DeleteMax(struct HeapStruct *p);
	void Insert(struct HeapStruct *p,ElementType k);
	struct HeapStruct* Create(int Maxsize);
	
	struct HeapStruct *p=Create(12);
	int a;
//	Insert1(p,83);
//	Insert1(p,87);
//	Insert1(p,43);
//	Insert1(p,72);
//	Insert1(p,91);
//	for(int i=1;i<6;i++)printf("%d",p->data[i]);
//	int a=DeleteMax(p);
//	int b=DeleteMin(p);
//	printf("\n");
//	for(int i=1;i<5;i++)printf("%d",p->data[i]);
	for(int i=1;i<13;i++){
		scanf("%d",&a);
		p->data[i]=a;
	}
	p->Size=12;
	p=CreatMinHeap(p); 
	for(int j=0;j<13;j++)printf("%d ",p->data[j]);
	printf("\n");
	a=DeleteMin(p);
	for(int j=0;j<12;j++)printf("%d ",p->data[j]);
	
	return 0;
}

哈夫曼树和编码

#####(考)哈夫曼树

定义：带权路径长度(WPL)：设二叉树有n个叶子结点，每个叶子结点带有权值 $W_k$ ,从根结点到每个叶子结点的长度为 $L_k$ ,则每个叶子结点的带权路径长度之和就是： $WPL=\sum_{k=1}^nW_kL_k$

最优二叉树或哈夫曼树：WPL最小的二叉树。

哈夫曼树构造：

由一段有序序列（可以用堆实现，效率更高O(NlogN)）中挑选最小的两个合并为一棵树后将权值重新加入排序，重复上述过程直到创建树成功.

哈夫曼树特点：

没有度为1的结点
n个叶子结点的哈夫曼树共有2n-1个结点；
哈夫曼树的任意非叶子结点的左右子树交换后仍是哈夫曼树；
对同一组权值**{ $w_1,w_2,...,w_n$ },存在不同构的哈夫曼树，但WPL**值相同。

//代码实现
#include <stdio.h>
#include <stdlib.h>
#define ElementType int
#define Mindata 0; 
//数据结构部分
struct tree{
	ElementType data;//数据 
	int Weight;//权重 
	struct tree *Left;
	struct tree *Right; 
}; 

struct HeapStruct{
	struct tree *data;//储存堆元素的数组
	int Size;//堆当前元素的个数 
	int Capacity; //堆的最大容量 
}; 

int IsFull(struct HeapStruct *p){
	if (p->Capacity==p->Size)return 1;
	else return 0; 
}

int IsEmpty(struct HeapStruct *p){
	if (p->Size==0)return 1;
	else return 0; 
}
//创建一个堆
struct HeapStruct* Create(int Maxsize){
	struct HeapStruct *p=(HeapStruct*)malloc(sizeof(struct HeapStruct));
	p->data=(tree*)malloc((Maxsize+1)*sizeof(struct tree));//从1开始存 
	p->Size=0;
	p->Capacity=Maxsize;
	p->data[0].data= Mindata;//结构体中嵌套结构体是对象，并不是指针
	p->data[0].Weight=Mindata;
	for(int i=1;i<=Maxsize;i++){
		p->data[i].Left=NULL;//树的左右指针要置空，否则最后遍历无法运行
		p->data[i].Right=NULL; 
	} 
	//定义哨兵，大于堆中所有可能元素的值，便于以后更快操作；
	return p; 
} 

//将一个结构体插入最小堆
//将结构体插入最小堆 
void InsertMin(struct HeapStruct *p,struct tree q){
	//将元素k插入最小堆p，其中p->data[0]已经定义为哨兵 
	int i;
	if(IsFull(p)){
		printf("最小堆已满");
		return; 
	}
	i=++p->Size;//i指向插入堆中的最后一个元素的位置 
	for(;p->data[i/2].Weight>q.Weight;i/=2)//如果不加哨兵，需要增加 && i>1  
		p->data[i]=p->data[i/2];//向下过滤结点i/2是父节点位置 
	p->data[i]=q; //将q插入
}

//删除最小元素
struct tree DeleteMin(struct HeapStruct *p){
	int Parent,Child;
	struct tree Min,temp;
	if(IsEmpty(p)){
		printf("最小堆已空");
	} else{
	
	Min=p->data[1];//取出树根结点最小值；
	/*用最大堆中最后一个元素从根节点开始向上过滤下层结点*/
	temp=p->data[p->Size--];//取出最后一个元素并且将整体Size减一 
	for(Parent=1;Parent*2<=p->Size;Parent=Child){//第三个函数在每一轮结束后执行 
		Child=Parent*2;
		if((Child!=p->Size) && (p->data[Child].Weight>p->data[Child+1].Weight))
			Child++;//Child 指向左右子结点较大者
		if(temp.Weight<=p->data[Child].Weight)break;
		else p->data[Parent]=p->data[Child]; 
	}
	p->data[Parent]=temp;
	return Min;//返回的是一个结构体变量
    }
}
//调整一个堆为最小堆
void CreatMinHeap(struct HeapStruct *&p){
	int Parent,Child,Parent1,Child1;
	struct tree temp;
	if(IsEmpty(p)){
		printf("最小堆已空");
		return; 
	} 
	/*用最后一个元素从倒数第一个父结点开始自下向上过滤结点*/
	for(Parent=p->Size/2;Parent>=1;Parent--){//从倒数第一个父结点开始依次递减 ， 
	Child=Parent*2;
	Parent1=Parent;
	Child1=Child;
		for(;Parent1*2<=p->Size;Parent1=Child1){
			Child1=Parent1*2;
			if((Parent1*2!=p->Size)&&(p->data[Child1].Weight>p->data[Child1+1].Weight))
				Child1++;
			if(p->data[Child1].Weight<p->data[Parent1].Weight){
				temp=p->data[Parent1];
				p->data[Parent1]=p->data[Child1];
				p->data[Child1]=temp; 
		    }		
	    }
	}
} 
//哈夫曼树  
struct tree* Huffmantree(struct HeapStruct *&p){
	struct tree *T;
	CreatMinHeap(p);//调整堆
	while(p->Size>1){//做p->size -1 次合并
		T=(tree*)malloc(sizeof(struct tree));//建立新的结点
		T->Left=(tree*)malloc(sizeof(struct tree));//没有申请空间不能使用 
		T->Right=(tree*)malloc(sizeof(struct tree));
		*T->Left=DeleteMin(p);//将从堆中删除的结构体置入新T的左子结点
		*T->Right=DeleteMin(p);//将从堆中删除的结构体置入新T的右子结点
		
		T->Weight=T->Left->Weight+T->Right->Weight;//合并左右子结点权重
		InsertMin(p,*T);//将T插入到堆中重新排序
	}
	*T=DeleteMin(p);//最后一个结点就是根节点，直接弹出
	
	return T; 
} 

int main(){
    //一定要和函数对应上TAT 特别是改了以后
	void InOrderTraversal(struct tree *BT); 
	void PreOrderTraversal(struct tree *BT);
	void CreatMinHeap(struct HeapStruct *&p);
	struct tree* Huffmantree(struct HeapStruct *&p);
	struct tree DeleteMin(struct HeapStruct *p);
	void InsertMin(struct HeapStruct *p,struct tree q);
	struct HeapStruct* Create(int Maxsize);
	
    struct HeapStruct *pp;
    pp=Create(10);
    for(int i=1;i<7;i++){
		scanf("%d",&pp->data[i].Weight);	
	}
    pp->Size=6;
    for(int i=1;i<7;i++){
	printf("%d ",pp->data[i].Weight);	
	}
    printf("\n");
    w=Huffmantree(pp);
    PreOrderTraversal(w);//先序遍历
	printf("\n");
	InOrderTraversal(w);//中序遍历
    
    return 0;
}

#####哈夫曼编码

Q:给定一段字符串，如何对字符进行编码，可以使该字符串的编码存储空间最少？

按照频率给定权值

Q:如何避免二义性？

前缀码：任何字符的编码都不是另一字符编码的前缀

用二叉树进行编码：

左右分支：0、1
字符只在叶结点上

###图

表示多对多的关系
包含
- 一组顶点：通常用 V(Vertex) 表示顶点集合
- 一组边：通常用 E(Edge) 表示边的集合
  - 边是顶点对：(v,w) ∈ E，其中 v,w ∈ V
  - 有向边 <v,w> 表示从 v 指向 w 的边(单行线)
  - 不考虑重边和自回路

图的表示法

邻接矩阵法

Q:对于无向图的存储，怎样可以省一半的空间？

用一个长度为N/(N+1)/2 的1 维数组 A 存储{ $G_{00},G_{10},G_{11},G_{20},G_{21},...,G_{n-1, 0}，...，G_{n-1,n-1}$ },则 $G_{i,j}$ 在A中对应的下标为： $(i*(i+1)/2+j)$
对于网络，只要把 $G[i][j]$ 的值定义为边< $v_i,v_j$ >的权重即可。

对于稀疏图浪费空间(稠密图还是很合算)，也浪费时间。

邻接表

方便找任一顶点的所有“邻接点”
节约稀疏图的空间
- 需要N个头指针 + 2E 个结点（每个结点至少2个域）
只方便计算无向图的度，不太适合有向图

图的遍历

(考)DFS 深度优先搜索

//递归访问,抽象表示，类似于树的先序遍历，栈也可
void DFS(Vertex V){//传入一个起始点
    visited[V]=true;
    for ( V的每个邻接点 W )
        if(!visited [W])
            DFS(w);
}

//代码

//深度优先搜索 
void DFS(struct GNode *Graph,int n,int visited[]){//G为已知图，n为起始点 
	int i;
	printf("%d",Graph->Data[n]);//先输出起始顶点，再输出访问的其他顶点
	visited[n]=1;//事先将起始顶点标记为true
	for(i=0;i<Graph->Nv;i++){
		 if(Graph->G[n][i]!=0 && visited[i]==0)///若第i个顶点与G->Data[n]有关，并且未被访问
        {
            DFS(Graph,i,visited);///用递归的方式继续搜寻
        }
	}
	for(i=0;i<Graph->Nv;i++)
    {
        if(visited[i]==0)///此循环用于判断顶点是否访问完成
        {
             DFS(Graph,i,visited);///用递归的方式继续搜寻，直至所有顶点访问完毕
        }
    }
}

采用队列实现

若有N个顶点、E条边，时间复杂度是

用邻接表存储图，有O(N+E)
用临界矩阵存储图，有O(N^2)

(考)BFS 广度优先搜索

//类似层序遍历队列实现，每次出队时入队相邻未访问元素
void BFS(Vertex V){
    visited[V]= true;
    Enqueue(V,Q);
    while(!IsEmpty(Q)){
        V = Dequeue(Q);
        for(V 的每个邻接点 W){
            if(!visited[W]){
                visited[W] = true;
                Enqueue(W,Q);
            }
        }
    }
}

//代码
#include <stdio.h>
#include <stdlib.h> 
#define ElementType int
#define WeightType int
#define DataType int
#define MaxVertexNum 20
#define Maxsize 5

struct Node{
	ElementType Data[Maxsize];
	int front;
	int rear;
}; 

struct Node* initNode(){
	struct Node *p;
	p=(Node*)malloc(sizeof(struct Node));
	p->front=0;
	p->rear=0;
	return p;
}

//循环队列 数组内只放放n-1个元素防止误判 满/空 尾(rear)进头(front)出 
void Add(struct Node *p,ElementType k){
	if((p->rear+1)%Maxsize==p->front){
		printf("队列满"); 
	}else{
		p->rear=(p->rear+1)%Maxsize;//最后一位会变零
		p->Data[p->rear]=k;
	}
}

//出队列
ElementType Delete(struct Node *p){
    if(p->front==p->rear){
        printf("队列空");
        return -1;
    }else{
        p->front=(p->front+1)%Maxsize;
        return p->Data[p->front];
    }
}
void BFS(struct GNode *Graph,int visited[],struct Node *p){//图、起始点、顶点数量、辅助数组、辅助队列 

	for(int i=0;i<Graph->Nv;i++){
		if(!visited[i]){//从未访问过该顶点 
			visited[i]=1; 
			printf("%d\n",Graph->Data[i]);
			Add(p,i);
			while(p->front!=p->rear){
				i=Delete(p);//出队需要访问的顶点下标 
				for(int j=0;j<Graph->Nv;j++){
					if(Graph->G[i][j]==1 && !visited[j]){//其他顶点与改顶点有联系 且未访问 
						visited[j]=1;
						printf("%d\n",Graph->Data[j]);//访问已出队的顶点 
						Add(p,j);//入队未访问的顶点下标 
					}
					
				}				
			}
			
		}
		
	}
		
}

若有N个顶点、E条边，时间复杂度是

用邻接表存储图，有O(N+E)
用临界矩阵存储图，有O(N^2)

每调用一次BFS/BFS 就是把 V 所在的连通分量遍历了一遍。

####如何建立一个图

//邻接矩阵
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;//顶点数
    int Ne;//边数
    WeightType G[MaxVertexNum][MaxVertexNum];
    DataType Data[MaxVertexNum];//存放顶点的数据，顶点表vertex
};
typedef PtrToGNode MGraph;//指针别名

//步骤1：初始化一个有VertexNum 个顶点但 没有边 的图
 typedef int Vertex;//用顶点下标表示顶点，为整型
MGraph CreateGraph(int VertexNum){
    Vertex V,W;//区分出入的顶点个数VertexNum
    MGraph Graph;
    
    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
    //注意这里默认顶点编号从0开始，到(Graph->Nv-1)
    for(V=0;V<Graph->Nv;V++)
        for (W=0;W<Graph->Nv;W++)
            Graph->G[V][W]=0;
    return Graph;
}
//步骤2：向图中插入边
typedef struct ENode *PtrToENode;
struct ENode{
  Vertex V1,V2;//有向边<V1,V2>,两个顶点
  WeightType Weight;//权重
};
typedef PtrToENode Edge;

void InsertEdge(MGraph Graph,Edge E){
    //插入边，有向图只用插一边<V1,V2>，无向图要两边
    Graph->G[E->V1][E->V2]=E->Weight;
    //无向图 插入<V2,V1>
    Graph->G[E->V2][E->V1]=E->Weight;
}

//完整的建立一个图
MGraph BuildGraph(){
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv,i;
    
    scanf("%d",&Nv);
    Graph = CreateGraph(Nv);
    scanf("%d",&(Graph->Ne));//直接读入 赋值边 输入函数不能加花里胡哨的东西
    if (Graph->Ne!=0){
        E = (Edge)malloc(sizeof(struct ENode));//临时
        for(i=0;i<Graph->Ne;i++){
            scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
            InsertEdge(Graph,E);
        }        
    }
    //如果顶点有数据的话，读入数据
    for(V=0; V<Graph->Nv;V++)
        scanf(" %c",&(Graph->Data[V]));
    
    return Graph;
}
//考试应急
int G[MAXN][MAXN],Nv,Ne;
void BuildGraph(){
    int i,j,v1,v2,w;
    
    scanf("%d",&Nv);
    //创建图
    for(i=0;i<Nv;i++){
        for(j=0;j<Nv;j++){
            G[i][j]=0;
        }
    }
    scanf("%d",&Ne);
    for(i=0;i<Ne;i++){
        scanf("%d %d %d",&v1,&v2,&w);
        //插入
        G[v1][v2]=w;
        G[v2][v1]=w;
    }
    
}

单元最短路径

(考)Dijkstra

template<class Type>
void Dijkstra(int n,int v,Type dist[],int prev[],Type **c){
    bool s[maxint];
    for(int i=1;i<=n;i++){
        dist[i]=c[v][i];
        s[i]=false;
        if(dist[i]==maxint)
            prev[i]=0;
        else
            prev[i]=v;//当前i顶点对应的前一个顶点下标
    }
    dist[v]=0;s[v]=true;
    for(int i=1;i<n;i++){
        int temp=maxint;
        int u=v;
        for(int j=1;j<=n;j++){
            if((!s[j])&&(dist[j]<temp)){
                u=j;
                temp = dist[j];
            }
            s[u]=true;
            for(int j=1;j<=n;j++){
                if((!s[j])&&(c[u][j]<maxint)){
                    Type newdist =dist[u]+c[u][j];
                    if(newdist<dist[j]){
                        dist[j]=newdist;
                        prev[j] = u;
                    }
                }
            }
        }
    }  
}

最小生成树

定义：

是一棵树
- 无回路
- V个顶点一定有V-1条边
是生成树
- 包含全部顶点
- V-1条边都在图里
边的权重和最小

等价于图连通

贪心算法：

贪：每一步要求最好
好：权重最小的边
需要约束：
- 只能用途中有的边
- 只能正好用掉V-1条边
- 不能有回路

(考)Prim算法

算法思想：

从连通网 N={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边(U0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从集合U中的所有顶点边中选择一条最小权值边(u,v)同时此边(u,v)所连接的顶点不包含在集合U中的任何顶点，则把它的顶点加入到集合U中。如此继续下去，直到网中的所有顶点都加入到生成树顶点集合U中为止。

//时间复杂度O(|V|2)适合稠密图
//Prim
template<class Type>
Void Prim(int n,Type **c){
    Type lowcost[maxint];
    int closest[maxint];
    bool s[maxint];
    s[1]=true;
    for (int i=2;i<=n;i++){
        lowcost[i]=c[1][i];
        closest[i]=1;
        s[i]=false;
    }
    for (int i=1;i<n;i++){
        Type min=inf;
        int j=1;
        //找中使用权值最小的顶点j
        for(int k=2;k<=n;k++){
            if((lowcost[k]<min)&& (!s[k])){
                min=lowcost[k];
                j=k;
            }
        }
        //找到符合贪心选择方式的边，将顶点j加入到集合S
        cout<<j<<' '<<closest[j]<<endl;
        s[j]=true;
        
        //找到一条边后，更新数组closest和lowcost
        for(int k=2;k<=n;k++){
        	if((c[j][k]<lowcost[k]) && (!s[k])){
            	lowcost[k]=c[j][k];
                closest[k]=j;
        	}
        }
    }
}

Kruskal算法

算法思想：

把森林合并成树

1	//时间复杂度（使用最小堆放权重集合并查集检查回路）O(\|E\|log\|E\|) 适合稀疏图

(考)查找和内部排序

#include<stdio.h>
#define ElementType int

void Swap(ElementType *x,ElementType *y){
    ElementType temp;
    temp = *x;
    *x=*y;
    *y=temp;
    
}

void Swap1(ElementType &x,ElementType &y){
    int temp=0;
    temp = x;
    x=y;
    y=temp;
    
}
int main(){
	void Bubble_Sort(ElementType A[],int N);
	int x[]={1,4,2,5,8,9}; 
	Bubble_Sort(x,6);
	
	for(int i =0;i<6;i++){
		printf("%d",x[i]);
	}
	return 0;
}

简单排序

冒泡排序

算法思想：比较相邻两个元素大小，若从小到大排则将大元素始终置后，每一趟完成会将最大的元素放到确定的位置。

void Bubble_Sort(ElementType A[],int N){
	for(int p=N-1;p>=0;p--){
    int flag=0;//判断是否在一趟排序过程中有序，没有触发Swap
    for(int i=0;i<p;i++){//一趟
    if(A[i]>A[i+1]){
    	//a=&A[i];
    	//b=&A[i+1];
        //Swap(a,b);
        Swap1(A[i],A[i+1]);
        flag=1;//发生了交换
    }
    }
        if(flag==0)break;
    }
}//适合单向链表，同一顺序，稳定 最好O(N)最坏O(N^2) 平均O(N^2)

插入排序

算法思想：从前往后取数，并从取数位置从后向前比较，将每一个数向后移，插入到合适得位置，从第一个数开始，第零个不动。

void Insertion_Sort(ElementType A[],int N){
	int i;
    ElementType tmp;
	for(int P=1;P<N;P++){
		tmp=A[P];//摸下一张，从前往后 
		for( i=P;i>0 && A[i-1]>tmp;i--){
			A[i]=A[i-1];//移出空位 
		}
	    A[i]=tmp;//新牌落位 
	}
}//稳定，最好O(N)最坏O(N^2) 平均O(N^2)

希尔排序

算法思想：通过设定增量序列，实现插入排序

void Shell_sort(ElementType A[],int N){
	int i;
    ElementType tmp;
	for(int D=N/2;D>0;D/=2){
		for(int P=D;P<N;P++){
		tmp=A[P];//摸下一张，从前往后 
		for( i=P;i>=D && A[i-D]>tmp;i-=D){
			A[i]=A[i-D];//移出空位 
		}
	    A[i]=tmp;//新牌落位 
	}		
	}	
}//最坏O(N^2) Hibbard 增量 Dk=2^k-1-相邻元素互质，不互质小增量排序没效果，最坏(O^3/2)

选择排序

void Selection_Sort(ElementType A[],int N){
    for(int i=0;i<N;i++){
        MinPosition = ScanForMin(A,i,N-1);
        //从A[i]到A[i-1]中找到最小元，并将其位置赋值给MinPosition
        Swap1(A[i],A[MinPosition]);
    }
}

堆排序

//算法1 时间O(NlogN) 并且需要额外O(N)空间，并且复制元素需要时间
void Heap_Sort(ElementType A[],int N){
    BuildHeap(A);// O(n)小顶堆/最小堆
    for(int i =0;i<N;i++)
        TmpA[i]=DeleteMin(A);//O(logN)
    for(int i=0;i<N;i++)//O(N)
        A[i]=TmpA[i];
}
//算法2 时间2NlogN-O(NloglogN) 
//通过调整最大堆，完成后将根结点最大元素与最小元素交换位置，并剔除最大元素，将剩余元素继续执行上述过程 由小到大排序
void Heap_Sort(ElementType A[],int N){
    for(int i=N/2-1;i>=0;i--)//BuildHeap
        PercDown(A , i ,N);
	for(int i=N-1;i>=0;i--){
        swap(A[0],A[i]);//deleteMax
        PercDown(A,0,i);   
    }
}

void PercDown(ElementType A[],int i,int N){
    int parent,child;
    ElementType temp;
	for(parent=i;parent*2+1<N;parent=child){//A[0]不是哨兵了
	        child=parent*2+1;
	        if(child!=N-1 && A[child]<A[child+1])
	            child++;
	        if(A[parent]<A[child]){
				temp=A[parent];
	            A[parent]=A[child];
	            A[child]=temp;
	        }
	}	
}

归并排序

核心：两个有序子列得归并

思想：比较两个序列中元素得大小，挑出小元素放到第三个序列中,适合外部排序

递归方式

//时间 O(N) 两个子列一共有N个元素
//L=左边起始位置(Aptr) R=右边起始位置(Bptr) RightEnd=右边终点位置
void Merge(ElementType A[],ElementType TmpA[],int L,int R,int RightEnd){
    int leftEnd=R-1;//左边终点位置，假设左右两列挨着 在一个数组里面
    int Tmp=L;//存放结果得数组得初始位置，从第二个数组得哪个地方开始
    int NumElements = RightEnd - L + 1;//归并结束后总元素数
    while(L<=leftEnd && R<=RightEnd){
        if(A[L]<=A[R])TmpA[Tmp++]=A[L++];
        else TmpA[Tmp++]=A[R++];
    }
    while(L<=leftEnd)
        TmpA[Tmp++]=A[L++];//直接复制左边剩下的
    while(R<=RightEnd)
        TmpA[Tmp++]=A[R++];//直接复制右边剩下得
    //两个只会执行一个
    //最后将TmpA数组倒回A数组，RightEnd 始终没变(传进来后，传进来前始终在变)
    for(int i=0;i<NumElements;i++,RightEnd--)
        A[RightEnd]=TmpA[RightEnd];
}
//分而治之 时间复杂度T(N)=T(N/2)+T(N/2)+O(N)=>T(N)=O(NlogN) 稳定
//RightEnd 始终在变 递归调用
void MSort(ElementType A[],ElementType TmpA[],int L,int RightEnd){
    int Center;
    if(L<RightEnd){
        Center = (L+RightEnd)/2;
        MSort(A,TmpA,L,Center);
        MSort(A,TmpA,Center+1,RightEnd);
        Merge(A,TmpA,L,Center+1,RightEnd);
    }
}

//统一接口 重要！！！！
void Merge_sort(ElementType A[],int N){
    ElementType *TmpA;
    TmpA=(ElementType*)malloc(N * sizeof(ElementType));
    if (TmpA!=NULL){
        MSort(A,TmpA,0,N-1);
        free(TmpA);//释放临时数组
    }
    else Error("内存不足");
}

过程图解：解决一段导回去一段

不合算，重复malloc

非递归方式

算法思想：利用临时数组，两边倒

void Merge1(ElementType A[],ElementType TmpA[],int L,int R,int RightEnd){
    int leftEnd=R-1;//左边终点位置，假设左右两列挨着 在一个数组里面
    int Tmp=L;//存放结果得数组得初始位置，从第二个数组得哪个地方开始
    int NumElements = RightEnd - L + 1;//归并结束后总元素数
    while(L<=leftEnd && R<=RightEnd){
        if(A[L]<=A[R])TmpA[Tmp++]=A[L++];
        else TmpA[Tmp++]=A[R++];
    }
    while(L<=leftEnd)
        TmpA[Tmp++]=A[L++];//直接复制左边剩下的
    while(R<=RightEnd)
        TmpA[Tmp++]=A[R++];//直接复制右边剩下得
    //两个只会执行一个
}

void Merge_pass(ElementType A[],ElementType TmpA[],int N,
               int length){//length = 当前有序子序列长度
    int i;
    for(i=0;i<=N-2*length;i+=2*length)
        Merge1(A,TmpA,i,i+length,i+2*length-1);//将A中元素归并到TmpA而不直接倒回来
    //处理最后两个
    if(i+length<N)//归并最后两个子列
        Merge1(A,TmpA,i,i+length,N-1);
    else//最后剩一个,直接倒进去就可以了
        for(int j=i;j<N;j++)TmpA[j]=A[j];
}

//统一接口 重要！！！！
void Merge_sort1(ElementType A[],int N){
    ElementType *TmpA;
    int length=1;//长度为1开始一次两个
    TmpA=(ElementType*)malloc(N * sizeof(ElementType));
    if (TmpA!=NULL){
        while(length<N){
            Merge_pass(A,TmpA,N,length);
        	length *=2;
            Merge_pass(TmpA,A,N,length);
            length *=2;//两边确保最后一次将TmpA中得序列倒回 A中
            
        }
          
        free(TmpA);//释放临时数组
    }
    else Error("内存不足");
}

快速排序

算法思想：分而治之(递归)，首先随机找一个数作为主元，将集合分为以主元为标识得左右两集合，通过递归将两个集合排序，最后合并三部分(左集合，主元，右集合)。

//最好情况，每次主元中分两个数组O(nlogn) 最坏O(N^2)
//选取头 中 尾得中位数 采用交换得方式，将头 中 尾处理为小到大得序列，选中间
ElementType Median3(ElementType A[],int Left,int Right){
    int Center=(Left+Right)/2;
    if(A[Left]>A[Center])
        Swap(A[Left],A[Center]);
    if(A[Left]>A[Right])
        Swap(A[Left],A[Right]);
    if(A[Center]>A[Right])
        Swap(A[Center],A[Right]);
    //A[Left]<=A[Center]<=A[Right]
    Swap(A[Center],A[Right-1]);//将pivot藏到右边倒数第二个，
    //只需考虑A[Left+1],A[Right-2]，因为第一个和最后一个已经比它小和大
    return A[Right-1];
}

void Quicksort(ElementType A[],int Left,int Right){
    if(Right-1>0 && Left+1<Right){//判断数组是否越界，越界直接退出
	int Pivot=Median3(A,Left,Right);
    int i=Left;
    int j=Right-1;
    
    for( ; ; ){
        //A[Left+1],A[Right-2]
        while(A[++i]<Pivot){}
        while(A[--j]>Pivot){}
        //两边都出现问题
        if(i<j)
            //说明都出现问题 可以调换
            Swap(&A[i],&A[j]);
        else break;//i>j 调换
    }
    
    Swap(&A[i],&A[Right-1]);//将Center这个数放到自己得位置上
    Quicksort(A,Left,i-1);//递归将两边集合继续划分子集排序
    Quicksort(A,i+1,Right);
	}   
}

void Quick_Sort(ElementType A[],int N){
    Quicksort(A,0,N-1);//数组下标
}

表排序

算法思想：间接排序，定义一个指针数组(数组下标/指针)作为“表”(table)

N个数字得排列一定是由若干个独立得环组成
- 每完成一个移动就重置table等于自己，最后一个环放置第一个拿出去的临时数

基数排序

算法思想：采用LSD”次位优先“，首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中，接下来将这些桶子中的数值重新串接起来，接着再进行一次分配，这次是根据十位数来分配，接下来将这些桶子中的数值重新串接起来，这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。