数据结构与算法

42次阅读

共计 19988 个字符，预计需要花费 50 分钟才能阅读完成。

最大子序列和（maxSubSeqSum）

  • 时间复杂度:T(N)=O(N3)
int MaxSubSeqSum(int arrays[],int length){
    int i,j,k,thisSum=0,maxSum=0;
    for(i=0;i<length;i++){for(j=i;j<length;j++){
            thisSum=0;
            for(k=i;k<=j;k++){thisSum+=arrays[k];
            }
            if(thisSum>maxSum)maxSum=thisSum;
        };
    }
    return maxSum;
}
最大子序列和改进 1（maxSubSeqSum）
  • 时间复杂度:T(N)=O(N2)
int MaxSubSeqSum(int arrays[],int length){
    int i,j,thisSum=0,maxSum=0;
    for(i=0;i<length;i++){// i 是子列左端
        thisSum=0;// 从 arrays[i]到 arrays[j]的子序列和
        for(j=i;j<length;j++){// j 是子序列右端
            thisSum+=arrays[j];
            if(thisSum>maxSum)maxSum=thisSum;// 如果本次求和大于最终结果，更新 maxSum
        };
    }
    return maxSum;
}
最大子序列和（maxSubSeqSum）– 分治法

算法复杂度:T(N)=O(NlgN)

int MaxSubSeqSum(int arrays[], int left, int right) {
    int sum = 0;
    if (left == right) {if (arrays[left] > 0)return arrays[left];
        else sum = 0;
    } else {int middle = (left + right) / 2;
        int leftSum = MaxSubSeqSum(arrays, left, middle);
        int rightSum = MaxSubSeqSum(arrays, middle + 1, right);
        int finalLeftSum = 0, thisLeftSum = 0;
        for (int i = left; i <=middle; i++) {thisLeftSum += arrays[i];
            if (thisLeftSum > finalLeftSum)finalLeftSum = thisLeftSum;
        }
        int finalRightSum = 0, thisRightSum = 0;
        for (int j = middle + 1; j < right; j++) {thisRightSum += arrays[j];
            if (thisRightSum > finalRightSum)finalRightSum = thisRightSum;
        }
        sum = finalLeftSum + finalRightSum;
        printf("left sum is %d,right sum is %d\n",finalLeftSum,finalRightSum);
        if (sum < leftSum)sum = leftSum;
        if (sum < rightSum)sum = rightSum;
    }
    return sum;
}
测试主函数
int main() {int array[] ={1,6,-5,4,2,-3,6};
    int result = MaxSubSeqSum(array,0,7);
    printf("result is %d\n", result);
}
运行结果

为了方便观察，我们将每次左右两边求得的最大子序列最大和都打印出来

F:\ClionProject\DataStruct\cmake-build-debug\DataStruct.exe
left sum is 1,right sum is 6
left sum is 0,right sum is 4
left sum is 7,right sum is 0
left sum is 2,right sum is 0
left sum is 6,right sum is 0
left sum is 0,right sum is 6
left sum is 6,right sum is 5
result is 11

Process finished with exit code 0

线性表是最基本、最简单、也是最常用的一种数据结构。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

线性表的两种存储方式

  • 顺序存储
  • 链式存储
线性表的顺序存储
typedef struct LinkedList{int data[MAXSIZE];// 存储数组
    int Last;// 游标指针
}List;
List * MakeEmpty(){
    List *Ptrl;
    Ptrl=(List *)malloc(sizeof(List));
    Ptrl->Last=-1;
    return Ptrl;
}
/**T(n)=O(N)*/
int FindElement(int result,List* Ptrl){
    int i=0;
    while(i<=Ptrl->Last&&Ptrl->data[i]!=result)
        i++;
    if(i>Ptrl->Last)return -1;// 如果没有找到返回 -1
    else return i;
}
void Insert(int result,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--)// 倒序移动（注意 j >=i-1）Ptrl->data[j+1]=Ptrl->data[j];
    Ptrl->data[i]=result;// 插入数据
    Ptrl->Last++;//Last 指针 ++
    return;
}
/*T(N)=O(N)*/
void DeleteElement(int i,List* Ptrl){
    int j;
    if(i<1||i>Ptrl->Last+1){// 判断位置的合法性（注：链表下标是从 1 开始的）printf("第 %d 个元素不存在",i);
        return;
    }
    for(j=i;j<=Ptrl->Last;j++)// 所有元素前移
        Ptrl->data[j-1]=Ptrl->data[j];
    Ptrl->Last--;
    return;
}

