串(String)

string类

用到了string.h的一些操作，应该学学,上网搜一下就好了

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

// 定义字符串类型
typedef struct {
    char *str;  // 动态分配的字符串内容
    int length; // 当前字符串长度
} MyString;

// 初始化字符串
MyString initString(const char *source) {
    MyString s;
    s.length = strlen(source);
    s.str = (char *)malloc((s.length + 1) * sizeof(char));
    strcpy(s.str, source);
    return s;
}

// 销毁字符串
void destroyString(MyString *s) {
    if (s->str) {
        free(s->str);
        s->str = NULL;
        s->length = 0;
    }
}

// 赋值
void assignString(MyString *s, const char *source) {
    if (s->str) free(s->str);
    s->length = strlen(source);
    s->str = (char *)malloc((s->length + 1) * sizeof(char));
    strcpy(s->str, source);
}

// 比较字符串
int compareString(MyString s1, MyString s2) {
    return strcmp(s1.str, s2.str);
}

// 求串长
int getStringLength(MyString s) {
    return s.length;
}

// 串联
MyString concatString(MyString s1, MyString s2) {
    MyString result;
    result.length = s1.length + s2.length;
    result.str = (char *)malloc((result.length + 1) * sizeof(char));
    strcpy(result.str, s1.str);
    strcat(result.str, s2.str);
    return result;
}

// 求子串
MyString substring(MyString s, int pos, int len) {
    MyString sub;
    if (pos < 0 || pos >= s.length || len <= 0 || pos + len > s.length) {
        sub.str = NULL;
        sub.length = 0;
        return sub;
    }
    sub.length = len;
    sub.str = (char *)malloc((len + 1) * sizeof(char));
    strncpy(sub.str, s.str + pos, len);
    sub.str[len] = '\0';
    return sub;
}

// 判空
int isEmpty(MyString s) {
    return s.length == 0;
}

// 清空串
void clearString(MyString *s) {
    if (s->str) {
        free(s->str);
        s->str = NULL;
    }
    s->length = 0;
}

// 子串的位置
int findSubstring(MyString s, MyString sub) {
    char *pos = strstr(s.str, sub.str);
    return pos ? (int)(pos - s.str) : -1;
}

// 替换子串
MyString replaceSubstring(MyString s, MyString oldSub, MyString newSub) {
    MyString result = initString("");
    int pos;
    while ((pos = findSubstring(s, oldSub)) != -1) {
        MyString left = substring(s, 0, pos);
        MyString right = substring(s, pos + oldSub.length, s.length - pos - oldSub.length);
        MyString temp = concatString(left, newSub);
        destroyString(&left);
        destroyString(&s);
        s = concatString(temp, right);
        destroyString(&temp);
        destroyString(&right);
    }
    result = s;
    return result;
}

// 插入子串
MyString insertSubstring(MyString s, int pos, MyString sub) {
    if (pos < 0 || pos > s.length) return s;
    MyString left = substring(s, 0, pos);
    MyString right = substring(s, pos, s.length - pos);
    MyString temp = concatString(left, sub);
    MyString result = concatString(temp, right);
    destroyString(&left);
    destroyString(&right);
    destroyString(&temp);
    return result;
}

// 删除子串
MyString deleteSubstring(MyString s, int pos, int len) {
    if (pos < 0 || pos >= s.length || len <= 0 || pos + len > s.length) return s;
    MyString left = substring(s, 0, pos);
    MyString right = substring(s, pos + len, s.length - pos - len);
    MyString result = concatString(left, right);
    destroyString(&left);
    destroyString(&right);
    return result;
}

// 示例程序
int main() {
    MyString s1 = initString("Hello");
    MyString s2 = initString("World");
    MyString s3 = concatString(s1, s2);

    printf("Concat: %s\n", s3.str);

    MyString sub = substring(s3, 5, 5);
    printf("Substring: %s\n", sub.str);

    int pos = findSubstring(s3, initString("World"));
    printf("Find position: %d\n", pos);

    MyString replaced = replaceSubstring(s3, initString("World"), initString("Everyone"));
    printf("Replaced: %s\n", replaced.str);

    destroyString(&s1);
    destroyString(&s2);
    destroyString(&s3);
    destroyString(&sub);
    destroyString(&replaced);
    return 0;
}

KMP算法

构建部分匹配表
- 部分匹配值是模式串中每个位置的前缀与后缀的最大匹配长度。
- 构建 next 数组，用于指示在模式串失配后，主串的比较位置可以跳转的地方，从而减少重复比较。

匹配主串与模式串

遍历主串时，如果字符匹配，则继续比较。

如果字符失配，则根据 next 数组跳转模式串的匹配起点，而不是回退主串指针。
kmp还是很难的，也很难去描述，建议【最浅显易懂的 KMP 算法讲解-哔哩哔哩】 https://b23.tv/To4ex7N

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

// 构建 next 数组（部分匹配表）
void buildNext(const char *pattern, int *next, int m) {
    int j = 0; // 当前匹配的前缀长度
    next[0] = 0; // 第一个字符的部分匹配值为 0

    for (int i = 1; i < m; i++) {
        // 如果前后缀不匹配，回退到上一个匹配的位置
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        // 如果前后缀匹配，前缀长度加 1
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
}

// KMP 主算法
int kmpSearch(const char *text, const char *pattern) {
    int n = strlen(text);    // 主串长度
    int m = strlen(pattern); // 模式串长度

    // 动态分配 next 数组
    int *next = (int *)malloc(m * sizeof(int));
    buildNext(pattern, next, m);

    int j = 0; // 模式串指针
    for (int i = 0; i < n; i++) {
        // 当字符失配时，根据 next 数组调整模式串位置
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        // 如果字符匹配，模式串指针加 1
        if (text[i] == pattern[j]) {
            j++;
        }
        // 如果整个模式串匹配成功，返回匹配的起始位置
        if (j == m) {
            free(next); // 释放动态分配的内存
            return i - m + 1;
        }
    }

    free(next); // 释放动态分配的内存
    return -1; // 没有找到匹配
}

// 示例程序
int main() {
    const char *text = "ababcabcacbab";
    const char *pattern = "abcac";

    int position = kmpSearch(text, pattern);
    if (position != -1) {
        printf("Pattern found at index %d\n", position);
    } else {
        printf("Pattern not found.\n");
    }
    return 0;
}

KMP算法的时间复杂度O(n + m)

数组和广义表

考概念居多，没代码实现，建议去看PPT

树和二叉树

树

树的定义
树是由 n (n≥ 0) 个结点组成的有限集合。
如果n= 0，称为空树；
否则，在一棵非空树中(n>0) ，满足如下两个条件：
(1)有且仅有一个特定的称之为**根(root)的结点，它只有直接后继，但没有直接前驱；
(2)除根以外的其它结点划分为 m (m ≥ 0) 个互不相交的有限集合 T0,T1, …, Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)**。

根结点: 非空树中无前驱结点的节点
结点的度(degree): 结点拥有的子树数
/叶子/终端结点: 度=0分支结点/非终端结点: 度≠0
部结点: 根结点以外的分支结点结点的子树的根称为该节点的孩子(Child)，该结点称为孩子的双亲(Parent)
同一双亲的孩子之间互称兄弟(Sibling)
树的深度(高度): 树中结点的最大层次

建议学好递归再来学树

二叉树

哈夫曼编码

哈夫曼编码的一个重要性质是无前缀性质（Prefix Property），即任何字符的编码都不会是其他字符编码的前缀。
具体来说，哈夫曼树的路径保证了任何一个字符的编码不会是另一个字符编码的前缀。这是通过树的结构保证的：每个字符的编码对应哈夫曼树中从根到叶子的路径。由于我们构建树时，频率较高的字符更靠近根节点，因此它们的编码长度较短，而频率较低的字符的编码则较长。
只要是叶子就不会是其他编码的前缀或者是后缀
数据压缩编码
其实就是实现没有公共前缀的01二进制编码来优化存储空间
A 5
B 9
C 12
D 13
E 16
F 45
构建过程：
将权值最小的两个节点 A(5) 和 B(9) 合并为新节点 T1(14)。
将 T1(14) 和 C(12) 合并为新节点 T2(26)。
将 T2(26) 和 D(13) 合并为新节点 T3(39)。
将 T3(39) 和 E(16) 合并为新节点 T4(55)。
将 T4(55) 和 F(45) 合并为根节点 T5(100)。

      [100]
     /     \
  [45]     [55]
          /     \
       [26]     [16]
      /    \
   [14]    [12]
  /   \
