数据结构复习

表、栈、队列

表

一般指的是链表，可以在任意节点进行插入活删除操作

栈

后进先出就是栈
栈是限定仅在**表尾（栈顶）**进行插入和删除操作的线性表
栈顶进栈出栈，栈底不能进行插入删除操作

栈的抽象数据类型

ADT 栈（stack）
Date  和线性表相同。元素有相同的数据类型，相邻元素有前驱和后继的关系
Operation
    InitStack (*S): 初始化操作，建立一个空栈S。
    DestoryStack（*S）:如果栈存在则销毁它。
    ClearStack (*S) : 将栈清空。
    StackEmpty（*S）:如果栈为空则返回true,否则返回false。
    GetTop（*S，*e）:如果栈存在且非空，用e返回S的栈顶储存的值。
    Push (*S, e) :若栈S存在，插入新的元素e到栈S中并成为栈顶元素。 
    Pop (*S，*e) :删除S中栈顶元素，并用e返回其值。
    StackLength (S) :返回栈S的元素个数。
endADT

顺序栈

栈的顺序储存结构

#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
typedef struct{
    ElemType data[MAXSIZE];
    int top;    //用于栈顶指针
}SqStack;

顺序栈操作

• 初始化

void InitStack(SqStack *S){
    S->top = -1;    //初始化栈顶指针
}

• 判断空栈

bool StackEmpty(SqStack S){
    if(S.top == -1){    
        return true;    //栈空
        }
    else{  
        return false;   //不空
    }
}

• 进栈

/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S, ElemType e){
    //满栈
    if(S->top == MAXSIZE-1){
        return ERROR;
    }
    S->top++;   //栈顶指针增加一
    S->data[S->top] = e;    //将新插入元素赋值给栈顶空间
    return OK;
}

• 出栈

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqStack *S, ElemType *e){
    if(S->top == -1){
        return ERROR;
    }
    *e = S->data[S->top];   //将要删除的栈顶元素赋值给e
    S->top--;   //栈顶指针减一
    return OK;
}

栈的链式结构

• 定义结构

typedef struct StackNode {
    ElemType data;	//每个结点储存数据处
    StackNode *next;/* 这个定义值的是：next是指向Struct StackNode型的
    指针变量，即指向包含某个结点的结构体 */
}StackNode, *LinkStackPtr;
/* 通过这个预定义，则这两串代码等同：
StackNode *next = LinkStackPtr next
*/
typedef struct LinkStack{
    LinkStackPtr top;
    //这个top即为头指针
    int count = 0;
    //这个count代表的是当前链栈中结点的个数, 开始初始化为0个
}LinkStack;
// 其实在这里第二个结构体声明可以不用写，直接写成如下也可以：
LinkStackPtr top;
//但是这样写的话要注意把栈顶结点的地址赋值给top
int count;
//但是这里我们应该注意这个count应该设置为一个全局变量

• 进栈

// 链栈的进栈操作
int Push(LinkStack *P, ElemType e){
	//这个P指针指向的是包含头指针top的结构体
	//这个e接受的是我们想插入的数据
	LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNOde));
	//创建一个新的结点并且为其分配空间
	s->data = e;
	//将我们想插入的数据放入新开创的结点的数据域
	s->next = P->top;
	/* 注意理解一下这里：因为栈的特性，每进栈一个数，那这个数处在栈顶的
	位置，而原来处在栈顶的位置的数会被新进栈的数压在底下,因此在这里我们
	把当前的栈顶元素赋值给新节点的直接后继 */
	P->top = s;
	//新插入的结点处在栈顶，因次让栈顶指针指向这个新结点
	P->count++;
	//结点的数量+1
	return OK;
}

• 出栈