线性表的链式存储

typedef struct LinkedList {
    int data;
    struct LinkedList *next;
} List;

// 求链表长度
int Length(List *Ptrl) {
    List *p = Ptrl;
    int j = 0;
    while (p) {
        p = p->next;
        j++;
    }
    return j;
}

// 按序号查找
List *FindKth(int k, List *Ptrl) {
    List *p = Ptrl;// 不改变头节点，返回移动指针 p
    int i = 1;
    while (p != NULL && i < k) {
        p = p->next;
        i++;
    }
    if (i == k)return p;
    else return NULL;
}

// 按值查找
List *Find(int result, List *Ptrl) {
    List *p = Ptrl;
    while (p != NULL && p->data != result)
        p = p->next;
    return p;
}

// 构造新的结点，申请空间
// 找到链表的低 i - 1 个结点
// 修改指针插入结点
List *Insert(int result, int i, List *Ptrl) {
    List *p, *s;
    if (i == 1) {// 判断链表为空的时候
        s = (List *) malloc(sizeof(List));
        s->data = result;
        s->next = Ptrl;
        return s;
    }
    p = FindKth(i - 1, Ptrl);// 查找第 i - 1 个节点
    if (p == NULL) {printf("参数错误");
        return NULL;
    } else {s = (List *) malloc(sizeof(List));
        s->data = result;
        s->next = p->next;
        p->next = s;
        return Ptrl;
    }
}

List *Delete(int i, List *Ptrl) {
    List *p, *s;
    if (i == 1) {// 检查要删除的是不是第一个结点
        s = Ptrl;// s 指向第一个结点
        if (Ptrl != NULL)Ptrl = Ptrl->next;// 从链表中删除
        else return NULL;
        free(s);// 释放空间
        return Ptrl;
    }
    p = FindKth(i, Ptrl);
    if (p == NULL) {// 后项前移
        printf("输入错误");
        return NULL;
    } else if (p->next != NULL) {
        s=p->next;
        p->next = s->next;
        free(s);// 清理无用空间
        return Ptrl;
    }
}
堆栈（顺序存储）数组方式
typedef struct{int Data[MAXSIZE];
    int Top;
}Stack;
void Push(Stack *stack,int value){if(stack->Top==MAXSIZE-1){// 数组有界
        printf("堆栈满");
    }else{stack->Data[++(stack->Top)]=value;
        return;
    }
}
int Pop(Stack *stack){if(stack->Top==-1){// 为空检查
        printf("堆栈为空");
        return ERROR;
    } else
    return stack->Data[stack->Top--];
}
一个有界数组存储两个堆栈
#define MAXSIZE 50
   /* 一个有界数组存储两个堆栈，如果数组有空间则执行入栈操作，（一个向右增长，一个向左增长）* */
   typedef struct DStack{int data[MAXSIZE];
       int Top1;
       int Top2;
   }Stacks;
   void Push(Stacks *stacks,int value,int Tag){if(stacks->Top2-stacks->Top1==1){printf("堆栈满");return;
       }
       if(Tag==1)
           stacks->data[++stacks->Top1]=value;
       else
           stacks->data[--stacks->Top2]=value;
   }
   int Pop(Stacks *stacks,int Tag){if(Tag==1){if(stacks->Top1==-1){printf("堆栈 1 空");
               return NULL;
           }else {return stacks->data[stacks->Top1--];
           }
       }else{if(stacks->Top2==MAXSIZE){printf("堆栈 2 空");
               return NULL;
           }else{return stacks->data[stacks->Top2++];
           }
       }
   }
   int main() {
       Stacks *stacks;
       stacks->Top1=-1;
       stacks->Top2=MAXSIZE;// 初始化两个堆栈头指针
       return 0;
   }

堆栈（链式存储）

/* 用单向链表表示栈时候，栈 Top 结点一定是链头结点
 * */