[5]   [9]

很喜欢用堆去解释这些东西，堆可以理解成每次在一个集合中取最大或者最小的元素，也可以放入元素进入集合
利用堆去实现的效率会高很多，很轻松的去实现，先放这里，看不懂算了，学会理论就好了

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

// 哈夫曼树节点结构
typedef struct HuffmanNode {
    char data;            // 字符
    int weight;           // 权值
    struct HuffmanNode *left, *right; // 左右子节点
} HuffmanNode;

// 最小堆结构
typedef struct MinHeap {
    int size;             // 当前堆大小
    int capacity;         // 堆容量
    HuffmanNode **array;  // 存放节点的指针数组
} MinHeap;

// 创建一个新节点
HuffmanNode *createNode(char data, int weight) {
    HuffmanNode *node = (HuffmanNode *)malloc(sizeof(HuffmanNode));
    node->data = data;
    node->weight = weight;
    node->left = node->right = NULL;
    return node;
}

// 创建一个最小堆
MinHeap *createMinHeap(int capacity) {
    MinHeap *heap = (MinHeap *)malloc(sizeof(MinHeap));
    heap->size = 0;
    heap->capacity = capacity;
    heap->array = (HuffmanNode **)malloc(capacity * sizeof(HuffmanNode *));
    return heap;
}

// 交换两个堆节点
void swapNodes(HuffmanNode **a, HuffmanNode **b) {
    HuffmanNode *temp = *a;
    *a = *b;
    *b = temp;
}

// 堆化调整
void minHeapify(MinHeap *heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap->size && heap->array[left]->weight < heap->array[smallest]->weight)
        smallest = left;
    if (right < heap->size && heap->array[right]->weight < heap->array[smallest]->weight)
        smallest = right;
    if (smallest != idx) {
        swapNodes(&heap->array[smallest], &heap->array[idx]);
        minHeapify(heap, smallest);
    }
}

// 提取堆中最小节点
HuffmanNode *extractMin(MinHeap *heap) {
    HuffmanNode *temp = heap->array[0];
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    minHeapify(heap, 0);
    return temp;
}

// 向堆中插入节点
void insertMinHeap(MinHeap *heap, HuffmanNode *node) {
    heap->size++;
    int i = heap->size - 1;

    while (i > 0 && node->weight < heap->array[(i - 1) / 2]->weight) {
        heap->array[i] = heap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    heap->array[i] = node;
}

// 构建最小堆
MinHeap *buildMinHeap(char data[], int weight[], int size) {
    MinHeap *heap = createMinHeap(size);
    for (int i = 0; i < size; i++)
        heap->array[i] = createNode(data[i], weight[i]);
    heap->size = size;

    for (int i = (size - 2) / 2; i >= 0; i--)
        minHeapify(heap, i);

    return heap;
}

// 构建哈夫曼树
HuffmanNode *buildHuffmanTree(char data[], int weight[], int size) {
    MinHeap *heap = buildMinHeap(data, weight, size);

    while (heap->size > 1) {
        HuffmanNode *left = extractMin(heap);
        HuffmanNode *right = extractMin(heap);

        HuffmanNode *top = createNode('$', left->weight + right->weight);
        top->left = left;
        top->right = right;

        insertMinHeap(heap, top);
    }

    return extractMin(heap);
}

// 打印哈夫曼编码（前序遍历）
void printCodes(HuffmanNode *root, int *code, int top) {
    if (root->left) {
        code[top] = 0;
        printCodes(root->left, code, top + 1);
    }

    if (root->right) {
        code[top] = 1;
        printCodes(root->right, code, top + 1);
    }

    if (!root->left && !root->right) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; i++)
            printf("%d", code[i]);
        printf("\n");
    }
}

// 主函数
int main() {
    char data[] = {'A', 'B', 'C', 'D', 'E', 'F'};
    int weight[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(data) / sizeof(data[0]);

    HuffmanNode *root = buildHuffmanTree(data, weight, size);

    int code[100], top = 0;
    printCodes(root, code, top);

    return 0;
}

F: 0
C: 100
A: 1010
B: 1011
D: 110
E: 111
再贴上一个书上用遍历去实现的哈夫曼树

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

#define MAX_TREE_SIZE 100  // 最大树节点数量

// 定义哈夫曼树的节点结构
typedef struct HuffmanNode {
    char data;           // 节点代表的字符
    int frequency;       // 字符的频率
    struct HuffmanNode* left;  // 左子树
    struct HuffmanNode* right; // 右子树
} HuffmanNode;

// 创建一个新的哈夫曼树节点
HuffmanNode* createHuffmanNode(char data, int frequency) {
    HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    node->data = data;
    node->frequency = frequency;
    node->left = node->right = NULL;
    return node;
}

// 比较两个节点的频率，返回频率较小的节点
int compareNodes(const void* a, const void* b) {
    return ((HuffmanNode*)a)->frequency - ((HuffmanNode*)b)->frequency;
}

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(char* data, int* freq, int n) {
    // 创建一个包含所有字符节点的数组
    HuffmanNode* nodes[MAX_TREE_SIZE];
    for (int i = 0; i < n; i++) {
        nodes[i] = createHuffmanNode(data[i], freq[i]);
    }

    // 用遍历的方式替代堆
    while (n > 1) {
        // 每次遍历数组，找到频率最小的两个节点
        qsort(nodes, n, sizeof(HuffmanNode*), compareNodes);
        
        // 取出最小的两个节点
        HuffmanNode* left = nodes[0];
        HuffmanNode* right = nodes[1];

        // 创建一个新节点，其频率为左右子树频率之和
        HuffmanNode* newNode = createHuffmanNode('\0', left->frequency + right->frequency);
        newNode->left = left;
        newNode->right = right;

        // 将新节点插入数组并调整数组
        nodes[0] = newNode;
        // 将其他节点向前移动一位
        for (int i = 1; i < n - 1; i++) {
            nodes[i] = nodes[i + 1];
        }

        n--;  // 节点数量减一
    }

    // 返回哈夫曼树的根节点
    return nodes[0];
}

// 打印哈夫曼树
void printHuffmanTree(HuffmanNode* root, char* code, int length) {
    if (root == NULL) return;
    
    // 如果是叶子节点，打印其字符和对应的编码
    if (root->left == NULL && root->right == NULL) {
        code[length] = '\0';  // 结束编码字符串
        printf("%c: %s\n", root->data, code);
        return;
    }

    // 向左子树递归添加'0'
    code[length] = '0';
    printHuffmanTree(root->left, code, length + 1);

    // 向右子树递归添加'1'
    code[length] = '1';
    printHuffmanTree(root->right, code, length + 1);
}

int main() {
    // 输入字符和频率
    char data[] = {'A', 'B', 'C', 'D', 'E', 'F'};
    int freq[] = {5, 9, 12, 13, 16, 45};
    int n = sizeof(data) / sizeof(data[0]);

    // 构建哈夫曼树
    HuffmanNode* root = buildHuffmanTree(data, freq, n);

    // 打印哈夫曼编码
    char code[MAX_TREE_SIZE];
    printf("Huffman Codes:\n");
    printHuffmanTree(root, code, 0);

    return 0;
}

满二叉树和完全二叉树

满二叉树
一个二叉树如果所有层上的结点数都达到了最大值，则称为满二叉树。
1
2
3
4
5
6
1
/ \
2 3
/ \ / \
4 5 6 7
完全二叉树
一个二叉树如果其所有层（除了最后一层）都完全填满，并且最后一层的结点都靠左排列，则称为完全二叉树。
1
2
3
4
5
1
/ \
2 3
/ \ /
4 5 6

树的建立，遍历

我认为看代码更能理解怎么前中后遍历

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

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

// 创建新节点
TreeNode *createNode(int value) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构建二叉树 (递归输入)
TreeNode *buildTree() {
    int value;
    printf("请输入节点值(-1表示为空)：");
    scanf("%d", &value);

    // 如果输入为 -1，返回空节点
    if (value == -1) {
        return NULL;
    }

    // 创建根节点
    TreeNode *root = createNode(value);

    printf("输入 %d 的左子节点：\n", value);
    root->left = buildTree();

    printf("输入 %d 的右子节点：\n", value);
    root->right = buildTree();

    return root;
}

// 前序遍历
void preOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);  // 访问根节点
    preOrder(root->left);      // 遍历左子树
    preOrder(root->right);     // 遍历右子树
}

