C语言基础

定义结构体

#include <stdio.h>

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

int main() {
    Node node1; // 定义一个结构体变量
    node1.data = 10;   // 为结构体成员赋值
    node1.next = NULL; // 指针初始化为 NULL

    printf("Data: %d\n", node1.data);
    return 0;
}

动态内存分配

#include <stdio.h>
#include <stdlib.h> // 包含 malloc 和 free

int main() {
    int* ptr = (int*)malloc(sizeof(int)); // 分配一个整数的内存
    if (ptr == NULL) {
        printf("内存分配失败\n");
        return -1;
    }

    *ptr = 42; // 给动态分配的内存赋值
    printf("Value: %d\n", *ptr);

    free(ptr); // 释放内存
    return 0;
}

指针和链表的结合

// 直接用结构体用.   指针用结构体用->  
// **ptr 可以看作指针的数组 
// 创建新节点
// 一定要记得free
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

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

// 释放链表
void freeList(struct Node* head) {
    struct Node* current = head;
    struct Node* nextNode;
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
}

int main() {
    Node* head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);

    printList(head);

    freeList(head); // 释放内存
    return 0;
}

数组与指针的关系

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    int* ptr = arr; // 数组名是首元素地址

    for (int i = 0; i < 5; i++) {
        printf("arr[%d] = %d, *(ptr + %d) = %d\n", i, arr[i], i, *(ptr + i));
    }

    return 0;
}

递归

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

时间复杂度和空间复杂度

时间复杂度

时间复杂度的重点在于关注最坏情况下的运行时间。比如，在冒泡排序中，我们可能需要比较所有元素，这使得时间复杂度为O(n^2);
一般是以循环，递归，二分去计算的
二分查找log(n), 循环遍历是n

遍历数组

void traverseArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
}
// 时间复杂度：O(n)

嵌套循环

void nestedLoops(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("i: %d, j: %d\n", i, j);
        }
    }
}
// 时间复杂度：O(n^2)

二分查找

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
// 时间复杂度：O(log n)
// 二分查找写法很多，这里只是例子

空间复杂度

无额外空间（原地操作）

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
// 空间复杂度：O(1)（只需要一个额外变量）

递归算法

int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}
// 空间复杂度：O(n)（递归调用栈消耗）

动态规划

int fibonacci(int n) {
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
// 空间复杂度：O(n)（存储数组 dp[] 占用）

线性表

顺序表和链表

顺序表

可以理解成数组
功能说明

初始化：动态分配内存并设置初始容量和长度。
销毁：释放顺序表的数据和结构体本身的内存。
清空：将表长设为 0，但不释放内存。
求表长：直接返回当前表的长度。
判断是否为空：判断表长是否为 0。
取值：根据索引取出指定位置的值。
查找：在顺序表中查找第一个匹配值的索引。
插入：在指定位置插入一个新元素。
删除：删除指定位置的元素，并返回被删除的值。

打印表：打印顺序表中的所有元素。

其实每种数据结构要做的都差不多，第一个学好了会怎么写了后面的光记住操作就好了

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

// 顺序表的定义
typedef struct {
    int* data;    // 动态数组
    int length;   // 当前表长
    int capacity; // 最大容量
} SeqList;

// 初始化顺序表
SeqList* InitList(int capacity) {
    SeqList* list = (SeqList*)malloc(sizeof(SeqList));
    if (!list) {
        printf("内存分配失败！\n");
        return NULL;
    }
    list->data = (int*)malloc(capacity * sizeof(int));
    if (!list->data) {
        printf("内存分配失败！\n");
        free(list);
        return NULL;
    }
    list->length = 0;
    list->capacity = capacity;
    return list;
}

// 销毁顺序表
void DestroyList(SeqList* list) {
    if (list) {
        free(list->data);
        free(list);
    }
}

// 清空顺序表
void ClearList(SeqList* list) {
    if (list) {
        list->length = 0;
    }
}

// 求表长
int GetLength(SeqList* list) {
    if (list) {
        return list->length;
    }
    return -1; // 错误标志
}

// 判断是否为空
bool IsEmpty(SeqList* list) {
    return list && list->length == 0; // 要存在才能判空
}

// 取值
bool GetValue(SeqList* list, int index, int* value) {
    if (!list || index < 0 || index >= list->length) {
        return false; // 无效操作
    }
    *value = list->data[index];
    return true;
}

// 查找值的位置
int Find(SeqList* list, int value) {
    if (!list) {
        return -1; // 错误标志
    }
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == value) {
            return i; // 返回第一个匹配的位置
        }
    }
    return -1; // 未找到
}