// 链栈的出栈操作
int Pop(LinkStack *P, ElemType *e){
	//这个P指针指向的是包含头指针top的结构体
	/* 这个e是来接收我们即将出栈的那个结点的数据域的数据，在这里它作为结
	点清楚步骤的中间变量 */
	LinkStackPtr temp;
	// 创建一个指向包含链栈结点的结构体的指针变量
	if(P->count == 0){
		//判断这个栈中结点个数是否为0，为0则说明是空栈，不可执行此操作
		return ERROR；
		//因为为空栈，不可执行出栈操作，所以返回ERROR
	}
	else{
		//当执行到这里时，说明链栈不为空栈，可以执行出栈操作
		*e = P->top->data;
		//注意这里是*e，因为这里不是传递地址
		temp = P->top;
		//把要即将出栈的这个栈顶结点的地址给我们出栈操作中的中间变量
		P->top = P->top->next;
		/* 让栈顶指针向下移动一位，因为这次出栈操作之后，原来处在栈顶
		结点下面的那个结点变成了新的栈顶结点 */
		free(temp);
		//释放我们想出栈的那个结点的空间，以防止占有内存
		P->count--;
		//结点的数量-1
	}
	return OK
	//执行到这一步时，说明出栈操作执行成功
}

队列

先进先出就是队列

普通队列

懒得细化了全丢代码了

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

int queue[MAX_SIZE]; // 定义一个整数数组作为队列
int front = -1;      // 队头指针初始化为-1
int rear = -1;       // 队尾指针初始化为-1

// 检查队列是否为空
bool isEmpty() {
    return front == -1 && rear == -1;
}

// 检查队列是否已满
bool isFull() {
    return (rear + 1) % MAX_SIZE == front;
}

// 获取队列的大小
int size() {
    if (isEmpty()) {
        return 0;
    }
    return (MAX_SIZE - front + rear + 1) % MAX_SIZE;
}

// 入队操作
void enqueue(int data) {
    if (isFull()) {
        printf("队列已满，无法入队\n");
        return;
    }
    if (isEmpty()) {
        front = rear = 0; // 第一个元素入队时，设置队头和队尾为0
    } else {
        rear = (rear + 1) % MAX_SIZE; // 更新队尾指针，使用循环队列
    }
    queue[rear] = data; // 将元素存储到队列中
}

// 出队操作
int dequeue() {
    if (isEmpty()) {
        printf("队列为空，无法出队\n");
        return -1; // 出错标志
    }
    int data = queue[front]; // 获取队头元素的值
    if (front == rear) {
        front = rear = -1; // 队列中只有一个元素时，重置队头和队尾
    } else {
        front = (front + 1) % MAX_SIZE; // 更新队头指针，使用循环队列
    }
    return data; // 返回出队的元素值
}

int main() {
    enqueue(1); // 入队操作
    enqueue(2);
    enqueue(3);

    printf("队头元素：%d\n", queue[front]);
    printf("队列大小：%d\n", size());

    printf("出队：%d\n", dequeue()); // 出队操作
    printf("出队：%d\n", dequeue());

    printf("队列是否为空：%s\n", isEmpty() ? "是" : "否");

    return 0;
}

双端队列

就是有两个端的队列，每个端的首尾都能进行插入删除操作

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

int deque[MAX_SIZE]; // 定义一个整数数组作为双端队列
int front = -1;      // 前端指针初始化为-1
int rear = -1;       // 后端指针初始化为-1

// 检查双端队列是否为空
bool isEmpty() {
    return front == -1 && rear == -1;
}

// 检查双端队列是否已满
bool isFull() {
    return (front == 0 && rear == MAX_SIZE - 1) || (rear == front - 1);
}

// 获取双端队列的大小
int size() {
    if (isEmpty()) {
        return 0;
    }
    if (front <= rear) {
        return rear - front + 1;
    } else {
        return (MAX_SIZE - front) + (rear + 1);
    }
}

// 前端入队操作
void enqueueFront(int data) {
    if (isFull()) {
        printf("双端队列已满，无法前端入队\n");
        return;
    }
    if (isEmpty()) {
        front = rear = 0; // 第一个元素前端入队时，设置前端和后端为0
    } else if (front == 0) {
        front = MAX_SIZE - 1; // 循环队列，前端指针循环到数组末尾
    } else {
        front--;
    }
    deque[front] = data; // 将元素存储到前端
}

// 后端入队操作
void enqueueRear(int data) {
    if (isFull()) {
        printf("双端队列已满，无法后端入队\n");
        return;
    }
    if (isEmpty()) {
        front = rear = 0; // 第一个元素后端入队时，设置前端和后端为0
    } else if (rear == MAX_SIZE - 1) {
        rear = 0; // 循环队列，后端指针循环到数组开头
    } else {
        rear++;
    }
    deque[rear] = data; // 将元素存储到后端
}