// 中序遍历
void inOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);       // 遍历左子树
    printf("%d ", root->data); // 访问根节点
    inOrder(root->right);      // 遍历右子树
}

// 后序遍历
void postOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);     // 遍历左子树
    postOrder(root->right);    // 遍历右子树
    printf("%d ", root->data); // 访问根节点
}

// 释放二叉树内存
void freeTree(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);  // 释放左子树
    freeTree(root->right); // 释放右子树
    free(root);            // 释放当前节点
}

int main() {
    printf("开始构建二叉树...\n");
    TreeNode *root = buildTree();

    printf("\n前序遍历结果：");
    preOrder(root);

    printf("\n中序遍历结果：");
    inOrder(root);

    printf("\n后序遍历结果：");
    postOrder(root);

    // 释放内存
    freeTree(root);

    return 0;
}

前序遍历结果：1 2 3 4
中序遍历结果：2 3 1 4
后序遍历结果：3 2 4 1

要想确定树的样子一定要有中序遍历，然后去根据定义一递归的去找左右就好了
多练习两个看看就好了
示例
假设：
前序遍历：A B D E C F G
中序遍历：D B E A F C G
构建过程：
从前序遍历中，A 是根节点。
在中序遍历中，A 将序列分为两部分：
左子树的中序序列：D B E
右子树的中序序列：F C G
从前序遍历的剩余部分：
左子树的前序序列：B D E
右子树的前序序列：C F G
递归构建左右子树：
左子树的根节点是 B。
右子树的根节点是 C。

    A
   / \
  B   C
 / \   \
D   E   F
         \
          G

中序遍历是分割子树的关键，前序或后序遍历提供了根节点的顺序。

线索二叉树

是一种对普通二叉树的扩展。通过利用二叉树中指针的空闲空间，将树中节点的左右指针扩展为指向前驱节点和后继节点，使遍历树更加高效。
就是可以不每一次从头节点开始遍历
前序线索二叉树：基于前序遍历建立的线索二叉树。
中序线索二叉树：基于中序遍历建立的线索二叉树。
后序线索二叉树：基于后序遍历建立的线索二叉树。
特点
线索二叉树在节点结构中新增了两个布尔变量，用来标记左右指针是否是线索：
LTag：标记左指针的含义，0 表示指向左子树，1 表示指向前驱。
RTag：标记右指针的含义，0 表示指向右子树，1 表示指向后继。
线索二叉树通过线索化处理后，可以通过线索指针快速找到前驱和后继节点，而无需递归或栈辅助。

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

// 定义线索二叉树节点
typedef struct ThreadedTreeNode {
    int data;
    struct ThreadedTreeNode *left;
    struct ThreadedTreeNode *right;
    int LTag; // 0: 左指针指向子树, 1: 左指针为线索
    int RTag; // 0: 右指针指向子树, 1: 右指针为线索
} ThreadedTreeNode;

// 全局变量，用来记录当前节点的前驱节点
ThreadedTreeNode *pre = NULL;

// 创建新节点
ThreadedTreeNode *createNode(int data) {
    ThreadedTreeNode *node = (ThreadedTreeNode *)malloc(sizeof(ThreadedTreeNode));
    node->data = data;
    node->left = node->right = NULL;
    node->LTag = 0;
    node->RTag = 0;
    return node;
}

// 中序线索化
void inThreading(ThreadedTreeNode *root) {
    if (root == NULL) return;

    // 线索化左子树
    inThreading(root->left);

    // 左指针为空，将其指向前驱
    if (root->left == NULL) {
        root->LTag = 1;
        root->left = pre;
    }

    // 前驱节点的右指针为空，将其指向当前节点
    if (pre != NULL && pre->right == NULL) {
        pre->RTag = 1;
        pre->right = root;
    }// 重点注意这个地方，虽然很难但是很关键

    // 更新前驱节点为当前节点
    pre = root;

    // 线索化右子树
    inThreading(root->right);
}

// 创建线索二叉树
ThreadedTreeNode *createThreadedTree() {
    // 构造普通二叉树
    ThreadedTreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // 线索化
    pre = NULL;
    inThreading(root);

    return root;
}

// 中序遍历线索二叉树
void inOrderTraverse(ThreadedTreeNode *root) {
    ThreadedTreeNode *current = root;
    while (current != NULL) {
        // 找到最左侧的节点
        while (current->LTag == 0) {
            current = current->left;
        }

        // 打印当前节点
        printf("%d ", current->data);

        // 使用线索访问后继节点
        while (current->RTag == 1) {
            current = current->right;
            printf("%d ", current->data);
        }

        // 转向右子树
        current = current->right;
    }
}

int main() {
    ThreadedTreeNode *root = createThreadedTree();
    printf("中序遍历线索二叉树：");
    inOrderTraverse(root);
    return 0;
}

其实和三种遍历一样，改改遍历顺序就好了

森林与树与二叉树的转换

感觉没啥用，自己去看ppt
技巧：

将树转换成二叉树：兄弟相连留长子
二叉树变树：左孩右右连双亲，去掉原来右孩线
森林变二叉树：树变二叉根相连

二叉树变森林：去掉全部右孩线，孤立二叉再还原 // 主要是树和森林怎么变
代码实现巨麻烦，我就贴一个看看就好了

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

// 定义N叉树节点（普通树节点）
typedef struct NTreeNode {
    char data;              // 数据
    struct NTreeNode **children; // 子节点数组
    int child_count;        // 子节点数目
} NTreeNode;

// 定义二叉树节点
typedef struct BinaryTreeNode {
    char data;              // 数据
    struct BinaryTreeNode *left;   // 左子节点（第一个子节点）
    struct BinaryTreeNode *right;  // 右子节点（下一个兄弟节点）
} BinaryTreeNode;

// 创建一个N叉树节点
NTreeNode* createNTreeNode(char data, int child_count) {
    NTreeNode* node = (NTreeNode*)malloc(sizeof(NTreeNode));
    node->data = data;
    node->child_count = child_count;
    node->children = (NTreeNode**)malloc(child_count * sizeof(NTreeNode*));
    return node;
}