// 插入元素
bool Insert(SeqList* list, int index, int value) {
    if (!list || index < 0 || index > list->length || list->length >= list->capacity) {
        return false; // 无效操作
    }
    for (int i = list->length; i > index; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[index] = value;
    list->length++;
    return true;
}

// 删除元素
bool Delete(SeqList* list, int index, int* deletedValue) {
    if (!list || index < 0 || index >= list->length) {
        return false; // 无效操作
    }
    *deletedValue = list->data[index];
    for (int i = index; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;
    return true;
}

// 打印顺序表
void PrintList(SeqList* list) {
    if (!list) {
        printf("顺序表不存在！\n");
        return;
    }
    printf("顺序表元素：");
    for (int i = 0; i < list->length; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

// 主函数测试
int main() {
    SeqList* list = InitList(10); // 初始化容量为10的顺序表
    if (!list) return -1;

    // 插入元素
    Insert(list, 0, 10);
    Insert(list, 1, 20);
    Insert(list, 2, 30);
    PrintList(list); // 输出：10 20 30

    // 删除元素
    int deletedValue;
    Delete(list, 1, &deletedValue);
    printf("删除的元素：%d\n", deletedValue);
    PrintList(list); // 输出：10 30

    // 查找元素
    int index = Find(list, 30);
    printf("查找30的位置：%d\n", index); // 输出：1

    // 取值
    int value;
    if (GetValue(list, 1, &value)) {
        printf("取出的值：%d\n", value); // 输出：30
    }

    // 清空列表
    ClearList(list);
    PrintList(list); // 输出：空表

    // 判断是否为空
    printf("顺序表是否为空：%s\n", IsEmpty(list) ? "是" : "否");

    // 销毁顺序表
    DestroyList(list);

    return 0;
}

有for的时间复杂度是O(n)其他的事O(1)
空间复杂度事O(n)

链表

顺序表：适合需要频繁访问和快速随机访问的场景（如数组），但插入和删除效率低，且内存大小固定。
链表：适合需要频繁插入和删除的场景，动态内存管理，灵活扩展，但访问效率较低。

链表的定义和基本操作实现

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

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

// 初始化链表
Node* InitList() {
    return NULL; // 空链表初始化，返回 NULL
}

// 取值（根据索引获取值）
int GetValue(Node* head, int index) {
    Node* current = head;
    int count = 0;

    while (current != NULL) {
        if (count == index) {
            return current->data;
        }
        current = current->next;
        count++;
    }

    printf("索引越界\n");
    return -1; // 返回一个错误标志
}

// 查找（返回第一个匹配元素的索引）
int Find(Node* head, int value) {
    Node* current = head;
    int index = 0;

    while (current != NULL) {
        if (current->data == value) {
            return index;
        }
        current = current->next;
        index++;
    }

    return -1; // 如果未找到，返回 -1
}

// 插入（在指定位置插入一个新节点）
int Insert(Node** head, int index, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败\n");
        return 0;
    }
    newNode->data = value;

    if (index == 0) {
        newNode->next = *head;
        *head = newNode;
        return 1;
    }

    Node* current = *head;
    int count = 0;
    while (current != NULL && count < index - 1) {
        current = current->next;
        count++;
    }

    if (current == NULL) {
        printf("插入位置无效\n");
        free(newNode);
        return 0;
    }

    newNode->next = current->next;
    current->next = newNode;
    return 1;
}

// 删除（删除指定位置的节点）
int Delete(Node** head, int index) {
    if (*head == NULL) {
        printf("链表为空\n");
        return 0;
    }

    Node* current = *head;

    // 删除头节点
    if (index == 0) {
        *head = current->next;
        free(current);
        return 1;
    }

    int count = 0;
    while (current != NULL && count < index - 1) {
        current = current->next;
        count++;
    }

    if (current == NULL || current->next == NULL) {
        printf("删除位置无效\n");
        return 0;
    }

    Node* temp = current->next;
    current->next = temp->next;
    free(temp);
    return 1;
}

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

// 主函数测试链表操作
int main() {
    Node* list = InitList(); // 初始化链表

    // 插入元素
    Insert(&list, 0, 10);
    Insert(&list, 1, 20);
    Insert(&list, 1, 15);
    PrintList(list); // 输出：10 -> 15 -> 20 -> NULL

    // 取值
    int value = GetValue(list, 1);
    printf("索引1的值：%d\n", value); // 输出：15

    // 查找元素
    int index = Find(list, 20);
    printf("值20的索引位置：%d\n", index); // 输出：2

    // 删除元素
    Delete(&list, 1);
    PrintList(list); // 输出：10 -> 20 -> NULL

    return 0;
}

初始化链表：通过返回 NULL 来表示一个空链表。
取值：通过索引查找链表中的元素。遍历链表直到找到指定位置。
查找：遍历链表，找到第一个匹配的元素并返回其索引。
插入：在指定位置插入一个新节点。如果插入位置是头部，则直接修改头指针；如果是中间或尾部，需要遍历到该位置并插入新节点。
删除：删除指定位置的节点。若删除的是头节点，需要直接修改头指针；删除中间或尾部节点，需要调整前一个节点的指针。
除了初始化其他操作都是O(n),不过实际只用可以用脑子优化

Node* 是指向链表节点的指针，通常用来操作单个节点。
Node** 是指向 Node* 的指针，常用于需要修改链表头指针或操作指针本身的场景。
通过使用 Node**，可以直接修改头指针，支持链表的动态操作（如插入头节点、删除头节点）。
熟练起来方便,课本还提供了虚拟头节点的方法

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建虚拟头节点
Node* CreateDummyHead() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    return head;
}

// 插入节点
void Insert(Node* head, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = head->next;
    head->next = newNode;
}

// 删除节点
void Delete(Node* head, int index) {
    Node* current = head;
    int count = 0;
    while (current->next != NULL && count < index) {
        current = current->next;
        count++;
    }

    if (current->next != NULL) {
        Node* temp = current->next;
        current->next = temp->next;
        free(temp);
    } else {
        printf("删除位置无效\n");
    }
}

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

// 主函数
int main() {
    Node* head = CreateDummyHead();  // 创建虚拟头节点

    // 插入元素
    Insert(head, 10);
    Insert(head, 20);
    Insert(head, 30);
    PrintList(head);  // 输出：30 -> 20 -> 10 -> NULL

    // 删除元素
    Delete(head, 1);  // 删除索引为 1 的元素（20）
    PrintList(head);  // 输出：30 -> 10 -> NULL

    return 0;
}

循环，双向在此基础上简单的加指针就好了

栈和队列

栈

重点是要记住栈事是后进先出的元素LIFO(last in first out)

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

// 定义顺序栈的结构
#define MAX_SIZE 100  // 定义栈的最大容量

typedef struct {
    int data[MAX_SIZE];  // 用数组来存储栈中的元素
    int top;              // 栈顶指针，指向栈的最后一个元素
} Stack;

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

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

// 3. 求栈长
int StackLength(Stack* stack) {
    return stack->top + 1;  // 栈的长度是 top + 1
}

// 4. 清空栈
void ClearStack(Stack* stack) {
    stack->top = -1;  // 将栈顶指针重置为 -1，表示栈为空
}

// 5. 销毁栈
void DestroyStack(Stack* stack) {
    // 对于顺序栈，销毁的操作就是释放栈内存，这里不做特别处理，因为内存是静态分配的
    // 如果是动态分配的栈，可以在这里使用 free(stack)。
    stack->top = -1;
    printf("栈已销毁\n");
}

// 6. 入栈
int Push(Stack* stack, int value) {
    if (stack->top == MAX_SIZE - 1) {  // 判断栈是否满
        printf("栈满，无法入栈\n");
        return 0;  // 入栈失败
    }
    stack->data[++stack->top] = value;  // 栈顶指针加 1，然后入栈
    return 1;  // 入栈成功
}

// 7. 出栈
int Pop(Stack* stack, int* value) {
    if (IsEmpty(stack)) {  // 判断栈是否为空
        printf("栈空，无法出栈\n");
        return 0;  // 出栈失败
    }
    *value = stack->data[stack->top--];  // 取栈顶元素，并将栈顶指针减 1
    return 1;  // 出栈成功
}

// 8. 读栈顶元素值
int Peek(Stack* stack, int* value) {
    if (IsEmpty(stack)) {  // 判断栈是否为空
        printf("栈空，无法读取栈顶元素\n");
        return 0;  // 读取失败
    }
    *value = stack->data[stack->top];  // 取栈顶元素
    return 1;  // 读取成功
}

// 打印栈的内容（辅助函数）
void PrintStack(Stack* stack) {
    if (IsEmpty(stack)) {
        printf("栈为空\n");
        return;
    }
    printf("栈中的元素是：");
    for (int i = 0; i <= stack->top; i++) {
        printf("%d ", stack->data[i]);
    }
    printf("\n");
}

// 主函数测试顺序栈操作
int main() {
    Stack stack;
    int value;

    InitStack(&stack);  // 初始化栈
    PrintStack(&stack);  // 输出：栈为空

    // 入栈操作
    Push(&stack, 10);
    Push(&stack, 20);
    Push(&stack, 30);
    PrintStack(&stack);  // 输出：栈中的元素是：10 20 30

    // 读取栈顶元素
    if (Peek(&stack, &value)) {
        printf("栈顶元素是：%d\n", value);  // 输出：栈顶元素是：30
    }

    // 出栈操作
    if (Pop(&stack, &value)) {
        printf("出栈元素是：%d\n", value);  // 输出：出栈元素是：30
    }
    PrintStack(&stack);  // 输出：栈中的元素是：10 20

    // 判断栈空和栈长
    printf("栈是否为空：%d\n", IsEmpty(&stack));  // 输出：栈是否为空：0
    printf("栈长：%d\n", StackLength(&stack));   // 输出：栈长：2

    // 清空栈
    ClearStack(&stack);
    PrintStack(&stack);  // 输出：栈为空

    // 销毁栈
    DestroyStack(&stack);

    return 0;
}

操作解释
初始化栈：设置栈顶指针 top 为 -1，表示栈为空。
判断栈空：检查栈顶指针是否为 -1。
求栈长：栈的长度就是栈顶指针加 1。
清空栈：将栈顶指针重置为 -1。
销毁栈：对于静态分配的栈，销毁操作不需要额外操作。若使用动态分配（malloc），则可以释放内存。
入栈：判断栈是否满，若未满，则将元素压入栈中并更新栈顶指针。
出栈：判断栈是否空，若不为空，取出栈顶元素并更新栈顶指针。
读栈顶元素值：判断栈是否空，若不为空，则读取栈顶元素。

顺序栈是通过数组实现的栈，主要使用一个栈顶指针 top 来标记栈顶元素的位置。
各种操作（如入栈、出栈、查看栈顶元素）都依赖于栈顶指针的更新。

栈的应用，递归

递归（Recursion）是一个函数通过直接或间接调用自身来解决问题。递归的核心在于将问题分解成较小的子问题，每次递归都处理一个更小的子问题，直到达到一个简单的基本情况（称为递归终止条件），然后逐步返回结果。
用实习阶层做个小例子

#include <stdio.h>

// 阶乘的递归实现
int factorial(int n) {
    if (n == 0) {
        return 1;  // 基本情况：0! = 1
    } else {
        return n * factorial(n - 1);  // 递归调用：n! = n * (n-1)!
    }
}

int main() {
    int num = 5;
    printf("%d! = %d\n", num, factorial(num));  // 输出：5! = 120
    return 0;
}

推荐联系题
https://www.luogu.com.cn/problem/B3623 // 递归实现排列型枚举
https://www.luogu.com.cn/problem/B3622 //递归实现指数型枚举
https://www.luogu.com.cn/problem/P10448 //组合型枚举

队列

重点是记住队列是先进先出的元素FIFO(first in first out)
队列的基本操作
初始化队列
判断队列是否为空
判断队列是否满
入队（enqueue）
出队（dequeue）
读取队头元素（front）
获取队列的长度
清空队列
销毁队列

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

#define MAX_SIZE 5  // 队列最大容量

// 队列结构体定义
typedef struct {
    int data[MAX_SIZE];  // 用数组来存储队列元素
    int front;           // 队头指针
    int rear;            // 队尾指针
} Queue;

// 1. 初始化队列
void InitQueue(Queue* queue) {
    queue->front = 0;   // 队头指针初始化为0
    queue->rear = 0;    // 队尾指针初始化为0
}

// 2. 判断队列是否为空
int IsEmpty(Queue* queue) {
    return queue->front == queue->rear;  // 队头指针和队尾指针相等表示队列为空
}

// 3. 判断队列是否满
int IsFull(Queue* queue) {
    return (queue->rear + 1) % MAX_SIZE == queue->front;  // 当队尾指针的下一个位置等于队头指针时，队列满
}

// 4. 入队操作
int Enqueue(Queue* queue, int value) {
    if (IsFull(queue)) {
        printf("队列已满，无法入队。\n");
        return 0;  // 入队失败
    }
    queue->data[queue->rear] = value;  // 将数据插入队列
    queue->rear = (queue->rear + 1) % MAX_SIZE;  // 队尾指针后移
    return 1;  // 入队成功
}

// 5. 出队操作
int Dequeue(Queue* queue, int* value) {
    if (IsEmpty(queue)) {
        printf("队列为空，无法出队。\n");
        return 0;  // 出队失败
    }
    *value = queue->data[queue->front];  // 获取队头元素
    queue->front = (queue->front + 1) % MAX_SIZE;  // 队头指针后移
    return 1;  // 出队成功
}

// 6. 读取队头元素
int Front(Queue* queue, int* value) {
    if (IsEmpty(queue)) {
        printf("队列为空，无法读取队头元素。\n");
        return 0;  // 读取失败
    }
    *value = queue->data[queue->front];  // 获取队头元素
    return 1;  // 读取成功
}

// 7. 获取队列长度
int QueueLength(Queue* queue) {
    return (queue->rear - queue->front + MAX_SIZE) % MAX_SIZE;  // 计算队列中的元素个数
}

// 8. 清空队列
void ClearQueue(Queue* queue) {
    queue->front = queue->rear = 0;  // 将队头和队尾指针重置为0
}

// 9. 销毁队列
void DestroyQueue(Queue* queue) {
    free(queue);  // 如果队列是动态分配的，使用free释放内存
    printf("队列已销毁。\n");
}

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

// 测试队列操作
int main() {
    Queue queue;
    int value;

    InitQueue(&queue);  // 初始化队列

    // 入队操作
    Enqueue(&queue, 10);
    Enqueue(&queue, 20);
    Enqueue(&queue, 30);
    Enqueue(&queue, 40);
    Enqueue(&queue, 50);  // 输出：队列已满，无法入队。
    PrintQueue(&queue);  // 输出：队列元素：10 20 30 40

    // 出队操作
    if (Dequeue(&queue, &value)) {
        printf("出队元素：%d\n", value);  // 输出：出队元素：10
    }
    PrintQueue(&queue);  // 输出：队列元素：20 30 40

    // 读取队头元素
    if (Front(&queue, &value)) {
        printf("队头元素是：%d\n", value);  // 输出：队头元素是：20
    }

    // 获取队列长度
    printf("队列长度：%d\n", QueueLength(&queue));  // 输出：队列长度：3

    // 清空队列
    ClearQueue(&queue);
    PrintQueue(&queue);  // 输出：队列为空。

    return 0;
}
//顺序队列是基于数组实现的，可以通过两个指针 front 和 rear 来维护队列状态。
//循环队列避免了数组头部空位的浪费，当队尾指针达到数组末尾时，自动回绕到数组开头。
//本实现通过循环队列的思想来保证队列操作的效率，并提供了常见的队列操作，如入队、出队、获取队头元素、清空队列等。

头尾相连的循环队列，可以充分利用空间