数据结构算法（C语言）

目录

排序

冒泡排序

快速排序

插入排序

选择排序

归并排序

希尔排序

堆排序

排序

冒泡排序

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

快速排序

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 分区操作
        int pivot = partition(arr, low, high);
        
        // 递归排序两部分
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 交换 arr[i+1] 和 arr[high]
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    
    return i + 1;
}

插入排序

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // 将比key大的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        // 插入key
        arr[j+1] = key;
    }
}

选择排序

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        // 找到最小元素的位置
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 交换最小元素和当前元素
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

归并排序

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // 计算中间点
        int m = l + (r - l) / 2;
        
        // 递归排序左右两部分
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        
        // 合并已排序的两部分
        merge(arr, l, m, r);
    }
}

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    
    // 创建临时数组
    int L[n1], R[n2];
    
    // 复制数据到临时数组
    for (i = 0; i < n1; i++) L[i] = arr[l + i];
    for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    
    // 合并临时数组回原数组
    i = 0; j = 0; k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // 复制剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

希尔排序

void shellSort(int arr[], int n) {
    // 初始增量为n/2，逐渐减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个增量进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            // 对相隔gap的元素进行比较和移动
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            // 插入temp
            arr[j] = temp;
        }
    }
}

堆排序

void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 一个个从堆中取出元素
    for (int i = n - 1; i > 0; i--) {
        // 交换堆顶(最大值)和当前元素
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        // 重新调整堆
        heapify(arr, i, 0);
    }
}

void heapify(int arr[], int n, int i) {
    int largest = i;    // 初始化根
    int l = 2 * i + 1;  // 左子节点
    int r = 2 * i + 2;  // 右子节点
    
    // 如果左子节点比根大
    if (l < n && arr[l] > arr[largest]) {
        largest = l;
    }
    
    // 如果右子节点比根大
    if (r < n && arr[r] > arr[largest]) {
        largest = r;
    }
    
    // 如果最大的不是根
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        
        // 递归调整受影响的子树
        heapify(arr, n, largest);
    }
}

查找

在一棵树中找到一个字符，输出查找时经过的结点序列

链表

合并两个有序单链表

Node* mergeLists(Node* l1, Node* l2) {
    // 创建虚拟头节点，避免处理空链表的边界情况
    Node dummy = {0, NULL};
    // 尾指针始终指向新链表的最后一个节点
    Node* tail = &dummy;

    // 同时遍历两个链表，直到其中一个遍历完
    while (l1 && l2) {
        // 比较当前节点值，选择较小的节点接入新链表
        if (l1->data < l2->data) {
            tail->next = l1;      // 将l1接入新链表
            l1 = l1->next;        // l1指针后移
        } else {
            tail->next = l2;      // 将l2接入新链表
            l2 = l2->next;        // l2指针后移
        }
        tail = tail->next;        // 尾指针后移
    }

    // 处理剩余节点：直接将非空链表的剩余部分接入新链表尾部
    tail->next = l1 ? l1 : l2;

    // 返回虚拟头节点的下一个节点，即合并后链表的头节点
    return dummy.next;
}

数组

合并两个有序数组

void mergeArrays(int* arr1, int m, int* arr2, int n) {
    // i指向arr1的有效元素末尾（从m-1开始）
    int i = m - 1;
    // j指向arr2的末尾（从n-1开始）
    int j = n - 1;
    // k指向合并后数组的末尾（总长度m+n-1）
    int k = m + n - 1;

    // 从后向前遍历两个数组，将较大元素放入合并位置
    while (i >= 0 && j >= 0) {
        if (arr1[i] > arr2[j]) {
            // arr1的当前元素更大，放入k位置
            arr1[k] = arr1[i];
            i--;  // 移动arr1的指针
        } else {
            // arr2的当前元素更大或相等，放入k位置
            arr1[k] = arr2[j];
            j--;  // 移动arr2的指针
        }
        k--;  // 合并位置指针前移
    }

    // 处理arr2中可能剩余的元素（arr1剩余元素无需处理，已在正确位置）
    while (j >= 0) {
        arr1[k] = arr2[j];  // 将arr2剩余元素复制到arr1前面
        j--;
        k--;
    }
}

有序数组倒置

void reverseArray(int* arr, int n) {
    int left = 0;           // 左指针初始化为数组起始位置
    int right = n - 1;      // 右指针初始化为数组末尾位置
    
    while (left < right) {  // 当左指针小于右指针时循环
        // 交换左右指针所指元素
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        
        left++;             // 左指针右移
        right--;            // 右指针左移
    }
}

树

判断二叉树是否为二叉搜索树

bool isBST(Node* root, Node* min, Node* max) {
    if (root == NULL) return true;  // 空树是BST
    
    // 检查当前节点是否在(min, max)范围内
    if ((min != NULL && root->data <= min->data) || 
        (max != NULL && root->data >= max->data)) {
        return false;
    }
    
    // 递归检查左右子树：左子树<root<右子树
    return isBST(root->left, min, root) && 
           isBST(root->right, root, max);
}

// 调用示例
bool checkBST(Node* root) {
    return isBST(root, NULL, NULL);
}

栈

#define MAX_SIZE 100

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

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;         // 空栈的栈顶指针为-1
}

// 判断栈是否为空
bool isEmpty(Stack* s) {
    return s->top == -1;
}

// 判断栈是否已满
bool isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈操作
bool push(Stack* s, int value) {
    if (isFull(s)) return false;  // 栈满则操作失败
    s->data[++(s->top)] = value;  // 先移动栈顶指针，再存入值
    return true;
}

// 出栈操作
bool pop(Stack* s, int* value) {
    if (isEmpty(s)) return false;  // 栈空则操作失败
    *value = s->data[(s->top)--];  // 先取出值，再移动栈顶指针
    return true;
}

// 获取栈顶元素
bool peek(Stack* s, int* value) {
    if (isEmpty(s)) return false;  // 栈空则操作失败
    *value = s->data[s->top];      // 仅获取值，不移动指针
    return true;
}

括号匹配

bool isValid(char* s) {
    Stack stack;
    init(&stack);
    
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            push(&stack, c);  // 左括号入栈
        } else {
            int top;
            if (!pop(&stack, &top)) return false;  // 栈空则匹配失败
            if ((c == ')' && top != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) {
                return false;  // 括号类型不匹配
            }
        }
    }
    
    return isEmpty(&stack);  // 栈空表示所有括号匹配成功
}

用两个栈实现队列

typedef struct {
    Stack s1, s2;  // s1用于入队，s2用于出队
} MyQueue;

// 初始化队列
MyQueue* myQueueCreate() {
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    init(&q->s1);
    init(&q->s2);
    return q;
}

// 入队操作
void myQueuePush(MyQueue* q, int x) {
    push(&q->s1, x);
}

// 出队操作
int myQueuePop(MyQueue* q) {
    if (isEmpty(&q->s2)) {
        while (!isEmpty(&q->s1)) {
            int val;
            pop(&q->s1, &val);
            push(&q->s2, val);
        }
    }
    int val;
    pop(&q->s2, &val);
    return val;
}