// 创建一个二叉树节点
BinaryTreeNode* createBinaryTreeNode(char data) {
    BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// N叉树转二叉树
BinaryTreeNode* NTreeToBinaryTree(NTreeNode* nNode) {
    if (nNode == NULL) return NULL;

    // 创建一个对应的二叉树节点
    BinaryTreeNode* bNode = createBinaryTreeNode(nNode->data);

    // 处理第一个子节点，作为左子节点
    if (nNode->child_count > 0) {
        bNode->left = NTreeToBinaryTree(nNode->children[0]);
    }

    // 处理剩余的子节点，作为右子节点链表
    BinaryTreeNode* current = bNode->left;
    for (int i = 1; i < nNode->child_count; i++) {
        if (current == NULL) {
            current = NTreeToBinaryTree(nNode->children[i]);
            bNode->left = current;
        } else {
            current->right = NTreeToBinaryTree(nNode->children[i]);
            current = current->right;
        }
    }

    return bNode;
}

// 二叉树转N叉树
NTreeNode* BinaryTreeToNTree(BinaryTreeNode* bNode) {
    if (bNode == NULL) return NULL;

    // 创建一个对应的N叉树节点
    NTreeNode* nNode = createNTreeNode(bNode->data, 0);
    
    // 处理左子树（第一个子节点）
    if (bNode->left != NULL) {
        NTreeNode* leftChild = BinaryTreeToNTree(bNode->left);
        nNode->children = (NTreeNode**)realloc(nNode->children, ++(nNode->child_count) * sizeof(NTreeNode*));
        nNode->children[nNode->child_count - 1] = leftChild;
    }

    // 处理右子树（兄弟节点）
    BinaryTreeNode* sibling = bNode->right;
    while (sibling != NULL) {
        NTreeNode* rightSibling = BinaryTreeToNTree(sibling);
        nNode->children = (NTreeNode**)realloc(nNode->children, ++(nNode->child_count) * sizeof(NTreeNode*));
        nNode->children[nNode->child_count - 1] = rightSibling;
        sibling = sibling->right;
    }

    return nNode;
}

// 前序遍历二叉树
void printBinaryTreePreorder(BinaryTreeNode* root) {
    if (root == NULL) return;
    printf("%c ", root->data);
    printBinaryTreePreorder(root->left);
    printBinaryTreePreorder(root->right);
}

// 打印N叉树
void printNTree(NTreeNode* root) {
    if (root == NULL) return;
    printf("%c ", root->data);
    for (int i = 0; i < root->child_count; i++) {
        printNTree(root->children[i]);
    }
}

int main() {
    // 创建一个N叉树
    NTreeNode* nRoot = createNTreeNode('A', 3);
    nRoot->children[0] = createNTreeNode('B', 2);
    nRoot->children[1] = createNTreeNode('C', 0);
    nRoot->children[2] = createNTreeNode('D', 0);
    nRoot->children[0]->children[0] = createNTreeNode('E', 0);
    nRoot->children[0]->children[1] = createNTreeNode('F', 0);

    // 将N叉树转换为二叉树
    BinaryTreeNode* bRoot = NTreeToBinaryTree(nRoot);

    // 打印二叉树（前序遍历）
    printf("Binary Tree (Preorder): ");
    printBinaryTreePreorder(bRoot);
    printf("\n");

    // 将二叉树转换回N叉树
    NTreeNode* newNRoot = BinaryTreeToNTree(bRoot);

    // 打印N叉树
    printf("N Tree: ");
    printNTree(newNRoot);
    printf("\n");

    return 0;
}

图

基本概念

图: G = (V, E)
V: 顶点（Vertex）的有穷非空集合; 顶点表示数据元素
E: 边（Edge，或称弧Arc）的有穷集合;
边表示数据元素之间的关系

G1=<V1,E1>
V1={v1 v2,v3,v4}
E1={<v1,v2 >,<v1,v3 >,<v3,v4 >,<v4,v1 >}

无向图(Directed Graph, or Digraph): 每条边都是无方向的;
有向图(Undirected Graph, or Undigraph): 每条边都是有方向的。

完全图(Completed Graph): 任意两个点都有一条边相连

无向完全图：有n(n-1)/2条边（图中每个顶点和其余n-1个顶点都有边相连）的无向图为完全图。
有向完全图：有n(n-1)条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为有向完全图。
稀疏图(Sparse Graph): 有很少边或弧的图（e < n log n）
稠密图(Dense Graph): 有较多边或弧的图

邻接: 有边/弧相连的两个顶点之间的关系

无向图: 存在边(v, v’), 称作v与v’互为邻接点(Adjacent)，即v与v’相邻接; 边(v, v’)依附于(Incident)顶点v和v’ , 或者说(v, v’)与顶点v和v’ 相关联
有向图: 存在边< v, v’> ，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v ，或者说弧< v, v’>与顶点v、v’相关联。

顶点的度(Degree):

对无向图而言，顶点v 的度是指和v相关联的边的数目，记作TD(v)
对有向图而言，顶点v的度是其入度和出度之和
• 入度(Indegree): 以v为终点的有向边的条数，记作ID(v)
• 出度(Outdegree): 以v为始点的有向边的条数，记作OD(v)
• TD(v) = ID(v) + OD(v)

路径(Path): 接续的边构成的顶点序列

对无向图而言，从顶点v到v’的路径是一个顶点序列(v=vi0, vi1, vi2, …,vim= v ’), 其中(vij-1, vij)∈E, 1≤j≤m。
对有向图而言，路径也是有向的，顶点序列应满足<vij-1, vij>∈E，1≤j≤m。

路径长度: 路径上边或弧的数目/权值之和
回路(环): 第一个顶点和最后一个顶点相同的路径
简单路径: 路径上顶点均不相同的路径
简单回路(简单环): 除路径起点和终点相同外，其余顶点均不相同的路径

连通图: 在无向图G=（V，{E}）中，若从vi到vj有路径相通，则称顶点vi与vj是连通的。如果对于图中的任意两个顶点vi、vj∈V，vi与vj都是连通的，则称该无向图G为**连通图(Connected Graph)**。
强连通图：在有向图G=（V，{A}）中，若对于每对顶点vi、vj∈V且vi≠vj，从vi到vj和vj到vi都有路径，则称该有向图为强连通图

连通分量：无向图G中的极大连通子图称为G的连通分量(Connected Component)。
极大连通子图：该子图是G的连通子图，将G的任何不在该子
图中的顶点加入，子图不再连通。

强连通分量：有向图的极大强连通子图称作有向图的强连通分量。
极大强连通子图：该子图是G的强连通子图，将D的任何不在子图中的顶点加入，子图不在是强连通的。

实现建图，dfs(深度优先遍历), bfs(广度优先遍历)

邻接表

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

// 图的邻接表表示
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int V;             // 顶点数
    Node** adjList;    // 邻接表
} Graph;

// 创建一个图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->adjList = (Node**)malloc(V * sizeof(Node*));

    // 初始化每个邻接表
    for (int i = 0; i < V; i++) {
        graph->adjList[i] = NULL;
    }

    return graph;
}

// 添加边到图中
void addEdge(Graph* graph, int src, int dest) {
    // 添加从src到dest的边
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;

    // 如果是无向图，也需要添加反向边
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}

// 打印图的邻接表
void printGraph(Graph* graph) {
    for (int v = 0; v < graph->V; v++) {
        Node* temp = graph->adjList[v];
        printf("\nVertex %d: ", v);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

// BFS 广度优先搜索
void BFS(Graph* graph, int start) {
    int* visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = 0;
    }

    // 创建一个队列来实现BFS
    int* queue = (int*)malloc(graph->V * sizeof(int));
    int front = 0, rear = 0;

    // 访问起始节点
    visited[start] = 1;
    queue[rear++] = start; //数组模拟队列

    printf("\nBFS starting from vertex %d: ", start);

    while (front < rear) {
        int vertex = queue[front++];
        printf("%d ", vertex);

        // 访问与当前节点相邻的未访问节点
        Node* temp = graph->adjList[vertex];
        while (temp) {
            if (!visited[temp->vertex]) {
                visited[temp->vertex] = 1;
                queue[rear++] = temp->vertex;
            }
            temp = temp->next;
        }
    }

    free(visited);
    free(queue);
}

// DFS 深度优先搜索
void DFSUtil(Graph* graph, int vertex, int* visited) {
    // 访问当前节点
    visited[vertex] = 1;
    printf("%d ", vertex);

    // 递归访问所有与当前节点相邻的未访问节点
    Node* temp = graph->adjList[vertex];
    while (temp) {
        if (!visited[temp->vertex]) {
            DFSUtil(graph, temp->vertex, visited);
        }
        temp = temp->next;
    }
}

void DFS(Graph* graph, int start) {
    int* visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = 0;
    }

    printf("\nDFS starting from vertex %d: ", start);
    DFSUtil(graph, start, visited);

    free(visited);
}

int main() {
    // 创建一个图并添加边
    Graph* graph = createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    // 打印图的邻接表
    printGraph(graph);

    // 执行BFS和DFS
    BFS(graph, 0);  // 从节点0开始BFS
    DFS(graph, 0);  // 从节点0开始DFS

    // 释放图的内存
    free(graph->adjList);
    free(graph);

    return 0;
}

临界表的好处是空间小，运行时间短，但是不好写
-> 头节点 -> 节点1 -> 节点2 -> 节点3 -> NULL
-> 新头节点(X) -> 头节点 -> 节点1 -> 节点2 -> 节点3 -> NULL

邻接矩阵
邻接矩阵是一种二维数组，其中矩阵中的元素表示图中节点之间的连接关系。如果图中存在边，则对应矩阵位置为1，否则为0。对于无向图，矩阵是对称的。
假设我们有一个图，包含 4 个节点，边的连接如下：

节点 0 与节点 1 和 2 有边。
节点 1 与节点 3 有边。
节点 2 与节点 3 有边。
这个图的邻接矩阵如下：

    0  1  2  3
  --------------
0 | 0  1  1  0
1 | 1  0  0  1
2 | 1  0  0  1
3 | 0  1  1  0

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

#define MAX_VERTICES 10  // 最大顶点数

// 图的邻接矩阵表示
typedef struct Graph {
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
    int V;  // 图的顶点数
} Graph;

// 创建图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;

    // 初始化邻接矩阵
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            graph->adjMatrix[i][j] = 0;  // 初始时没有边
        }
    }

    return graph;
}

// 添加边到图
void addEdge(Graph* graph, int src, int dest) {
    graph->adjMatrix[src][dest] = 1;
    graph->adjMatrix[dest][src] = 1;  // 如果是无向图
}

// 打印邻接矩阵
void printGraph(Graph* graph) {
    for (int i = 0; i < graph->V; i++) {
        for (int j = 0; j < graph->V; j++) {
            printf("%d ", graph->adjMatrix[i][j]);
        }
        printf("\n");
    }
}

