c语言的数据结构

顺序表

顺序表是一种线性表，其元素在内存中连续存放，可以通过数组来实现。

顺序表是一种顺序存储的线性表，其特点如下：

数组下标与元素位置的关系：
- 数组下标从0开始，每个元素的索引与其在数组中的物理位置相对应。
内存地址的计算公式：
- 对于一个长度为n的顺序表A，其中第i个元素（假设类型为ElemType）的内存地址可以通过以下公式计算得出：
  [LOC(A[i]) = LOC(A[0]) + sizeof(ElemType) * i]
  其中：
- (LOC(A[0])) 是第一个元素（即数组下标为0的元素）的内存地址。
- (sizeof(ElemType)) 表示元素类型的字节大小。
- (i) 是当前元素的数组下标。
示例分析：
- 假设有一个整型数组A，其起始地址为1000，且每个整数占用4个字节的空间。
- 则第二个元素（即数组下标为1的元素）的内存地址可以计算为：
  [LOC(A[1]) = 1000 + 4 * 1 = 1004]
  通过上述结构，我们可以方便地访问顺序表中任意位置的元素，只需知道数组的起始地址、元素类型以及目标元素的索引即可。
关于c语言的基础：
1. 传入指针（例如 SeqList *list）
  - 当你传入 SeqList *list 时，表示你传递的是一个指针（也就是 list 的地址）。
  - 传递指针的好处是你可以直接在函数内部修改指针指向的内存中的内容。
  - 举个例子，在 InitList() 函数中，你传入了 SeqList *list，因为你需要修改 list->length 的值，而不是修改一个副本。
  1
  2
  3
  void InitList(SeqList *list) { list->length = 0; // 直接修改指针指向的结构体的成员 }
2. 传入结构体（例如 SeqList list）
  - 如果你传入的是 SeqList list，那么传递的是整个结构体的副本。
  - 在这种情况下，函数内对 list 的任何修改都不会影响到原始的结构体，因为函数只是对 list 进行了值传递，原来的数据并没有被改变。
  - 例如，如果你用下面的方式传递 list：
  1
  2
  3
  void InitList(SeqList list) { list.length = 0; // 只是修改了副本，不会影响到原始的顺序表 }
3. 使用示例对比
假设你有一个顺序表，并希望使用一个函数初始化它：
1
2
SeqList list; InitList(&list); // 传递指针，这样函数可以修改原始 list 的内容
在 InitList() 函数中，传入的是 &list，这是 list 的地址，所以 InitList() 函数接收的是一个指向 SeqList 的指针（SeqList *list）。
- 在函数内部，list 是一个指针，指向了原始的 SeqList 变量。
- 使用 list->length 可以直接修改原始顺序表中的 length 值。
而如果你传递 SeqList list：
1
2
SeqList list; InitList(list); // 传递的是结构体的副本
这样 InitList() 函数接收的是 SeqList list，它只是原始数据的副本，任何修改都不会影响原始的 list。

4. 为什么要传递指针？
传递指针的主要原因有以下几点：
1. 修改原始数据：通过传递指针，你可以在函数内部修改原始数据，而不仅仅是修改副本。
2. 提高效率：传递一个指针比传递整个结构体更加高效，特别是当结构体较大时，传递副本会浪费大量的内存和时间。

代码的实现

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

#define MAX_SIZE 100  // 定义顺序表的最大容量

// 顺序表结构体
typedef struct {
    int data[MAX_SIZE]; // 用于存储元素的数组
    int length;         // 顺序表的当前长度
} SeqList;
// 初始化顺序表
void InitList(SeqList *list) {
    list->length = 0;
}
// 打印顺序表
void PrintList(SeqList list) {
    for (int i = 0; i < list.length; i++) {
        printf("%d ", list.data[i]);
    }
    printf("\n");
}
// 在顺序表中插入元素
int Insert(SeqList *list, int pos, int value) {
    if (pos < 1 || pos > list->length + 1) {
        printf("插入位置不合法\n");
        return 0; // 插入位置不合法
    }
    if (list->length >= MAX_SIZE) {
        printf("顺序表已满，无法插入\n");
        return 0; // 顺序表已满
    }
    // 从最后一个元素开始，向后移动数据
    for (int i = list->length; i >= pos; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[pos - 1] = value; // 插入元素
    list->length++;              // 表长度增加
    return 1;
}
// 删除顺序表中的元素
int Delete(SeqList *list, int pos) {
    if (pos < 1 || pos > list->length) {
        printf("删除位置不合法\n");
        return 0; // 删除位置不合法
    }
    // 从删除位置开始，向前移动数据
    for (int i = pos; i < list->length; i++) {
        list->data[i - 1] = list->data[i];
    }
    list->length--; // 表长度减少
    return 1;
}
// 查找顺序表中的元素
int Find(SeqList list, int value) {
    for (int i = 0; i < list.length; i++) {
        if (list.data[i] == value) {
            return i + 1; // 返回元素的位置（从1开始）
        }
    }
    return -1; // 未找到
}
int main() {
    SeqList list;
    // 初始化顺序表
    InitList(&list);
    // 插入元素
    Insert(&list, 1, 10);
    Insert(&list, 2, 20);
    Insert(&list, 3, 30);
    Insert(&list, 2, 15);
    // 打印顺序表
    printf("顺序表的内容为：");
    PrintList(list);
    // 查找元素
    int pos = Find(list, 20);
    if (pos != -1) {
        printf("元素20的位置是：%d\n", pos);
    } else {
        printf("未找到元素20\n");
    }
    // 删除元素
    Delete(&list, 3);
    // 打印顺序表
    printf("删除元素后的顺序表为：");
    PrintList(list);
    return 0;
}

//这里是运用动态分配写的代码
#include <stdio.h>
#include <stdlib.h>

// 定义顺序表结构体
typedef struct {
    int *data;    // 指向动态分配的数组
    int size;     // 当前顺序表的大小
    int capacity; // 顺序表的容量
} SeqList;
// 初始化顺序表
SeqList* initSeqList(int initialCapacity) {
    SeqList *list = (SeqList *)malloc(sizeof(SeqList));
    list->data = (int *)malloc(initialCapacity * sizeof(int));
    list->size = 0;
    list->capacity = initialCapacity;
    return list;
}
// 扩展顺序表容量
void expandCapacity(SeqList *list) {
    int newCapacity = list->capacity * 2;
    int *newData = (int *)realloc(list->data, newCapacity * sizeof(int));
    if (newData != NULL) {
        list->data = newData;
        list->capacity = newCapacity;
    } else {
        printf("内存分配失败！\n");
        exit(1);
    }
}
// 插入元素到顺序表
void insertElement(SeqList *list, int position, int value) {
    if (position < 0 || position > list->size) {
        printf("插入位置不合法！\n");
        return;
    }
    if (list->size == list->capacity) {
        expandCapacity(list);
    }
    for (int i = list->size; i > position; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[position] = value;
    list->size++;
}
// 删除顺序表中的元素
void deleteElement(SeqList *list, int position) {
    if (position < 0 || position >= list->size) {
        printf("删除位置不合法！\n");
        return;
    }
    for (int i = position; i < list->size - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->size--;
}
// 查找元素在顺序表中的位置
int findElement(SeqList *list, int value) {
    for (int i = 0; i < list->size; i++) {
        if (list->data[i] == value) {
            return i;
        }
    }
    return -1; // 未找到返回-1
}
// 打印顺序表
void printSeqList(SeqList *list) {
    printf("顺序表：");
    for (int i = 0; i < list->size; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}
// 释放顺序表
void destroySeqList(SeqList *list) {
    free(list->data);
    free(list);
}
int main() {
    // 初始化顺序表
    SeqList *list = initSeqList(5);
    // 插入元素
    insertElement(list, 0, 10);
    insertElement(list, 1, 20);
    insertElement(list, 2, 30);
    insertElement(list, 3, 40);
    insertElement(list, 4, 50);
    printSeqList(list);
    // 删除元素
    deleteElement(list, 2);
    printSeqList(list);
    // 查找元素
    int pos = findElement(list, 40);
    if (pos != -1) {
        printf("元素40的位置是：%d\n", pos);
    } else {
        printf("未找到元素40\n");
    }
    // 释放顺序表
    destroySeqList(list);
    return 0;
}

链表

单链表

单链表是一种链式存储的线性表结构。

结构定义：

typedef struct Node {
    int data;           // 数据域，存储节点的数据
    struct Node* next;  // 指针域，指向下一个节点
} LinkList;

其中：

ElemType 是节点的数据类型，可以是任何合法的数据类型。
data 域用于存储节点的实际数据。
next 域是指向下一个节点的指针。
通过这种方式，每个节点都只保存了它后面一个节点的地址，从而形成了一个单向的链接关系。

注意区分：带头节点的链表和不带头节点的链表的区别

带头节点的链表：有一个专门的头节点，这个头节点不存储有效数据，只是作为链表的起始位置，用来简化对链表的插入、删除等操作。
不带头节点的链表：链表的第一个节点就是存储有效数据的节点。

L->| | ->| 1 | -> | 2 |

L->| 1 | -> | 2 |

版本一：

带头节点的链表实现

使用一个额外的头节点，头节点不存储有效数据。
头节点的作用是方便对链表的操作，例如在插入、删除时，不需要判断链表是否为空。

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

typedef struct Node {
    int data;           // 数据域，存储节点的数据
    struct Node* next;  // 指针域，指向下一个节点
} LinkList;
void InitList(LinkList *head) {
    /* 初始化带头结点的链表头指针 */
    head = (LinkList *)malloc(sizeof(LinkList));  // 创建头结点
    head->next = NULL;                            // 头结点的 next 指向 NULL，表示空链表
}
/* 用头插法建立带头结点的单链表 */
LinkList *AddHead() {
    LinkList *head, *p;
    int x;
    head = (LinkList *)malloc(sizeof(LinkList));  // 创建头结点
    head->next = NULL;            // 初始化一个空链表，L为头指针
    printf("请输入节点数据（输入-1结束）：");
    scanf("%d", &x);                   // 输入数据
    while (x != -1) {            // 循环条件：输入值不为 -1
        p = (LinkList *)malloc(sizeof(LinkList)); // 生成新节点
        p->data = x;                   // 赋值给新节点
        p->next = head->next;         // 将新节点插入到头结点之后
        head->next = p;                 // 更新头结点的 next 指针
        scanf("%d", &x);            // 继续输入下一个数据
    }
    return head;                     // 返回头指针
}
/* 尾插法建立带头结点的单链表 */
LinkList *AddTail() {
    LinkList *head, *p, *q;
    int x;
    head = (LinkList *)malloc(sizeof(LinkList));  // 创建头结点
    head->next = NULL;               // 初始化一个空链表，L为头指针
    q = head;                        // 尾指针初始化为头结点
    printf("请输入节点数据（输入-1结束）：");
    scanf("%d", &x);                              // 输入数据
    while (x != -1) {                // 循环条件：输入值不为 -1
        p = (LinkList *)malloc(sizeof(LinkList)); // 生成新节点
        p->data = x;                // 赋值给新节点
        if(head->next == NULL ){
            head->next = p;
        }else{
            q->next = p;
        }
        q = p;                                  // 更新尾指针
        scanf("%d", &x);                    // 继续输入下一个数据
    }
    if(q!=NULL){
        q->next = NULL;
    }
    return head;                                  // 返回头指针
}

void InitList(LinkList *head) {
    head = (LinkList*)malloc(sizeof(LinkList)); // 创建头结点
    head->next = NULL;  // 头结点的next初始化为空
}


// 初始化带头节点的链表
Node* InitList() {
    Node *head = (Node*)malloc(sizeof(Node)); // 创建头节点
    if (head == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    head->next = NULL; // 初始化为空链表
    return head;
}


// 在链表末尾插入新节点
void Insert(Node *head, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;

    Node *p = head; // 从头节点开始
    while (p->next != NULL) {
        p = p->next; // 找到链表的末尾
    }
    p->next = newNode; // 将新节点插入到链表末尾
}

// 在指定节点之前插入新节点（前插法）
void InsertBefore(Node *head, Node *target, int value) {
    if (target == NULL) {
        printf("目标节点为空，无法插入\n");
        return;
    }

    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    Node *p = head;
    while (p->next != NULL && p->next != target) {
        p = p->next;
    }
    if (p->next == target) {
        newNode->next = target;
        p->next = newNode;
    } else {
        printf("未找到目标节点\n");
        free(newNode);
    }
}
// 在指定节点之后插入新节点（后插法）
void InsertAfter(Node *target, int value) {
    if (target == NULL) {
        printf("目标节点为空，无法插入\n");
        return;
    }

    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = target->next;
    target->next = newNode;
}

// 打印链表
void PrintList(Node *head) {
    Node *p = head->next; // 从头节点后的第一个有效节点开始
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

// 按值删除节点
void Delete(Node *head, int value) {
    Node *p = head; // 从头节点开始
    while (p->next != NULL && p->next->data != value) {
        p = p->next;
    }
    if (p->next != NULL) {
        Node *temp = p->next; // 找到要删除的节点
        p->next = temp->next; // 重新连接链表
        free(temp);           // 释放节点内存
    }
}

// 按序号删除节点
void DeleteAt(Node *head, int index) {
    if (index < 0) {
        printf("无效的索引\n");
        return;
    }

    Node *p = head;
    int currentIndex = 0;
    while (p->next != NULL && currentIndex < index) {
        p = p->next;
        currentIndex++;
    }
    if (p->next != NULL) {
        Node *temp = p->next; // 找到要删除的节点
        p->next = temp->next; // 重新连接链表
        free(temp);           // 释放节点内存
    } else {
        printf("索引超出范围\n");
    }
}

// 按值查找节点
Node* FindByValue(Node *head, int value) {
    Node *p = head->next; // 从第一个有效节点开始
    while (p != NULL) {
        if (p->data == value) {
            return p;
        }
        p = p->next;
    }
    return NULL; // 未找到匹配的节点
}

// 按序号查找节点
Node* FindByIndex(Node *head, int index) {
    if (index < 0) {
        return NULL;
    }

    Node *p = head->next;
    int currentIndex = 0;
    while (p != NULL && currentIndex < index) {
        p = p->next;
        currentIndex++;
    }
    return p; // 如果索引超出范围，将返回 NULL
}

// 求链表长度
int GetLength(Node *head) {
    int length = 0;
    Node *p = head->next;
    while (p != NULL) {
        length++;
        p = p->next;
    }
    return length;
}

int main() {
    Node *head = InitList(); // 初始化带头节点的链表

    // 插入一些节点
    Insert(head, 10);
    Insert(head, 20);
    Insert(head, 30);
    Insert(head, 40);

    // 打印链表内容
    printf("链表内容为：");
    PrintList(head);

    // 在值为30的节点之前插入值为25的节点
    InsertBefore(head, head->next->next, 25);
    printf("在值为30的节点之前插入值为25的节点后链表内容为：");
    PrintList(head);

    // 在值为25的节点之后插入值为27的节点
    InsertAfter(head->next->next, 27);
    printf("在值为25的节点之后插入值为27的节点后链表内容为：");
    PrintList(head);

    // 删除值为20的节点
    Delete(head, 20);
    printf("删除值为20的节点后链表内容为：");
    PrintList(head);

    // 按序号删除节点
    DeleteAt(head, 2);
    printf("删除索引为2的节点后链表内容为：");
    PrintList(head);

    // 按值查找节点
    Node *foundNode = FindByValue(head, 30);
    if (foundNode != NULL) {
        printf("找到值为30的节点，地址为：%p\n", foundNode);
    } else {
        printf("未找到值为30的节点\n");
    }

    // 按序号查找节点
    foundNode = FindByIndex(head, 1);
    if (foundNode != NULL) {
        printf("找到索引为1的节点，值为：%d\n", foundNode->data);
    } else {
        printf("未找到索引为1的节点\n");
    }

    // 求链表长度
    int length = GetLength(head);
    printf("链表长度为：%d\n", length);

    // 释放链表内存
    Node *p = head;
    while (p != NULL) {
        Node *temp = p;
        p = p->next;
        free(temp);
    }

不带头节点的链表实现

没有额外的头节点，第一个节点直接存储有效数据。
在对链表进行插入、删除操作时，需要考虑链表为空或者操作的节点为第一个节点的特殊情况。

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

typedef struct Node {
    int data;           // 数据域，存储节点的数据
    struct Node* next;  // 指针域，指向下一个节点
} LinkList;



// 初始化没有头节点的链表
Node* InitList() {
    return NULL; // 初始化为空链表
}

/* 用头插法建立一个不带头结点的单链表 */
LinkList *AddHead() {
    LinkList *head = NULL;        // 初始化为空链表
    LinkList *p;              // 临时指针，用于新节点的创建
    int x;                      // 存放输入数据的临时变量

    printf("请输入节点数据（输入-1结束）：");
    scanf("%d", &x);             // 输入第一个数据

    while (x != -1) {      // 循环条件：输入值不为 -1
        p = (LinkList *)malloc(sizeof(LinkList)); // 生成新节点
        p->data = x;               // 将数据存入新节点
        p->next = head;        // 新节点的 next 指向当前的头指针
        head = p;             // 更新头指针指向新节点
        scanf("%d", &x);           // 继续输入下一个数据
    }
    return head;                                // 返回头指针
}



 /* 尾插法建立一个不带头结点的单链表 */
LinkList *AddTail() {
    LinkList *head = NULL;            // 初始化为空链表
    LinkList *p, *q = NULL;  // p 用于新节点的创建，q 指向链表的尾部
    int x;                     // 存放输入数据的临时变量

    printf("请输入节点数据（输入-1结束）：");
    scanf("%d", &x);              // 输入第一个数据
    while (x != -1) {           // 循环条件：输入值不为 -1
        p = (LinkList *)malloc(sizeof(LinkList)); // 生成新节点
        p->data = x;                         // 将数据存入新节点
        p->next = NULL;   // 新节点的 next 指向 NULL，表示链表末尾
        if (head == NULL) {                    // 如果链表为空
            head = p;                     // 新节点作为第一个节点
        } else {
            q->next = p;             // 尾节点的 next 指向新节点
        }
        q = p;                          // 更新尾指针指向新节点
        scanf("%d", &x);                // 继续输入下一个数据
    }
    return head;                   // 返回头指针
}



// 在链表末尾插入新节点
Node* Insert(Node *head, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        return newNode; // 如果链表为空，新节点作为头节点
    }

    Node *p = head; // 从头节点开始
    while (p->next != NULL) {
        p = p->next; // 找到链表的末尾
    }
    p->next = newNode; // 将新节点插入到链表末尾
    return head;
}

// 在指定节点之前插入新节点（前插法）
Node* InsertBefore(Node *head, Node *target, int value) {
    if (target == NULL) {
        printf("目标节点为空，无法插入\n");
        return head;
    }

    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;

    if (head == target) { // 如果目标节点是头节点
        newNode->next = head;
        return newNode; // 新节点作为新的头节点
    }

    Node *p = head;
    while (p != NULL && p->next != target) {
        p = p->next;
    }
    if (p != NULL) {
        newNode->next = target;
        p->next = newNode;
    } else {
        printf("未找到目标节点\n");
        free(newNode);
    }
    return head;
}


// 在指定节点之后插入新节点（后插法）
void InsertAfter(Node *target, int value) {
    if (target == NULL) {
        printf("目标节点为空，无法插入\n");
        return;
    }

    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = target->next;
    target->next = newNode;
}

// 打印链表
void PrintList(Node *head) {
    Node *p = head; // 从头节点开始
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

// 按值删除节点
Node* Delete(Node *head, int value) {
    if (head == NULL) {
        return head;
    }

    if (head->data == value) { // 如果要删除的是头节点
        Node *temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    Node *p = head;
    while (p->next != NULL && p->next->data != value) {
        p = p->next;
    }
    if (p->next != NULL) {
        Node *temp = p->next; // 找到要删除的节点
        p->next = temp->next; // 重新连接链表
        free(temp);           // 释放节点内存
    }
    return head;
}

// 按序号删除节点
Node* DeleteAt(Node *head, int index) {
    if (index < 0) {
        printf("无效的索引\n");
        return head;
    }

    if (index == 0 && head != NULL) { // 删除头节点
        Node *temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    Node *p = head;
    int currentIndex = 0;
    while (p != NULL && p->next != NULL && currentIndex < index - 1) {
        p = p->next;
        currentIndex++;
    }
    if (p != NULL && p->next != NULL) {
        Node *temp = p->next; // 找到要删除的节点
        p->next = temp->next; // 重新连接链表
        free(temp);           // 释放节点内存
    } else {
        printf("索引超出范围\n");
    }
    return head;
}

// 按值查找节点
Node* FindByValue(Node *head, int value) {
    Node *p = head; // 从头节点开始
    while (p != NULL) {
        if (p->data == value) {
            return p;
        }
        p = p->next;
    }
    return NULL; // 未找到匹配的节点
}

// 按序号查找节点
Node* FindByIndex(Node *head, int index) {
    if (index < 0) {
        return NULL;
    }

    Node *p = head;
    int currentIndex = 0;
    while (p != NULL && currentIndex < index) {
        p = p->next;
        currentIndex++;
    }
    return p; // 如果索引超出范围，将返回 NULL
}

// 求链表长度
int GetLength(Node *head) {
    int length = 0;
    Node *p = head;
    while (p != NULL) {
        length++;
        p = p->next;
    }
    return length;
}

int main() {
    Node *head = InitList(); // 初始化没有头节点的链表
    // 插入一些节点
    head = Insert(head, 10);
    head = Insert(head, 20);
    head = Insert(head, 30);
    head = Insert(head, 40);
    // 打印链表内容
    printf("链表内容为：");
    PrintList(head);
    // 在值为30的节点之前插入值为25的节点
    head = InsertBefore(head, head->next->next, 25);
    printf("在值为30的节点之前插入值为25的节点后链表内容为：");
    PrintList(head);
    // 在值为25的节点之后插入值为27的节点
    InsertAfter(head->next->next, 27);
    printf("在值为25的节点之后插入值为27的节点后链表内容为：");
    PrintList(head);
    // 删除值为20的节点
    head = Delete(head, 20);
    printf("删除值为20的节点后链表内容为：");
    PrintList(head);
    // 按序号删除节点
    head = DeleteAt(head, 2);
    printf("删除索引为2的节点后链表内容为：");
    PrintList(head);
    // 按值查找节点
    Node *foundNode = FindByValue(head, 30);
    if (foundNode != NULL) {
        printf("找到值为30的节点，地址为：%p\n", foundNode);
    } else {
        printf("未找到值为30的节点\n");
    }
    // 按序号查找节点
    foundNode = FindByIndex(head, 1);
    if (foundNode != NULL) {
        printf("找到索引为1的节点，值为：%d\n", foundNode->data);
    } else {
        printf("未找到索引为1的节点\n");
    }
    // 求链表长度
    int length = GetLength(head);
    printf("链表长度为：%d\n", length);
    // 释放链表内存
    Node *p = head;
    while (p != NULL) {
        Node *temp = p;
        p = p->next;
        free(temp);
    }
    return 0;
}

带头节点的链表

初始化时创建一个头节点，头节点不存储有效数据。
插入、删除、遍历等操作都从头节点开始，简化了对第一个节点的特殊判断。
例如在Insert()和Delete()函数中操作时，由于有头节点的存在，所有的节点都可以用统一的方式来处理。

不带头节点的链表

初始化时直接设置为空链表（NULL）。
插入操作时，如果链表为空，新节点成为头节点。
删除操作需要特殊处理第一个节点的情况，以确保头节点正确连接后续节点。

双链表

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

// 定义双向链表节点
typedef struct Node {
    int data;           // 存储数据
    struct Node *next;  // 指向下一个节点的指针
    struct Node *prev;  // 指向前一个节点的指针
} Node;

// 初始化双向链表
Node* InitList() {
    return NULL; // 初始化为空链表
}

// 在链表末尾插入新节点
Node* Insert(Node *head, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    newNode->prev = NULL;

    if (head == NULL) {
        return newNode; // 如果链表为空，新节点作为头节点
    }

    Node *p = head; // 从头节点开始
    while (p->next != NULL) {
        p = p->next; // 找到链表的末尾
    }
    p->next = newNode; // 将新节点插入到链表末尾
    newNode->prev = p;
    return head;
}

// 在指定节点之前插入新节点（前插法）
Node* InsertBefore(Node *head, Node *target, int value) {
    if (target == NULL) {
        printf("目标节点为空，无法插入\n");
        return head;
    }

    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;

    if (head == target) { // 如果目标节点是头节点
        newNode->next = head;
        newNode->prev = NULL;
        head->prev = newNode;
        return newNode; // 新节点作为新的头节点
    }

    Node *p = target->prev;
    newNode->next = target;
    newNode->prev = p;
    if (p != NULL) {
        p->next = newNode;
    }
    target->prev = newNode;
    return head;
}

// 在指定节点之后插入新节点（后插法）
void InsertAfter(Node *target, int value) {
    if (target == NULL) {
        printf("目标节点为空，无法插入\n");
        return;
    }

    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = target->next;
    newNode->prev = target;

    if (target->next != NULL) {
        target->next->prev = newNode;
    }
    target->next = newNode;
}

// 打印链表
void PrintList(Node *head) {
    Node *p = head; // 从头节点开始
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

// 按值删除节点
Node* Delete(Node *head, int value) {
    Node *p = head;
    while (p != NULL && p->data != value) {
        p = p->next;
    }
    if (p == NULL) {
        return head; // 未找到节点
    }

    if (p->prev != NULL) {
        p->prev->next = p->next;
    } else {
        head = p->next; // 如果删除的是头节点
    }

    if (p->next != NULL) {
        p->next->prev = p->prev;
    }

    free(p); // 释放节点内存
    return head;
}

// 按序号删除节点
Node* DeleteAt(Node *head, int index) {
    if (index < 0) {
        printf("无效的索引\n");
        return head;
    }

    Node *p = head;
    int currentIndex = 0;
    while (p != NULL && currentIndex < index) {
        p = p->next;
        currentIndex++;
    }
    if (p == NULL) {
        printf("索引超出范围\n");
        return head;
    }

    if (p->prev != NULL) {
        p->prev->next = p->next;
    } else {
        head = p->next; // 如果删除的是头节点
    }

    if (p->next != NULL) {
        p->next->prev = p->prev;
    }

    free(p); // 释放节点内存
    return head;
}

// 按值查找节点
Node* FindByValue(Node *head, int value) {
    Node *p = head; // 从头节点开始
    while (p != NULL) {
        if (p->data == value) {
            return p;
        }
        p = p->next;
    }
    return NULL; // 未找到匹配的节点
}

// 按序号查找节点
Node* FindByIndex(Node *head, int index) {
    if (index < 0) {
        return NULL;
    }

    Node *p = head;
    int currentIndex = 0;
    while (p != NULL && currentIndex < index) {
        p = p->next;
        currentIndex++;
    }
    return p; // 如果索引超出范围，将返回 NULL
}

// 求链表长度
int GetLength(Node *head) {
    int length = 0;
    Node *p = head;
    while (p != NULL) {
        length++;
        p = p->next;
    }
    return length;
}

int main() {
    Node *head = InitList(); // 初始化双向链表

    // 插入一些节点
    head = Insert(head, 10);
    head = Insert(head, 20);
    head = Insert(head, 30);
    head = Insert(head, 40);

    // 打印链表内容
    printf("链表内容为：");
    PrintList(head);

    // 在值为30的节点之前插入值为25的节点
    head = InsertBefore(head, head->next->next, 25);
    printf("在值为30的节点之前插入值为25的节点后链表内容为：");
    PrintList(head);

    // 在值为25的节点之后插入值为27的节点
    InsertAfter(head->next->next, 27);
    printf("在值为25的节点之后插入值为27的节点后链表内容为：");
    PrintList(head);

    // 删除值为20的节点
    head = Delete(head, 20);
    printf("删除值为20的节点后链表内容为：");
    PrintList(head);

    // 按序号删除节点
    head = DeleteAt(head, 2);
    printf("删除索引为2的节点后链表内容为：");
    PrintList(head);

    // 按值查找节点
    Node *foundNode = FindByValue(head, 30);
    if (foundNode != NULL) {
        printf("找到值为30的节点，地址为：%p\n", foundNode);
    } else {
        printf("未找到值为30的节点\n");
    }

    // 按序号查找节点
    foundNode = FindByIndex(head, 1);
    if (foundNode != NULL) {
        printf("找到索引为1的节点，值为：%d\n", foundNode->data);
    } else {
        printf("未找到索引为1的节点\n");
    }

    // 求链表长度
    int length = GetLength(head);
    printf("链表长度为：%d\n", length);

    // 释放链表内存
    Node *p = head;
    while (p != NULL) {
        Node *temp = p;
        p = p->next;
        free(temp);
    }

    return 0;
}

循环链表

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

// 定义循环链表节点
typedef struct Node {
    int data;           // 存储数据
    struct Node *next;  // 指向下一个节点的指针
    struct Node *prev;  // 指向前一个节点的指针
} Node;

// 初始化循环链表
Node* InitList() {
    return NULL; // 初始化为空链表
}

// 在链表末尾插入新节点
Node* Insert(Node *head, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;

    if (head == NULL) {
        newNode->next = newNode;
        newNode->prev = newNode;
        return newNode; // 如果链表为空，新节点作为头节点
    }

    Node *tail = head->prev; // 获取链表的尾节点
    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = head;
    head->prev = newNode;
    return head;
}

// 在指定节点之前插入新节点（前插法）
Node* InsertBefore(Node *head, Node *target, int value) {
    if (target == NULL) {
        printf("目标节点为空，无法插入\n");
        return head;
    }

    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;

    Node *prevNode = target->prev;
    newNode->next = target;
    newNode->prev = prevNode;
    target->prev = newNode;
    prevNode->next = newNode;

    if (target == head) { // 如果目标节点是头节点
        return newNode; // 新节点作为新的头节点
    }
    return head;
}

// 在指定节点之后插入新节点（后插法）
void InsertAfter(Node *target, int value) {
    if (target == NULL) {
        printf("目标节点为空，无法插入\n");
        return;
    }

    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;

    Node *nextNode = target->next;
    newNode->next = nextNode;
    newNode->prev = target;
    target->next = newNode;
    nextNode->prev = newNode;
}

// 打印链表
void PrintList(Node *head) {
    if (head == NULL) {
        printf("NULL\n");
        return;
    }
    Node *p = head;
    do {
        printf("%d -> ", p->data);
        p = p->next;
    } while (p != head);
    printf("(回到头节点)\n");
}

// 按值删除节点
Node* Delete(Node *head, int value) {
    if (head == NULL) {
        return head;
    }

    Node *p = head;
    do {
        if (p->data == value) {
            if (p->next == p) { // 链表中只有一个节点
                free(p);
                return NULL;
            }
            Node *prevNode = p->prev;
            Node *nextNode = p->next;
            prevNode->next = nextNode;
            nextNode->prev = prevNode;
            if (p == head) {
                head = nextNode; // 如果删除的是头节点，更新头节点
            }
            free(p);
            return head;
        }
        p = p->next;
    } while (p != head);

    return head; // 未找到节点
}

// 按序号删除节点
Node* DeleteAt(Node *head, int index) {
    if (head == NULL || index < 0) {
        printf("无效的索引\n");
        return head;
    }

    Node *p = head;
    int currentIndex = 0;
    do {
        if (currentIndex == index) {
            if (p->next == p) { // 链表中只有一个节点
                free(p);
                return NULL;
            }
            Node *prevNode = p->prev;
            Node *nextNode = p->next;
            prevNode->next = nextNode;
            nextNode->prev = prevNode;
            if (p == head) {
                head = nextNode; // 如果删除的是头节点，更新头节点
            }
            free(p);
            return head;
        }
        p = p->next;
        currentIndex++;
    } while (p != head);

    printf("索引超出范围\n");
    return head;
}

// 按值查找节点
Node* FindByValue(Node *head, int value) {
    if (head == NULL) {
        return NULL;
    }
    Node *p = head;
    do {
        if (p->data == value) {
            return p;
        }
        p = p->next;
    } while (p != head);
    return NULL; // 未找到匹配的节点
}

// 按序号查找节点
Node* FindByIndex(Node *head, int index) {
    if (head == NULL || index < 0) {
        return NULL;
    }

    Node *p = head;
    int currentIndex = 0;
    do {
        if (currentIndex == index) {
            return p;
        }
        p = p->next;
        currentIndex++;
    } while (p != head);
    return NULL; // 如果索引超出范围，将返回 NULL
}

// 求链表长度
int GetLength(Node *head) {
    if (head == NULL) {
        return 0;
    }
    int length = 0;
    Node *p = head;
    do {
        length++;
        p = p->next;
    } while (p != head);
    return length;
}

int main() {
    Node *head = InitList(); // 初始化循环链表

    // 插入一些节点
    head = Insert(head, 10);
    head = Insert(head, 20);
    head = Insert(head, 30);
    head = Insert(head, 40);

    // 打印链表内容
    printf("链表内容为：");
    PrintList(head);

    // 在值为30的节点之前插入值为25的节点
    head = InsertBefore(head, head->next->next, 25);
    printf("在值为30的节点之前插入值为25的节点后链表内容为：");
    PrintList(head);

    // 在值为25的节点之后插入值为27的节点
    InsertAfter(head->next->next, 27);
    printf("在值为25的节点之后插入值为27的节点后链表内容为：");
    PrintList(head);

    // 删除值为20的节点
    head = Delete(head, 20);
    printf("删除值为20的节点后链表内容为：");
    PrintList(head);

    // 按序号删除节点
    head = DeleteAt(head, 2);
    printf("删除索引为2的节点后链表内容为：");
    PrintList(head);

    // 按值查找节点
    Node *foundNode = FindByValue(head, 30);
    if (foundNode != NULL) {
        printf("找到值为30的节点，地址为：%p\n", foundNode);
    } else {
        printf("未找到值为30的节点\n");
    }

    // 按序号查找节点
    foundNode = FindByIndex(head, 1);
    if (foundNode != NULL) {
        printf("找到索引为1的节点，值为：%d\n", foundNode->data);
    } else {
        printf("未找到索引为1的节点\n");
    }

    // 求链表长度
    int length = GetLength(head);
    printf("链表长度为：%d\n", length);

    // 释放链表内存
    if (head != NULL) {
        Node *p = head;
        do {
            Node *temp = p;
            p = p->next;
            free(temp);
        } while (p != head);
    }

    return 0;
}

题目

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

// 定义链表节点结构
typedef struct Node {
    int data;        
    struct Node* next; 
} Node;

// 反转链表
void reverseList(Node **head) {
    Node *prev = NULL;  // 初始时，前一个节点为空
    Node *curr = *head; // 当前节点是链表的头节点
    Node *next = NULL;  // 下一个节点初始化为空

    while (curr != NULL) {
        next = curr->next;    // 保存当前节点的下一个节点
        curr->next = prev;    // 反转当前节点的指针
        prev = curr;          // 将prev指向当前节点
        curr = next;          // 当前节点移动到下一个节点
    }
    *head = prev;  // 最终，prev会指向原链表的最后一个节点，成为新的头节点
}

对给定的单链表L，编写一个删除中值为×的结点的直接前驱结点的算法

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

// 定义链表节点结构
typedef struct Node {
    int data;        // 存储数据
    struct Node* next; // 指向下一个节点的指针
} Node;

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

// 删除中值为x的节点的前驱节点
void deletePredecessor(Node *head, int x) {
    // 链表为空或者只有一个节点，无法进行删除
    if (head == NULL || head->next == NULL) {
        printf("链表为空或只有一个节点，无法删除前驱节点！\n");
        return;
    }

    Node *prev = NULL;  // 前一个节点
    Node *curr = head; // 当前节点

    // 遍历链表，寻找值为x的节点
    while (curr != NULL && curr->next != NULL) {
        if (curr->next->data == x) {
            // 找到前驱节点（curr）和后继节点（curr->next）
            // 删除当前节点的前驱节点
            Node *temp = prev;
            if (temp != NULL) {
                temp->next = curr->next;  // 将前驱节点的next指向curr->next，从而删除前驱节点
                free(curr);  // 释放前驱节点的内存
            }
            return;
        }
        prev = curr;
        curr = curr->next;
    }

    // 如果没有找到值为x的节点
    printf("未找到值为 %d 的节点或该节点没有前驱节点！\n", x);
}

有两个循环单链表，链表头指针分别为 headl 和 head2，
-个函数将链表 headl
链接到链表head2 之后，链接后的链表仍保持是循环链表的形式。

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

typedef struct Node {
    int data;           // 数据域，存储节点的数据
    struct Node* next;  // 指针域，指向下一个节点
} LinkList;

// 初始化带头结点的循环链表
LinkList* InitCircularList() {
    LinkList *head = (LinkList*)malloc(sizeof(LinkList)); // 创建头结点
    head->next = head;  // 初始化为空循环链表
    return head;
}

// 头插法插入节点
void AddHead(LinkList *head, int data) {
    LinkList *newNode = (LinkList*)malloc(sizeof(LinkList)); // 创建新节点
    newNode->data = data;
    newNode->next = head->next; // 新节点的 next 指向头结点之后的第一个节点
    head->next = newNode;       // 头结点的 next 指向新节点
}

// 尾插法插入节点
void AddTail(LinkList *head, int data) {
    LinkList *newNode = (LinkList*)malloc(sizeof(LinkList)); // 创建新节点
    newNode->data = data;
    newNode->next = head;       // 新节点的 next 指向头结点，保持循环

    LinkList *p = head;
    while (p->next != head) {   // 找到尾节点
        p = p->next;
    }
    p->next = newNode;          // 尾节点的 next 指向新节点
}

// 遍历循环链表并打印
void PrintList(LinkList *head) {
    LinkList *p = head->next;   // 从第一个有效节点开始
    while (p != head) {         // 遍历到头结点时停止
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("回到头结点\n");
}

// 合并两个带头结点的循环链表
void ConnectCircularLists(LinkList *head1, LinkList *head2) {
    if (head1 == NULL || head2 == NULL) {
        return; // 如果任何一个链表为空，则不需要连接
    }

    LinkList *p1 = head1;
    LinkList *p2 = head2;

    // 找到 head1 的尾节点（即 next 指向 head1 的节点）
    while (p1->next != head1) {
        p1 = p1->next;
    }

    // 找到 head2 的尾节点（即 next 指向 head2 的节点）
    while (p2->next != head2) {
        p2 = p2->next;
    }

    // 连接两个链表并形成整体循环
    p1->next = head2->next; // head1 的尾节点连接到 head2 的第一个有效节点
    p2->next = head1;       // head2 的尾节点连接到 head1，确保整体循环
}

// 主函数测试代码
int main() {
    // 初始化两个循环链表
    LinkList *head1 = InitCircularList();
    LinkList *head2 = InitCircularList();

    // 插入节点到 head1 链表
    AddTail(head1, 1);
    AddTail(head1, 2);
    AddTail(head1, 3);
    printf("链表 head1:\n");
    PrintList(head1);

    // 插入节点到 head2 链表
    AddTail(head2, 4);
    AddTail(head2, 5);
    AddTail(head2, 6);
    printf("链表 head2:\n");
    PrintList(head2);

    // 合并两个循环链表
    ConnectCircularLists(head1, head2);

    // 打印合并后的链表
    printf("合并后的循环链表:\n");
    PrintList(head1);

    return 0;
}

复制链表

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

typedef struct Node {
    int data;           // 数据域，存储节点的数据
    struct Node* next;  // 指针域，指向下一个节点
} LinkList;

// 初始化带头结点的单向链表
LinkList* InitList() {
    LinkList* head = (LinkList*)malloc(sizeof(LinkList)); // 创建头结点
    head->next = NULL;  // 头结点的 next 初始化为空
    return head;
}

// 尾插法插入节点
void AddTail(LinkList* head, int data) {
    LinkList* newNode = (LinkList*)malloc(sizeof(LinkList)); // 创建新节点
    newNode->data = data;
    newNode->next = NULL;

    LinkList* p = head;
    while (p->next != NULL) { // 找到链表的尾节点
        p = p->next;
    }
    p->next = newNode; // 尾节点的 next 指向新节点
}

// 复制带头结点的单向链表
LinkList* CopyList(LinkList* head) {
    if (head == NULL) return NULL;

    LinkList* newHead = (LinkList*)malloc(sizeof(LinkList)); // 创建新链表的头结点
    newHead->next = NULL;
    LinkList* p = head->next;  // 指向原链表第一个有效节点
    LinkList* q = newHead;     // 指向新链表的尾部，用于追加新节点

    while (p != NULL) {
        LinkList* newNode = (LinkList*)malloc(sizeof(LinkList)); // 创建新节点
        newNode->data = p->data;
        newNode->next = NULL;
        q->next = newNode; // 将新节点添加到新链表
        q = newNode;       // 更新 q 为新节点

        p = p->next;       // 移动到原链表的下一个节点
    }

    return newHead;
}

// 打印链表
void PrintList(LinkList* head) {
    LinkList* p = head->next;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

int main() {
    // 创建原始链表并添加节点
    LinkList* head = InitList();
    AddTail(head, 1);
    AddTail(head, 2);
    AddTail(head, 3);
    printf("原链表: ");
    PrintList(head);

    // 复制链表
    LinkList* copiedHead = CopyList(head);
    printf("复制后的链表: ");
    PrintList(copiedHead);

    return 0;
}

栈

顺序栈的实现

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 栈的最大容量

typedef struct {
    int data[MAX_SIZE]; // 存储栈中元素的数组
    int top;            // 栈顶指针，表示栈顶元素的索引
} Stack;

// 初始化栈
void InitStack(Stack *stack) {
    stack->top = -1; // 初始化时栈顶指针为-1，表示空栈
}

// 判断栈是否为空
int IsEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int IsFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

// 入栈操作
int Push(Stack *stack, int value) {
    if (IsFull(stack)) {
        printf("栈满，无法入栈\n");
        return 0; // 栈满，入栈失败
    }
    stack->data[++stack->top] = value; // 先将栈顶指针加1，再存入元素
    return 1;
}

// 出栈操作
int Pop(Stack *stack) {
    if (IsEmpty(stack)) {
        printf("栈空，无法出栈\n");
        return -1; // 栈空，出栈失败，返回特殊值
    }
    return stack->data[stack->top--]; // 取出栈顶元素，并将栈顶指针减1
}

// 查看栈顶元素
int Peek(Stack *stack) {
    if (IsEmpty(stack)) {
        printf("栈空，无法查看栈顶元素\n");
        return -1; // 栈空，查看失败，返回特殊值
    }
    return stack->data[stack->top]; // 返回栈顶元素
}

int main() {
    Stack stack;
    InitStack(&stack);

    Push(&stack, 10);
    Push(&stack, 20);
    Push(&stack, 30);

    int value = Peek(&stack);
    if (value != -1) {  // 检查返回值是否有效
        printf("栈顶元素为: %d\n", value);
    }

    while (!IsEmpty(&stack)) {
        value = Pop(&stack);
        if (value != -1) {  // 检查返回值是否有效
            printf("出栈元素: %d\n", value);
        }
    }

    return 0;
}

栈的链式结构

top -> 顶 -> … -> 底

栈顶结点：

位于链表的头部，指向下一个元素。
栈底结点：

位于链表的尾部，没有后续元素。
链表表示：

1	`top -> a1 -> a2 -> ... -> an`

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 栈的最大容量

typedef struct {
    int data[MAX_SIZE]; // 存储栈中元素的数组
    int top;            // 栈顶指针，表示栈顶元素的索引
} Stack;

// 初始化栈
void InitStack(Stack *stack) {
    stack->top = -1; // 初始化时栈顶指针为-1，表示空栈
}

// 判断栈是否为空
int IsEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int IsFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

// 入栈操作
int Push(Stack *stack, int value) {
    if (IsFull(stack)) {
        printf("栈满，无法入栈\n");
        return 0; // 栈满，入栈失败
    }
    stack->data[++stack->top] = value; // 先将栈顶指针加1，再存入元素
    return 1;
}

// 出栈操作
int Pop(Stack *stack) {
    if (IsEmpty(stack)) {
        printf("栈空，无法出栈\n");
        return -1; // 栈空，出栈失败，返回特殊值
    }
    return stack->data[stack->top--]; // 取出栈顶元素，并将栈顶指针减1
}

// 查看栈顶元素
int Peek(Stack *stack) {
    if (IsEmpty(stack)) {
        printf("栈空，无法查看栈顶元素\n");
        return -1; // 栈空，查看失败，返回特殊值
    }
    return stack->data[stack->top]; // 返回栈顶元素
}

int main() {
    Stack stack;
    InitStack(&stack);

    Push(&stack, 10);
    Push(&stack, 20);
    Push(&stack, 30);

    int value = Peek(&stack);
    if (value != -1) {  // 检查返回值是否有效
        printf("栈顶元素为: %d\n", value);
    }

    while (!IsEmpty(&stack)) {
        value = Pop(&stack);
        if (value != -1) {  // 检查返回值是否有效
            printf("出栈元素: %d\n", value);
        }
    }

    return 0;
}

队列

队列是一种先进先出（FIFO）的数据结构，元素从队尾入队，从队头出队。它的基本操作包括入队（Enqueue）、出队（Dequeue）、取队头（Peek/Front）和判定队空（IsEmpty）。

队列（Queue）：一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。

基本操作：

入队或进队（Enqueue）：元素从队列尾部进入队列。
出队或离队（Dequeue）：元素从队列头部离开队列。
特性：

先进先出（First-In-First-Out, FIFO）
结构示意图：

1
2
3

a1, a2, a3, a4
↑               ↑
队头(队首)      队尾

允许插入的一端称为队尾，
允许删除的一端称为队首，
队列具有先进先出的特点。
通过以上笔记，可以清晰地理解队列的定义、操作以及其特有的“先进先出”的特性。

好的，以下是关于队列存储结构的数据结构笔记：

队列的顺序存储

定义：

队列是一种先进先出（FIFO）的数据结构。

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 队列的最大容量

// 定义顺序队列结构
typedef struct Queue {
    int data[MAX_SIZE]; // 用数组存储队列元素
    int front;          // 队列头索引
    int rear;           // 队列尾索引
} Queue;

// 初始化队列
Queue* InitQueue() {
    Queue *queue = (Queue*)malloc(sizeof(Queue));
    if (queue == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

// 判断队列是否为空
int IsEmpty(Queue *queue) {
    return queue->front == queue->rear;
}

// 判断队列是否已满
int IsFull(Queue *queue) {
    return queue->rear == MAX_SIZE;
}

// 入队操作
void Enqueue(Queue *queue, int value) {
    if (IsFull(queue)) {
        printf("队列已满，无法插入元素\n");
        return;
    }
    queue->data[queue->rear] = value;
    queue->rear++;
}

// 出队操作
int Dequeue(Queue *queue) {
    if (IsEmpty(queue)) {
        printf("队列为空，无法删除元素\n");
        exit(1);
    }
    int value = queue->data[queue->front];
    queue->front++;
    return value;
}

// 获取队列头部元素
int GetFront(Queue *queue) {
    if (IsEmpty(queue)) {
        printf("队列为空，无法获取元素\n");
        exit(1);
    }
    return queue->data[queue->front];
}

// 打印队列内容
void PrintQueue(Queue *queue) {
    if (IsEmpty(queue)) {
        printf("队列为空\n");
        return;
    }
    for (int i = queue->front; i < queue->rear; i++) {
        printf("%d -> ", queue->data[i]);
    }
    printf("NULL\n");
}

int main() {
    Queue *queue = InitQueue(); // 初始化队列

    // 入队一些元素
    Enqueue(queue, 10);
    Enqueue(queue, 20);
    Enqueue(queue, 30);
    Enqueue(queue, 40);

    // 打印队列内容
    printf("队列内容为：");
    PrintQueue(queue);

    // 出队一个元素
    int dequeuedValue = Dequeue(queue);
    printf("出队的元素为：%d\n", dequeuedValue);
    printf("出队后队列内容为：");
    PrintQueue(queue);

    // 获取队列头部元素
    int frontValue = GetFront(queue);
    printf("队列头部元素为：%d\n", frontValue);

    // 释放队列内存
    free(queue);

    return 0;
}

关键点：

定义结构体 Queue：
- int data[MAX_SIZE]; 用数组存储队列元素，MAX_SIZE 为队列的最大容量。
- int front; 表示队列头部的索引。
- int rear; 表示队列尾部的索引。
初始化队列：
- InitQueue() 初始化队列，front 和 rear 都设为 0，表示队列为空。
判断队列状态：
- IsEmpty(queue) 判断队列是否为空：front == rear 表示队列为空。
- IsFull(queue) 判断队列是否已满：rear == MAX_SIZE 表示队列满。
入队操作（Enqueue）：
- Enqueue(queue, value) 向队列末尾插入新元素，将新值存储在 data[rear]，然后 rear++。
出队操作（Dequeue）：
- Dequeue(queue) 删除队列头部元素，从队列头部移除元素，返回 data[front] 的值，然后 front++。
获取队列头部元素：
- GetFront(queue) 返回队列头部的元素，不改变队列结构。
打印队列内容：
- PrintQueue(queue) 从 front 到 rear 打印队列中的所有元素。

队列的链式存储

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

// 定义链表节点
typedef struct Node {
    int data;           // 存储数据
    struct Node *next;  // 指向下一个节点的指针
} Node;

// 定义链表队列结构
typedef struct Queue {
    Node *front;  // 队列头指针
    Node *rear;   // 队列尾指针
} Queue;

// 初始化队列
Queue* InitQueue() {
    Queue *queue = (Queue*)malloc(sizeof(Queue));
    if (queue == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

// 判断队列是否为空
int IsEmpty(Queue *queue) {
    return queue->front == NULL;
}

// 入队操作
void Enqueue(Queue *queue, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;

    if (IsEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 出队操作
int Dequeue(Queue *queue) {
    if (IsEmpty(queue)) {
        printf("队列为空，无法删除元素\n");
        exit(1);
    }
    Node *temp = queue->front;
    int value = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL; // 如果队列变空，更新尾指针
    }
    free(temp);
    return value;
}

// 获取队列头部元素
int GetFront(Queue *queue) {
    if (IsEmpty(queue)) {
        printf("队列为空，无法获取元素\n");
        exit(1);
    }
    return queue->front->data;
}

// 打印队列内容
void PrintQueue(Queue *queue) {
    if (IsEmpty(queue)) {
        printf("队列为空\n");
        return;
    }
    Node *p = queue->front;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

int main() {
    Queue *queue = InitQueue(); // 初始化队列

    // 入队一些元素
    Enqueue(queue, 10);
    Enqueue(queue, 20);
    Enqueue(queue, 30);
    Enqueue(queue, 40);

    // 打印队列内容
    printf("队列内容为：");
    PrintQueue(queue);

    // 出队一个元素
    int dequeuedValue = Dequeue(queue);
    printf("出队的元素为：%d\n", dequeuedValue);
    printf("出队后队列内容为：");
    PrintQueue(queue);

    // 获取队列头部元素
    int frontValue = GetFront(queue);
    printf("队列头部元素为：%d\n", frontValue);

    // 释放队列内存
    while (!IsEmpty(queue)) {
        Dequeue(queue);
    }
    free(queue);

    return 0;

循环队列

循环队列是队列的一种变形，它使用数组实现，并通过将队尾指针和队头指针进行“环绕”处理，以有效利用数组空间。以下是循环队列的进队和出队操作。把存储队列元素的表从逻辑上视为一个环。

rear 指针总是指向一个空位置，这就是为什么循环队列总会有一个空位置的原因。这个设计目的是为了区分队列为空和队列已满**的状态。

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 队列的最大容量

// 定义循环队列结构
typedef struct Queue {
    int data[MAX_SIZE]; // 用数组存储队列元素
    int front;          // 队列头索引
    int rear;           // 队列尾索引
} Queue;

// 初始化队列
Queue* InitQueue() {
    Queue *queue = (Queue*)malloc(sizeof(Queue));
    if (queue == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

// 判断队列是否为空
int IsEmpty(Queue *queue) {
    return queue->front == queue->rear;
}

// 判断队列是否已满
int IsFull(Queue *queue) {
    return (queue->rear + 1) % MAX_SIZE == queue->front;
}

// 入队操作
void Enqueue(Queue *queue, int value) {
    if (IsFull(queue)) {
        printf("队列已满，无法插入元素\n");
        return;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_SIZE;
}

// 出队操作
int Dequeue(Queue *queue) {
    if (IsEmpty(queue)) {
        printf("队列为空，无法删除元素\n");
        exit(1);
    }
    int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_SIZE;
    return value;
}

// 获取队列头部元素
int GetFront(Queue *queue) {
    if (IsEmpty(queue)) {
        printf("队列为空，无法获取元素\n");
        exit(1);
    }
    return queue->data[queue->front];
}

// 打印队列内容
void PrintQueue(Queue *queue) {
    if (IsEmpty(queue)) {
        printf("队列为空\n");
        return;
    }
    int i = queue->front;
    while (i != queue->rear) {
        printf("%d -> ", queue->data[i]);
        i = (i + 1) % MAX_SIZE;
    }
    printf("NULL\n");
}

int main() {
    Queue *queue = InitQueue(); // 初始化队列

    // 入队一些元素
    Enqueue(queue, 10);
    Enqueue(queue, 20);
    Enqueue(queue, 30);
    Enqueue(queue, 40);

    // 打印队列内容
    printf("队列内容为：");
    PrintQueue(queue);

    // 出队一个元素
    int dequeuedValue = Dequeue(queue);
    printf("出队的元素为：%d\n", dequeuedValue);
    printf("出队后队列内容为：");
    PrintQueue(queue);

    // 获取队列头部元素
    int frontValue = GetFront(queue);
    printf("队列头部元素为：%d\n", frontValue);

    // 释放队列内存
    free(queue);

    return 0;
}

循环队列中的关键公式与要点总结

初始状态

[ Q_front = Q_rear = 0 ]

队首指针 Q_front 和队尾指针 Q_rear 都初始化为 0，表示队列为空。

队首指针进 1（出队操作）

[ Q_front = (Q_front + 1) % MaxSize ]

当有元素出队时，队首指针 Q_front 向前移动一位，使用取模操作 % MaxSize 确保它可以循环到数组的开头。

队尾指针进 1（入队操作）

[ Q_rear = (Q_rear + 1) % MaxSize ]

当有新元素入队时，队尾指针 Q_rear 向前移动一位，取模操作 % MaxSize 确保它可以循环到数组的开头。

队列长度计算公式

[ \text{元素个数} = (Q_rear + MaxSize - Q_front) % MaxSize ]

该公式用于计算当前队列中的元素个数。
(Q_rear + MaxSize - Q_front) 用于计算 rear 和 front 之间的距离，无论它们的位置关系如何。
取模操作 % MaxSize 确保结果在合法范围内。

队列状态判断

队列为空：当 Q_front == Q_rear 时，表示队列为空。
队列已满：当 (Q_rear + 1) % MaxSize == Q_front 时，表示队列已满（保留了一个空位置用于区分空和满的状态）。

题目

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

#define MAX_SIZE 100 // 栈的最大容量

typedef struct {
    char data[MAX_SIZE]; // 存储栈中元素的数组
    int top;             // 栈顶指针
} Stack;

// 初始化栈
void InitStack(Stack *stack) {
    stack->top = -1; // 初始化为空栈
}

// 判断栈是否为空
int IsEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int IsFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

// 入栈操作
int Push(Stack *stack, char value) {
    if (IsFull(stack)) {
        return 0; // 栈满，入栈失败
    }
    stack->data[++stack->top] = value; // 先将栈顶指针加1，再存入元素
    return 1;
}

// 出栈操作
char Pop(Stack *stack) {
    if (IsEmpty(stack)) {
        return '\0'; // 栈空，返回特殊字符
    }
    return stack->data[stack->top--]; // 取出栈顶元素，并将栈顶指针减1
}

// 查看栈顶元素
char Peek(Stack *stack) {
    if (IsEmpty(stack)) {
        return '\0'; // 栈空，返回特殊字符
    }
    return stack->data[stack->top];
}

// 检查括号是否匹配
int IsMatchingPair(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '{' && right == '}') ||
           (left == '[' && right == ']');
}

// 判断括号字符串是否匹配
int AreParenthesesBalanced(const char *expr) {
    Stack stack;
    InitStack(&stack);

    for (int i = 0; i < strlen(expr); i++) {
        char ch = expr[i];

        // 如果是左括号，入栈
        if (ch == '(' || ch == '{' || ch == '[') {
            Push(&stack, ch);
        }
        // 如果是右括号，检查栈顶元素是否匹配
        else if (ch == ')' || ch == '}' || ch == ']') {
            if (IsEmpty(&stack) || !IsMatchingPair(Pop(&stack), ch)) {
                return 0; // 不匹配
            }
        }
    }

    // 最后检查栈是否为空
    return IsEmpty(&stack);
}

int main() {
    const char *expr = "{[()]}";

    if (AreParenthesesBalanced(expr)) {
        printf("括号匹配成功\n");
    } else {
        printf("括号不匹配\n");
    }

    return 0;
}

生成杨辉三角

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

#define MAX_SIZE 100 // 队列的最大容量，用于存储杨辉三角的元素

typedef struct {
    int data[MAX_SIZE]; // 队列数组
    int front;          // 队头指针
    int rear;           // 队尾指针
} Queue;

// 初始化队列
void InitQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

// 判断队列是否为空
int IsEmpty(Queue *q) {
    return q->front == q->rear;
}

// 判断队列是否已满
int IsFull(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// 入队操作
int Enqueue(Queue *q, int value) {
    if (IsFull(q)) {
        return 0; // 队列已满，入队失败
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return 1;
}

// 出队操作
int Dequeue(Queue *q, int *value) {
    if (IsEmpty(q)) {
        return 0; // 队列为空，出队失败
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return 1;
}

// 生成并打印杨辉三角
void PrintYangHuiTriangle(int rows) {
    Queue q;
    InitQueue(&q);

    Enqueue(&q, 1); // 初始化第一行

    for (int i = 1; i <= rows; i++) {
        int prev = 0, current;

        // 打印并生成当前行
        for (int j = 0; j < i; j++) {
            Dequeue(&q, &current); // 取出当前元素
            printf("%d ", current);
            Enqueue(&q, prev + current); // 将前一个元素和当前元素之和入队
            prev = current; // 更新 prev 为当前元素
        }
        Enqueue(&q, 1); // 每行末尾加入 1
        printf("\n");
    }
}

int main() {
    int rows;

    printf("请输入杨辉三角的行数: ");
    scanf("%d", &rows);

    PrintYangHuiTriangle(rows);

    return 0;
}

设有两个栈 sl、s2都采用顺序栈方式，并且共享一个存储区[0.MAXSIZE-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式，试设计入栈、出栈的算法。

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

#define MAXSIZE 100 // 共享存储区的最大容量

typedef struct {
    int data[MAXSIZE]; // 存储区
    int top1;          // 栈s1的栈顶指针
    int top2;          // 栈s2的栈顶指针
} SharedStack;

// 初始化共享栈
void InitStack(SharedStack *stack) {
    stack->top1 = -1;        // s1的栈顶指针初始化为-1
    stack->top2 = MAXSIZE;   // s2的栈顶指针初始化为MAXSIZE
}

// 入栈操作，flag=1表示s1，flag=2表示s2
int Push(SharedStack *stack, int value, int flag) {
    if (stack->top1 + 1 == stack->top2) { // 判断是否栈满
        printf("栈满，无法入栈\n");
        return 0;
    }
    if (flag == 1) { // s1入栈
        stack->data[++stack->top1] = value;
    } else if (flag == 2) { // s2入栈
        stack->data[--stack->top2] = value;
    } else {
        printf("无效的栈标识\n");
        return 0;
    }
    return 1;
}

// 出栈操作，flag=1表示s1，flag=2表示s2
int Pop(SharedStack *stack, int *value, int flag) {
    if (flag == 1) { // s1出栈
        if (stack->top1 == -1) { // 判断s1是否为空
            printf("栈s1空，无法出栈\n");
            return 0;
        }
        *value = stack->data[stack->top1--];
    } else if (flag == 2) { // s2出栈
        if (stack->top2 == MAXSIZE) { // 判断s2是否为空
            printf("栈s2空，无法出栈\n");
            return 0;
        }
        *value = stack->data[stack->top2++];
    } else {
        printf("无效的栈标识\n");
        return 0;
    }
    return 1;
}

int main() {
    SharedStack stack;
    InitStack(&stack);

    // 测试s1的入栈
    Push(&stack, 10, 1);
    Push(&stack, 20, 1);
    Push(&stack, 30, 1);

    // 测试s2的入栈
    Push(&stack, 100, 2);
    Push(&stack, 200, 2);
    Push(&stack, 300, 2);

    // 测试s1的出栈
    int value;
    printf("栈s1出栈元素: ");
    while (Pop(&stack, &value, 1)) {
        printf("%d ", value);
    }
    printf("\n");

    // 测试s2的出栈
    printf("栈s2出栈元素: ");
    while (Pop(&stack, &value, 2)) {
        printf("%d ", value);
    }
    printf("\n");

    return 0;
}

假设用一个循环单链表来表示循环队列，该队列只设一个队尾指针，不设队头指针编写如下函数:
(1)向循环链队中插入一个元素为x的结点。
(2)从循环链队中删除一个结点。

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

// 定义节点结构
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 定义循环链队列，仅包含队尾指针
typedef struct {
    Node *rear;  // 队尾指针
} CircularQueue;

// 初始化循环队列
void InitQueue(CircularQueue *queue) {
    queue->rear = NULL;  // 队尾指针初始化为空
}

// 插入元素x（入队）或删除元素（出队）
int QueueOperation(CircularQueue *queue, int *value, int isEnqueue) {
    if (isEnqueue) {  // 入队操作
        Node *newNode = (Node *)malloc(sizeof(Node));
        if (!newNode) {
            printf("内存分配失败\n");
            exit(1);
        }
        newNode->data = *value;

        if (!queue->rear) {  // 队列为空
            newNode->next = newNode;  // 自环
            queue->rear = newNode;    // 队尾指向新节点
        } else {  // 队列不为空
            newNode->next = queue->rear->next;  // 新节点的next指向队头
            queue->rear->next = newNode;        // 队尾的next指向新节点
            queue->rear = newNode;              // 更新队尾指针
        }
        return 1;  // 入队成功
    } else {  // 出队操作
        if (!queue->rear) {  // 队列为空
            printf("队列为空，无法出队\n");
            return 0;
        }
        
        Node *temp = queue->rear->next;  // 队头节点
        *value = temp->data;             // 获取队头元素
        
        if (queue->rear == temp) {  // 队列仅有一个节点
            queue->rear = NULL;
        } else {  // 队列有多个节点
            queue->rear->next = temp->next;  // 队尾的next指向新的队头
        }
        free(temp);  // 释放旧的队头节点
        return 1;    // 出队成功
    }
}

int main() {
    CircularQueue queue;
    InitQueue(&queue);

    // 入队操作
    int value = 10;
    QueueOperation(&queue, &value, 1);
    value = 20;
    QueueOperation(&queue, &value, 1);
    value = 30;
    QueueOperation(&queue, &value, 1);

    // 出队操作
    if (QueueOperation(&queue, &value, 0)) {
        printf("出队元素: %d\n", value);
    }
    if (QueueOperation(&queue, &value, 0)) {
        printf("出队元素: %d\n", value);
    }
    if (QueueOperation(&queue, &value, 0)) {
        printf("出队元素: %d\n", value);
    }
    if (QueueOperation(&queue, &value, 0)) {
        printf("队列为空，无法出队\n");
    }

    return 0;
}

假设将循环队列定义为:以域变量rear 和 length 分别表示循环队列中队尾元素的位和内含元素的个数。试给出循环队列的队满条件，并写出相应的入队和出队的算法。

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

#define MAXSIZE 100 // 队列的最大容量

typedef struct {
    int data[MAXSIZE];  // 存储队列元素的数组
    int rear;           // 队尾指针
    int length;         // 队列中元素的个数
} CircularQueue;

// 初始化循环队列
void InitQueue(CircularQueue *queue) {
    queue->rear = -1;      // 初始时，队尾指针为 -1 表示空队列
    queue->length = 0;     // 初始时，队列中没有元素
}

// 队列操作：入队（isEnqueue为1）和出队（isEnqueue为0）
int QueueOperation(CircularQueue *queue, int *value, int isEnqueue) {
    if (isEnqueue) { // 入队操作
        if (queue->length == MAXSIZE) { // 队满条件
            printf("队列已满，无法入队\n");
            return 0;
        }
        queue->rear = (queue->rear + 1) % MAXSIZE; // 更新队尾位置
        queue->data[queue->rear] = *value;         // 在队尾插入新元素
        queue->length++;                           // 增加队列长度
        return 1;
    } else { // 出队操作
        if (queue->length == 0) { // 队空条件
            printf("队列为空，无法出队\n");
            return 0;
        }
        int front = (queue->rear - queue->length + 1 + MAXSIZE) % MAXSIZE; // 计算队头位置
        *value = queue->data[front];   // 获取队头元素
        queue->length--;               // 减少队列长度
        return 1;
    }
}

int main() {
    CircularQueue queue;
    InitQueue(&queue);

    // 入队操作
    int value = 10;
    QueueOperation(&queue, &value, 1);
    value = 20;
    QueueOperation(&queue, &value, 1);
    value = 30;
    QueueOperation(&queue, &value, 1);

    // 出队操作
    if (QueueOperation(&queue, &value, 0)) {
        printf("出队元素: %d\n", value);
    }
    if (QueueOperation(&queue, &value, 0)) {
        printf("出队元素: %d\n", value);
    }
    if (QueueOperation(&queue, &value, 0)) {
        printf("出队元素: %d\n", value);
    }
    if (!QueueOperation(&queue, &value, 0)) {
        printf("队列为空，无法出队\n");
    }

    return 0;
}

字符串

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

#define MAXSIZE 100 // 顺序串的最大容量

typedef struct {
    char data[MAXSIZE]; // 存储空间
    int length;         // 实际长度
} SString;

// 初始化顺序串
void InitString(SString *str) {
    str->length = 0;
    str->data[0] = '\0';
}

// 求子串操作，获取 str 中从 pos 开始长度为 len 的子串，结果保存在 substr 中
int SubString(SString *str, SString *substr, int pos, int len) {
    if (pos < 0 || pos >= str->length || len < 0 || pos + len > str->length) {
        printf("位置或长度不合法\n");
        return 0;
    }
    for (int i = 0; i < len; i++) {
        substr->data[i] = str->data[pos + i];
    }
    substr->data[len] = '\0';
    substr->length = len;
    return 1;
}

// 插入子串操作，将 substr 插入到 str 的 pos 位置
int InsertString(SString *str, int pos, SString *substr) {
    if (pos < 0 || pos > str->length || str->length + substr->length > MAXSIZE) {
        printf("插入位置或长度不合法\n");
        return 0;
    }
    // 将原串从插入点向后移动
    for (int i = str->length - 1; i >= pos; i--) {
        str->data[i + substr->length] = str->data[i];
    }
    // 插入子串
    for (int i = 0; i < substr->length; i++) {
        str->data[pos + i] = substr->data[i];
    }
    str->length += substr->length;
    str->data[str->length] = '\0';
    return 1;
}

// 删除子串操作，从 str 的 pos 位置开始删除 len 长度的字符
int DeleteString(SString *str, int pos, int len) {
    if (pos < 0 || pos >= str->length || len < 0 || pos + len > str->length) {
        printf("删除位置或长度不合法\n");
        return 0;
    }
    // 将后续的字符前移
    for (int i = pos + len; i < str->length; i++) {
        str->data[i - len] = str->data[i];
    }
    str->length -= len;
    str->data[str->length] = '\0';
    return 1;
}

// 串连接操作，将 str1 和 str2 连接成 result
int ConcatString(SString *result, SString *str1, SString *str2) {
    if (str1->length + str2->length > MAXSIZE) {
        printf("连接后的字符串过长，无法连接\n");
        return 0;
    }
    strcpy(result->data, str1->data);
    strcat(result->data, str2->data);
    result->length = str1->length + str2->length;
    return 1;
}

// 模式匹配操作，在主串 str 中查找模式串 pattern 的位置，返回首次匹配位置
int IndexOf(SString *str, SString *pattern) {
    for (int i = 0; i <= str->length - pattern->length; i++) {
        int j = 0;
        while (j < pattern->length && str->data[i + j] == pattern->data[j]) {
            j++;
        }
        if (j == pattern->length) {
            return i; // 找到匹配位置
        }
    }
    return -1; // 未找到匹配
}

数组

数组是具有相同类型元素的集合，元素在内存中按顺序存储。根据数组维度的不同，数组可以分为一维数组、二维数组和三维数组。

一维数组

一维数组是一组具有相同类型的变量。数组中的每个元素都有一个索引，索引从0开始。

1	`int arr[5] = {1, 2, 3, 4, 5};`

可以通过索引访问和修改数组中的元素：

1	`arr[2] = 10; // 修改第三个元素的值为10`

二维数组

行优先存储

Loc(i,j)=Loc(r,c)+(i−r)×n×xs+(j−c)×xs

列优先存储方式

Loc(i,j)=Loc(r,c)+(j−c)×m×xs+(i−r)×xs

Loc(i, j)：表示二维数组中元素 A[i][j] 的内存地址。

Loc(r, c)：表示数组的基地址，也就是 A[r][c] 的内存地址。通常情况下，r 和 c 可以取值为 0，即 Loc(0, 0) 为基地址。

j - c：表示 j 列相对于基准列 c 的偏移列数。

m：数组的行数（每列的元素数）。

xs：每个元素占据的存储单元大小（例如 int 类型通常为 4 字节）。

i - r：表示 i 行相对于基准行 r 的偏移行数。

例子

设二维数组a[1..60] [2.70]的基地址为2048，每个元素占2个存储单元，若以行优先顺序存储，元素a[32] [58]的地址是

已知条件

基地址：2048
数组维度

：
1
a[1..60][2..70]
- 行数：60
- 列数：69（从列 2 到列 70，共 69 列）
元素大小：每个元素占 2 个存储单元（即 2 字节）
目标元素：a[32][58]
存储方式：行优先存储

行优先存储寻址公式

在行优先存储中，二维数组的寻址公式为：

Loc(i,j)=Loc(r,c)+(i−r)×n×xs+(j−c)×xs

其中：

base_address = 2048
i = 32（目标行索引）
j = 58（目标列索引）
r = 1（起始行索引）
c = 2（起始列索引）
n = 69（每行的列数）
xs = 2（每个元素的大小）

二维数组可以看作是数组的数组，通常用于表示矩阵或表格数据。声明一个二维数组的方法如下：

int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

访问二维数组元素：

1	`int value = matrix[1][2]; // 获取第二行第三列的元素`

矩阵转置

    SimpleTranspose(matrix, transpose, 3, 3);
    printf("Transposed Matrix:\n");
    PrintMatrix(transpose, 3, 3);

    return 0;
}

三元组表示的稀疏矩阵转置

这种方法适用于稀疏矩阵，使用三元组表示法，仅存储非零元素的位置和值。

c复制代码#include <stdio.h>

#define MAXSIZE 100

typedef struct {
    int row;
    int col;
    int value;
} Triple;

typedef struct {
    Triple data[MAXSIZE];
    int rows;
    int cols;
    int len;
} TSMatrix;

void FastTranspose(TSMatrix *A, TSMatrix *B) {
    B->rows = A->cols;
    B->cols = A->rows;
    B->len = A->len;

    int num[A->cols], position[A->cols];

    // Step 1: Initialize num array to count each column's non-zero elements
    for (int i = 0; i < A->cols; i++) num[i] = 0;

    for (int i = 0; i < A->len; i++) num[A->data[i].col]++;

    // Step 2: Calculate the starting position of each column in B
    position[0] = 0;
    for (int i = 1; i < A->cols; i++) {
        position[i] = position[i - 1] + num[i - 1];
    }

    // Step 3: Place each element of A in the correct position in B
    for (int i = 0; i < A->len; i++) {
        int col = A->data[i].col;
        int pos = position[col]++;
        B->data[pos].row = A->data[i].col;
        B->data[pos].col = A->data[i].row;
        B->data[pos].value = A->data[i].value;
    }
}

void PrintTSMatrix(TSMatrix *M) {
    printf("row\tcol\tvalue\n");
    for (int i = 0; i < M->len; i++) {
        printf("%d\t%d\t%d\n", M->data[i].row, M->data[i].col, M->data[i].value);
    }
}

int main() {
    TSMatrix A = {{{0, 0, 3}, {0, 2, 5}, {1, 1, 7}, {2, 0, 6}}, 3, 3, 4};
    TSMatrix B;

    FastTranspose(&A, &B);
    printf("Transposed Sparse Matrix in Triple Form:\n");
    PrintTSMatrix(&B);

    return 0;
}

快速转置算法（适用于稀疏矩阵的快速转置）

使用快速转置算法，通过辅助数组 num 和 position 来加速转置过程。

c复制代码#include <stdio.h>

#define MAXSIZE 100

typedef struct {
    int row;
    int col;
    int value;
} Triple;

typedef struct {
    Triple data[MAXSIZE];
    int rows;
    int cols;
    int len;
} TSMatrix;

void FastTranspose(TSMatrix *A, TSMatrix *B) {
    B->rows = A->cols;
    B->cols = A->rows;
    B->len = A->len;

    int num[A->cols], position[A->cols];

    // Step 1: Initialize num array to count each column's non-zero elements
    for (int i = 0; i < A->cols; i++) num[i] = 0;

    for (int i = 0; i < A->len; i++) num[A->data[i].col]++;

    // Step 2: Calculate the starting position of each column in B
    position[0] = 0;
    for (int i = 1; i < A->cols; i++) {
        position[i] = position[i - 1] + num[i - 1];
    }

    // Step 3: Place each element of A in the correct position in B
    for (int i = 0; i < A->len; i++) {
        int col = A->data[i].col;
        int pos = position[col]++;
        B->data[pos].row = A->data[i].col;
        B->data[pos].col = A->data[i].row;
        B->data[pos].value = A->data[i].value;
    }
}

void PrintTSMatrix(TSMatrix *M) {
    printf("row\tcol\tvalue\n");
    for (int i = 0; i < M->len; i++) {
        printf("%d\t%d\t%d\n", M->data[i].row, M->data[i].col, M->data[i].value);
    }
}

int main() {
    TSMatrix A = {{{0, 0, 3}, {0, 2, 5}, {1, 1, 7}, {2, 0, 6}}, 3, 3, 4};
    TSMatrix B;

    FastTranspose(&A, &B);
    printf("Transposed Sparse Matrix in Triple Form:\n");
    PrintTSMatrix(&B);

    return 0;
}

十字链表法—适用于稀疏矩阵

typedef struct OLNode /*十字链表结点类型定义*/
{
    int row, col; /*非零元素的行和列下标*/
    DataType value; /*非零元素所在行表、列表的后继链表*/
    struct OLNode *right, *down;
} OLink;
typedef struct
{
    OLink *row_head, *col_head; /*行、列链表的头指针向量*/
    int m, n, len; /*稀疏矩阵的行数、列数、非零元素个数*/
} CrossList;
int CreateCrossList(CrossList *M)
{
    int i, j;
    OLink p, q;
    /*用十字链表存储结构，创建稀疏矩阵 M*/
    if(M != NULL) free(M);
    scanf("%d%d%d", &m, &n, &len); /*输入 M 的行数，列数和非零元素个数*/
    M->m = m; M->n = n; M->len = len;
    if ((M->row_head = (OLink*)malloc(m * sizeof(OLink))) == NULL) exit(OVERFLOW);
    if ((M->col_head = (OLink*)malloc(n * sizeof(OLink))) == NULL) exit(OVERFLOW);
    M->row_head = M->col_head = NULL; /*初始化行、列头指针向量，各行、列链表为空的链表*/
    for (scanf("%d%d%d", &i, &j, &e); i != 0; scanf("%d%d%d", &i, &j, &e))
    {
        if ((p = (OLink*)malloc(sizeof(OLink))) == NULL) exit(OVERFLOW);
        p->row = i; p->col = j; p->value = e; /*生成结点*/
        if (M->row_head == NULL)
            M->row_head = p;
        else
        {
            for (q = M->row_head; q->right && q->right->col < j; q = q->right);
            p->right = q->right; q->right = p; /*寻找行表中的插入位置*/
        }
        if (M->col_head == NULL)
            M->col_head = p;
        else
        {
            for (q = M->col_head; q->down && q->down->row < i; q = q->down);
            p->down = q->down; q->down = p; /*寻找列表中的插入位置*/
        }
    }
}

三维数组

三维数组是数组的进一步扩展，通常用于表示多维空间中的数据。

int array3D[2][3][4] = {
    {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    },
    {
        {13, 14, 15, 16},
        {17, 18, 19, 20},
        {21, 22, 23, 24}
    }
};

访问三维数组元素：

1	`int value = array3D[1][2][3]; // 获取第二个2D数组的第三行第四列的元素`

矩阵的压缩存储

矩阵压缩存储用于节省空间，特别是在矩阵具有某种特殊结构时，例如对称矩阵、三角矩阵和稀疏矩阵。

对称矩阵

对称矩阵是指矩阵的元素满足 A[i][j] == A[j][i]。对于对称矩阵，只需要存储矩阵的上三角或下三角部分即可。

假设存储上三角部分：

int n = 3; // 矩阵的维度
int symmetricMatrix[(n * (n + 1)) / 2]; // 存储上三角部分的数组

// 计算索引
int index = (i * (i + 1)) / 2 + j;
symmetricMatrix[index] = value;

访问元素时：

int getSymmetricMatrixValue(int* mat, int i, int j) {
    if (i <= j) {
        return mat[(i * (i + 1)) / 2 + j];
    } else {
        return mat[(j * (j + 1)) / 2 + i];
    }
}

三角矩阵

上三角矩阵：只存储非零的上三角部分。

1	`int upperTriangular[(n * (n + 1)) / 2];`

存储上三角矩阵的元素：

1
2
3

if (i <= j) {
    upperTriangular[(i * n) - (i * (i - 1)) / 2 + (j - i)] = value;
}

下三角矩阵：只存储非零的下三角部分。

1	`int lowerTriangular[(n * (n + 1)) / 2];`

存储下三角矩阵的元素：

1
2
3

if (i >= j) {
    lowerTriangular[(i * (i + 1)) / 2 + j] = value;
}

稀疏矩阵压缩存储

稀疏矩阵是指大部分元素为零的矩阵。稀疏矩阵可以通过三元组（行、列、值）来压缩存储。常见的存储方法包括COO（Coordinate List）、CSR（Compressed Sparse Row）和CSC（Compressed Sparse Column）。

COO（Coordinate List）：使用三个数组分别存储非零元素的行索引、列索引和对应的值。

1
2
3

int row[] = {0, 0, 1, 2};
int col[] = {0, 2, 2, 3};
int val[] = {10, 20, 30, 40};

CSR（Compressed Sparse Row）：使用三个数组存储稀疏矩阵，分别是 values（非零元素的值），col_index（非零元素所在的列索引）和 row_pointer（每行开始的位置）。

1
2
3

int values[] = {10, 20, 30, 40};
int col_index[] = {0, 2, 2, 3};
int row_pointer[] = {0, 2, 3, 4};

CSC（Compressed Sparse Column）：与CSR类似，使用三个数组存储稀疏矩阵，只不过是按列进行存储。

1
2
3

int values[] = {10, 30, 20, 40};
int row_index[] = {0, 1, 0, 2};
int col_pointer[] = {0, 2, 3, 4};

这些压缩存储方法通过只存储非零元素和它们的位置，大大减少了稀疏矩阵所需的存储空间。

树

树的存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法

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

双亲表示法—-适合查找节点的父节点，但是在查找孩子节点时效率较低

typedef struct {
    ElementType data; // 数据域，存储节点的值
    int parent;       // 存储父节点的索引（若是根节点，父节点设为-1）
} PTNode;

typedef struct {
    PTNode nodes[MAX_SIZE]; // 存储节点的数组
    int n;                  // 树中节点的数量
} PTree;

在双亲表示法中，每个节点记录自己的父节点索引：

索引	数据	父节点索引
0	A	-1
1	B	0
2	C	0
3	D	0
4	E	1
5	F	1
6	G	3

在这个例子中，“A”节点是根节点，因此它的父节点索引为 -1。每个节点的父节点索引指向它在数组中的位置。

孩子表示法—-适合查找节点的孩子，尤其是树的度较大时

typedef struct ChildNode {
    int child;                // 指向孩子节点的索引
    struct ChildNode *next;   // 指向下一个孩子节点
} ChildNode;

typedef struct {
    ElementType data;        // 数据域，存储节点的值
    ChildNode *firstChild;   // 孩子链表的头指针
} CTNode;

typedef struct {
    CTNode nodes[MAX_SIZE]; // 节点数组
    int n;                  // 树中节点的数量
} CTree;

A → 孩子链表 → B → C → D

B → 孩子链表 → E → F

C → 孩子链表 → (空)

D → 孩子链表 → G

E → 孩子链表 → (空)

F → 孩子链表 → (空)

G → 孩子链表 → (空)

孩子兄弟表示法—-适合同时查找孩子和兄弟节点。此结构将多叉树转换为二叉树，有利于在实际中使用二叉树的算法来处理多叉树

typedef struct CSNode {
    ElementType data;         // 数据域，存储节点的值
    struct CSNode *firstChild; // 左孩子指针，指向第一个孩子节点
    struct CSNode *nextSibling; // 右兄弟指针，指向右兄弟节点
} CSNode, *CSTree;

A → firstChild → B

B → firstChild → E, nextSibling → C

C → nextSibling → D

D → firstChild → G

E → nextSibling → F

F → nextSibling → (空)

G → nextSibling → (空)

二叉树

节点数的性质

性质 1：对任何一棵非空二叉树，第 iii 层上的最多节点数为 2i−12^{i-1}2i−1（i≥1i \geq 1i≥1）。
- 例如，第 1 层最多有 21−1=12^{1-1} = 121−1=1 个节点，第 2 层最多有 22−1=22^{2-1} = 222−1=2 个节点，第 3 层最多有 23−1=42^{3-1} = 423−1=4 个节点，依此类推。
性质 2：深度为 kkk 的二叉树的最多节点数为 2k−12^k - 12k−1（k≥1k \geq 1k≥1）。
- 例如，深度为 3 的二叉树最多有 23−1=72^3 - 1 = 723−1=7 个节点。
性质 3：对任何一棵二叉树，若其叶节点数为 n0n_0n0，度为 2 的节点数为 n2n_2n2，则满足关系式：n0=n2+1n_0 = n_2 + 1n0=n2+1。
- 这个性质帮助我们快速计算一棵二叉树的叶节点和度为 2 的节点之间的关系。

完全二叉树的性质

性质 4：如果一棵完全二叉树有 nnn 个节点，则这些节点可以从上至下、从左到右编号为 1 到 nnn。对于任意节点 iii（1 ≤ iii ≤ nnn）：
- 若 i=1i = 1i=1，则节点 iii 是根节点。
- 若 i>1i > 1i>1，则节点 iii 的父节点编号为 ⌊i/2⌋\lfloor i/2 \rfloor⌊i/2⌋。
- 若 2i≤n2i \leq n2i≤n，则节点 iii 的左孩子编号为 2i2i2i。
- 若 2i+1≤n2i + 1 \leq n2i+1≤n，则节点 iii 的右孩子编号为 2i+12i + 12i+1。

二叉树的深度和高度关系

性质 5：对于一棵有 nnn 个节点的完全二叉树，其深度（或高度）为 ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1⌊log2n⌋+1。
- 例如，一棵有 7 个节点的完全二叉树的深度为 ⌊log⁡27⌋+1=3\lfloor \log_2 7 \rfloor + 1 = 3⌊log27⌋+1=3。

满二叉树的性质

性质 6：一棵深度为 kkk 的满二叉树的节点数为 2k−12^k - 12k−1。
- 满二叉树指的是每一层都被完全填满的二叉树，没有空缺。
性质 7：满二叉树的叶节点数等于度为 2 的节点数加 1，且所有的叶节点都在同一层。

二叉树的节点之间的关系

性质 8：在二叉树的顺序存储中，父节点、左孩子和右孩子之间的索引关系可以简化操作：
- 如果某节点的索引为 iii，则其左孩子的索引为 2i2i2i，右孩子的索引为 2i+12i + 12i+1，父节点的索引为 ⌊i/2⌋\lfloor i/2 \rfloor⌊i/2⌋。
性质 9：在二叉树中，深度越大的层，其节点数呈指数增长。即在二叉树的末端层节点数最多，而根节点只有一个。

二叉树顺序存储

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

按照顺序存储的方式，这棵树会被存储在数组中如下：

索引	数据
1	A
2	B
3	C
4	D
5	E
6	F
7	G

在这个数组中：

A 的左孩子是 B（索引 2），右孩子是 C（索引 3）。
B 的左孩子是 D（索引 4），右孩子是 E（索引 5）。
C 的左孩子是 F（索引 6），右孩子是 G（索引 7）。


#include <stdio.h>

#define MAX_SIZE 100 // 定义顺序存储二叉树的最大节点数

typedef char ElementType; // 定义节点元素的类型
typedef struct {
    ElementType data[MAX_SIZE]; // 用数组存储二叉树的节点
    int size;                   // 记录二叉树的节点数量
} SeqBinaryTree;

// 初始化二叉树
void initTree(SeqBinaryTree *tree) {
    tree->size = 0; // 初始时二叉树为空
}

// 添加节点到二叉树
void addNode(SeqBinaryTree *tree, ElementType data) {
    if (tree->size + 1 < MAX_SIZE) {
        tree->data[++(tree->size)] = data;
    } else {
        printf("二叉树已满，无法插入更多节点。\n");
    }
}

// 前序遍历二叉树（递归）
void preOrderTraverse(SeqBinaryTree *tree, int index) {
    if (index > tree->size) return; // 如果索引超过节点数，则返回

    // 访问根节点
    printf("%c ", tree->data[index]);

    // 递归访问左孩子
    preOrderTraverse(tree, 2 * index);

    // 递归访问右孩子
    preOrderTraverse(tree, 2 * index + 1);
}

int main() {
    SeqBinaryTree tree;
    initTree(&tree);

    // 添加节点（按照层次顺序添加）
    addNode(&tree, 'A'); // 根节点
    addNode(&tree, 'B'); // 左孩子
    addNode(&tree, 'C'); // 右孩子
    addNode(&tree, 'D'); // B 的左孩子
    addNode(&tree, 'E'); // B 的右孩子
    addNode(&tree, 'F'); // C 的左孩子
    addNode(&tree, 'G'); // C 的右孩子

    printf("前序遍历结果：");
    preOrderTraverse(&tree, 1); // 从根节点（索引 1）开始前序遍历
    printf("\n");

    return 0;
}

二叉树由节点组成，每个节点包含以下内容：

数据域：存储节点的数据。
左子节点指针：指向左子节点。
右子节点指针：指向右子节点。

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

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

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

// 插入节点（基于二叉查找树的插入）
TreeNode* Insert(TreeNode *root, int value) {
    if (root == NULL) {
        return CreateNode(value);
    }
    if (value < root->data) {
        root->left = Insert(root->left, value);
    } else {
        root->right = Insert(root->right, value);
    }
    return root;
}

// 前序遍历
void PreorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    PreorderTraversal(root->left);
    PreorderTraversal(root->right);
}

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

// 后序遍历
void PostorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    PostorderTraversal(root->left);
    PostorderTraversal(root->right);
    printf("%d ", root->data);
}
int getHeight(TreeNode* root) {
    if (root == NULL) {
        return 0; // 空树的高度为 0
    }
    int leftHeight = getHeight(root->left);  // 左子树高度
    int rightHeight = getHeight(root->right); // 右子树高度
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; // 取较大值加 1
}
int getNodeCount(TreeNode* root) {
    if (root == NULL) {
        return 0; // 空树的节点数为 0
    }
    return getNodeCount(root->left) + getNodeCount(root->right) + 1; // 左子树节点数 + 右子树节点数 + 根节点
}
int getLeafNodeCount(TreeNode* root) {
    if (root == NULL) {
        return 0; // 空树的叶子节点数为 0
    }
    if (root->left == NULL && root->right == NULL) {
        return 1; // 当前节点是叶子节点
    }
    return getLeafNodeCount(root->left) + getLeafNodeCount(root->right); // 左子树叶子节点数 + 右子树叶子节点数
}




int main() {
    TreeNode *root = NULL;
    root = Insert(root, 5);
    root = Insert(root, 3);
    root = Insert(root, 7);
    root = Insert(root, 2);
    root = Insert(root, 4);
    root = Insert(root, 6);
    root = Insert(root, 8);

    printf("前序遍历: ");
    PreorderTraversal(root);
    printf("\n");

    printf("中序遍历: ");
    InorderTraversal(root);
    printf("\n");

    printf("后序遍历: ");
    PostorderTraversal(root);
    printf("\n");

    return 0;
}

代码解析

节点定义：
- 使用结构体 TreeNode 来定义二叉树的节点，每个节点包含一个 data 数据域，以及指向左、右子节点的指针。
创建节点：
- 使用 CreateNode(int value) 函数来创建一个新节点。
插入节点：
- 使用 Insert(TreeNode *root, int value) 函数来向二叉树中插入节点。插入节点的规则是：左子节点小于父节点，右子节点大于父节点。
遍历操作：
- 前序遍历：先访问根节点，再访问左子树，最后访问右子树。
- 中序遍历：先访问左子树，再访问根节点，最后访问右子树。
- 后序遍历：先访问左子树，再访问右子树，最后访问根节点。

对应算法

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

#define MaxSize 50  // 栈的最大容量

// 定义二叉树节点结构体
typedef struct BTNode {
    char data;              // 节点数据
    struct BTNode* lchild;  // 左子节点
    struct BTNode* rchild;  // 右子节点
} BTNode;

// 函数：根据括号表示法建立二叉树
void CreateBTree(BTNode* bt, char* str) {
    BTNode* St[MaxSize], *p = NULL; // 定义栈和当前处理的节点
    int top = -1, k = 0, j = 0;     // 栈顶指针，k表示左/右子树标志，j遍历字符串索引
    char ch;
    bt = NULL;  // 初始化树根为空
    ch = str[j];
    while (ch != '\0') {  // 遍历输入字符串
        switch (ch) {
            case '(':
                top++;
                St[top] = p;  // 将当前节点入栈
                k = 1;        // 下一个节点为左子节点
                break;
            case ')':
                top--;  // 子树处理完毕，出栈
                break;
            case ',':
                k = 2;  // 下一个节点为右子节点
                break;
            default:
                p = (BTNode*)malloc(sizeof(BTNode));  // 创建新节点
                p->data = ch;
                p->lchild = p->rchild = NULL;  // 初始化左右子树为空
                if (bt == NULL) {  // 如果树根为空，说明当前节点是根节点
                    bt = p;
                } else {  // 否则，连接左右子树
                    if (k == 1) {
                        St[top]->lchild = p;  // 左子树
                    } else if (k == 2) {
                        St[top]->rchild = p;  // 右子树
                    }
                }
                break;
        }
        j++;  // 移动到下一个字符
        ch = str[j];
    }
}

// 求树的高度
int tree_height(TreeNode* root) {
    if (root == NULL) {
        return 0;  // 空树高度为0
    }
    int left_height = tree_height(root->left);
    int right_height = tree_height(root->right);
    return (left_height > right_height) ? (left_height +1) : (right_height + 1);
}

// 求树的节点个数
int count_nodes(TreeNode* root) {
    if (root == NULL) {
        return 0;  // 空树没有节点
    }
    return count_nodes(root->left) + count_nodes(root->right) + 1;
}

// 求树的叶子节点个数
int count_leaves(TreeNode* root) {
    if (root == NULL) {
        return 0;  // 空树没有叶子
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;  // 叶子节点
    }
    return count_leaves(root->left) + count_leaves(root->right);
}

// 以括号的形式输出二叉树
void print_tree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d", root->value);  // 打印根节点
    if (root->left || root->right) {  // 如果有子节点
        printf("(");
        print_tree(root->left);  // 打印左子树
        printf(",");
        print_tree(root->right); // 打印右子树
        printf(")");
    }
}

二叉树的种类

二叉查找树（BST）：左子树节点值小于根节点，右子树节点值大于根节点，且左右子树分别也是二叉查找树。
平衡二叉树（AVL树）：任意节点的左右子树高度差不超过1，保证二叉查找树的平衡性，从而提高查找效率。
完全二叉树：除最后一层外，其他层节点都达到最大数目，且最后一层的节点从左向右连续排列。
满二叉树：所有的非叶节点都有两个子节点，且所有叶节点在同一层。

应用场景

表达式解析：二叉树可用于表达式的解析和计算，如中缀表达式、前缀表达式、后缀表达式的解析。
查找和排序：二叉查找树适合快速查找数据。
数据存储：在数据库的索引、文件系统的目录结构中，二叉树是常见的存储结构。

图

顶点（Vertex）：图中的节点。
边（Edge）：连接两个顶点的线段，表示两个顶点之间的关系。
有向图（Directed Graph）：图中的边是有方向的。
无向图（Undirected Graph）：图中的边是无方向的。
邻接：如果两个顶点之间有一条边连接，则称它们是相邻的。
邻接矩阵（Adjacency Matrix）：使用矩阵表示图。
邻接表（Adjacency List）：使用链表表示图。

在C语言中，通常使用邻接矩阵和邻接表来表示图结构。

图的表示方法

1. 邻接矩阵表示法

邻接矩阵是一种二维数组，矩阵中的元素表示顶点之间是否有边。对于一个包含 n 个顶点的图，我们可以使用一个 n × n 的二维数组来表示：

如果有边 i -> j，则 adj[i][j] = 1（或权重）。
如果没有边 i -> j，则 adj[i][j] = 0。

邻接矩阵适用于边数比较多的稠密图。

#define MAX_VERTICES 100
#define INF 9999  // 表示无穷大，用于带权图中无连接的情况

int adjMatrix[MAX_VERTICES][MAX_VERTICES];

// 初始化邻接矩阵
void initAdjMatrix(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adjMatrix[i][j] = (i == j) ? 0 : INF; // 无权无连接的边设为 0，其他边为 INF
        }
    }
}

// 添加边（无向图）
void addEdge(int u, int v, int weight) {
    adjMatrix[u][v] = weight;
    adjMatrix[v][u] = weight; // 对称添加，表示无向边
}


// 添加边
void AddEdge(Graph *g, int src, int dest) {
    g->adjMatrix[src][dest] = 1; // 对于无向图，两端都需标记为1
    g->adjMatrix[dest][src] = 1; // 如果是有向图，只需标记一处即可
}

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

int main() {
    Graph g;
    InitGraph(&g, 5); // 初始化5个顶点的图

    AddEdge(&g, 0, 1);
    AddEdge(&g, 0, 4);
    AddEdge(&g, 1, 2);
    AddEdge(&g, 1, 3);
    AddEdge(&g, 1, 4);
    AddEdge(&g, 2, 3);
    AddEdge(&g, 3, 4);

    PrintGraph(&g);
    return 0;
}

2. 邻接表表示法

邻接表使用链表数组来表示图，每个顶点有一个链表，该链表中存储与该顶点相邻的所有顶点。邻接表适用于边数较少的稀疏图，可以节省内存。

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

#define MAX_VERTICES 100

// 定义邻接表的链表节点
typedef struct AdjListNode {
    int vertex; // 邻接顶点的编号
    int weight; // 权值（对于带权图）
    struct AdjListNode* next;
} AdjListNode;

// 定义邻接表
typedef struct {
    AdjListNode* head; // 指向链表头节点
} AdjList;

// 定义图结构
typedef struct {
    int numVertices;       // 顶点数量
    AdjList adjLists[MAX_VERTICES]; // 顶点的邻接表数组
} Graph;

// 创建一个新的邻接表节点
AdjListNode* createNode(int vertex, int weight) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->vertex = vertex;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// 初始化图
void initGraph(Graph* graph, int numVertices) {
    graph->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        graph->adjLists[i].head = NULL;
    }
}

// 添加边（无向图）
void addEdge(Graph* graph, int src, int dest, int weight) {
    AdjListNode* newNode = createNode(dest, weight);
    newNode->next = graph->adjLists[src].head;
    graph->adjLists[src].head = newNode;

    // 对于无向图，还需要在 dest -> src 添加一条边
    newNode = createNode(src, weight);
    newNode->next = graph->adjLists[dest].head;
    graph->adjLists[dest].head = newNode;
}

图的常见操作

遍历（Traversal）：
- 深度优先遍历（DFS）：从某个顶点开始尽可能深地访问图中的节点。
- 广度优先遍历（BFS）：从某个顶点开始，逐层访问图中的节点。
最短路径：
- Dijkstra算法：用于求解有向图中单源最短路径。
- Floyd算法：用于求解任意两点之间的最短路径。
连通性：
- 判断图是否是连通图。
- 求连通分量。
最小生成树（MST）：
- Prim算法：构建最小生成树。
- Kruskal算法：构建最小生成树

深度优先遍历（DFS）

// 深度优先搜索（DFS）递归版本
void DFS(Graph* graph, int vertex, bool visited[MAX_VERTICES]) {
    visited[vertex] = true;
    printf("%d ", vertex);

    // 访问当前节点的所有邻接节点
    AdjListNode* temp = graph->adjLists[vertex].head;
    while (temp) {
        if (!visited[temp->vertex]) {
            DFS(graph, temp->vertex, visited);
        }
        temp = temp->next;
    }
}



// 栈的实现
int stack[MAX_VERTICES];
int top = -1;

void push(int vertex) {
    stack[++top] = vertex;
}

int pop() {
    return stack[top--];
}

bool isStackEmpty() {
    return top == -1;
}

// 深度优先搜索（DFS）非递归版本
void DFS_Stack(Graph* graph, int startVertex) {
    bool visited[MAX_VERTICES] = {false}; // 记录节点是否访问过
    push(startVertex);
    visited[startVertex] = true;

    while (!isStackEmpty()) {
        int vertex = pop();
        printf("%d ", vertex);

        // 访问当前节点的所有邻接节点
        AdjListNode* temp = graph->adjLists[vertex].head;
        while (temp) {
            if (!visited[temp->vertex]) {
                push(temp->vertex);
                visited[temp->vertex] = true;
            }
            temp = temp->next;
        }
    }
}

广度优先遍历（BFS）

#define MAX_QUEUE_SIZE 100

// 队列结构
int queue[MAX_QUEUE_SIZE];
int front = 0, rear = 0;

// 入队操作
void enqueue(int vertex) {
    queue[rear++] = vertex;
}

// 出队操作
int dequeue() {
    return queue[front++];
}

// 判断队列是否为空
bool isEmpty() {
    return front == rear;
}

// 广度优先搜索（BFS）
void BFS(Graph* graph, int startVertex) {
    bool visited[MAX_VERTICES] = {false}; // 记录节点是否访问过
    enqueue(startVertex);
    visited[startVertex] = true;

    while (!isEmpty()) {
        int vertex = dequeue();
        printf("%d ", vertex);

        // 访问当前节点的所有邻接节点
        AdjListNode* temp = graph->adjLists[vertex].head;
        while (temp) {
            if (!visited[temp->vertex]) {
                enqueue(temp->vertex);
                visited[temp->vertex] = true;
            }
            temp = temp->next;
        }
    }
}

最小生成树（MST）

对于一个连接图，最小生成树是图中所有顶点的一个子集，它包括图中所有的顶点，并且是一个无环的树。最小生成树的边的总权重是最小的。

算法：

Prim 算法
Kruskal 算法
Prim 算法

Prim 算法通过从一个顶点开始，逐步将最小的边加入生成树，直到所有顶点都在树中。每次都选择当前生成树与剩余顶点之间的最小边。

Prim 算法的步骤：

从任意一个顶点（例如顶点 0）开始，标记为已访问。
每次选择一个已经加入生成树的顶点，通过它与尚未加入树的顶点之间的最小边，将一个新顶点加入生成树。
重复步骤 2，直到所有顶点都加入生成树。

数据结构：

邻接矩阵或邻接表来存储图。
最小堆或优先队列用于高效地选择最小边。

Prim 算法（使用邻接矩阵实现）：

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

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
int parent[MAX_VERTICES];  // 用来存储最小生成树中每个顶点的父节点
int key[MAX_VERTICES];     // 用来存储连接已加入树的顶点和未加入树的顶点的最小边的权值

// 找到当前没有被加入生成树的顶点中，最小边的权值的顶点
int minKey(int key[], bool mstSet[], int numVertices) {
    int min = INT_MAX, minIndex;
    for (int v = 0; v < numVertices; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// Prim 算法
void primMST(int numVertices) {
    bool mstSet[MAX_VERTICES];  // 用来标记顶点是否已加入生成树
    for (int i = 0; i < numVertices; i++) {
        key[i] = INT_MAX;  // 初始化 key 数组为无穷大
        mstSet[i] = false; // 初始时，所有顶点都不在生成树中
    }
    key[0] = 0; // 从顶点 0 开始
    parent[0] = -1; // 顶点 0 没有父节点

    for (int count = 0; count < numVertices - 1; count++) {
        int u = minKey(key, mstSet, numVertices); // 找到最小的 key 值的顶点 u
        mstSet[u] = true; // 将顶点 u 加入到生成树中

        // 更新与 u 相邻的所有未加入生成树的顶点的 key 值
        for (int v = 0; v < numVertices; v++) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                key[v] = graph[u][v]; // 更新 key 值
                parent[v] = u;        // 更新父节点
            }
        }
    }

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

int main() {
    int numVertices = 5;

    // 示例图
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };

    primMST(numVertices);

    return 0;
}

Kruskal 算法

Kruskal 算法是另一种常见的最小生成树算法，它通过边的方式来构建生成树。算法的核心思想是按边的权重从小到大排序，然后逐一添加边到生成树中，前提是不会形成环（使用并查集判断是否形成环）。

Kruskal 算法的步骤：

将图中的所有边按权重升序排列。
使用 并查集（Union-Find） 来判断两个顶点是否属于同一个连通分量。
按照权重从小到大的顺序，依次添加边到生成树中，若添加的边不会形成环，则将边加入生成树。
重复上述步骤直到生成树包含 V−1V - 1V−1 条边。

数据结构：

边列表：存储图的所有边。
并查集（Union-Find）：用于判断是否形成环。

Kruskal 算法（使用边列表和并查集实现）：

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

#define MAX_VERTICES 100

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

// 并查集查找函数
int find(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

// 并查集合并函数
void unionSets(int parent[], int x, int y) {
    int xroot = find(parent, x);
    int yroot = find(parent, y);
    if (xroot != yroot)
        parent[xroot] = yroot;
}

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

// Kruskal 算法
void kruskalMST(Edge edges[], int numEdges, int numVertices) {
    qsort(edges, numEdges, sizeof(Edge), compare);  // 按权重排序所有边

    int parent[MAX_VERTICES];
    for (int i = 0; i < numVertices; i++)
        parent[i] = -1;  // 初始化并查集

    printf("Edge \tWeight\n");

    int mstWeight = 0;
    for (int i = 0; i < numEdges; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int weight = edges[i].weight;
        int setU = find(parent, u);
        int setV = find(parent, v);
        if (setU != setV) {
            printf("%d - %d \t%d\n", u, v, weight);
            unionSets(parent, setU, setV);  // 将两个集合合并
            mstWeight += weight;
        }
    }
    printf("Total weight of MST: %d\n", mstWeight);
}

int main() {
    // 示例图，4个顶点和5条边
    int numVertices = 4;
    int numEdges = 5;

    Edge edges[] = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    kruskalMST(edges, numEdges, numVertices);

    return 0;
}

最短路径算法

Dijkstra 算法

Dijkstra 算法是一个贪心算法，用于计算一个图中单源最短路径的问题，即从一个起始节点出发，计算到所有其他节点的最短路径。该算法适用于图中没有负权边的情况。

Dijkstra 算法的步骤：

初始化一个距离数组 dist[]，用来存储源节点到各个节点的最短距离。起始节点的距离设置为 0，其他节点的距离设置为无限大。
使用一个优先队列（或最小堆）来选取当前未处理的、具有最小 dist[] 值的节点。
从当前节点出发，更新所有相邻节点的最短距离，如果发现更小的距离，则更新。
重复以上步骤直到所有节点都被访问过。

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

#define MAX_VERTICES 100
#define INF INT_MAX

int graph[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
int dist[MAX_VERTICES];  // 源节点到其他节点的最短路径
bool visited[MAX_VERTICES];  // 记录节点是否已被访问

// Dijkstra 算法
void dijkstra(int numVertices, int start) {
    for (int i = 0; i < numVertices; i++) {
        dist[i] = INF;  // 初始化所有顶点的最短路径为无限大
        visited[i] = false;  // 初始化所有顶点为未访问
    }

    dist[start] = 0;  // 起点到起点的距离是 0

    for (int count = 0; count < numVertices - 1; count++) {
        // 找到距离起点最近的未访问顶点
        int u = -1, minDist = INF;
        for (int v = 0; v < numVertices; v++) {
            if (!visited[v] && dist[v] < minDist) {
                u = v;
                minDist = dist[v];
            }
        }

        visited[u] = true;  // 标记当前顶点为已访问

        // 更新与当前顶点相邻的顶点的最短路径
        for (int v = 0; v < numVertices; v++) {
            if (graph[u][v] && !visited[v] && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // 打印最短路径
    printf("Vertex \t Distance from source\n");
    for (int i = 0; i < numVertices; i++) {
        printf("%d \t %d\n", i, dist[i]);
    }
}

int main() {
    int numVertices = 5;

    // 示例图的邻接矩阵表示
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 10, 0, 30, 100},
        {10, 0, 50, 0, 0},
        {0, 50, 0, 20, 10},
        {30, 0, 20, 0, 60},
        {100, 0, 10, 60, 0}
    };

    dijkstra(numVertices, 0);  // 从顶点 0 开始计算最短路径

    return 0;
}
/*Vertex 	Distance from source
0 	 0
1 	 10
2 	 60
3 	 30
4 	 70

Floyd-Warshall 算法

Floyd-Warshall 算法的步骤：

初始化一个距离矩阵 dist[][]，将所有边的权值赋给相应位置。如果没有边，赋值为无限大。
对于每一对顶点 i,ji, ji,j，检查是否有一个中间顶点 kkk，使得通过 kkk 达到 jjj 的路径比直接从 iii 到 jjj 的路径更短。如果是，则更新 dist[i][j]。
重复上述过程，直到找到所有顶点对的最短路径。

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

#define MAX_VERTICES 100
#define INF INT_MAX

int graph[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵

// Floyd-Warshall 算法
void floydWarshall(int numVertices) {
    int dist[MAX_VERTICES][MAX_VERTICES];

    // 初始化距离矩阵
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            if (i == j)
                dist[i][j] = 0;
            else if (graph[i][j])
                dist[i][j] = graph[i][j];
            else
                dist[i][j] = INF;
        }
    }

    // 动态规划计算最短路径
    for (int k = 0; k < numVertices; k++) {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (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 < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            if (dist[i][j] == INF)
                printf("INF ");
            else
                printf("%d ", dist[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int numVertices = 4;

    // 示例图的邻接矩阵表示
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 3, INF, INF},
        {3, 0, 1, INF},
        {INF, 1, 0, 7},
        {INF, INF, 7, 0}
    };

    floydWarshall(numVertices);  // 计算所有顶点对之间的最短路径

    return 0;
}
/*Shortest distances between every pair of vertices:
0 3 4 8 
3 0 1 4 
4 1 0 5 
8 4 5 0

AOV网和拓扑排序

入度法

思路：

计算所有节点的入度。
将入度为 0 的节点加入队列。
从队列中取出一个节点，加入排序结果中，并减少它的邻接节点的入度。
如果邻接节点的入度变为 0，则将其加入队列。
继续这个过程，直到所有节点都被处理。如果处理完后还有节点没有加入排序结果，说明图中存在环。

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

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示图
int inDegree[MAX_VERTICES];            // 存储每个节点的入度
int numVertices;                       // 图的顶点数

// 入度法实现拓扑排序
void topologicalSort() {
    int queue[MAX_VERTICES], front = 0, rear = 0;
    
    // 将入度为 0 的节点加入队列
    for (int i = 0; i < numVertices; i++) {
        if (inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }
    
    // 记录已排序的顶点数量
    int sortedCount = 0;
    
    while (front < rear) {
        int u = queue[front++];  // 取出一个节点
        
        printf("%d ", u);        // 输出当前节点（加入拓扑排序结果）
        sortedCount++;
        
        // 减少与该节点相邻的顶点的入度
        for (int v = 0; v < numVertices; v++) {
            if (graph[u][v] == 1) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue[rear++] = v;
                }
            }
        }
    }
    
    // 如果所有节点都已排序，则图是DAG，否则存在环
    if (sortedCount != numVertices) {
        printf("\n图中存在环，无法进行拓扑排序。\n");
    }
}

int main() {
    numVertices = 6;  // 图的顶点数

    // 构建示例图（邻接矩阵表示）
    int g[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 1, 1},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 0}
    };
    
    // 将邻接矩阵赋值给图
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            graph[i][j] = g[i][j];
        }
    }
    
    // 初始化入度数组
    for (int i = 0; i < numVertices; i++) {
        inDegree[i] = 0;
        for (int j = 0; j < numVertices; j++) {
            if (graph[j][i] == 1) {
                inDegree[i]++;
            }
        }
    }

    printf("拓扑排序结果：\n");
    topologicalSort();
    
    return 0;
}
/*拓扑排序结果：
0 1 2 3 4 5

深度优先搜索法实现拓扑排序

对图进行深度优先搜索（DFS）。

在回溯过程中，将节点压入栈中。

最终栈中的节点顺序即为拓扑排序的结果（栈顶到栈底）。

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

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示图
bool visited[MAX_VERTICES];            // 记录节点是否被访问
int numVertices;                       // 图的顶点数

// 递归深度优先搜索
void dfs(int u, int stack[], int *top) {
    visited[u] = true;
    
    // 访问所有邻接节点
    for (int v = 0; v < numVertices; v++) {
        if (graph[u][v] == 1 && !visited[v]) {
            dfs(v, stack, top);
        }
    }
    
    // 将节点加入栈
    stack[(*top)++] = u;
}

// 深度优先搜索法实现拓扑排序
void topologicalSort() {
    int stack[MAX_VERTICES];
    int top = 0;

    // 初始化访问标记
    for (int i = 0; i < numVertices; i++) {
        visited[i] = false;
    }
    
    // 对每个未访问的节点进行DFS遍历
    for (int i = 0; i < numVertices; i++) {
        if (!visited[i]) {
            dfs(i, stack, &top);
        }
    }

    // 打印拓扑排序结果（栈中的顺序）
    printf("拓扑排序结果：\n");
    for (int i = top - 1; i >= 0; i--) {
        printf("%d ", stack[i]);
    }
    printf("\n");
}

int main() {
    numVertices = 6;  // 图的顶点数

    // 构建示例图（邻接矩阵表示）
    int g[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 1, 1},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 0}
    };
    
    // 将邻接矩阵赋值给图
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            graph[i][j] = g[i][j];
        }
    }

    topologicalSort();
    
    return 0;
}

图是一种重要的数据结构，主要用于表示对象之间的关系，可以分为有向图和无向图。

在C语言中，图通常使用邻接矩阵或邻接表来表示，邻接矩阵适用于稠密图，邻接表适用于稀疏图。

常见的图操作包括深度优先遍历（DFS）、广度优先遍历（BFS）、求最短路径、连通性等。

选择合适的图表示方式和遍历方法可以提高程序的效率和可读性。

排序

二叉排序树

插入操作（Insert）

插入操作的目的是将新节点插入到树中的合适位置。插入过程如下：

从根节点开始，比较要插入的值与当前节点的值。
如果新值小于当前节点的值，则递归插入到左子树；如果新值大于当前节点的值，则递归插入到右子树。
如果当前节点的左子树或右子树为空，则直接插入节点。

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* insert(TreeNode* root, int value) {
    if (root == NULL) {
        TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
        newNode->data = value;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if (value < root->data) {
        root->left = insert(root->left, value);  // 插入到左子树
    } else if (value > root->data) {
        root->right = insert(root->right, value);  // 插入到右子树
    }
    return root;
}

查找操作（Search）

查找操作用于判断某个值是否在二叉排序树中。查找的过程与插入类似，从根节点开始，依次向左或向右子树移动，直到找到目标节点或到达叶子节点。

TreeNode* search(TreeNode* root, int value) {
    if (root == NULL || root->data == value) {
        return root;  // 如果找到值或到达空节点
    }
    if (value < root->data) {
        return search(root->left, value);  // 在左子树查找
    } else {
        return search(root->right, value);  // 在右子树查找
    }
}

删除操作（Delete）

删除操作有三种情况：

删除叶子节点：直接删除该节点。
删除只有一个子节点的节点：将该节点的父节点指向该节点的唯一子节点。
删除有两个子节点的节点：找到该节点的中序后继（右子树中最小的节点）或中序前驱（左子树中最大的节点），用它替换该节点，然后删除中序后继或前驱节点。

TreeNode* minValueNode(TreeNode* node) {
    TreeNode* current = node;
    while (current && current->left != NULL) {
        current = current->left;  // 查找左子树的最小节点
    }
    return current;
}

TreeNode* deleteNode(TreeNode* root, int value) {
    if (root == NULL) return root;
    
    if (value < root->data) {
        root->left = deleteNode(root->left, value);  // 删除左子树中的节点
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);  // 删除右子树中的节点
    } else {
        // 处理删除节点的三种情况
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        
        // 找到右子树中的最小节点，并用它替换当前节点
        TreeNode* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);  // 删除右子树中的最小节点
    }
    return root;
}

4. 中序遍历（Inorder Traversal）

中序遍历可以按升序输出二叉排序树中的所有节点。在二叉排序树中，中序遍历的结果总是递增的。

void inorder(TreeNode* root) {
    if (root != NULL) {
        inorder(root->left);  // 先遍历左子树
        printf("%d ", root->data);  // 然后访问当前节点
        inorder(root->right);  // 最后遍历右子树
    }
}

5. 前序遍历（Preorder Traversal）

前序遍历的顺序是：先访问根节点，再遍历左子树，最后遍历右子树。

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

6. 后序遍历（Postorder Traversal）

后序遍历的顺序是：先遍历左子树，再遍历右子树，最后访问根节点。

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

c语言的数据结构

#c语言

c语言的数据结构

https://theganlove.github.io/2024/09/03/c语言的数据结构/

作者

uert

发布于

2024年9月3日

许可协议

ctf基础笔记上一篇

ssrf 下一篇

c语言的数据结构

c语言的数据结构

顺序表

3. 使用示例对比

4. 为什么要传递指针？

链表

单链表

双链表

循环链表

题目

栈

顺序栈的实现

栈的链式结构

队列

队列的顺序存储

队列的链式存储

循环队列

循环队列中的关键公式与要点总结

题目

字符串

数组

一维数组

二维数组

已知条件

行优先存储寻址公式

矩阵转置

三维数组

矩阵的压缩存储

对称矩阵

三角矩阵

稀疏矩阵压缩存储

树

二叉树

代码解析

二叉树的种类

应用场景

图

图的表示方法

1. 邻接矩阵表示法

2. 邻接表表示法

图的常见操作

最小生成树（MST）

最短路径算法

AOV网和拓扑排序

4. 中序遍历（Inorder Traversal）

5. 前序遍历（Preorder Traversal）

6. 后序遍历（Postorder Traversal）