// 前端出队操作
int dequeueFront() {
    if (isEmpty()) {
        printf("双端队列为空，无法前端出队\n");
        return -1; // 出错标志
    }
    int data = deque[front]; // 获取前端元素的值
    if (front == rear) {
        front = rear = -1; // 队列中只有一个元素时，重置前端和后端
    } else if (front == MAX_SIZE - 1) {
        front = 0; // 循环队列，前端指针循环到数组开头
    } else {
        front++;
    }
    return data; // 返回前端出队的元素值
}

// 后端出队操作
int dequeueRear() {
    if (isEmpty()) {
        printf("双端队列为空，无法后端出队\n");
        return -1; // 出错标志
    }
    int data = deque[rear]; // 获取后端元素的值
    if (front == rear) {
        front = rear = -1; // 队列中只有一个元素时，重置前端和后端
    } else if (rear == 0) {
        rear = MAX_SIZE - 1; // 循环队列，后端指针循环到数组末尾
    } else {
        rear--;
    }
    return data; // 返回后端出队的元素值
}

int main() {
    enqueueFront(1); // 前端入队操作
    enqueueRear(2);  // 后端入队操作
    enqueueFront(3); // 前端入队操作

    printf("前端出队：%d\n", dequeueFront()); // 前端出队操作
    printf("后端出队：%d\n", dequeueRear());  // 后端出队操作

    printf("双端队列大小：%d\n", size());
    printf("双端队列是否为空：%s\n", isEmpty() ? "是" : "否");

    return 0;
}

树

遍历

• 前序遍历：根节点->左节点->右节点
• 中序遍历：左节点->根节点->右节点
• 后序遍历：左节点->右节点->根节点

二叉树

// 定义二叉树节点结构
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 创建新节点
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入节点
struct TreeNode* insert(struct TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }

    return root;
}