// BFS 广度优先搜索
void BFS(Graph* graph, int start) {
    int visited[MAX_VERTICES] = {0};  // 标记访问的节点
    int queue[MAX_VERTICES];  // 队列
    int front = 0, rear = 0;

    // 访问起始节点
    visited[start] = 1;
    queue[rear++] = start;

    printf("\nBFS starting from vertex %d: ", start);

    while (front < rear) {
        int vertex = queue[front++];

        printf("%d ", vertex);

        // 访问与当前节点相邻且未访问的节点
        for (int i = 0; i < graph->V; i++) {
            if (graph->adjMatrix[vertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

// DFS 深度优先搜索（使用递归）
void DFSUtil(Graph* graph, int vertex, int* visited) {
    // 访问当前节点
    visited[vertex] = 1;
    printf("%d ", vertex);

    // 递归访问所有与当前节点相邻的未访问节点
    for (int i = 0; i < graph->V; i++) {
        if (graph->adjMatrix[vertex][i] == 1 && !visited[i]) {
            DFSUtil(graph, i, visited);
        }
    }
}

void DFS(Graph* graph, int start) {
    int visited[MAX_VERTICES] = {0};  // 标记访问的节点

    printf("\nDFS starting from vertex %d: ", start);
    DFSUtil(graph, start, visited);
}

int main() {
    // 创建一个图并添加边
    Graph* graph = createGraph(4);  // 4个顶点
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 3);

    // 打印图的邻接矩阵
    printf("Graph's Adjacency Matrix:\n");
    printGraph(graph);

    // 执行BFS和DFS
    BFS(graph, 0);  // 从节点0开始BFS
    DFS(graph, 0);  // 从节点0开始DFS

    // 释放图的内存
    free(graph);

    return 0;
}

深度优先搜索 (DFS)
DFS 是一种“深度”优先的遍历方式，意味着它会尽可能深地访问一个节点的子节点，直到无法继续深度访问为止，然后回溯并访问其他未被访问的节点。

工作原理：
从一个起始节点开始，访问这个节点。
然后递归地访问所有与当前节点相邻且未被访问的节点，直到达到没有未访问的相邻节点为止。
当无法继续深度访问时，回到上一个节点，继续访问它的其他邻居。
特点：
递归或栈：DFS 通常使用递归或者显式栈来实现，依靠栈的后进先出（LIFO）特性来实现回溯。
深入探索：优先沿着一条路径探索下去，直到遇到死胡同，再回溯。
应用：用于求解连通分量、拓扑排序、寻找路径等问题。

0 -> 1 -> 3 -> 2 -> 4

void DFS(int graph[][5], int node, int visited[]) {
    visited[node] = 1;  // 标记节点为已访问
    printf("%d ", node);  // 访问节点

    // 递归访问与当前节点相邻的未访问节点
    for (int i = 0; i < 5; i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            DFS(graph, i, visited);
        }
    }
}

BFS 是一种“宽度”优先的遍历方式，意味着它会先访问所有与起始节点直接相邻的节点，然后逐层扩展，访问与当前节点相邻的节点。

工作原理：
从一个起始节点开始，访问这个节点。
然后访问所有与当前节点直接相邻的未访问节点，并将它们加入队列。
接着从队列中依次取出节点，继续访问它们的相邻节点，直到所有节点都被访问过。
特点：
队列：BFS 使用队列来实现，依靠队列的先进先出（FIFO）特性来保证按层次遍历。
层次遍历：优先访问与当前节点在同一层的节点，然后再向下访问下一层节点。
应用：用于最短路径查找、图的层次遍历、连通性等问题。
同样的例子

0 -> 1 -> 2 -> 3 -> 4
看了代码就理解了

void BFS(int graph[][5], int start, int visited[]) {
    int queue[5], front = 0, rear = 0;
    visited[start] = 1;  // 标记起始节点为已访问
    queue[rear++] = start;  // 将起始节点加入队列

    while (front < rear) {
        int node = queue[front++];  // 从队列取出一个节点
        printf("%d ", node);  // 访问节点

        // 访问与当前节点相邻且未访问的节点
        for (int i = 0; i < 5; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

图的连通性问题，最小生成树

Prim算法(基于贪心去实现的)
Kruskal算法(基于并查集去实现的)

prim
它的基本思想是从图中的某个起始节点出发，逐步选择最小的边，扩展生成树，直到所有节点都被包含在内。

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 10
#define INF INT_MAX  // 表示没有连接的边

// 选择最小的权重边
int minKey(int key[], int mstSet[], int vertices) {
    int min = INF, min_index;

    for (int v = 0; v < vertices; v++) {
        if (mstSet[v] == 0 && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }

    return min_index;
}

// Prim算法实现
void prim(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
    int parent[MAX_VERTICES];  // 存储生成树的父节点
    int key[MAX_VERTICES];     // 存储权重值，key[i]表示从生成树到i的最小边权重
    int mstSet[MAX_VERTICES];  // mstSet[i]为1表示顶点i已经包含在生成树中

    // 初始化
    for (int i = 0; i < vertices; i++) {
        key[i] = INF;
        mstSet[i] = 0;
    }
    
    key[0] = 0;  // 从第一个顶点开始
    parent[0] = -1;  // 第一个顶点没有父节点

    // 生成树包含所有顶点
    for (int count = 0; count < vertices - 1; count++) {
        // 选择一个权重最小的顶点
        int u = minKey(key, mstSet, vertices);
        
        mstSet[u] = 1;  // 将选择的顶点加入生成树

        // 更新邻接顶点的key值
        for (int v = 0; v < vertices; v++) {
            // graph[u][v]是从u到v的边的权重
            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    // 输出最小生成树
    printf("Edge \tWeight\n");
    for (int i = 1; i < vertices; i++) {
        printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 2, 0, 6, 0, 0},
        {2, 0, 3, 8, 5, 0},
        {0, 3, 0, 0, 7, 0},
        {6, 8, 0, 0, 9, 4},
        {0, 5, 7, 9, 0, 3},
        {0, 0, 0, 4, 3, 0}
    };

    int vertices = 6;  // 图中顶点的数量
    prim(graph, vertices);
    
    return 0;
}

Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
3 - 4 5
4 - 5 3

Kruskal算法
Kruskal算法的步骤：
排序边：将图中的所有边按照权重从小到大进行排序。
初始化：每个顶点开始时是一个独立的集合，表示每个顶点都在自己的连通分量中。
遍历边：依次检查排序后的每一条边，如果边的两个端点属于不同的连通分量，就将它们连接起来，并合并这两个连通分量。

重复：直到生成树包含图中所有的顶点或者所有边都被处理完。

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

#define MAX_VERTICES 10
#define INF 99999  // 表示无穷大

// 边的结构体
typedef struct {
    int u, v, weight;
} Edge;

// 比较函数，用于排序
int compareEdges(const void *a, const void *b) {
    return ((Edge *)a)->weight - ((Edge *)b)->weight;
}

// 查找操作：返回顶点的父节点（即该顶点所在的连通分量）
int findParent(int parent[], int x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

// Kruskal算法实现
void kruskal(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
    Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];
    int edgeCount = 0;
    
    // 初始化边集合
    for (int i = 0; i < vertices; i++) {
        for (int j = i + 1; j < vertices; j++) {
            if (graph[i][j] != 0 && graph[i][j] != INF) {
                edges[edgeCount].u = i;
                edges[edgeCount].v = j;
                edges[edgeCount].weight = graph[i][j];
                edgeCount++;
            }
        }
    }

    // 按照边的权重升序排序
    qsort(edges, edgeCount, sizeof(Edge), compareEdges);
    
    int parent[MAX_VERTICES];
    for (int i = 0; i < vertices; i++) {
        parent[i] = i;  // 每个顶点初始化为自己的父节点
    }

    int mstWeight = 0;
    printf("Edge \tWeight\n");

    // 遍历排序后的边集合
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i].u;
        int v = edges[i].v;

        // 查找u和v的父节点（连通分量）
        int rootU = findParent(parent, u);
        int rootV = findParent(parent, v);

        // 如果u和v的父节点不同，则说明它们不在同一个连通分量，加入生成树
        if (rootU != rootV) {
            printf("%d - %d \t%d\n", u, v, edges[i].weight);
            mstWeight += edges[i].weight;
            
            // 合并u和v的连通分量
            parent[rootU] = rootV;
        }
    }

    printf("Minimum spanning tree weight: %d\n", mstWeight);
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 2, 0, 6, 0, 0},
        {2, 0, 3, 8, 5, 0},
        {0, 3, 0, 0, 7, 0},
        {6, 8, 0, 0, 9, 4},
        {0, 5, 7, 9, 0, 3},
        {0, 0, 0, 4, 3, 0}
    };
    
    int vertices = 6;  // 图中顶点的数量
    kruskal(graph, vertices);
    
    return 0;
}

最短路

问题抽象:在有向网中A点（源点）到达B点(终点)的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

单源最短路 dijstra

Dijkstra算法的步骤：
初始化：
将起点的最短路径初始化为0，其他所有节点的最短路径初始化为无穷大（表示尚未确定最短路径）
使用一个布尔数组（或集合）S，记录已经找到最短路径的节点
选择当前最短的节点：
在未被加入集合S的节点中，选择当前最短路径值最小的节点u
更新邻接节点的最短路径：
对于节点u的每个邻接节点v，如果通过u到v的路径更短，就更新v的最短路径
重复步骤2和3，直到所有节点的最短路径都被找到

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 10
#define INF INT_MAX  // 表示无穷大

// 选择当前最短路径的节点
int minDistance(int dist[], int sptSet[], int vertices) {
    int min = INF, min_index;
    
    for (int v = 0; v < vertices; v++) {
        if (sptSet[v] == 0 && dist[v] < min) {
            min = dist[v];
            min_index = v;
        }
    }
    
    return min_index;
}

// Dijkstra算法实现
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int vertices, int start) {
    int dist[MAX_VERTICES];    // 存储最短路径的数组
    int sptSet[MAX_VERTICES];  // sptSet[i]表示顶点i是否在最短路径树中
    
    // 初始化dist数组和sptSet数组
    for (int i = 0; i < vertices; i++) {
        dist[i] = INF;         // 初始时所有点的最短路径设为无穷大
        sptSet[i] = 0;         // 所有顶点都不在最短路径树中
    }
    
    dist[start] = 0;  // 起点的最短路径为0
    
    // 计算从起点到所有其他顶点的最短路径
    for (int count = 0; count < vertices - 1; count++) {
        // 选择最短路径的顶点
        int u = minDistance(dist, sptSet, vertices);
        
        sptSet[u] = 1;  // 将u加入最短路径树
        
        // 更新邻接节点的最短路径
        for (int v = 0; v < vertices; v++) {
            if (graph[u][v] != 0 && sptSet[v] == 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    
    // 输出结果
    printf("Vertex\tDistance from Source\n");
    for (int i = 0; i < vertices; i++) {
        printf("%d \t%d\n", i, dist[i]);
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 10, 0, 0, 0, 0},
        {10, 0, 5, 0, 0, 0},
        {0, 5, 0, 2, 3, 0},
        {0, 0, 2, 0, 3, 9},
        {0, 0, 3, 3, 0, 1},
        {0, 0, 0, 9, 1, 0}
    };
    
    int vertices = 6;  // 图中顶点的数量
    int start = 0;     // 从顶点0开始计算最短路径
    dijkstra(graph, vertices, start);
    
    return 0;
}

多源最短路 floyd

当然也可以跑n遍dijstra
floyd其实就是简单的动态规划

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 10
#define INF INT_MAX  // 无穷大，表示不可达

// Floyd-Warshall算法实现
void floydWarshall(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
    int dist[MAX_VERTICES][MAX_VERTICES];

    // 初始化dist数组为图的邻接矩阵
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            if (i == j) {
                dist[i][j] = 0;  // 从顶点到自己，最短路径为0
            } else if (graph[i][j] == 0) {
                dist[i][j] = INF;  // 如果没有边，设为无穷大
            } else {
                dist[i][j] = graph[i][j];
            }
        }
    }

    // 动态规划更新最短路径
    for (int k = 0; k < vertices; k++) {
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出最终的最短路径矩阵
    printf("Shortest distances between every pair of vertices:\n");
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            if (dist[i][j] == INF) {
                printf("INF\t");
            } else {
                printf("%d\t", dist[i][j]);
            }
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 3, INF, INF, INF, INF},
        {3, 0, 1, INF, INF, INF},
        {INF, 1, 0, 7, INF, 2},
        {INF, INF, 7, 0, 2, 3},
        {INF, INF, INF, 2, 0, 3},
        {INF, INF, 2, 3, 3, 0}
    };

    int vertices = 6;  // 图中的顶点数
    floydWarshall(graph, vertices);

    return 0;
}

拓扑排序

思想：
计算每个顶点的入度。
将所有入度为0的顶点加入队列（或集合），它们没有任何依赖关系。
每次从队列中取出一个顶点，将其加入拓扑排序中，并将其邻接点的入度减1。如果某个邻接点的入度变为0，加入队列。
重复步骤3，直到所有顶点都被处理。如果图中存在环，说明无法进行拓扑排序。

步骤：
初始化一个队列，将所有入度为0的节点放入队列。
当队列不为空时：
从队列中取出一个节点。
将这个节点加入拓扑排序结果中。
遍历该节点的所有邻接节点，减少它们的入度。如果某个邻接节点的入度变为0，将其加入队列。
如果最终拓扑排序的节点数小于图中的总节点数，说明图中存在环，无法进行拓扑排序。

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

#define MAX_VERTICES 10

// 使用邻接表表示图
typedef struct {
    int vertices;
    int adj[MAX_VERTICES][MAX_VERTICES];
} Graph;

// 初始化图
void initGraph(Graph *g, int vertices) {
    g->vertices = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            g->adj[i][j] = 0;  // 初始化邻接矩阵
        }
    }
}

