算法与数据结构c语言描述源代码

这份合集涵盖了从基础到核心的多种数据结构和算法,每个部分都包含：

1. 数据结构定义：如何用C语言的结构体和指针来表示数据。
2. 核心操作函数：如初始化、插入、删除、查找、遍历等。
3. 完整的示例代码：展示如何使用这些函数。
4. 复杂度分析：时间复杂度和空间复杂度的简要说明。

目录

1. [数据结构]
   • 1 [链表]
   • 2 [栈]
   • 3 [队列]
   • 4 [二叉树]
   • 5 [哈希表]
2. [算法]
   • 1 [排序算法]
     • 冒泡排序
     • 选择排序
     • 插入排序
     • 快速排序
     • 归并排序
   • 2 [查找算法]
     • 顺序查找
     • 二分查找
   • 3 [图算法]
     • 深度优先搜索
     • 广度优先搜索

数据结构

1 链表

链表是一种线性数据结构，元素（节点）在内存中不是连续存储的,每个节点包含数据和指向下一个节点的指针。

结构定义

#include <stdio.h>
#include <stdlib.h>
// 定义链表节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// 定义链表
typedef struct {
    Node* head;
    int size;
} LinkedList;

核心操作函数

// 初始化链表
void initList(LinkedList* list) {
    list->head = NULL;
    list->size = 0;
}
// 在链表头部插入节点
void insertAtHead(LinkedList* list, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = list->head;
    list->head = newNode;
    list->size++;
}
// 打印链表
void printList(LinkedList* list) {
    Node* current = list->head;
    printf("List: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
// 释放链表内存
void freeList(LinkedList* list) {
    Node* current = list->head;
    Node* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    list->head = NULL;
    list->size = 0;
}

完整示例

// 主函数示例
int main() {
    LinkedList list;
    initList(&list);
    insertAtHead(&list, 30);
    insertAtHead(&list, 20);
    insertAtHead(&list, 10);
    printList(&list); // 输出: List: 10 -> 20 -> 30 -> NULL
    freeList(&list);
    return 0;
}

复杂度分析

• insertAtHead: O(1)
• printList: O(n)
• freeList: O(n)

2 栈

栈是一种“后进先出”（LIFO）的数据结构,操作只在栈顶进行。

结构定义

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int top; // 栈顶指针
} Stack;

核心操作函数

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}
// 判断栈是否已满
int isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}
// 压栈
void push(Stack* s, int value) {
    if (isFull(s)) {
        printf("Stack Overflow!\n");
        return;
    }
    s->data[++s->top] = value;
}
// 弹栈
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack Underflow!\n");
        return -1; // 返回一个错误值
    }
    return s->data[s->top--];
}
// 查看栈顶元素
int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->data[s->top];
}

完整示例

int main() {
    Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("Top element: %d\n", peek(&s)); // 输出: 30
    printf("Popped element: %d\n", pop(&s)); // 输出: 30
    printf("Popped element: %d\n", pop(&s)); // 输出: 20
    printf("Top element: %d\n", peek(&s)); // 输出: 10
    return 0;
}

复杂度分析

• push, pop, peek: O(1)

3 队列

队列是一种“先进先出”（FIFO）的数据结构，元素在队尾加入,在队头移除。

结构定义 (使用数组实现循环队列)

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
    int size;
} Queue;

核心操作函数