// 查找最小值
struct TreeNode* findMin(struct TreeNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// 删除节点
struct TreeNode* deleteNode(struct TreeNode* root, int data) {
    if (root == NULL) {
        return root;
    }

    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        if (root->left == NULL) {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }

        struct TreeNode* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

    return root;
}

// 中序遍历
void inOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

哈夫曼树

// 定义哈夫曼树节点结构
struct HuffmanNode {
    char data;  // 字符
    int frequency;  // 频率
    struct HuffmanNode* left;
    struct HuffmanNode* right;
};

// 创建哈夫曼树节点
struct HuffmanNode* createNode(char data, int frequency) {
    struct HuffmanNode* newNode = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->frequency = frequency;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 创建哈夫曼树
struct HuffmanNode* buildHuffmanTree(struct HuffmanNode* nodes[], int n) {
    while (n > 1) {
        // 找到两个频率最小的节点
        int min1 = 0, min2 = 1;
        if (nodes[min1]->frequency > nodes[min2]->frequency) {
            int temp = min1;
            min1 = min2;
            min2 = temp;
        }

        for (int i = 2; i < n; i++) {
            if (nodes[i]->frequency < nodes[min1]->frequency) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->frequency < nodes[min2]->frequency) {
                min2 = i;
            }
        }

        // 创建一个新节点，作为两个频率最小的节点的父节点
        struct HuffmanNode* parent = createNode('$', nodes[min1]->frequency + nodes[min2]->frequency);
        parent->left = nodes[min1];
        parent->right = nodes[min2];

        // 删除已合并的两个节点，并将新节点插入数组
        nodes[min1] = parent;
        nodes[min2] = nodes[n - 1];
        n--;
    }

    return nodes[0];
}

// 哈夫曼树编码
void huffmanEncode(struct HuffmanNode* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        huffmanEncode(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        huffmanEncode(root->right, arr, top + 1);
    }
    if (!root->left && !root->right) {
        printf("字符: %c, 编码: ", root->data);
        for (int i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

// 哈夫曼树解码
void huffmanDecode(struct HuffmanNode* root, int index, char encodedStr[]) {
    if (root == NULL) {
        return;
    }

    if (!root->left && !root->right) {
        printf("%c", root->data);
        huffmanDecode(root, index, encodedStr);
    } else {
        index++;
        if (encodedStr[index] == '0') {
            huffmanDecode(root->left, index, encodedStr);
        } else {
            huffmanDecode(root->right, index, encodedStr);
        }
    }
}

// 销毁哈夫曼树
void destroyHuffmanTree(struct HuffmanNode* root) {
    if (root) {
        destroyHuffmanTree(root->left);
        destroyHuffmanTree(root->right);
        free(root);
    }
}

AVL树

在AVL树中，每个节点有以下特性：

• 平衡因子（Balance Factor）：每个节点的平衡因子是其左子树的高度减去其右子树的高度。在AVL树中，每个节点的平衡因子必须是-1、0或1。
• 自平衡：如果在插入或删除节点后，某个节点的平衡因子变得不在-1、0或1的范围内，那么就需要通过旋转来重新平衡树。常见的旋转操作有：
• 右旋（Right Rotation）：当节点的左子树比右子树高两个单位时进行，特别是在左子节点的左子树添加了一个新节点时。
• 左旋（Left Rotation）：当节点的右子树比左子树高两个单位时进行，特别是在右子节点的右子树添加了一个新节点时。
• 左-右旋（Left-Right Rotation）：当在一个节点的左子节点的右子树添加一个新节点时进行，这是一种双旋转，先对左子节点进行左旋，然后对原节点进行右旋。
• 右-左旋（Right-Left Rotation）：当在一个节点的右子节点的左子树添加一个新节点时进行，这也是一种双旋转，先对右子节点进行右旋，然后对原节点进行左旋。
  AVL树的操作：
• 插入（Insertion）：插入新节点后，沿着路径向上回溯并检查每个节点的平衡因子。如果发现平衡因子不在-1、0或1的范围内，执行适当的旋转操作来重新平衡树。
• 删除（Deletion）：删除节点后，也需要回溯并检查平衡因子，采取相应的旋转操作来维持树的平衡。
• 搜索（Search）：由于AVL树是二叉搜索树，所以搜索操作与普通的二叉搜索树相同，遵循二分查找的原则。

#include <stdio.h>
#include <stdlib.h>

// 定义AVL树节点结构
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
    int height; // 节点的高度
};

AVL平衡因子

// 计算节点的高度
int height(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 计算节点的平衡因子
int getBalance(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

AVL创建新节点

// 创建新节点
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    newNode->height = 1;
    return newNode;
}

右旋

// 旋转节点以修正平衡
struct TreeNode* rotateRight(struct TreeNode* y) {
    struct TreeNode* x = y->left;
    struct TreeNode* T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));

    return x;
}

左旋

struct TreeNode* rotateLeft(struct TreeNode* x) {
    struct TreeNode* y = x->right;
    struct TreeNode* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
    y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));

    return y;
}

AVL插入节点

// 插入节点
struct TreeNode* insert(struct TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    } else {
        return root; // 重复的节点不允许插入
    }

    root->height = 1 + (height(root->left) > height(root->right) ? height(root->left) : height(root->right));

    int balance = getBalance(root);

    // 左子树高度大于右子树，需要进行右旋转
    if (balance > 1 && data < root->left->data) {
        return rotateRight(root);
    }
    
    // 右子树高度大于左子树，需要进行左旋转
    if (balance < -1 && data > root->right->data) {
        return rotateLeft(root);
    }
    
    // 左子树高度大于右子树，需要进行左旋转后右旋转
    if (balance > 1 && data > root->left->data) {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }
    
    // 右子树高度大于左子树，需要进行右旋转后左旋转
    if (balance < -1 && data < root->right->data) {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }

    return root;
}

AVL找到最小值

// 找到最小值节点
struct TreeNode* findMin(struct TreeNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

AVL删除节点

// 删除节点
struct TreeNode* deleteNode(struct TreeNode* root, int data) {
    if (root == NULL) {
        return root;
    }

    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        if (root->left == NULL || root->right == NULL) {
            struct TreeNode* temp = (root->left) ? root->left : root->right;
            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else {
                *root = *temp;
            }
            free(temp);
        } else {
            struct TreeNode* temp = findMin(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }

    if (root == NULL) {
        return root;
    }

    root->height = 1 + (height(root->left) > height(root->right) ? height(root->left) : height(root->right));

    int balance = getBalance(root);

    if (balance > 1 && getBalance(root->left) >= 0) {
        return rotateRight(root);
    }

    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }

    if (balance < -1 && getBalance(root->right) <= 0) {
        return rotateLeft(root);
    }

    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }

    return root;
}