// 添加有向边
void addEdge(Graph *g, int u, int v) {
    g->adj[u][v] = 1;
}

// Kahn算法实现拓扑排序
int topologicalSort(Graph *g) {
    int inDegree[MAX_VERTICES] = {0};  // 入度数组
    int queue[MAX_VERTICES], front = 0, rear = 0;
    int result[MAX_VERTICES];
    int idx = 0;
    
    // 计算每个节点的入度
    for (int i = 0; i < g->vertices; i++) {
        for (int j = 0; j < g->vertices; j++) {
            if (g->adj[i][j] == 1) {
                inDegree[j]++;
            }
        }
    }

    // 将所有入度为0的节点加入队列
    for (int i = 0; i < g->vertices; i++) {
        if (inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }

    // 处理队列中的节点
    while (front < rear) {
        int u = queue[front++];
        result[idx++] = u;  // 将节点加入拓扑排序

        // 减少邻接节点的入度，如果某个邻接节点的入度为0，则加入队列
        for (int v = 0; v < g->vertices; v++) {
            if (g->adj[u][v] == 1) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue[rear++] = v;
                }
            }
        }
    }

    // 如果拓扑排序的节点数等于图中的节点数，说明没有环，排序成功
    if (idx != g->vertices) {
        printf("图中有环，无法进行拓扑排序。\n");
        return 0;  // 返回0表示图中有环
    }

    // 输出拓扑排序结果
    printf("拓扑排序结果：\n");
    for (int i = 0; i < g->vertices; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    return 1;  // 返回1表示拓扑排序成功
}

int main() {
    Graph g;
    initGraph(&g, 6);  // 创建一个有6个顶点的图

    // 添加边
    addEdge(&g, 5, 2);
    addEdge(&g, 5, 0);
    addEdge(&g, 4, 0);
    addEdge(&g, 4, 1);
    addEdge(&g, 2, 3);
    addEdge(&g, 3, 1);

    // 执行拓扑排序
    topologicalSort(&g);

    return 0;
}

  5      4
 / \    / \
2   0  0   1
    \    /
     3

拓扑排序结果：5 4 2 3 0 1

查找

线性表

顺序查找（线性查找）

for循环啊
折半查找（二分查找）
初始范围：设定查找区间的左右边界，初始时为数组的开始和结束索引。
中间值：每次通过计算区间的中间元素（mid = (low + high) / 2），与目标值进行比较。
缩小范围：
如果中间值等于目标值，则查找成功。
如果目标值小于中间值，则将查找区间缩小为左半部分。
如果目标值大于中间值，则将查找区间缩小为右半部分。
继续查找：重复上述步骤，直到找到目标值或查找范围为空