typedef struct Node{
    int value;
    struct Node *next;
}LinkedStack;
LinkedStack * CreateLinkedStack(){
    LinkedStack *stack;
    stack=(LinkedStack *)malloc(sizeof(LinkedStack));
    stack->next=NULL;
    return stack;
};
int isEmpty(LinkedStack *stack){// 注意 Top 结点没有值，只有一个单链表的头指针
    return (stack->next==NULL);
}
void Push(LinkedStack *stack,int value){
    LinkedStack *insertElement;
    insertElement=malloc(sizeof(LinkedStack));// 分配内存空间
    insertElement->value=value;// 插入的值赋值给结点
    insertElement->next=stack->next;// 将已存在链表链接到插入的结点
    stack->next=insertElement;// 改变 Top 结点
}
int Pop(LinkedStack *stack){
    int result;
    LinkedStack *popElement;
    if(isEmpty(stack)){printf("链表为空");
        return ERROR;
    }else{
        popElement=stack->next;
        result=popElement->value;
        stack->next=popElement->next;
        free(popElement);// 记得释放无用内存空间
        return result;
    }
}

中缀表达式如何转换为后缀表达式
从头到尾读取中缀表达式的每一个对象

  • 1. 运算数：直接输出
  • 2. 左括号：压入堆栈
  • 3. 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈不输出）
  • 4. 运算符：
    若优先级大于栈顶运算符，则压栈
    若优先级小于等于栈顶运算符，将栈顶运算符弹出，

再比较新的栈顶运算符，直到改运算符大于栈顶运算符优先级为止，然后压栈

  • 5. 若个对象处理完毕，则把堆栈中存留的运算符一并输出

堆栈用途：

  • 函数调用及递归实现
  • 深度优先搜索
  • 回溯算法
队列（顺序存储）
#define MAXSIZE 50
typedef struct {int value[MAXSIZE];
    int rear;
    int front;
}Queue;
Queue *CreateQueue(){
    Queue *queue;
    queue=(Queue *)malloc(sizeof(Queue));
    queue->front=0;
    queue->rear=0;
    return queue;
}
void AddQueue(Queue *queue,int value){if((queue->rear+1)%MAXSIZE==queue->front){printf("queue is full");
        return;
    }else {queue->rear=(queue->rear+1)%MAXSIZE;
        queue->value[queue->rear] = value;
    }
}
int IsEmpty(Queue *queue){if(queue->rear==queue->front)return 1;
    else return 0;
}
void OutQueue(Queue* queue,int *value){if(IsEmpty(queue)){printf("Queue is empty");
        return;
    }else{queue->front=(queue->front+1)%MAXSIZE;
        *value=queue->value[queue->front];
    }
}

队列（链式存储）注意

typedef struct Node {
    int value;
    struct Node *next;
} QNode;
typedef struct {
    QNode *rear;
    QNode *front;
} Queue;

void InitQueue(Queue **queue) {
    QNode *p;
    p = (QNode *) malloc(sizeof(QNode));
    p->next = NULL;
    (*queue)->front = p;
    (*queue)->rear = p;
}

void InQueue(Queue *queue, int value) {
    QNode *InElement;
    InElement = (QNode *) malloc(sizeof(QNode));
    InElement->value = value;
    InElement->next = NULL;
    queue->rear->next = InElement;
    queue->rear = InElement;
}

int IsEmpty(Queue *queue) {if (queue->rear = queue->front)return 1;
    else return 0;
}

void OutQueue(Queue *queue, int *value) {
    QNode *OutElement;
    if (IsEmpty(queue)) {printf("queue is empty");
        return;
    } else {
        OutElement = queue->front->next;
        queue->front->next=OutElement->next;// 指针头结点指向下一个结点(pspspspsps)
        *value=OutElement->value;
        free(OutElement);
        if(IsEmpty(queue)){// 出队列后如果队列为空则置为空队列
            queue->front=queue->rear;
        }
    }
}

判定树

每个结点需要查找的次数刚好为该结点所在的层数，查找成功时查找次数不会超过判定树的深度，n 个结点的判定树的深度为[LgN]+1

平均查找长度 ASL（Average Search Length）
ASL=sum(层数 * 个数)/ 各层总个数 n(n>=0)个结点构成的有限集合当 n = 0 时称为空树

对于任何一棵非空树（n>0），它具备以下性质

  • 树中会有一个 root 特殊结点用 r 表示
  • 其余结点可分为 m(m>0)个互不相交的有限集，其中每个集合本身又是一棵树，称为原来树的子树

树的特点：

  • 子树是不相交的
  • 出了根节点外，每隔结点有且仅有一个父结点
  • 一棵 N 个结点的树有 N - 1 条边（树是保证结点连通的最少边链接方式）