B树

优先队列（堆）

二叉堆

二叉堆是一种完全二叉树，可以被分为两种类型：最大堆和最小堆。

• 最大堆：在这种堆中，父节点的值总是大于或等于其子节点的值。这意味着堆的最大元素总是位于根节点。
• 最小堆：相反地，在最小堆中，父节点的值总是小于或等于其子节点的值。这样，堆的最小元素总是位于根节点。
  二叉堆的主要操作包括：
• 插入（Insert）：新元素被添加到树的最后一个位置，即完全二叉树的最后一个节点。然后，这个新元素会上浮到合适的位置，以保持堆的性质。这个过程被称为上浮（或堆化向上）。
• 删除最大（或最小）元素（Delete Max/Min）：在最大堆中，删除最大元素意味着移除根节点。为了填补根节点的位置，通常将堆中最后一个元素移动到根位置，然后进行下沉操作，以恢复堆的性质。这个过程被称为下沉（或堆化向下）。
  二叉堆通常使用数组来实现，因为它是一种完全二叉树，所以可以高效地利用数组空间。
  两种构建方式如下

// 将一个值插入到堆中的函数
void insertHeap(int heap[], int *size, int value) {
    int i;
    heap[*size] = value;
    i = *size;
    (*size)++;

    // 上浮调整
    while (i != 0 && heap[(i - 1) / 2] > heap[i]) {
        int temp = heap[(i - 1) / 2];
        heap[(i - 1) / 2] = heap[i];
        heap[i] = temp;
        i = (i - 1) / 2;
    }
}
/* ------------------------------------------------------- */
// 从数组建立堆的函数
void buildHeap(int arr[], int n) {
    int startIdx = (n / 2) - 1; // 从最后一个非叶子节点开始调整
    for (int i = startIdx; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

// 调整以节点i为根的子树的函数
void heapify(int arr[], int n, int i) {
    int smallest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    // 找到最小的子节点
    if (l < n && arr[l] < arr[smallest])
        smallest = l;
    if (r < n && arr[r] < arr[smallest])
        smallest = r;

    // 进行调整
    if (smallest != i) {
        int temp = arr[i];
        arr[i] = arr[smallest];
        arr[smallest] = temp;

        heapify(arr, n, smallest);
    }
}

d-堆

d-堆是一种扩展了的二叉堆，它是一种优先队列的数据结构。在标准的二叉堆中，每个节点最多有两个子节点。而在d-堆中，每个节点最多有d个子节点。这里的d是一个大于或等于2的整数，它表示堆中每个节点的最大子节点数目。
d-堆的主要操作包括：

• 插入（Insert）: 插入一个新元素通常是在堆的最后添加这个元素，然后将它上浮（Upheap）到合适的位置，以保持堆的性质。上浮的过程是将这个新节点与其父节点比较，并在必要时交换它们的位置，这一过程重复进行直到恢复堆的性质。
• 删除最小（或最大）元素（Delete Min/Max）: 在d-堆中删除最小（或最大）元素通常涉及移除根节点，然后将堆的最后一个元素移动到根位置，并进行下沉（Downheap）操作，以保持堆的性质。下沉操作是将节点与其子节点进行比较，并在必要时与最小（或最大）的子节点交换位置，这一过程重复进行直到恢复堆的性质。

左式堆

左式堆是一种优先队列的数据结构，它是二叉堆的一个变种。左式堆的特点在于它的左偏性质，这意味着对于左式堆中的任意节点，其左子树的零路径长度（null path length，即到达一个空链接的最短路径）至少和右子树的零路径长度一样长。
左式堆的主要操作包括：

• 合并（Merge）: 这是左式堆的基本操作。当合并两个左式堆时，会比较两个堆的根节点，并将值较大（或较小，取决于是最大堆还是最小堆）的堆的右子树与另一个堆合并。然后，如果需要，交换合并后的堆的左右子树以保持左偏性质。这个过程是递归的。
• 删除最小（或最大）元素（Delete Min/Max）: 删除堆中的最小（或最大）元素是通过删除根节点，并将其左右子树合并成一个新堆来实现的。
  左式堆的一个重要特性是它能够高效地合并两个堆，这使得它在需要频繁合并堆的场景下非常有用。左式堆的操作一般都能在对数时间内完成，这使得它成为实现优先队列的一个很好的选择

二项队列

二项树
二项队列的基础是二项树。一个阶数为k的二项树（记为Bk）具有以下特性：

• 结构：它是递归定义的。B0是只包含一个节点的树。Bk树有一个根节点，这个根节点有k个子节点，这些子节点分别是B(k-1), B(k-2), …, B0。
• 节点数：一个Bk树正好有2^k个节点。
• 高度：Bk树的高度是k。
  二项队列
  一个二项队列可以看作是二项树的集合，其中每个二项树遵循最小堆性质（或最大堆性质，取决于具体实现），即父节点的键值小于或等于其子节点的键值。在任何时刻，一个二项队列中不能有两个具有相同阶数的二项树。
  二项队列的操作
• 插入（Insert）：插入一个新元素等价于合并一个只包含这个元素的二项队列。这通常通过一系列的树合并操作完成。
• 删除最小元素（Delete Min）：由于每个二项树遵循最小堆性质，最小元素总是在根节点中。删除最小元素涉及找到具有最小根的二项树，删除这个根节点，然后将其子树合并回队列中。
• 合并（Merge）：合并两个二项队列是通过合并具有相同阶数的二项树并按照需要进行进位来完成的。
  二项队列的优点
  高效的合并操作：二项队列可以在对数时间内完成合并，这在某些应用中是非常有用的，特别是在需要频繁合并优先队列的场景中。
  其他操作也相对高效：如插入和删除最小元素等操作也能在对数时间内完成。

排序算法

插入排序

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        /* 将arr[i]移动到其在前面子数组中的正确位置 */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

选择排序

void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    // 遍历未排序的数组
    for (i = 0; i < n-1; i++) {
        // 找到未排序部分的最小元素
        min_idx = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min_idx])
            min_idx = j;

        // 将找到的最小元素与第 i 个位置的元素交换
        swap(&arr[min_idx], &arr[i]);
    }
}