一定要保证是升序或者降序

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;  // 避免溢出
        
        if (arr[mid] == target) {
            return mid;  // 找到目标值，返回其索引
        } else if (arr[mid] < target) {
            low = mid + 1;  // 目标值在右侧，缩小范围到右半部分
        } else {
            high = mid - 1;  // 目标值在左侧，缩小范围到左半部分
        }
    }
    
    return -1;  // 目标值不存在，返回-1
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    
    int result = binarySearch(arr, size, target);
    
    if (result != -1) {
        printf("目标元素 %d 在数组中的位置是 %d\n", target, result);
    } else {
        printf("目标元素 %d 不在数组中\n", target);
    }
    
    return 0;
}

分块查找（索引顺序查找）
基本思路：
– （1）先让数据分块有序，即分成若干子表，
要求每个子表中的数据元素值都比后一块
中的数值小（但子表内部未必有序）

（2）然后将各子表中的最大关键字构成
一个索引表，表中还要包含每个子表的起
始地址。
分块 + 二分可以优化

#include <stdio.h>
#include <math.h>

// 使用二分查找在块内查找目标值
int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            return mid;  // 找到目标值
        } else if (arr[mid] < target) {
            low = mid + 1;  // 目标值在右侧
        } else {
            high = mid - 1;  // 目标值在左侧
        }
    }
    return -1;  // 目标值不在块内
}

// 分块查找
int blockSearch(int arr[], int size, int target) {
    int blockSize = (int)sqrt(size);  // 块的大小为 sqrt(n)
    
    // 查找目标值所在的块
    int blockStart = 0;
    while (blockStart < size && arr[blockStart + blockSize - 1] < target) {
        blockStart += blockSize;
    }

    // 在找到的块内进行二分查找
    return binarySearch(arr, blockStart, blockStart + blockSize - 1, target);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 19;

    int result = blockSearch(arr, size, target);
    
    if (result != -1) {
        printf("目标元素 %d 在数组中的位置是 %d\n", target, result);
    } else {
        printf("目标元素 %d 不在数组中\n", target);
    }

    return 0;
}

二叉排序树

二叉排序树的基本操作：

查找（Search）：根据树的性质，从根节点开始，比较目标值与当前节点的值：

如果目标值小于当前节点的值，则在左子树中查找。
如果目标值大于当前节点的值，则在右子树中查找。
如果目标值等于当前节点的值，则查找成功，返回该节点。
2. 插入（Insert）：从根节点开始，逐层比较待插入值与当前节点的值，找到合适的位置后插入新的节点。

删除（Delete）：删除节点有三种情况：

删除的节点没有子节点：直接删除该节点。
删除的节点有一个子节点：用该节点的唯一子节点代替该节点。
删除的节点有两个子节点：找到该节点的右子树中的最小节点（即中序遍历的下一个节点），用该最小节点的值替代当前节点的值，再删除该最小节点。
4. 遍历（Traversal）：常用的遍历方法有：

前序遍历（Pre-order Traversal）：根节点 -> 左子树 -> 右子树。
中序遍历（In-order Traversal）：左子树 -> 根节点 -> 右子树。
后序遍历（Post-order Traversal）：左子树 -> 右子树 -> 根节点。

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

// 二叉树节点结构
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 创建一个新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入节点
Node* insert(Node* root, int data) {
    if (root == NULL) {
        return createNode(data); //注意没有return，所以可以这么写
    }
    
    if (data < root->data) {
        root->left = insert(root->left, data);  // 插入左子树
    } else {
        root->right = insert(root->right, data);  // 插入右子树
    }
    
    return root;
}

// 查找节点
Node* search(Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    
    if (data < root->data) {
        return search(root->left, data);  // 在左子树查找
    } else {
        return search(root->right, data);  // 在右子树查找
    }
}

// 删除节点
Node* deleteNode(Node* 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 {
        // 找到节点
        // 1. 删除的节点没有子节点
        if (root->left == NULL && root->right == NULL) {
            free(root);
            root = NULL;
        }
        // 2. 删除的节点只有一个子节点
        else if (root->left == NULL) {
            Node* temp = root;
            root = root->right;
            free(temp);
        } else if (root->right == NULL) {
            Node* temp = root;
            root = root->left;
            free(temp);
        }
        // 3. 删除的节点有两个子节点
        else {
            Node* temp = root->right;
            while (temp && temp->left != NULL) {
                temp = temp->left;  // 找到右子树的最小节点
            }
            root->data = temp->data;  // 用右子树最小节点的值替代当前节点
            root->right = deleteNode(root->right, temp->data);  // 删除右子树最小节点
        }
    }
    return root;
}

// 中序遍历
void inorderTraversal(Node* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);  // 访问左子树
    printf("%d ", root->data);     // 访问根节点
    inorderTraversal(root->right); // 访问右子树
}

// 主函数
int main() {
    Node* root = NULL;
    
    // 插入元素
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);
    
    // 中序遍历：输出顺序应该是升序
    printf("中序遍历结果：");
    inorderTraversal(root);
    printf("\n");

    // 查找元素
    Node* result = search(root, 40);
    if (result != NULL) {
        printf("找到了节点 %d\n", result->data);
    } else {
        printf("节点未找到\n");
    }

    // 删除元素
    root = deleteNode(root, 20);
    root = deleteNode(root, 30);
    root = deleteNode(root, 50);

    // 中序遍历：删除后的结果
    printf("删除后中序遍历结果：");
    inorderTraversal(root);
    printf("\n");
    
    return 0;
}

问题是可能退化成链，所以这里需要引入平衡树的概念
课本中学的是AVL树
就四个操作
右旋

    y                                  x
   / \                               /   \
  x   T4     Right Rotate(y)      z       y
 / \       - - - - - - - - - - - > / \     / \
z   T3                            T1   T2   T3  T4

左旋

  x                                y
 /  \                             /   \
T1    y     Left Rotate(x)     x       z
    /  \   - - - - - - - - - - > /  \    /  \
   T2   z                       T1   T2  T3   T4

左-右旋

    z                            x                           z
   / \                         /   \                       /   \
  x   T4   Left Rotate(z)    y      T4  Right Rotate(x)  x       y
 / \      - - - - - - - - - - > / \                        / \     / \
T1   y                        T1   x                      T1   T2   T3  T4
     / \                      /  \ 
    T2   T3                  T2   T3

右-左旋

  x                           z                            x
 / \                         /   \                        /   \
T1   z   Right Rotate(x)   y      T2   Left Rotate(z)  y       z
    / \   - - - - - - - - - > / \                       / \     / \
   y   T3                    T1   x                     T1   T2  T3  T4
  / \                          /  \ 
 T2   T3                      T3   T4

贴个代码

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

// 二叉树节点
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    int height;  // 记录树的高度
} Node;

// 获取节点的高度
int height(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 获取节点的平衡因子
int getBalanceFactor(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    newNode->height = 1;
    return newNode;
}

// 右旋操作
Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* 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;
}

// 左旋操作
Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* 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;
}

// 插入操作
Node* insert(Node* node, int data) {
    // 1. 插入普通的二叉搜索树
    if (node == NULL) {
        return createNode(data);
    }

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

    // 2. 更新当前节点的高度
    node->height = 1 + (height(node->left) > height(node->right) ? height(node->left) : height(node->right));

    // 3. 检查是否需要旋转
    int balance = getBalanceFactor(node);

    // 左左情况（右旋）
    if (balance > 1 && data < node->left->data) {
        return rightRotate(node);
    }

    // 右右情况（左旋）
    if (balance < -1 && data > node->right->data) {
        return leftRotate(node);
    }

    // 左右情况（左旋再右旋）
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // 右左情况（右

哈希表

重点是哈希冲突，简单来讲就是1 % 13 == 14 % 13，两个数具有相同的哈希值

优化：

选择合适的质数：使用质数作为哈希表的大小可以显著减少冲突。如果选择的质数太小，可能会导致哈希表容量不足；如果太大，则可能浪费空间。

变种哈希函数：为了进一步减少冲突，可以使用更多的哈希函数组合，或使用一些其他哈希技术，如乘法散列法、位运算、多项式哈希法等
会除留余数法就好了

有冲突时就去寻找下一个空的哈希地址

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

#define TABLE_SIZE 11  // 选择一个质数作为哈希表大小

// 哈希表结构体
typedef struct HashTable {
    int *table;  // 哈希表
    int size;    // 哈希表大小
} HashTable;

// 创建哈希表
HashTable* createTable(int size) {
    HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));
    hashTable->size = size;
    hashTable->table = (int*)malloc(sizeof(int) * size);
    
    // 初始化哈希表，所有位置设置为 -1，表示空
    for (int i = 0; i < size; i++) {
        hashTable->table[i] = -1;
    }
    
    return hashTable;
}