void initQueue(Queue* q) {
    q->front = 0;
    q->rear = -1;
    q->size = 0;
}
int isQueueEmpty(Queue* q) {
    return q->size == 0;
}
int isQueueFull(Queue* q) {
    return q->size == MAX_SIZE;
}
void enqueue(Queue* q, int value) {
    if (isQueueFull(q)) {
        printf("Queue Overflow!\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->data[q->rear] = value;
    q->size++;
}
int dequeue(Queue* q) {
    if (isQueueEmpty(q)) {
        printf("Queue Underflow!\n");
        return -1;
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
    return value;
}

完整示例

int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Dequeued element: %d\n", dequeue(&q)); // 输出: 10
    printf("Dequeued element: %d\n", dequeue(&q)); // 输出: 20
    enqueue(&q, 40);
    printf("Dequeued element: %d\n", dequeue(&q)); // 输出: 30
    printf("Dequeued element: %d\n", dequeue(&q)); // 输出: 40
    return 0;
}

复杂度分析

• enqueue, dequeue: O(1)

4 二叉树

二叉树是每个节点最多有两个子节点的树结构。

结构定义

#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

核心操作函数

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// 先序遍历: 根 -> 左 -> 右
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);
}
// 释放树内存
void freeTree(TreeNode* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

完整示例

int main() {
    /*
        创建如下二叉树:
            1
           / \
          2   3
         / \
        4   5
    */
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Pre-order traversal: ");
    preOrderTraversal(root); // 输出: 1 2 4 5 3
    printf("\n");
    printf("In-order traversal: ");
    inOrderTraversal(root); // 输出: 4 2 5 1 3
    printf("\n");
    printf("Post-order traversal: ");
    postOrderTraversal(root); // 输出: 4 5 2 3 1
    printf("\n");
    freeTree(root);
    return 0;
}

复杂度分析

• 遍历操作: O(n),其中n是树中节点的数量。

5 哈希表

哈希表通过哈希函数将键映射到数组中的一个位置，以实现快速的插入、删除和查找,这里展示一个简单的分离链接法解决冲突的实现。

结构定义

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10
// 链表节点（用于解决冲突）
typedef struct HashNode {
    char key[50];
    int value;
    struct HashNode* next;
} HashNode;
// 哈希表
typedef struct {
    HashNode* buckets[TABLE_SIZE];
} HashTable;

核心操作函数

// 简单的哈希函数 (djb2算法)
unsigned long hashFunction(const char* str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash % TABLE_SIZE;
}
// 初始化哈希表
void initHashTable(HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->buckets[i] = NULL;
    }
}
// 插入键值对
void insert(HashTable* ht, const char* key, int value) {
    unsigned long index = hashFunction(key);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    strcpy(newNode->key, key);
    newNode->value = value;
    newNode->next = NULL;
    // 如果桶为空，直接插入
    if (ht->buckets[index] == NULL) {
        ht->buckets[index] = newNode;
    } else {
        // 否则，插入到链表头部
        newNode->next = ht->buckets[index];
        ht->buckets[index] = newNode;
    }
}
// 查找值
int search(HashTable* ht, const char* key) {
    unsigned long index = hashFunction(key);
    HashNode* current = ht->buckets[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    return -1; // 未找到
}
// 打印哈希表
void printHashTable(HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Bucket %d: ", i);
        HashNode* current = ht->buckets[i];
        while (current != NULL) {
            printf("(%s, %d) -> ", current->key, current->value);
            current = current->next;
        }
        printf("NULL\n");
    }
}

完整示例

int main() {
    HashTable ht;
    initHashTable(&ht);
    insert(&ht, "apple", 10);
    insert(&ht, "banana", 20);
    insert(&ht, "orange", 30);
    insert(&ht, "grape", 40);
    insert(&ht, "mango", 50);
    printHashTable(&ht);
    printf("Value of 'apple': %d\n", search(&ht, "apple")); // 输出: 10
    printf("Value of 'banana': %d\n", search(&ht, "banana")); // 输出: 20
    printf("Value of 'pear': %d\n", search(&ht, "pear")); // 输出: -1
    // 注意：实际应用中需要实现释放内存的函数
    return 0;
}

复杂度分析

• 平均情况: O(1) (假设哈希函数分布均匀)
• 最坏情况: O(n) (所有键都哈希到同一个桶,退化为链表查找)

算法

1 排序算法

1.1 快速排序

一种高效的分治排序算法。

#include <stdio.h>
// 交换两个整数的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1);      // i 是小于基准的元素的边界
    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++; // 扩展小于基准的元素的边界
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]); // 将基准放到正确的位置
    return (i + 1);
}
// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi 是分区索引，arr[pi] 现在在正确的位置
        int pi = partition(arr, low, high);
        // 递归排序分区
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: ");
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

复杂度分析

• 平均时间复杂度: O(n log n)
• 最坏时间复杂度: O(n²) (当数组已经有序或逆序时)
• 空间复杂度: O(log n) (由于递归调用栈)

1.2 归并排序

一种稳定的、分治的排序算法，时间复杂度稳定在 O(n log n)。

#include <stdio.h>
#include <stdlib.h>
// 合并两个已排序的子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    // 创建临时数组
    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));
    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    // 合并临时数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 拷贝剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
    free(L);
    free(R);
}
// 归并排序主函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 递归排序左右两半
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 合并已排序的两半
        merge(arr, left, mid, right);
    }
}
// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: ");
    printArray(arr, n);
    mergeSort(arr, 0, n - 1);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

复杂度分析