树的一些基本术语：

  • 结点的度：结点的子树个数（满二叉树单个结点的度为 2）
  • 树的度：树的所有结点中最大的度数
  • 叶结点：结点度为 0 的结点
  • 父节点，子节点，兄弟结点
  • 路径和路径长度
  • 祖先节点：沿树根到某一结点路径上的所有节点都是这个结点的祖先结点
    子孙结点通；
  • 结点的层次：规定根结点在一层，其他层次随子节点 +1
  • 树的深度：树中结点的最大层次就是这棵树的深度

    儿子兄弟表示法可以将所有的树转化为二叉树

特殊二叉树：

  • 斜二叉树：只有左儿子或只有右结点
  • 完美二叉树：满二叉树
  • 完全二叉树：结点编号与满二叉树结点编号相同（编号不间断）

二叉树的特点

  • 一个二叉树第 i 层的最大节点数为：2(i-1),i>=1
  • 深度为 k 的二叉树有最大节点总数为 2k-1,k>=1;
  • 对于任何非空二叉树 T，若 N0 表示叶子结点的个数，N2 是度为 2 的非叶结点个数，那么两者满足关系：N0=N2+1;(即叶子结点个数 -1= 度数为 2 的结点个数)

二叉树的抽象数据类型定义
数据对象集：一个有穷的结点集合
若不为空，则由根节点和其左、右二叉树组成
操作集：判断树是否为空，遍历，创建二叉树

常用的遍历方法有：
先序遍历（根左右），
中序遍历（左根右），
后序遍历（左右根），
层次遍历（从上到下，从左到右）

在二叉树中，我们知道叶结点总数 n0 与有两个儿子的结点总数 n2 之间的关系是：n0=n2+1.
那么类似关系是否可以推广到 m 叉树中？也就是，如果在 m 叉树中，叶结点总数是 n0，
有一个儿子的结点总数是 n1，有 2 个儿子的结点总数是 n2，有 3 个儿子的结点总数是 n3，
那么，ni 之间存在什么关系？

  • 完全二叉树，非根节点的父节点序号是[i/2]
  • 结点的左孩子结点序号是 2i，若 2i<=n，否则没有左孩子结点
  • 结点的右孩子结点序号是 2i+1，（若 2i+1<=n, 否则没有右孩子）
 typedef struct BT{
     int value;
     struct BT *leftchild;
     struct BT *rightchild;
 }BinTree;
 // 二叉树的每个结点遍历都会遇到三次，第一次遇到就打印的为先序遍历，第二次遇到就打印的为中序遍历，第三次遇到就打印的为后序遍历
 // 先序遍历(递归遍历)
 void PreOrderTraversal(BinTree *BT){if(BT){if(!BT->leftchild&&!BT->rightchild)
         printf("%d\n",BT->value);
         PreOrderTraversal(BT->leftchild);
         PreOrderTraversal(BT->rightchild);
     }
 }
 // 中序遍历(递归遍历)
 void InOrderTraversal(BinTree *BT){if(BT){if(!BT->leftchild&&!BT->rightchild)
         InOrderTraversal(BT->leftchild);
         printf("%d\n",BT->value);
         InOrderTraversal(BT->rightchild);
     }
 }
 // 后序遍历(递归遍历)
 void PostOrderTraversal(BinTree *BT){if(BT){if(!BT->leftchild&&!BT->rightchild)
         PostOrderTraversal(BT->leftchild);
         PostOrderTraversal(BT->rightchild);
         printf("%d\n",BT->value);
     }
 }
 // 二叉树遍历的本质是将二维序列转换为一维序列
 // 使用队列进行二叉树的层级访问（遍历根节点，将左右儿子节点入队列）void LevelOrderTraversal(BinTree BT){
     Queue *queue;
     BinTree *T;
     queue=CreateQueue();
     AddQueue(queue,BT);
     while(!IsEmptyQueue(queue)){T=DeleteQueue(queue);
         printf("%d\n",T->value);
         if(T->leftchild)AddQueue(queue,T->leftchild);
         if(T->rightchild)AddQueue(queue,T->rightchild);
     }
 }
 // 给定前中序遍历结果或中后序遍历结果可以唯一确定一棵二叉树，给定前后序遍历结果不能唯一确定二叉树
 // 非递归实现（中序遍历）void InOrderTraversal(BinTree *BT){
     BinTree *T=BT;
     LinkedStack *stack=CreateLinkedStack();// 创建并初始化堆栈
     while(T||!isEmpty(stack)){while(T){// 一直向左将沿途结点压入堆栈
             Push(stack,T);
             T=T->leftchild;// 转向左子树
         }
         if(!isEmpty(stack)){T=Pop(stack);// 结点弹出堆栈
             printf("%5d",T->value);// 打印结点
             T=T->rightchild;// 转向右子树
         }
     }
 }
 // 非递归实现（先序遍历）void PreOrderTraversal(BinTree *BT){
     BinTree *T=BT;
     LinkedStack *stack=CreateLinkedStack();// 创建并初始化堆栈
     while(T||!isEmpty(stack)){while(T){// 一直向左将沿途结点压入堆栈
             printf("%5d",T->value);// 打印结点
             Push(stack,T);
             T=T->leftchild;// 转向左子树
         }
         if(!isEmpty(stack)){T=Pop(stack);// 结点弹出堆栈
             T=T->rightchild;// 转向右子树
         }
     }
 }