希尔排序

直接上代码

void shellSort(int arr[], int n) {
    // 开始的增量 gap 为 n / 2，每次减少一半，直到为1
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子列表进行插入排序
        for (int i = gap; i < n; i += 1) {
            // 添加 arr[i] 到已经排序的子列表中
            int temp = arr[i];
            int j;            
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}

快速排序

int partition(int arr[], int low, int high) {
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于枢纽值
        if (arr[j] <= pivot) {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

/* arr[] --> 待排序数组，low --> 起始索引，high --> 结束索引 */
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        /* pi 是 partitioning index，arr[pi] 现在放在正确位置 */
        int pi = partition(arr, low, high);

        // 分别递归地对划分后的两部分进行快速排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

前缀表达式转后缀表达式

中缀表达式转换成后缀表达式（也称为逆波兰表示法）涉及到运算符的优先级和括号的使用。转换规则如下：

• 初始化两个栈：运算符栈 s1 用于临时存储运算符，包括括号；后缀表达式栈 s2 用于存储最终的后缀表达式。
• 从左到右扫描中缀表达式。
• 遇到操作数：直接将其压入 s2。
• 遇到左括号 (：将其压入 s1。
• 遇到右括号 )： 依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃。
• 遇到运算符：
  • 比较其与 s1 栈顶运算符的优先级：
    • 如果 s1 为空，或栈顶运算符为左括号 (，则直接将此运算符入栈；
    • 否则，若优先级比栈顶运算符的高，也将运算符压入 s1；
    • 如果优先级低于或等于栈顶运算符，则将 s1 栈顶的运算符弹出并压入到 s2 中，然后再次转到(6)与 s1 中新的栈顶运算符相比较。
    • 将 s1 中剩余的运算符依次弹出并压入 s2。
• 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。

查缺补漏

• 线性结构：线性表