Java数据结构

一、队列

1.多项式相关

加法运算实现

Polynomial PolyAdd (Polynomial P1, Polynomial P2){
    Polynomial front, rear, temp;
    int sum;
    rear=(Polynomial) malloc(sizeof(struct PolyNode));/*由front记录结果多项式链表头结点*/
    front = rear;
    while(P1 && P2)/*当两个多项式都有非零项待处理时*/
        switch (Compare(P1->expon, P2->expon)){
            case 1:
                Attach( P1->coef, P1->expon, &rear);
                P1 = P1->link;break;
            case -1:
                Attach(P2->coef, P2->expon, &rear);
                P2 = P2->link;break;
            case 0:
                sum =P1->coef + P2->coef;
                if ( sum )Attach(sum, P1->expon, &rear);
                P1 = P1->link;
                P2 = P2->link;
                break;
        }
	/*将未处理完的另一个多项式的所有节点依次复制到结果多项式中去*/
    for( ; P1; P1=P1->link)Attach(P1->coef, P1->expon, &rear);
    for( ; P2; P2 = P2->link)Attach(P2->coef, P2->expon, &rear);
    rear->link = NULL;
    temp = front;
    front=front->link;/*令front指向结果多项式第一个非零项*/
    free(temp);/*释放临时空表头结点*/
    return front;
}

void Attach( int c, int e, Polynomial *pRear )
{
    Polynomial P;
    P=(Polynomial)malloc(sizeof(struct PolyNode));
    P->coef=c;/*对新结点赋值*/
    P->expon = e;
    P->link = NULL;
    (*pRear)->link= P;
    *pRear = P;/*修改pRear值 */
}

2.多项式练习题

方法一：

数组：编程简单、调试容易；事先确定数组大小

链表：动态性强；编程略微复杂、调试比较困难

数据结构设计

typedef struct PolyNode *Polynomial;
struct PolyNode{
    int coef;
    int expon;
    Polynomial link;
}

程序框架：

读入程序：
Polynomial ReadPoly()
{
   Polynomial P, Rear, t;
    int c, e, N;
    
    scanf("%d",&N);
    P=(Polynomial)malloc(sizeof(struct PolyNode));/*链表头空结点 */
    P->link = NULL;
    Rear = P;
    while(N--){
        scanf("%d %d", &c, &e);
        Attach(c, e, &Rear);/*将当前项插入多项式尾部*/
    }
    t=P;P=P->link; free(t);/*删除临时生成的头结点*/
    return P; 
}

void  lynomial *pRear )
{
    Polynomial P;
    P=(Polynomial)malloc(sizeof(struct PolyNode));
    P->coef=c;/*对新结点赋值*/
    P->expon = e;
    P->link = NULL;
    (*pRear)->link= P;
    *pRear = P;/*修改pRear值 */
}

二、树

1 基本概念

定义：n(n≥0)个结点构成的有限集合。当n=0时，称为空树；对于任一棵非空树(n>0)，它具备以下性质:

树中有一个称为 “根(Root)” 的特殊结点，用r表示;

其余结点可分为m(m>0)个互不相交的有限集T1，T2…. ，Tm，其中每个集合本身又是一棵树，称为原来树的“子树(Sub Tree)”

作用：用于查找。查找又分为静态和动态.

特点：

子树是不相交的；

除了根节点外，每个结点有且仅有一个父节点

一棵树N个结点的树有N-1条边

树的基本术语

结点的度(Degree)：结点的子树个数；

树的度：树的所有结点中最大的度数树的度；

叶结点(Leaf)：度为0的结点；

父结点(Parent)：有子树的结点是其子树的根结点的父结点；

子结点(Child)：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点；

兄弟结点(Sibling)：具有同一父结点的各结点彼此是兄弟结点；

路径和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，…，nk，ni是 ni+1的父结点。路径所包含边的个数为路径的长度。

祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。

子孙结点(Descendant):：某一结点的子树中的所有结点是这个结点的子孙。

11.结点的层次(Level):规定根结点在1层其它任一结点的层数是其父结点的层数加1.12.树的深度(Depth):树中所有结点中的最大层次是这棵树的深度。

2 二叉树

2.1 基本概念

2.1.1 二叉树定义

一个又穷的结点集合。这个集合可以为空，若不为空，则它是由根节点和称为其左子树T˪和右子树Tᵣ的两个不相交的二叉树组成

几个重要性质

一个二叉树第i层的最大结点数为：2ⁱ⁻¹，i≥1。

深度为k的二叉树有最大结点总数为：2ᵏ-1，k≥1

对任何非空二叉树T，若n₀表示叶结点的个数、n₂是度为2的非叶结点个数，那么两者满足关系n₀=n₂+1

2.1.2 抽象数据定义

数据对象集：一个有穷的结点集合。若不为空，则由根结点和其左、右二叉子树组成。
操作集：BT∈BinTree，ltem∈ElementType，重要操作有:

Boolean lsEmpty ( BinTree BT)：判别BT是否为空；

void Traversal ( BinTree BT)：遍历，按某顺序访问每个结点；

BinTree CreatBinTree( )：创建一个二叉树。

2.1.3 五种基本形式

2.1.4 子树左右顺序之分

2.2 特殊二叉树

2.2.1 斜二叉树

2.2.2 完美二叉树（满二叉树）

2.2.3 完全二叉树

跟满二叉树相似，但是不同点是完全二叉树可以比满二叉树少后面连续的几个度。

2.3 存储结构

2.3.1 顺序存储

注：一般二叉树也可实现这种方法，但是必须造成空间额外的开销

2.3.2 链表存储

2.4 常用的遍历

2.4.1 先序遍历

遍历过程（根、左子树、右子树）：①访问根结点；②先序遍历其左子树；③先序遍历其右子树