二叉搜索树：BST(binary search tree)

也称二叉排序树或二叉查找树
二叉搜索树条件

   1. 非空左子树的所有键值小于其根节点的键值
   2. 非空右子树的所有键值大于其根节点的键值
   3. 左，右子树都是二叉搜索树
// 递归方式实现
Position Find(BinTree *binTree,int result){if(!binTree)return NULL;
    if(result>binTree->value)return Find(binTree->rightchild,result);
    else if(result<binTree->value)return Find(binTree,result);
    else return binTree;// 查找成功，返回结点地址(return 尾递归)
}
// 非递归方式实现
Position IterFind(BinTree *binTree,int value){while(binTree){if(result>binTree->value)
            binTree=binTree->rightchild;
        else if(result<binTree->value)
            binTree=binTree->leftchild;
        else 
            return binTree;
    }
    return NULL;
}
// 寻找最小值
Position FindMin(BinTree *binTree){if(!binTree)return NULL;
    else if(!binTree->leftchild)
        return binTree;
    else
        return FindMin(binTree->leftchild);
}
// 寻找最大值
Position FindMax(BinTree *binTree){if(binTree){while(binTree->rightchild)
            binTree=binTree->rightchild;
    }
    return binTree;
}
// 结点插入
BinTree * Insert(BinTree *binTree, int value) {if(!binTree){binTree=malloc(sizeof(BinTree));
        binTree->value=value;
        binTree->leftchild=binTree->rightchild=NULL;
    }else{if(value<binTree->value)
            binTree->leftchild=Insert(binTree->leftchild,value);
        else if(value>binTree->value)
            binTree->rightchild=Insert(binTree->rightchild,value);
    }
    return binTree;
}
// 删除结点
BinTree *Delete(BinTree *binTree,int value){(Position)BinTree *Temp;
    if(!binTree)printf("要删除的元素未找到");
        // 左子树递归删除
    else if(value<binTree->value)binTree->leftchild=Delete(binTree,value);
        // 右子树递归删除
    else if(value>binTree->value)binTree->rightchild=Delete(binTree->rightchild,value);
    else // 找到要删除的结点
        if(binTree->leftchild&&binTree->rightchild){// 被删除结点有左右量子子节点
            Temp=FindMin(binTree->rightchild);// 在右子树中招最小的元素填充删除结点
            binTree->value=Temp->value;
            binTree->rightchild=Delete(binTree->rightchild,binTree->value);
        }else{// 被删除的结点有一个或无子结点
            Temp=binTree;
            if(!binTree->leftchild)binTree=binTree->rightchild;
            else if(!binTree->rightchild)binTree=binTree->leftchild;
            free(Temp);
        }
    return binTree;
}
平衡二叉树(Balanced Binary Tree)

(AVL 树)(AVL 是提出平衡树的学者名字首字母)

  • 空树或任一结点左右子树高度差不超不过 1 |BF(T)|<=1
  • 平衡因子(Balance Factor 简称 BF：BF(T)=Hl-Hr)
  • 其中 hl 和 hr 分别为 T 的左右子树高度
  • 高度 = 层数 -1
  • 完全二叉树高度为 log2N(平衡二叉树)
  • Nh 是高度为 h 的平衡二叉树的最小结点树
  • Nh=F(h+2)-1
 #define MaxData 10000
 typedef struct HeapStruct{
     int *value;// 存储对元素的数组
     int length;// 堆的当前元素个数
     int capacity;// 堆的最大容量
 }Heap;
优先队列（PriorityQueue）