// 哈希函数：除留余数法
int hash(int key, int size) {
    return key % size;
}

// 插入操作
void insert(HashTable* hashTable, int key) {
    int index = hash(key, hashTable->size);
    
    // 处理冲突，使用开放寻址法（线性探测）
    while (hashTable->table[index] != -1) {
        index = (index + 1) % hashTable->size;  // 线性探测
    }
    
    hashTable->table[index] = key;
}

// 查找操作
int search(HashTable* hashTable, int key) {
    int index = hash(key, hashTable->size);
    
    // 查找元素
    while (hashTable->table[index] != -1) {
        if (hashTable->table[index] == key) {
            return 1;  // 找到元素
        }
        index = (index + 1) % hashTable->size;
    }
    
    return 0;  // 未找到元素
}

// 打印哈希表
void printTable(HashTable* hashTable) {
    for (int i = 0; i < hashTable->size; i++) {
        if (hashTable->table[i] != -1) {
            printf("%d ", hashTable->table[i]);
        } else {
            printf("X ");  // X 表示空位置
        }
    }
    printf("\n");
}

// 测试代码
int main() {
    HashTable* hashTable = createTable(TABLE_SIZE);
    
    // 插入数据
    insert(hashTable, 23);
    insert(hashTable, 45);
    insert(hashTable, 67);
    insert(hashTable, 12);
    
    // 打印哈希表
    printTable(hashTable);
    
    // 查找元素
    printf("Search 45: %d\n", search(hashTable, 45));  // 找到
    printf("Search 100: %d\n", search(hashTable, 100));  // 未找到
    
    return 0;
}

排序

排序的定义不需要介绍了吧
有几个比较简单的直接看代码就好了

插入排序

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, key, j;
    
    // 从第二个元素开始插入排序
    for (i = 1; i < n; i++) {
        key = arr[i];  // 当前要插入的元素
        j = i - 1;
        
        // 将大于 key 的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        
        // 将 key 插入到合适的位置
        arr[j + 1] = key;
    }
}

优化：二分插入排序

#include <stdio.h>

// 二分查找，返回插入位置
int binarySearch(int arr[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        // 找到插入位置
        if (arr[mid] == key) {
            return mid + 1; // 返回插入位置（在相同元素后面插入）
        }
        if (arr[mid] > key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left; // 返回插入位置
}

// 二分插入排序函数
void binaryInsertionSort(int arr[], int n) {
    int i, key, j, insertPos;

    for (i = 1; i < n; i++) {
        key = arr[i];  // 当前要插入的元素
        insertPos = binarySearch(arr, 0, i - 1, key); // 找到插入位置
        
        // 将大于 key 的元素向右移动
        for (j = i - 1; j >= insertPos; j--) {
            arr[j + 1] = arr[j];
        }
        
        // 插入 key 到正确位置
        arr[insertPos] = key;
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: \n");
    printArray(arr, n);
    
    // 调用二分插入排序
    binaryInsertionSort(arr, n);
    
    printf("Sorted array: \n");
    printArray(arr, n);
    
    return 0;
}

不过只是优化了常数，因为本身的交换缺陷，无法更快

交换排序

两两比较，如果发生逆序则交换，直到所有记录都排好序为止

起泡排序(Bubble Sorting)

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    int swapped;
    
    // 外层循环控制遍历次数
    for (i = 0; i < n - 1; i++) {
        swapped = 0;  // 标志位，记录当前遍历是否发生了交换
        
        // 内层循环进行相邻元素比较和交换
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                
                swapped = 1;  // 发生了交换
            }
        }
        
        // 如果这一轮没有交换，说明数组已经有序，可以提前退出
        if (!swapped) {
            break;
        }
    }
}

快速排序

【三分钟学会快速排序-哔哩哔哩】 https://b23.tv/7IwWAC3
还行,很有必要学

// 分区操作，返回基准元素的位置
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最右边的元素作为基准
    int i = low - 1;  // i指向比基准元素小的区域的末尾

    // 遍历数组，找到比基准小的元素
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            // 交换arr[i]和arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 将基准元素交换到正确的位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;  // 返回基准元素的位置
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 获取基准元素的位置
        int pi = partition(arr, low, high);

        // 对基准元素左侧和右侧的子数组递归排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

选择排序

首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第1个记录交换
2.再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第2个记录交换
3.重复上述操作，共进行n-1趟排序后，排序结束

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
    }
}

树形选择排序

基本思想：首先对n个记录的关键字进行两两比较，然后在其中┎ n/2 ┐个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。
实现：这个过程可用一棵有n个叶子结点的完全二叉树表示树表示
建树是nlogn，每次选择是logn，所以总的是nlogn，常数项比较大

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

// 定义一个二叉树节点结构
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 创建一个新的节点
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// 插入数据到二叉树
Node* insert(Node* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }

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

    return root;
}

// 中序遍历输出树的数据（升序排列）
void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// 查找树中的最小节点
Node* findMin(Node* root) {
    while (root && root->left != NULL) {
        root = root->left;
    }
    return root;
}

// 从树中删除最小节点
Node* deleteMin(Node* root) {
    if (root == NULL) return NULL;
    if (root->left == NULL) {
        Node* rightChild = root->right;
        free(root);
        return rightChild;
    }

    root->left = deleteMin(root->left);
    return root;
}

// 树形选择排序
void treeSelectionSort(int arr[], int n) {
    Node* root = NULL;

    // 将所有数组元素插入到树中
    for (int i = 0; i < n; i++) {
        root = insert(root, arr[i]);
    }

    // 从树中提取最小元素并放到数组中
    for (int i = 0; i < n; i++) {
        Node* minNode = findMin(root);
        arr[i] = minNode->data;
        root = deleteMin(root);  // 删除最小元素
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    treeSelectionSort(arr, n);

    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

堆排序

分为大根堆和小根堆，就是字面意思
这里建议看一下课件，描述不如图片直观

#include <stdio.h>

// 交换两个数的值
void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

// 调整堆（最大堆）
void heapify(int arr[], int n, int i) {
    int largest = i;  // 初始化最大元素为当前节点
    int left = 2 * i + 1;  // 左子节点
    int right = 2 * i + 2;  // 右子节点

    // 如果左子节点大于父节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点大于当前最大元素
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大元素不是父节点，则交换并继续调整
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);  // 递归调整
    }
}

// 堆排序主函数
void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 从堆中一个个取出最大元素，并调整堆
    for (int i = n - 1; i > 0; i--) {
        // 交换当前根节点和最后一个元素
        swap(&arr[0], &arr[i]);

        // 调整堆，排除掉已排序的元素
        heapify(arr, i, 0);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    heapSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

归并排序

递归的将两个已经排序的序列合并成一个序列
还是建议看课件

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

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    // 计算子数组的长度
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    int L[n1], R[n2];

    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int i = 0; i < n2; i++)
        R[i] = arr[mid + 1 + i];

    // 合并两个临时数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 如果左子数组还有剩余
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 如果右子数组还有剩余
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // 找到中点
        int mid = left + (right - left) / 2;

        // 递归对左右两部分进行归并排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并两个已排序的部分
        merge(arr, left, mid, right);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

数据结构复习2

串(String)

string类

KMP算法

数组和广义表

树和二叉树

树

二叉树

哈夫曼编码

满二叉树和完全二叉树

树的建立，遍历

线索二叉树

森林与树与二叉树的转换

图

基本概念

实现建图，dfs(深度优先遍历), bfs(广度优先遍历)

图的连通性问题，最小生成树

最短路

单源最短路 dijstra

多源最短路 floyd

拓扑排序

查找

线性表

二叉排序树

哈希表

排序

插入排序

交换排序

起泡排序(Bubble Sorting)

快速排序

选择排序

树形选择排序

堆排序

归并排序

完结撒花，建议配合ppt使用

串(String)

string类

KMP算法

数组和广义表

树和二叉树

树

二叉树

哈夫曼编码

满二叉树 和 完全二叉树

树的建立，遍历

线索二叉树

森林与树与二叉树的转换

图

基本概念

实现建图，dfs(深度优先遍历), bfs(广度优先遍历)

图的连通性问题，最小生成树

最短路

单源最短路 dijstra

多源最短路 floyd

拓扑排序

查找

线性表

二叉排序树

哈希表

排序

插入排序

交换排序

起泡排序(Bubble Sorting)

快速排序

选择排序

树形选择排序

堆排序

归并排序

完结撒花，建议配合ppt使用

满二叉树和完全二叉树