void Preordertraversal(BinTree BT)
{
   if( BT ){
       printf(“d", BT->Data);
       PreOrderTraversal( BT -> Left );
       PreOrderTraversal( BT -> Right );
	}
}

例：

先序遍历 => A (B D F E) (C G H I)

先序非递归遍历：

void InOrderTraversal( BinTree BT )
{
    BinTree T=BT;
    Stack S = Creatstack(MaxSize);   	/*创建并初始化堆栈S*/
    while( T || !IsEmpty(S) ){
        while( T ){ 					/*一直向左并将沿途结点压入堆栈*/
            Push( S, T);
            printf(“%5d”, T->Data);     /*(访问)打印结点*/
            T = T -> Left;
        }
        if( !IsEmpty(S) ) {
            T=Pop(S);					/*结点弹出堆栈*/
            T=T->Right;					/*转向右子树*/
        }
    }
}

2.4.2 中序遍历

遍历过程（左子树、根、右子树）：①先序遍历其左子树；②访问根结点；③先序遍历其右子树；

void Preordertraversal(BinTree BT)
{
   if( BT ){
       PreOrderTraversal( BT -> Left );
       printf(“d", BT->Data);
       PreOrderTraversal( BT -> Right );
	}
}

例：

中序遍历=> ( D B E F ) A ( G H C I)

中序也可以用递归来实现：

遇到一个结点，就把它压栈，并去遍历它的左子树；
当左子树遍历结束后，从栈顶弹出这个结点并访问它；
然后按其右指针再去中序遍历该结点的右子树。

void InOrderTraversal( BinTree BT )
{
    BinTree T=BT;
    Stack S = Creatstack(MaxSize);   	/*创建并初始化堆栈S*/
    while( T || !IsEmpty(S) ){
        while( T ){ 					/*一直向左并将沿途结点压入堆栈*/
            Push( S, T);
            T = T -> Left;
        }
        if( !IsEmpty(S) ) {
            T=Pop(S);					/*结点弹出堆栈*/
            printf(“%5d”, T->Data);     /*(访问)打印结点*/
            T=T->Right;					/*转向右子树*/
        }
    }
}

2.4.3 后序遍历

遍历过程（左子树、右子树、根）：①先序遍历其左子树；②先序遍历其右子树③访问根结点；

void Preordertraversal(BinTree BT)
{
   if( BT ){
       PreOrderTraversal( BT -> Left );
       PreOrderTraversal( BT -> Right );
       printf(“d", BT->Data);
	}
}

例：

后序遍历=> (D E F B) (H G I C) A

后续非递归遍历：

void InOrderTraversal( BinTree BT )
{
    BinTree T=BT;
    Stack S = Creatstack(MaxSize);   	/*创建并初始化堆栈S*/
    while( T || !IsEmpty(S) ){
        while( T ){ 					/*一直向左并将沿途结点压入堆栈*/
            Push( S, T);
            T = T -> Left;
        }
        if( !IsEmpty(S) ) {
            T=Pop(S);					/*结点弹出堆栈*/
            T=T->Right;					/*转向右子树*/
            printf(“%5d”, T->Data);     /*(访问)打印结点*/
        }
    }
}

2.4.4 层次遍历

层次遍历过程：从上到下、从左到右。

**队列实现：**遍历从根结点开始，首先将根结点入队，然后开始执行循环：（结点出队、访问该结点、其左右儿子入队）

实现思路：

先放入A，抛出A。再依次放入左右儿子B C，再抛出B。再放入B的左右儿子D F，抛出C。放入C的左右孩子G I，抛出D。由于D没有左右孩子，抛出F。放入E，抛出G。放入 H，抛出I，最后抛出E H。

A B C D F G I E H

void LevelOrderTraversal(BinTree BT)
{
    Queue Q;
    BinTree T;				/*若是空树则直接返回*/
    if( !BT ) return;
    Q = CreatQueue( Maxsize );	/*创建并初始化队列Q*/
    AddQ(Q, BT);
    while(!IsEmptyQ( Q )){
        T = DeleteQ( Q );
        printf(“%d\n”, T->Data);	/*访间取出队列的结点*/
        if( T -> Left)    AddQ( Q, T->Left);
        if( T -> Right)   AddQ( Q, T->Right);
    }
}

2.5 二叉树的应用

2.5.1 输出二叉树中的叶子结点

再二叉树的遍历算法中增加检测结点的“左右子树是否都为空”。

void PrerderPrintLeaves(BinTree B){
    if(BT ){
        if( !BT -> Left && !BT -> Right ){
            printf(“%d", BT->Data );
        PreOrderPrintLeaves(BT -> Left);
        PreOrderPrintLeaves(BT -> Right); 
    }
}

2.5.2 二叉树的高度

PostorderGetHeight( Bintree BT )
{
    int HL, HR, MaxH;
    if(BT ){
        HL = PostOrderGetHeight(BT -> Left);	/*求左子树的深度*/
        HR = PostorderGetHeight(BT -> Right);	/*求右子树的深度*/
        MaxH=(HL > HR) ? HL : HR;				/*取左右子树较大的深度*/
        return(MaxH + 1);						/*返回树的深度*/
    }
    else return 0;							/*空树深度为0*/
}

注：查找的效率与树的高度有关

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

例：

三种不同的访问结果：

先序：++ a * b c * + * d e f g

中序：a + b * c + d * e + f * g (中序可能带来符号的问题，解决办法可添加符号进行运算)

后序：a b c * + d e * f + g * +

2.5.4 由两种遍历序列确定二叉树

必须要有两个中序遍历才行。因为必须确定根节点

先序序列：a b c d e f g h i j
中序序列：c b e d a h g i j f

2.5.5 同构树判断

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。

输入给出2棵二叉树的信息：

先在一行中给出该树的结点数，随后N行
第i行对应编号第i个结点，给出该结点中存储的字母、其左孩子结点的编号、右孩子结点的编号。
如果孩子结点为空，则在相应位置上给出“-”

求解思路：

二叉树表示
建二叉树
同构判别

#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1

/*定义数据结构*/
struct TreeNode
{
    ElementType Element;
    Tree Left;
    Tree Right;
}T1[MaxTree], T2[MaxTree];
  
/*程序框架*/
int main(){
    Tree R1, R2;
    R1 = BuildTree(T1);
    R2 = BuildTree(T2);
    if(Isomorphic(R1, R2)) printf("Yes\n");
    else printf("No\n");
    return 0
}

Tree BuildTree( struct TreeNode T[] ){
    ......
    scanf("%d\n", &N);
    if (N){
        for (i=0; i<N; i++) check[i]= 0;
        for (i=0; i<N; i++){
            scanf("%c %c %c\n", &T[i].Element, &cl, &cr);
            if (cl != '-'){
                T[i].Left = cl-'0';  /*将字符转化为数字*/
                check[T[i].Left]=1;
            }
            else T[i].Left = Null;
            ....../*对cr的对应处理*/
        }
        for (i=0; i<N; i++)
            if (!check[i]) break;
        Root =i;
    }
    return Root;
}

int Isomorphic ( Tree R1, Tree R2 ){
    if((R1 == Null) && (R2 == Null) )/* both empty */
        return 1;
    if(( (R1==Null) && (R2 != Null) )|| ( (R1!=Null) && (R2==Null) ))
        return 0;/* one of them is empty */
    if(T1[R1].Element != T2[R2].Element)
        return 0; /* roots are different */
    if((T1[R1].Left ==Null) && (T2[R2].Left == Null))
        /* both have no left subtree */
        return Isomorphic( T1[R1].Right, T2[R2].Right );
    if(( (T1[R1].Left!=Nul) && (T2[R2].Left!=Null)) && 
       ((T1[T1[R1].Left].Element) == (T2[T2[R2].Left].Element)))
        /* no need to swap the left and the right */
        return(lsomorphic( T1[R1].Left, T2[R2].Left )&&
               Isomorphic( T1[R1].Right, T2[R2].Right ));
    else /* need to swap the left and the right */
        return ( lsomorphic( T1[R1].Left, T2[R2].Right) &&
                Isomorphic(T1[R1].Right, T2[R2].Left ));
}

3 二叉搜索树

二叉搜索树(BST，Binary Search Tree)，也称二叉排序树或二叉查找树
二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质:

非空左子树的所有键值小于其根结点的键值。

非空右子树的所有键值大于其根结点的键值。

左、右子树都是二叉搜索树

3.1 查找操作Find

/*查找普通元素*/
Position Find( ElementType X, BinTree BST){
    if( !BST ) return NULL;/*查找失败*/
    if( X > BST->Data)
        return Find(X, BST -> Right );/*在右子树中继续查找*/
    Else if( X < BST->Data )
        return Find(X, BST -> Left);/*在左子树中继续查找*/
    else /*X == BST -> Data */
        return BST;/*查找成功，返回结点的找到结点的地址*/
}

/*查找最大元素*/
Position FindMin( BinTree BST){
    if( !BST ) return NULL; /*空的二叉搜索树，返回NULL*/
    else if( !BST -> Left )
        return BST;   		/*找到最左叶结点井返回*/
    else
        return FindMin(BST -> Left);/*沿左分支维续查找
}

/*查找最小元素*/
Position FindMax( BinTree BST){
    if( BST )
        /*沿右分支继续查找，直到最右叶结点*/
        while(BST -> Right) BST = BST -> Right;
    return BsT;
}

3.2 插入操作Insert

BinTree Insert( ElementType X, BinTree BST){
    if( !BST ){
        /*若原树为空，生成并返回一个结点的二叉搜索树*/
        BST = malloc(sizeof(struct TreeNode));
        BST -> Data = X;
        BST -> Left = BST -> Right = NULL;
    }else
        /*开始找要插入元素的位置*/
        if(X<BST->Data )
            /*递归插入左子树*/
            BST -> Left = Insert(X, BST -> Left);
    	else if(X>BST->Data)
            /*递归插入右子树*/
            BST -> Right = Insert(X, BST -> Right);
    /*else X已经存在，什么都不做*/
    return BST;
}

3.3 删除操作

要考虑的三种情况：

要删除的是叶结点：直接删除，并再修改其父结点指针设置为NULL

要删除的结点只有一个孩子结点：将其父结点的指针指向要删除结点的孩子结点

要删除的结点有左、右两棵子树：用另一结点替代被删除结点，即右子树的最小元素或者左子树的最大元素

取右子树中的最小元素替代：

取左子树中的最大元素替代：

程序代码：

BinTree Delete(ElementType X, BinTree BST){
    Position Tmp;
    if( !BST ) printf("要删除的元素未找到");
    else if( X < BST -> Data )
        BST -> Left = Delete( X, BST -> Left );	/*左子树递归删除*/
    else if( X > BST -> Data )
        BST -> Right = Delete( X，BS -> Right );/*右子树递归删除*/
    else 
        /*找到要删除的结点*/
        /*被删除结点有左右两个子结点 */
        if( BST -> Left && BST -> Right){
            /*在右子树中找最小的元素填充删除结点*/
            Tmp = FindMin(BST -> Right);
            BST -> Data = Tmp -> Data;
            /*在删除结点的右子树中删除最小元素*/
            BST -> Right = Delete( BST -> Data, BST -> Right);
        }else{
            /*被删除结点有一个或无子结点*/
            Tmp = BST;
            /*有右孩子或无子结点，下面的语句是左边是空*/
            if( !BST -> Left)
                BST = BST -> Right;
            /*有左孩子或无子结点*/
            else if( !BsT -> Right)
                BST = BST -> Left;
            free( Tmp );
        }
    return BST;
}

3.4 判别是否同一搜索树

求解思路

分别建两棵搜索树的判别方法

不建树的判别方法

建一棵树，再判别其他序列是否与该树一致

选择第3种进行设计

搜索树表示

建搜索树T

判别一序列是否与搜索树T一致

代码实现：

/*搜索树表示*/
typedef struct TreeNode *Tree;
struct TreeNode {
    int v;
    Tree Left, Right;
    int flag;
};

/*主函数*/
int main(){
    int N, L, i;
    Tree T;
    
    scanf("%d", &N);
    while (N) {
        scanf("%d", &L);
        T = MakeTree(N);
        for (i=0; i<L; i++){
            if (Judge(T, N)) printf("Yes\n");
            else printf("No\n");
            /*清除T中的标记flag*/
            ResetT(T);
        }
        FreeTree(T);
        scanf("%d",&N);
    }
    return 0;
}
/*如何建搜索树*/
Tree MakeTree( int N ){
    Tree T;
    int i, V;
    
    scanf("%d", &V);
    /*申请一个树节点空间函数*/
    T = NewNode(V);
    for (i=1; i<N; i++){
        scanf("%d",&V);
        T =Insert(T, V);
    }
    return T;
}

/*申请一个树节点空间具体实现*/
Tree NewNode( int V ){
    TreeT = (Tree)malloc(sizeof(struct TreeNode));
    T -> v = V;
    T -> Left = T -> Right = NULL;
    T -> flag = 0;
    return T;
}

Tree insert( Tree T, int V ){
    if ( !T ) T = NewNode(V);
    else {
        if( V > T -> v )
            T->Right = Insert( T->Right, V );
        else
            T->Left = Insert( T->Left, V );
    }
    return T;
}

/*判别搜索树*/
int check ( Tree T, int V ){
    if ( T -> flag ){
        if ( V < T -> v ) return check( T -> Left, V);
        else if ( V > T -> v ) return check( T -> Right, V);
        else return 0;
    }
    else {
        if( V == T -> v ){
            T -> flag =1;
            return 1;
        }
        else return 0;
    }
}

int Judge( Tree T, int N ){
    /*flag:0代表目前还一致，1代表已经不一致*/
    int i, V, flag = 0;
    scanf( "%d", &V);
    if( V != T->v ) flag = 1;
    else T -> flag = 1;
    for (i = 1; i < N; i++){
        scanf("%d", &V);
        if ( (!flag) && (!check(T, V))) flag = 1;
    }
    if (flag) return 0;
    else return 1;
}

/*清除T中各结点的flag标记*/
void ResetT(TreeT){
    if ( T -> Left) ResetT( T -> Left);
    if (T -> Right) ResetT( T -> Right);
    T -> flag = 0;
}

/*释放T的空间*/
void FreeTree(TreeT){
    if (T -> Left) FreeTree(T -> Left);
    if (T -> Right) FreeTree(T -> Right);
    free(T);
}

4 平衡二叉树

4.1 基本概念

平衡二叉树(Balanced Binary Tree) (AVL树)：空树，或者任一结点左、右子树高度差的绝对值不超过1，即**|BF(T)|≤1**

平衡因子(Balance Factor，简称BF)：BF(T)= h˪-hᵣ其中h˪和hᵣ分别为T的左、右子树的高度。

给定结点数为 n 的 AVL 树的最大高度为 O(log₂n)

搜索树节点不同的插入次序，将导致不同的深度和平均查找长度ASL

4.2 调平

RR旋转

LL旋转

LR旋转

RL旋转

5 静态查找

5.1 顺序查找

5.2 二分查找（Binary Search）

实现算法

int BinarySearch ( List Tbl, ElementType K)
{/*在表Tbl中查找关键字为K的数据元素*/
    int left, right, mid, NoFound=-1;

    left = 1;					/*初始左边界*/
    right = Tbl->Length;		/*初始右边界*/
    while ( left <= right )
    {
        mid =(left+right)/2;	/*计算中间元素坐标*/
        if( K < Tbl->Element[mid])           right = mid-1；/*调整右边界*/
            else if( K >Tbl->Element[mid])   left = mid+1;  /*调整左边界*/
        else return mid;   /*查找成功，返回数据元素的下标*/
    }
    return NotFound;/*查找不成功，返回-1*/
}

生成判断树

判定树上每个结点需要的查找次数刚好为该结点所在的层数;
查找成功时查找次数不会超过判定树的深度

n个结点的判定树的深度为[log₂n]+1

三、堆

1 基本概念

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

堆的两个特性：

结构性：用数组表示的完全二叉树；

有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)

最大堆(MaxHeap)，也称“大顶堆“，最大值

最小堆(MinHeap)，也称“小顶堆”，最小值

2 堆的操作

堆的数据结构

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

2.1 堆的创建

MaxHeap Create(int MaxSize){
    /*创建容量为MaxSize的空的最大堆*/
    MaxHeap H = malloc( sizeof( struct Heapstruct ) );
    /*MaxSize + 1代表我们是从下标为1的元素开始存放，一般下表为0不存放元素*/
    H -> Elements = malloc((MaxSize + 1) * sizeof(ElementType));
    H -> Size = 0;
    H -> Capacity = MaxSize;
    H -> Elements[0] = MaxData;
    /*定义“哨兵”为大于堆中所有可能元素的值，便于以后更快操作*/
    return H;
}

建立最大堆：将已经存在的N个元素按最大堆的要求存放在个一维数组中

方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为0(N log N)。
方法2：在线性时间复杂度下建立最大堆。
- (1)将N个元素按输入顺序存入，先满足完全二叉树的结构特性
- (2)调整各结点位置，以满足最大堆的有序特性

2.2 堆的插入

将新增结点插入到从其父结点到根结点的有序序列中，时间复杂度：T(N) = O(log N)

void Insert(MaxHeap H, ElementType item){
    /*将元素item 插入最大堆H，其中H->Elements[0]已经定义为哨兵*/
    int i;
    if(IsFu11(H)){
        printf("最大堆已满");
        return;
    }
    /*i指向插入后堆中的最后一个元素的位置*/
    i = ++H -> Size;
    for(;H->Elements[i/2]<item;i/=2)
        /*向下过滤结点 */
        H -> Elements[i] = H->Elements[i/2];
    /*将item 插入*/
    H->Elements[il= item;
}

2.3 堆的删除

时间复杂度：T(N) = O (log N)

删除下标最大的元素


ElementType DeleteMax( MaxHeap H ){
    /*从最大堆H中取出键值为最大的元素，并删除一个结点*/
    int Parent, Child;
    ElementType MaxItem, temp;
    if( IsEmpty(H) ){
        printf("最大堆已为空");
        return;
    }
    /*取出根结点最大值*/
    MaxItem = H -> Elements[1];
    /*用最大堆中最后一个元素从根结点开始向上过滤下层结点*/
    temp = H -> Elements[ H -> Size--];
    /* Parent * 2 <= H -> Size判别是否有左儿子*/
    for( Parent = 1; Parent * 2 <= H -> Size; Parent =Child ){
        Child = Parent * 2;
        /*child指向左右子结点的较大者，Child!= H->Size是否有右儿子*/ 
        if((Child!= H->Size) && (H -> Elements[Child] < H -> Elements[Child+1]))
            Child++;
        if(temp >= H -> Elements[Child]) break;
        /*移动temp元素到下一层*/
        else
            H -> Elements[Parent] = H->Elements[Child];
    }
    H -> Elements[Parent] = temp;
    return MaxItem;
}

3 哈夫曼树与哈夫曼编码

3.1 基本概念

定义：

带权路径长度(WPL)：设二叉树有n个叶子结点，每个叶子结点带有权值Wₖ，从根结点到每个叶子结点的长度为Iₖ ，则每个叶子结点的带权路径长度之和就是：

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

时间复杂度：O(N log N)

typedef struct TreeNode *HuffmanTree;
struct TreeNode{
    int weight;
    HuffmanTree Left, Right;
}
HuffmanTree Huffman( MinHeap H){
    /*假设H->size个权值已经存在H->Elements[]->weight里*/
    int i;
    HuffmanTree T;
    /*将H->Elements[]按权值调整为最小堆*/
    BuildMinHeap(H);
    /*做H->Size-1次合并*/
    for( i = 1; i < H -> Size; i++){
        /*建立新结点*/
        T = malloc(sizeof(struct TreeNode));
        /*从最小堆中删除一个结点，作为新的左子结点*/
        T -> Left = DeleteMin(H);
        /*从最小堆中删除一个结点，作为新的右子结点*/
        T -> Right = DeleteMin(H);
        /*计算新权值*/
        T -> Weight = T -> Left -> Weight + T -> Right -> Weight;
        /*将新T插入最小堆*/
        Insert(H, T);
    }
        T = DeleteMin(H);
        return T;
}

特点：

没有度为1的结点；
n个叶子结点的哈夫曼树共有2n-1个结点；
哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树；

权值WPL相同，但是构造出来的树不同：

用途：它可以用来生成文本的索引、单词频率统计和特征向量表示等任务。哈夫曼编码在各种需要对数据进行高效压缩和编码表示的应用中具有重要作用，能够显著减小数据的大小，提高数据传输和存储的效率。

例子：

4 集合运算

集合运算：交、并、补、差，判定一个元素是否属于某一集合

例子：

有10台电脑{1，2，3，…，9，10}，已知下列电脑之间已经实现了连接：1和2、2和4、3和5、4和7、5和8、6和9、6和10

问：

2和7之间，5和9之间是否是连通的?

解决思路

(1)将10台电脑看成10个集合{1}，{2}，{3}，…，{9}，{10}；
(2)已知一种连接“x和y”，就将x和y对应的集合合并;
(3)查询“x和y是否是连通的”就是判别x和y是否属于同集合。

/*数据结构构造*/
typedef struct {
    ElementType Data;
    int Parent;
}SetType;

4.1 集合查找

/*查找某个元素所在的集合*/
int Find(SetType S[], ElementType X){
    /*在数组s中查找值为x的元素所属的集合*/
    /*Maxsize是全局变量，为数组S的最大长度*/
    int i;
    for( i = 0; i < MaxSize && S[i].Data != X; i++);
    /* 未找到X，返回-1 */
    if( i >= MaxSize ) return -1;
    for( ; S[il.Parent >= 0; i = S[i].Parent);
    /*找到x所属集合，返回树根结点在数组s中的下标*/
    return i;
}

4.2 集合的并运算

分别找到X1和X2两个元素所在集合树的根结点;

如果它们不同根，则将其中一个根结点的父结点指针设置成另一个根结点的数组下标。

void Union( SetType s[ ], ElementType X1, ElementType X2){
    int Rootl,Root2;
    Root1 = Find(s, X1);
    Root2 = Find(s, x2);
    if(Root1 != Root2 ) S[Root2].Parent = Root1;
}

简化：

/*默认元素可以用非负整数表示*/
typedef int Elementrype;
/*默认用根结点的下标作为集合名称*/
typedef int setName;
typedef ElementType SetType[Maxsize];

SetName Find(SetType S, ElementType X )
{
    /*默认集合元素全部初始化为-1*/
    for( ; S[X] >= 0; X = S[X]);
    return X;
}

void Union( SetType S, SetName Root1,SetName Root2 ){
    /*这里默认Root1和Root2是不同集合的根结点 */
    S[Root2]= Root1;
}

5 堆中的路径

5.1 程序设计题

将一系列给定数字插入一个初始为空的小顶堆H。随后对任意给定的下标“ i ”，打印从H[i]到根结点的路径。

输入样例:

5 3

46 23 26 24 10

5 4 3

输出样例:

24 23 10

46 23 10

26 10

程序设计：

#define MAXN 1001
#define MINH -10001

int H[MAXN], size;

void Create(){
    size = 0;
    /*设置“岗哨”*/
    H[0] = MINH;
}

void insert(int X){
    /*将X插入H。这里省略检查堆是否已满的代码*/
    int i;
    for (i = ++size; H[i/2] > X; i /= 2)
        H[i] = H[i/2];
    H[i] = X;
}

int main(){
    int n, m, x, i, j;
    scanf("%d %d", &n, &m);
    /*堆初始化*/
    Create();
    /*以逐个插入方式建堆*/
    for ( i = 0; i < n; i++){
        scanf("%d", &x);
        Insert(x);
    }
    for (i = 0; i < m; i++){
        scanf("%d", &j);
        printf("%d",H[j]);
        while ( j > 1){ 
            /*沿根方向输出各结点*/
            j /= 2;
            printf(" %d", H[j]);
        }
        printf("\n");
    }
    return 0;
}

例：判断系统是否连通

int main(){ 
    SetType S;
    int n;
    char in;
    scanf("&d\n", &n);
    Initialization(S, n);
    do {
        scanf("%c", &in);
        switch(in){
            case 'I': Input connection(S); break;
            case 'c': Check connection(S); break;
            case 'S': Check network(S, n); break;
        }
    } while(in != 'S');
    return 0;
}

void Input_connection( SetType S){
    ElementType u, v;
    SetName Root1, Root2;
    scanf("%d %d\n", &u, &v);
    Root1 =Find(S，u-1);
    Root2 =Find(S，v-1);
    if(Rootl != Root2 )
        Union(S，Root1，Root2);
}

void Check_connection( SetType S){
    ElementType u, v;
    SetName Root1, Root2;
    scanf("%d %d\n", &u, &v);
    Root1 =Find(S，u-1);
    Root2 =Find(S，v-1);
    if(Rootl == Root2 )
        printf("yes\n");
    else printf("No\n");
}

5.2 按秩归并（优化Union）

另一种做法：比规模，即把小树贴到大树上。S[Root]= -元素个数；

void Union( SetType S, SetName Root1, SetName Root2){
    if(S[Root2] < S[Root1]){
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }
    else{
        S[Root1] += S[Root2];
        S[Root2] = Root1; 
    }
}

5.3 路径压缩（优化Find）

SetName Find( SetType S, ElementType X){
    /*找到集合的根 */
    if ( S[X]<0) return X;
    /*先找到根；把根变成x的父结点；再返回根*/
    else return S[X]=Find(S，S[X]);
}

四、图

1 基本概念

1.1 抽象数据类型

类型名称：图（Graph）

数据对象集：G(V, E)由一个非空的有限顶点集合V和一个有限边集合E组成。

特点：

表示“多对多”的关系

包含

一组顶点：通常用V(Vertex)表示顶点集合

一组边：通常用E(Edge)表示边的集合

边是顶点对：(v,w)∈E，其中v,w∈V

有向边< v, w >表示从v指向w的边（单行线）

不考虑重边和自回路

1.2 邻接矩阵

优点
- 直观、简单、好理解
- 方便检查任意一对顶点间是否存在边
- 方便找任一顶点的所有"邻接点"(有边直接相连的顶点)
- 方便计算任一顶点的"度"(从该点发出的边数为"出度"指向该点的边数为“入度”)
	无向图:对应行(或列)非0元素的个数
	有向图:对应行非0元素的个数是“出度”;对应列非0元素的个数是"入度"

缺点：
- 浪费空间、浪费时间

1.3 邻接表

- 方便找任一顶点的所有“邻接点”
- 节约稀疏图的空间：需要N个头指针+2E个结点(每个结点至少2个域)
- 方便计算任一顶点的“度”？
	对无向图:是的
	对有向图:只能计算“出度”;需要构造“逆邻接表”(存指向自己的边)来方便计算“入度”
- 不方便检查任意一对顶点间是否存在边

2 图的遍历

2.1 深度优先搜索

DFS:Depth First Search

void DFS(Vertexy){
    visited[V]= true;
    for( V的每个邻接点W )
        if( !visited[w] )
            DES( W ); 
}

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

用邻接表存储图，有O(N+E);
用邻接矩阵存储图，有O(N²);

2.2 广度优先搜索

BFS: Breadth First Search

伪码描述

void BFs(VertexV){
    visited[V]= true;
    Enqueue(V, Q);
    while(!IsEmpty(Q)){
        V = Dequeue(Q);
        for(V的每个邻接点W)
            if(!visited[w]){
                visited[w]= true;
                Enqueue(W，Q);
            }
    }
}

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

用邻接表存储图，有O(N+E);
用邻接矩阵存储图，有O(N²);

3 图的表示

3.1 邻接矩阵表示

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;/*顶点数*/
    int Ne;/*边数 */
    WeightType G[MaxVertexNum][MaxVertexNum];
    DataType Data[MaxVertexNum];/*存顶点的数据*/
};
typedef PtrToGNode MGraph;/*以邻接矩阵存储的图类型*/

初始化一个有VertexNum个顶点但没有边图

typedef int Vertex;/*用顶点下标表示顶点,为整型*/
MGraph CreateGraph(int VertexNum){
    Vertex V, W;
    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;/*或INFINITY */
    return Graph;
}

向MGraph中插入边

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

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;
}

3.2 邻接表表示

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;   /*顶点数*/
    int Ne;   /*边数 */
    ADjList G; /*邻接表*/
};
typedef PtrToGNode LGraph;/*以邻接矩阵存储的图类型*/

typedef struat Vnode {
    PtrToAdjVNode FirstEdge;
    DataType Data;/*存顶点的数据*/
}AdjList[MaxVertexNum];/*AdjList是邻接表类型 */
    
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
    Vertex AdjV;/*邻接点下标*/
    WeightType Weight;/*边权重*/
    PtrToAdjVNode Next;
};

LGraph初始化：

typedef int Vertex;/* 用顶点下标表示顶点,为整型 */
LGraph CreateGraph(int VertexNum){
    Vertex V，W;
    LGraph Graph;
    
    Graph = (Graph)malloc(sizeof(structGNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    
    /*注意:这里默认顶点编号从0开始，到(Graph->Nv - 1)*/
    for(V=0:V<Graph->Nv;V++)
        Graph->G[V].FirstEdge =NULL;
    return Graph;
}

LGraph插入边：

void InsertEdge(LGraph Graph，EdgeE){
    PtrToAdjVNode NewNode;
    
    /*************<V1,V2> ***************/
    /*为V2建立新的邻接点 */
    NewNode =(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    /*将v2插入V1的表头*/
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;
    
    /********** 若是无向图，还要插入边 <V2,V1> **********/
    /*为V1建立新的邻接点*/
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    /*将V1插入V2的表头*/
    NewNode->Next= Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

4 图的最短路径

4.1 单源最短路径

无权单源最短

void Unweighted(Vertex S)
{
    Enqueue(S, Q);
    while( !IsEmpty(Q) ){
        V = Dequeue(Q);
        for( V的每个邻接点W )
            if( dist[w]==-1 ){
                dist[w] = dist[V]+1;
                path[w] = V;
                Enqueue(W, Q);
            }
    }
}

有无权单源最短

4.1.1 Dijkstra算法

其他类似问题

要求数最短路径有多少条
- count[s]=1;
- 如果找到更短路：count[w] = count[V];
- 如果找到等长路：count[w] += count[V];
要求边数最少的最短路
- count[s]=0
- 如果找到更短路：count[w] = count[V] + 1;
- 如果找到等长路：count[w] = count[V] + 1;

练习旅游问题

核心算法：

void Dijkstra(Vertex s){
    while(1){
        V = 未收录顶点中dist最小者;
        if(这样的V不存在)
            break;
        collected[V] = true;
        for(V 的每个邻接点 W)
            if(collected[W] == false )
                if(dist[V] + E<v,w> < dist[W]){
                    dist[W] = dist[V] + E<v,w>;
                    path[W] = V;
                    cost[W] = cost[V] + C<v,w>;
                }
        else if((dist[V] + E<v,w> == dist[W])&&(cost[V] + C<v,w> <cost[W])){
            cost[W] = cost[V] + C<v,w>;
            path[W] = V;
        }
    }
}

4.2 多源最短路径

Floyd算法(时间复杂度V³)：

void Floyd(){
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++){
            D[i][j] = G[i][j];
        }
    for(k = 0; k < N; k++)
        for(i = 0; i < N; i++)
            for(j = 0; j < N; j++)
                if(D[i][k] + D[k][j] < D[i][j]){
                    D[i][j] = D[i][k]+ D[k][j];
                    path[i][j] = k;
                }
}

4.3 练习

程序设计：

void FindAnimal(MGraph Graph){
    WeightType D[MaxVertexNum][MaxVertexNum], MaxDist, MinDist;
    Vertex Animal, i;
    Floyd( Graph, D);
    MinDist = INFINITY;
    for(i = 0; i< Graph->Nv; i++){
        MaxDist = FindMaxDist(D, i, Graph->Nv);
        /*说明有从i无法变出的动物 */
        if(MaxDist == INFINITY){
            printf("0\n");
            return;
        }
        /*找到最长距离更小的动物 */
        if(MinDist > MaxDist){
            /*更新距离，记录编号 */
            MinDist = MaxDist;
            Animal=i+1;
        }
    }
    printf("%d %d\n", Animal, MinDist);
}

int main(){
    MGraph G = BuildGraph();
    FindAnimal(G);
    return 0;
}

WeightType FindMaxDist( WeightType D[][MaxVertexNum], Vertex i, int N){
    WeightType MaxDist;
    Vertex j;
    
    MaxDist = 0;
    /*找出i到其他动物j的最长距离 */
    for(j = 0; j < N; j++)
        if(i != j && D[i][j] > MaxDist )
            MaxDist = D[i][j];
    return MaxDist
}

MGraph CreateGraph(int VertexNum){
    /*初始化一个有vertexNu个顶点但没有边的图 */
    Vertex V, W;
    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] = INFINITY;
    return Graph;
}

void InsertEdge( MGraph Graph, Edge E){
    /*插入边 <v1，y2>*/
    Graph->G[E->V1][E->V2] = E->Weight;
    /*若是无向图，还要插入边<V2，Vl> */
    Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph(){
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;
    /*读入顶点个数 */
    scanf("%d", &Nv);
    /*初始化有v个顶点但没有边的图*/
    Graph=createGraph(Nv);
    
    /*读入边数 */
    scan£("名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);
            /*注意:如果权重不是整型，weight的读入格式要改*/
            InsertEdge(Graph,E);
        }
    }
    
    /*如果顶点有数据的话，读入数据*/
    for(V = 0; V<Graph->Nv; V++)
        scanf("%c", &(Graph->Data[V]));
    return Graph;
}


void Floyd(MGraph Graph, WeightTypr D[][MaxVertexNum]){
    Vertex i, j, k;
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++){
            D[i][j] = G[i][j];
        }
    
    for(k = 0; k < N; k++)
        for(i = 0; i < N; i++)
            for(j = 0; j < N; j++)
                if(D[i][k] + D[k][j] < D[i][j]){
                    D[i][j] = D[i][k]+ D[k][j];
                    if( i == j && D[i][j] < 0)
                        return false;
                }
}

五相应算法

1 贪心算法

概念：每一步都要权重最小的边

约束：

只能用图里面有的边
只能正好用掉n-1条边
不能有回路

1.1 Prim算法（稠密图）

最小生成树——让一棵小树长大：

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

向生成树中加一条边都一定构成回路，最小生成树存在<->图连通

void Prim(){
    MST = {s};
    while( 1 ){
        V = 未收录顶点中dist最小者;/* 稠密图时间复杂度——|V|² */
        if(这样的V不存在)
            break;
        将V收录进MST: dist[V] = 0;
        for( V 的每个邻接点 W )
            if(dist[W] != 0)
                if(E(v,w) < dist[W]){
                    dist[W] = E(v,w);
                    parent[W] = V;
                }
    }
    if(MST中收的顶点不到|V|个)
        Error(“生成树不存在”);
}

1.2 Kruskal算法

稀疏图——时间复杂度：|E|log|E|

void Kruskal( Graph G ){
    MST={ };
    while( MST中不到|V|-1条边 && E中还有边){
        从中取一条权重最小的边E(v,w);   /*最小堆 */
        将 E(v,w)从 E 中删除;
        if(E(v,w)不在 MST 中构成回路)
            将 E(v,w)加入 MST;       /*并査集 */
        else
            彻底无视E(v,w);
    }
    if (MST中不到IV!-1条边)
        Error(“生成树不存在”);
}

2 拓扑排序

拓扑序：如果图中从v到w有一条有向路径则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序
获得一个拓扑序的过程就是拓扑排序
AOV(Activity On Vertex)如果有合理的拓扑序，则必定是有向无环图(Directed Acyclic Graph，DAG)

void Topsort(){
    for( 图中每个顶点V )
        if(Indegree[V] == 0)
            Enqueue(V, Q);
    while( !IsEmpty(Q) ){
        V=Dequeue(Q);
        输出V, 或者记录V的输出序号;
        cnt++;
        for( V的每个邻接点W )
            if(--Indegree[w] == 0)
                Enqueue(W, Q);
    }
    if(cnt != |V|)
        Error(“图中有回路”);
}

3 关键路径问题

AOE(Activity On Edge)网络：一般用于安排项目的工序

4 KMP算法

#include <stdio.h>
#include <string.h>
typedef int Position;
#define NotFound -1
int main(){
    char string[] = "This is a simple example.";
    char pattern[] = "simple";
    Position p = KMP(string, pattern);
    if( p == NotFound ) printf("Not Found.\n");
    else printf("%s\n", string + p);
    return 0;
}

Position KMP(char *string, char *pattern){  
    int n = strlen(string);
    int m = strlen(pattern);
    int s, p, *match;
    
    if(n < m) return NotFound;
    match = (int *)malloc(sizeof(int) *m);
    BuildMatch(pattern,match);
    s = p = 0;
    while( s < n && p < m){
        if(string[s] == pattern[p]){
            s++;
            p++;
        }
        else if(p > 0) p = match[p-1] + 1;
        else s++;
    }
    return( p = m) ? (s - m) : NotFound;
}

void BuildMatch(char *pattern, int *match){
    int i, j;
    int m = strlen(pattern);
    match[0] = -1;
    
    for(j = 1; j < m; j++){
        i = match[j-1];
        while((i >= 0) && (pattern[i+1] != pattern[j]))
            i = match[i];
        if (pattern[i+1] == pattern[j])
            match[j] = i+1;
        else match[j] = -1;
    }
}

六、排序

没有一种排序是任何情况下都表现最好的

6.1 冒泡排序

优点：

在链表中排序性能比较好
在两个元素相等时候不做交换，一定程度上保证了稳定性

时间复杂度：

最好情况：顺序T=O(N)
最坏情况：逆序T=O(N²)

void Bubble_Sort(ElementType A[], int N){
    for(P=N-1;P>=0;P--){
        flag =0;
        /*一趟冒泡*/
        for(i = 0; i < P; i++){
            if(A[i] > A[i+1]){
                Swap(A[i], A[i+1]);
                /*标识发生了交换*/
                flag =1;
            }
        }
        /*全程无交换*/
        if(flag==0) break;
    }
}

6.2 插入排序

时间复杂度：

最好情况：顺序T=O(N)
最坏情况：逆序T=O(N²)

void Insertion_Sort(ElementType A[], int N){
    for(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;/* 新牌落位 */
    }
}

6.3 希尔排序

最坏：T=O(N²)

void shell_sort(ElementType A[], int N){
    /*希尔增量序列*/
    for(D = N / 2; D > 0; D /= 2){
        /*插入排序*/
        for(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;
        }
    }
}

6.4 堆排序

void Heap_Sort(ElementType A[], int N){
    for(i = N/2; i >= 0; i--)/*BuildHeap */
        PercDown(A, i, N);
    for(i = N-1; i > 0; i--){
        Swap(&A[0], &A[i]);/*DeleteMax*/
        PercDown(A, 0, i);
    }
}

6.5 快速排序

分而治之

伪码描述：

void Quicksort(ElementType A[], int N){
    if (N < 2) return; 
    pivot = 从A[]中选一个主元;
    将s={ A[] \pivot }分成2个独立子集:
    	A1 = {a∈s | a ≤ pivot }和
        A2 = {a∈s | a ≥ pivot };
    A[] = Quicksort( A1, N1) ∪ {pivot} ∪ Quicksort(A2, N2);
}

当递归的数据规模充分小，则停止递归，直接调用简单排序（例如插入排序）

代码实现：

void Quicksort( ElementType A[], int Left, int Right ){
    if(Cutoff <= Right - Left){
        Pivot = Median3(A, Left, Right);
        i = Left; j= Right - 1;
        for( ; ; ){
            while(A[++i] < Pivot){}
            while(A[--j] > Pivot){}
            if(i<j)
                Swap(&A[i], &A[j]);
            else break;
        }
        Swap( &A[i], &A[ Right-1 ]);
        Quicksort(A, Left, i-1);
        Quicksort(A, i+1, Right);
    }
    else
        Insertion_Sort( A + Left, Right - Left + 1);
}

void Quick_sort(ElementType A[],int N){
    Quicksort(A, 0, N-1);
}

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 ]*/
    /*将pivot藏到右边 */
    Swap(&A[ Center ], &A[ Right-1 ]);
    /*只需要考虑 A[ Left+1 ]...A[ Right-2 ]*/
    /*返回 pivot */
    return A[ Right-1 ];
}

6.6 表排序

最好情况：初始即有序
最坏情况：

有⌊N/2⌋个环，每个环包含2个元素
需要⌊3N/2⌋次元素移动

T=O(m*N)，m是每个A元素的复制时间。

6.7 桶排序

假设我们有N个学生，他们的成绩是0到100之间的整数(于是有M=101个不同的成绩值)。如何在线性时间内将学生按成绩排序?

思想：将成绩分成101个桶，然后不停的插入学生成绩，并将其放入不同的桶中，用链表连接起来。

时间复杂度：T(N,M) = O(M+N)

void Bucket_Sort(ElementType A[],int N){
        count[]初始化;
    while(读入1个学生成绩grade)
        将该生插入count[grade]链表;
    for(i = 0; i < M; i++){
        if( count[i])
            输出整个count[i]链表;
    }
}

6.8 基数排序

6.9 多关键字排序

问题：LSD任何时候都比MSD快吗？

不一定。极端情况下，当主位可以一次性把元素都直接分开、而次位办不到的时候，显然MSD更好。一般情况下，如果主位的基数比次位大（例如扑克牌如果先按面值、同一面值内部按花色排序的话），则主位更有可能把元素分开，这时候用MSD就可能比LSD快。

6.10 排序算法的比较

排序方法	平均时间复杂度	最坏情况下时间复杂度	额外空间复杂度	稳定性
简单选择排序	O(N²)	O(N²)	O(1)	不稳定
冒泡排序	O(N²)	O(N²)	O(1)	稳定
直接插入排序	O(N²)	O(N²)	O(1)	稳定
希尔排序	O(Nᵈ)	O(N²)	O(1)	不稳定
堆排序	O(NlogN)	O(NlogN)	O(1)	不稳定
快速排序	O(NlogN)	O(N²)	O(logN)	不稳定
归并排序	O(NlogN)	O(NlogN)	O(N)	稳定
基数排序	O(P(N+B))	O(P(N+B))	O(N+B)	稳定

七、散列表

【问题】如何快速搜索到需要的关键词？如果关键词不方便比较怎么办？

查找的本质：已知对象找位置

有序安排对象:全序、半序
直接“算出”对象位置：散列

散列查找法的两项基本工作：

计算位置：构造散列函数确定关键词存储位置；
解决冲突：应用某种策略解决多个关键词位置相同的问题

时间复杂度几乎是常量：O(1)，即查找时间与间题规模无关！

7.1 基本概念

“散列函数”的基本思想：

(1)以关键字key为自变量，通过一个确定的函数h(散列函数)计算出对应的函数值h(key)，作为数据对象的存储地址。

(2)可能不同的关键字会映射到同一个散列地址上，即h(keyi)= h(keyj)(当key¡≠keyj)，称为“冲突(Collision)”

—需要某种冲突解决策略

好的散列函数需要考虑两个因素

计算简单，以便提高转换速度；
关键词对应的地址空间分布均匀，以尽量减少冲突。

选择合适的h(key)，散列法的查找效率期望是常数0(1)，它几乎与关键字的空间的大小n无关！也适合于关键字直接比较计算量大的问题。

它是以较小的a为前提。因此，散列方法是一个以空间换时间

散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大值最小值查找。

7.2 数字关键词的散列函数构造

直接地址法

取关键词的某个线性函数值为散列地址，即：h(key) = a * key + b
除留余数法

散列函数为：h(key) = key mod p
数字分析法
分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址

比如:取11位手机号码key的后4位作为地址：
散列函数为：h(key)= atoi(key + 7)(char * key)

折叠法
把关键词分割成位数相同的几个部分，然后叠加

平方取中法

总结：

一个简单的散列函数——ASCII码加和法

对字符型关键词key定义散列函数如下
h(key)= (Σkey[i]) mod TableSize
简单的改进——前3个字符移位法
h(key)=(key[0]x27² + key[1]x27 + key[2]) mod TableSize
好的散列函数——移位法

涉及关键词所有n个字符，并且分布得很好:

7.3 冲突处理方法

常用处理冲突的思路：

换个位置:开放地址法
同一位置的冲突对象组织在一起：链地址法

7.3.1 开放定址法(OpenAddressing)

一旦产生了冲突（该地址已有其它元素），就按某种规则去寻找另一空地址

若发生了第i次冲突，试探的下一个地址将增加d，基本公式是：

hᵢ(key) = (h(key)+dᵢ) mod TableSize (1< i < TableSize)
dᵢ决定了不同的解决冲突方案：线性探测、平方探测、双散列

优点：
	散列表是一个数组，存储效率高，随机查找

缺点：
	散列表有“聚集”现象

7.3.2 分离链接法(Separate Chaining)

将相应位置上冲突的所有关键词储存在同一个单链表中，将其相应的都串起来

散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低。

关键字删除不需要“懒惰删除”法，从而没有存储“垃圾”

太小的a可能导致空间浪费，大的a又将付出更多的时间代价。不均匀的链表长度导致时间效率的严重下降。

数据结构

#数据结构 #java

Java数据结构

http://example.com/2024/06/25/Java数据结构/

作者

Alaskaboo

发布于

2024年6月25日

更新于

2025年6月25日

许可协议

python语法上一篇

Hello World 下一篇

Java数据结构

一、队列

1.多项式相关

2.多项式练习题

二、树

1 基本概念

2 二叉树

2.1 基本概念

2.1.1 二叉树定义

2.1.2 抽象数据定义

2.1.3 五种基本形式

2.1.4 子树左右顺序之分

2.2 特殊二叉树

2.2.1 斜二叉树

2.2.2 完美二叉树（满二叉树）

2.2.3 完全二叉树

2.3 存储结构

2.3.1 顺序存储

2.3.2 链表存储

2.4 常用的遍历

2.4.1 先序遍历

2.4.2 中序遍历

2.4.3 后序遍历

2.4.4 层次遍历

2.5 二叉树的应用

2.5.1 输出二叉树中的叶子结点

2.5.2 二叉树的高度

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

2.5.4 由两种遍历序列确定二叉树

2.5.5 同构树判断

3 二叉搜索树

3.1 查找操作Find

3.2 插入操作Insert

3.3 删除操作

3.4 判别是否同一搜索树

4 平衡二叉树

4.1 基本概念

4.2 调平

5 静态查找

5.1 顺序查找

5.2 二分查找（Binary Search）

三、堆

1 基本概念

2 堆的操作

2.1 堆的创建

2.2 堆的插入

2.3 堆的删除

3 哈夫曼树与哈夫曼编码

3.1 基本概念

4 集合运算

4.1 集合查找

4.2 集合的并运算

5 堆中的路径

5.1 程序设计题

5.2 按秩归并（优化Union）

5.3 路径压缩（优化Find）

四、图

1 基本概念

1.1 抽象数据类型

1.2 邻接矩阵

1.3 邻接表

2 图的遍历

2.1 深度优先搜索

2.2 广度优先搜索

3 图的表示

3.1 邻接矩阵表示

3.2 邻接表表示

4 图的最短路径

4.1 单源最短路径

4.1.1 Dijkstra算法

练习 旅游问题

4.2 多源最短路径

4.3 练习

五 相应算法

1 贪心算法

1.1 Prim算法（稠密图）

1.2 Kruskal算法

2 拓扑排序

3 关键路径问题

4 KMP算法

练习旅游问题

五相应算法