取出元素的先后顺序是按照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序
最大堆和最小堆都必须满足完全二叉树（切根节点最大或最小）最大堆的建立

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

  • 方法一：通过插入操作，将 N 个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为 O（NlogN）

  • 方法二：在线性时间复杂度下建立最大堆

    • (1)将 N 个元素按输入顺序存入，先满足完全二叉树的结构特性
    • (2)调整各结点位置以满足最大堆的有序特性
      建堆时，最坏的情况下需要挪动的元素次数等于树中各节点的高度和

对由同样 n 个整数构成的二叉搜索树（查找树）和最小堆：有以下结论

  • 二叉搜索树高度大于等于最小堆高度
  • 对该二叉搜索树进行中序遍历可得到从小到大的序列
  • 从最小堆根节点到起任何叶结点的路径上的结点值构成从小到大的序列
 Heap * Create(int MaxSize){Heap *heap=malloc(sizeof(Heap));
     heap->value=malloc((MaxSize+1)*sizeof(int));
     heap->length=0;
     heap->capacity=MaxSize;
     heap->value[0]=MaxData;// 定义哨兵，便于操作
     return heap;
 }
 void Insert(Heap *heap,int value){
     int i;
     if(IsFull(heap)){printf("最大堆已经满了");
         return;
     }
     i=++heap->length;
     for(;heap->value[i/2]<value;i/=2)
         heap->value[i]=heap->value[i/2];
     heap->value[i]=value;
 }
 int DeleteMax(Heap *heap){
     int parent,child;
     int maxValue,temp;
     if(IsEmpty(heap)){printf("最大堆已空");
         return 0;
     }
     maxValue=heap->value[1];
     // 用最大堆中最后一个元素从根节点开始过滤下层结点
     temp=heap->value[heap->length--];
     for(parent=1;parent*2<=heap->length;parent=child){
         child=parent*2;
         // 左儿子和右儿子节点比较取较大者
         if((child!=heap->length)&&(heap->value[child]<heap->value[child+1]))
             child++;
         if(temp>=heap->value[child])break;
         else
             heap->value[parent]=heap->value[child];
     }
     heap->value[parent]=temp;
     return maxValue;
 }
 int IsEmpty(Heap *heap){return heap->length==0;}
 int IsFull(Heap *heap){return heap->length==heap->capacity;}
 
 typedef struct TreeNode{
     int weight;
     struct TreeNode *left,*right;
 }HuffmanTree;
哈夫曼树（HuffmanTree）