• 时间复杂度: O(n log n) (所有情况)
• 空间复杂度: O(n) (需要额外的临时数组)

2 查找算法

2.1 二分查找

要求数组必须是有序的,通过不断将搜索范围减半来查找目标值。

#include <stdio.h>
// 返回目标值在数组中的索引，如果未找到则返回-1
int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // 防止溢出
        // 如果目标值在中间，返回索引
        if (arr[mid] == target) {
            return mid;
        }
        // 如果目标值大于中间值，则在右半部分搜索
        else if (arr[mid] < target) {
            low = mid + 1;
        }
        // 如果目标值小于中间值，则在左半部分搜索
        else {
            high = mid - 1;
        }
    }
    // 未找到
    return -1;
}
int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 23;
    int result = binarySearch(arr, n, target);
    if (result == -1) {
        printf("Element %d not found in the array.\n", target);
    } else {
        printf("Element %d found at index %d.\n", target, result);
    }
    return 0;
}

复杂度分析

• 时间复杂度: O(log n)
• 空间复杂度: O(1)

3 图算法

图通常用邻接表表示,这里我们使用一个结构体数组来表示邻接表。

结构定义

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 邻接表节点
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;
// 邻接表
typedef struct AdjList {
    AdjListNode* head;
} AdjList;
// 图
typedef struct Graph {
    int V; // 顶点数
    AdjList* array;
} Graph;

3.1 深度优先搜索

使用栈（或递归）来遍历图。

// 创建新的邻接表节点
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}
// 创建图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));
    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }
    return graph;
}
// 添加边
void addEdge(Graph* graph, int src, int dest) {
    // 添加从 src 到 dest 的边
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
    // 对于无向图，添加反向边
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}
// DFS的辅助函数 (递归)
void DFSUtil(Graph* graph, int vertex, int visited[]) {
    visited[vertex] = 1;
    printf("%d ", vertex);
    AdjListNode* pCrawl = graph->array[vertex].head;
    while (pCrawl) {
        if (!visited[pCrawl->dest]) {
            DFSUtil(graph, pCrawl->dest, visited);
        }
        pCrawl = pCrawl->next;
    }
}
// DFS主函数
void DFS(Graph* graph, int startVertex) {
    int* visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = 0;
    }
    printf("DFS starting from vertex %d: ", startVertex);
    DFSUtil(graph, startVertex, visited);
    printf("\n");
    free(visited);
}

3.2 广度优先搜索

使用队列来遍历图。

#include "queue.h" // 需要前面定义的队列结构
// BFS主函数
void BFS(Graph* graph, int startVertex) {
    int* visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = 0;
    }
    Queue q;
    initQueue(&q);
    visited[startVertex] = 1;
    enqueue(&q, startVertex);
    printf("BFS starting from vertex %d: ", startVertex);
    while (!isQueueEmpty(&q)) {
        int currentVertex = dequeue(&q);
        printf("%d ", currentVertex);
        AdjListNode* pCrawl = graph->array[currentVertex].head;
        while (pCrawl) {
            if (!visited[pCrawl->dest]) {
                visited[pCrawl->dest] = 1;
                enqueue(&q, pCrawl->dest);
            }
            pCrawl = pCrawl->next;
        }
    }
    printf("\n");
    free(visited);
}

完整图算法示例

int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    DFS(graph, 0);
    BFS(graph, 0);
    // 释放图的内存 (这里省略，实际应用中需要实现)
    return 0;
}

复杂度分析

• DFS 和 BFS:
  • 时间复杂度: O(V + E), V 是顶点数，E 是边数。
  • 空间复杂度: O(V) (用于存储访问标记和栈/队列)。

如何学习和使用这些代码

1. 理解概念：在阅读代码前,确保你已经理解了数据结构或算法的基本原理。
2. 逐行分析：仔细阅读代码，特别是指针操作和内存管理部分,这是C语言的难点和重点。
3. 动手编译运行：将代码复制到你的C语言开发环境中（如GCC, Clang, Visual Studio Code + C/C++ 插件等），编译并运行,观察输出结果。
4. 修改和扩展：尝试修改参数、添加新的功能或用不同的方式实现同一个算法，你可以尝试用链表实现栈,或者用不同的哈希函数。
5. 调试：如果遇到问题，使用GDB等调试工具单步执行，观察变量值的变化,帮助你理解代码的执行流程。

这份合集为你提供了一个坚实的起点,希望这些源代码能帮助你更好地掌握C语言下的算法与数据结构！