查找效率，查找次数乘查找概率
带权路径长度（WPL）：设二叉树有 n 个叶子结点，每隔叶子结点带有权值 Wk，从根节点到每隔叶子结点的长度是 Lk，则每隔叶子结点的带全路径长度之和 WPL=（nEk=1）WkLk
最优二叉树或哈夫曼树 ：WPL 最小的二叉树
哈夫曼树的特点

  • 没有度为 1 的结点
  • n 个叶子结点的 HuffmanTree 有 2n- 1 个结点

  • HuffmanTree 的任意非叶结点的左右子树交换后仍是 HuffmanTree
    对于一组权值，可能有不同构的两棵 HuffmanTree

    HuffmanTree *Huffman(Heap *heap){// 假设 heap->length 权值已经存在 heap->value[]->weight 里面
    int i;HuffmanTree *huffmanTree;
    BuildHeap(heap);// 将 heap->value[]按权值调整为最小堆
    for(i=1;i<heap->length;i++){huffmanTree=malloc(sizeof(HuffmanTree));// 建立新结点
        huffmanTree->left=DeleteMin(heap);// 从最小堆中删除一个结点，作为新 huffmanTree 的左子结点
        huffmanTree->right=DeleteMin(heap);// 从最小堆中删除一个结点，作为新 huffmanTree 的右子结点
        huffmanTree->weight=huffmanTree->weight+huffmanTree->right->weight;// 计算新 // 权值
        Insert(heap,huffmanTree);
    }
    huffmanTree=DeleteMin(heap);
    return huffmanTree;
}
/* 二叉树用于编码
 * 当被编码字母全部在二叉树的叶子结点的时候（即，编码字母不会出现在有子节点的结点中）便可以保证字符编码没有二义性

            
    
偶然在一本书上看到这样一道题觉得听一意思的就拿来做了一下，题目是这样设置的
** 在已知一维数组 A[m+n]中一次存放两个线性表(a1,a2,a3,a4...am),(b1,b2,b3...bn), 试写出一个函数将两个顺序表位置互换, 即由 `(a,1,a2,a3,a4...am,b1,b2,b3...bn)` 转换成 `(b1,b2,b3...bn,a,1,a2,a3,a4...am)` 要求空间复杂度为 O(1)** 想必这种题会经常出现在面试题目中吧，哈哈，扯远了，以下是我的答案，水平有限，如有纰漏还望各位大神不吝赐教。乍一看题目还挺麻烦的，两个数组大小不一样，原地逆置循环次数不容易控制，换个思路重新整理一下发现可以用一种很巧妙的方法分三步实现
第一步：将字母序列逆置
第二部：将数字序列逆置
第三部：将数组整体逆置
** 其中逆置函数如下:**
逆置函数需要两个参数，分别为需要逆置的数组起始位置 [start] 和终止位置[end];

public static void reverse(int start,int end){// 逆置函数
    char temp;
    while(start<end) {temp = array[start];
        array[start++] = array[end];
        array[end--] = temp;
    }
}

tip:*char array[]={'A','B','C','D','E','F','G','H','1','2','3','4'}*
测试数组 A[0-7],B[8-11]

** 测试结果如下：**
![image.png](http://upload-images.jianshu.io/upload_images/2480310-05c78f4d0acc3395.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/640)


### 完整代码

public class Main {

public static char array[]={'A','B','C','D','E','F','G','H','1','2','3','4'};
public static void main(String[] args) {reverse(0,7);// 逆置字母序列结果为：HGFEDCBA1234
    reverse(8,11);// 逆置数字序列结果为：HGFEDCBA4321
    reverse(0,11);// 整体逆置结果为：1234ABCDEFG
    print(array);
}
public static void reverse(int start,int end){// 逆置函数
    char temp;
    while(start<end) {temp = array[start];
        array[start++] = array[end];
        array[end--] = temp;
    }
}
private static void print(char[] array) {for (int i = 0; i <array.length; i++)
        System.out.print(array[i]);
    System.out.println();}

}


### N 皇后问题

/**

  • n queens problem

*

  • */

public class EightQueen {

private int QUEEN_COUNT = 0;//represent the queen count
private int[][] queenCount;//chess box matrix
private int resultCount = 0;//solution number
private int[] queenPlace;//mark the queen placed position
/**
 * construct a EightQueen with a argument represent the number of queen
 * initial a empty chess box
 * 0 represent empty
 * 1 represent the area has been taken
 * recurse to call the putQueen method
 * the queenPlace array to mark the queen's taken area which uses to print
 *
 * */
public EightQueen(int n) {
    this.QUEEN_COUNT = n;
    this.resultCount = 0;
    this.queenCount = new int[QUEEN_COUNT][QUEEN_COUNT];
    queenPlace = new int[QUEEN_COUNT];
    putQueen(0);
}
/**
 * implement the putQueen function to recursion
 * use column index in outer loop and row index in inner loop with step increase
 * */
private void putQueen(int row) {for (int column = 0; column < QUEEN_COUNT; column++) {//loop for QUEEN_COUNT times
        if (queenCount[row][column] == 0) {//judge the condition
            /**
             * each row has one queen
             * mark the column and diagonal back diagonal(row has been scatter)
             *
             * */
            for (int nextRow = row + 1; nextRow < QUEEN_COUNT; nextRow++) {queenCount[nextRow][column]++;
                if (column - nextRow + row >= 0) {queenCount[nextRow][column - nextRow + row]++;
                }
                if (column + nextRow - row < QUEEN_COUNT) {queenCount[nextRow][column + nextRow - row]++;
                }
            }
            queenPlace[row] = column;//place the queen with only column information
            if (row == QUEEN_COUNT - 1) printQueen(++resultCount);//recursion has completed
            else putQueen(row + 1);//recurse to call the putQueen function
            /**
             *
             * unmarked the column and diagonal back diagonal(row has been scatter)
             *
             * */
            for (int rows = row + 1; rows < QUEEN_COUNT; rows++) {queenCount[rows][column]--;
                if (column - rows + row >= 0) {queenCount[rows][column - rows + row]--;
                }
                if (column + rows - row < QUEEN_COUNT) {queenCount[rows][column + rows - row]--;
                }
            }
        }
    }
    if (row == 0) System.out.println(QUEEN_COUNT + "queens has totally" + resultCount + "result.");
}

private void printQueen(int size)
{System.out.println("**********"+size+"**********\n");
    for (int i = 0; i < QUEEN_COUNT; i++) {for (int j = 0; j < QUEEN_COUNT; j++) {System.out.print(queenPlace[i] == j ? "#" : "-");
        }
        System.out.println();}
}

}


### 优先队列

/**

  • use maximum-top heap to implement priority queue
  • define a MAX_SIZE_OF_PRIORITY_QUEUE to limit the max length of priority queue
  • use a integer array to store element
  • hypothesis i is the root node and then use 2i to mark left child and 2i+1 to mark right child
  • use initialArray[0] to store the length of heap
  • */

public class PriorityQueue{

private static final int MAX_SIZE_OF_PRIORITY_QUEUE=100;
private int[] initialArray;
/**
 * initial priority queue with a exist array which can't be null
 * */
public PriorityQueue(int[] initialElement) {if(initialElement==null)return;
    if(initialElement.length==0)return;
    initialArray=new int[MAX_SIZE_OF_PRIORITY_QUEUE];
    initialArray[0]=initialElement.length;
    for(int i=0;i<initialElement.length;i++)initialArray[i+1]=initialElement[i];
    System.out.println(initialArray[0]);
    for (int i = initialArray[0]; i >0 ; i--)reBuildHeap(i);
}
/**
 * rebuild array according to the value of each node
 * maximum-top heap
 * index represents the index of a node which should be rebuild(include it's children node)
 *
 * simple:
 *         1
 *      2     3
 *   4   5  6   7
 *
 * */
private void reBuildHeap(int index){System.out.println("execute rebuild function to rebuild a maximum-top heap with one loop");
    int leftChildIndex=index*2;
    int rightChildIndex=leftChildIndex+1;
    int length=initialArray[0];
    int biggerValueIndex=-1;
    if(leftChildIndex>length&&rightChildIndex>length){System.out.println("no left child");
        return;
    }
    if(leftChildIndex<=length&&rightChildIndex>length){System.out.println("only left child");
        biggerValueIndex=leftChildIndex;
    }
    if(leftChildIndex>length&&rightChildIndex<=length){System.out.println("only right child");
        biggerValueIndex=rightChildIndex;
    }
    if(leftChildIndex<=length&&rightChildIndex<=length){System.out.println("both children");
        biggerValueIndex=initialArray[leftChildIndex]>initialArray[rightChildIndex]?leftChildIndex:rightChildIndex;
    }
    if(initialArray[index]>initialArray[biggerValueIndex]){System.out.println("unnecessary to swap!");
        return;
    }else{int temp=initialArray[index];
        initialArray[index]=initialArray[biggerValueIndex];
        initialArray[biggerValueIndex]=temp;
        this.reBuildHeap(biggerValueIndex);
    }
}
public int getLength() {return initialArray[0];
}
/**
 * get top priority value of heap
 * the first element of array
 * */
public int priority(){return initialArray[1];
}
/**
 * length++
 * add element to the tail of array
 * rebuild the heap to regular priority heap
 * */
public void insert(int element){initialArray[0]++;
    initialArray[initialArray[0]]=element;
    for(int i=initialArray[0];i>=1;i=i/2){reBuildHeap(i);
    }
}
/**
 * length--
 * swap the first element and last element
 * delete last value
 * rebuild the heap
 * */
public int deletePriority(){if(initialArray[0]<=0)return -1;
    int maxValue=initialArray[1];
    initialArray[1]=initialArray[initialArray[0]];
    initialArray[0]--;
    for(int i=initialArray[0];i>=1;i=i/2){reBuildHeap(i);
    }
    return maxValue;
}
/**
 * print the structure of priority heap
 * */
@Override
public String toString() {StringBuilder builder=new StringBuilder("{");
    for (int i = 1; i <= initialArray[0]; i++) {if(i!=1)builder.append(",");
        builder.append(initialArray[i]);
    }
    builder.append("}");
    return builder.toString();}

}

正文完
c 数据结构 算法
发表至： java
2019-08-27
 0
关于java:松哥手把手教你在-Vue3-中自定义插件
关于java:熬夜重构了IDEA插件Toolkit整合程序员常用的工具箱更加便捷
LeetCode-350-两个数组的交集-II-Intersection-of-Two-Arrays-II
小型的编程项目有哪些值得推荐这本神书写了-22-个个个了不得