動态數組（Dynamic Array）

動态數組是一種可以自動調整大小的數組，具有可變長度。在C語言中，可以使用指針和記憶體動态配置設定函數（如malloc和realloc）實作動态數組。

以下是一個簡單的動态數組實作示例代碼：

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

typedef struct {
    int *arr;
    int size;
    int capacity;
} dynamic_array;

void init(dynamic_array *da, int capacity) {
    da->arr = (int *)malloc(capacity * sizeof(int));
    da->size = 0;
    da->capacity = capacity;
}

void append(dynamic_array *da, int value) {
    if (da->size == da->capacity) {
        da->capacity *= 2;
        da->arr = (int *)realloc(da->arr, da->capacity * sizeof(int));
    }
    da->arr[da->size++] = value;
}

void print(dynamic_array *da) {
    for (int i = 0; i < da->size; i++) {
        printf("%d ", da->arr[i]);
    }
    printf("\n");
}

int main() {
    dynamic_array da;
    init(&da, 10);
    append(&da, 1);
    append(&da, 2);
    append(&da, 3);
    print(&da);
    free(da.arr);
    return 0;
}

以上代碼中，動态數組通過結構體實作，其中arr指向實際存儲元素的數組，size表示目前數組中的元素個數，capacity表示數組最多可以容納的元素個數。init函數用于初始化動态數組，append函數用于在數組末尾添加元素，如果數組容量不足，則動态擴充數組容量。print函數用于列印數組中的元素。在程式結束前，需要釋放動态配置設定的記憶體。

連結清單（Linked List）

連結清單是一種常見的資料結構，它由一組節點組成，每個節點包含一個值和一個指向下一個節點的指針。在C語言中，可以通過定義結構體來實作連結清單。

以下是一個簡單的連結清單實作示例代碼：

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

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

void insert(node **head, int value) {
    node *new_node = (node *)malloc(sizeof(node));
    new_node->data = value;
    new_node->next = *head;
    *head = new_node;
}

void print(node *head) {
    while (head) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

int main() {
    node *head = NULL;
    insert(&head, 3);
    insert(&head, 2);
    insert(&head, 1);
    print(head);
    return 0;
}

以上代碼中，連結清單通過定義結構體來實作，其中data表示節點存儲的值，next表示指向下一個節點的指針。insert函數用于在連結清單頭部插入節點，print函數用于列印連結清單中的元素。在程式結束前，需要釋放動态配置設定的記憶體

棧（Stack）

棧是一種後進先出（LIFO）的資料結構，它可以通過數組或連結清單實作。在C語言中，可以使用數組實作棧。

以下是一個簡單的棧實作示例代碼：

#include <stdio.h>
#define MAX_SIZE 10

typedef struct {
    int arr[MAX_SIZE];
    int top;
} stack;

void init(stack *s) {
    s->top = -1;
}

void push(stack *s, int value) {
    if (s->top == MAX_SIZE - 1) {
        printf("Stack Overflow!\n");
        return;
    }
    s->arr[++s->top] = value;
}

int pop(stack *s) {
    if (s->top == -1) {
        printf("Stack Underflow!\n");
        return -1;
    }
    return s->arr[s->top--];
}

int peek(stack *s) {
    if (s->top == -1) {
        printf("Stack Underflow!\n");
        return -1;
    }
    return s->arr[s->top];
}

int main() {
    stack s;
    init(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", peek(&s));
    return 0;
}

以上代碼中，棧通過結構體實作，其中arr表示存儲棧元素的數組，top表示棧頂元素的下标。init函數用于初始化棧，push函數用于将元素入棧，如果棧已滿則報錯，pop函數用于将棧頂元素出棧，如果棧為空則報錯，peek函數用于檢視棧頂元素，但不将其出棧。在程式結束前，不需要顯式釋放記憶體。

隊列（Queue）

隊列是一種先進先出（FIFO）的資料結構，它也可以通過數組或連結清單實作。在C語言中，可以使用數組實作隊列。

以下是一個簡單的隊列實作示例代碼：

#include <stdio.h>
#define MAX_SIZE 10

typedef struct {
    int arr[MAX_SIZE];
    int front;
    int rear;
} queue;

void init(queue *q) {
    q->front = 0;
    q->rear = -1;
}

void enqueue(queue *q, int value) {
    if (q->rear == MAX_SIZE - 1) {
        printf("Queue Overflow!\n");
        return;
    }
    q->arr[++q->rear] = value;
}

int dequeue(queue *q) {
    if (q->front > q->rear) {
        printf("Queue Underflow!\n");
        return -1;
    }
    return q->arr[q->front++];
}

int peek(queue *q) {
    if (q->front > q->rear) {
        printf("Queue Underflow!\n");
        return -1;
    }
    return q->arr[q->front];
}

int main() {
    queue q;
    init(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printf("%d\n", dequeue(&q));
    printf("%d\n", peek(&q));
    return 0;
}

以上代碼中，隊列通過結構體實作，其中arr表示存儲隊列元素的數組，front和rear分别表示隊列頭和隊列尾元素的下标。init函數用于初始化隊列，enqueue函數用于将元素入隊，如果隊列已滿則報錯，dequeue函數用于将隊頭元素出隊，如果隊列為空則報錯，peek函數用于檢視隊頭元素，但不将其出隊。在程式結束前，不需要顯式釋放記憶體。

二叉樹（Binary Tree）

二叉樹是一種樹形結構，其中每個節點最多有兩個子節點，分别為左子節點和右子節點。在C語言中，可以使用結構體和指針實作二叉樹。

以下是一個簡單的二叉樹實作示例代碼：

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

typedef struct node {
    int value;
    struct node *left;
    struct node *right;
} node;

node *create_node(int value) {
    node *new_node = (node*) malloc(sizeof(node));
    new_node->value = value;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

void inorder_traversal(node *root) {
    if (root == NULL) {
        return;
    }
    inorder_traversal(root->left);
    printf("%d ", root->value);
    inorder_traversal(root->right);
}

int main() {
    node *root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);
    inorder_traversal(root);
    return 0;
}

以上代碼中，二叉樹通過結構體實作，其中value表示節點的值，left和right分别表示左子節點和右子節點。create_node函數用于建立新節點，并傳回指向該節點的指針。inorder_traversal函數用于中序周遊二叉樹，即先周遊左子樹，再周遊根節點，最後周遊右子樹。在程式結束前，需要顯式釋放二叉樹中所有節點的記憶體。

快速排序（Quick Sort）

快速排序是一種常用的排序算法，其基本思想是通過標明一個基準元素，将待排序序列劃分為兩個子序列，其中一個子序列的所有元素均小于等于基準元素，另一個子序列的所有元素均大于等于基準元素，然後對兩個子序列分别進行遞歸排序，最終将整個序列排序。

以下是一個簡單的快速排序實作示例代碼：

#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;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quick_sort(arr, low, pivot - 1);
        quick_sort(arr, pivot + 1, high);
    }
}

int main() {
    int arr[] = {5, 1, 9, 3, 7, 4, 8, 2, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    quick_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

以上代碼中，快速排序通過遞歸實作，其中partition函數用于選取基準元素，并将序列劃分為兩個子序列。具體地，選擇最右邊的元素為基準元素，使用i和j兩個指針掃描整個序列，若arr[j]小于基準元素，則将其與arr[i+1]交換，并将i加1，最終将基準元素交換到i+1處。quick_sort函數用于遞歸排序子序列，直到整個序列有序。在程式結束前，不需要顯式釋放記憶體。

廣度優先搜尋（Breadth-First Search）

廣度優先搜尋是一種圖周遊算法，其基本思想是從圖中某個頂點開始，依次通路其所有鄰居節點，然後再通路鄰居節點的所有鄰居節點，直到圖中所有節點都被通路為止。在C語言中，可以使用隊列實作廣度優先搜尋。

以下是一個簡單的廣度優先搜尋實作示例代碼：

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

#define MAX_N 100  // 最大節點數

// 鄰接表結點
typedef struct node {
    int val;
    struct node* next;
} Node;

// 鄰接表
typedef struct graph {
    Node* head[MAX_N];
    int n;  // 節點總數
} Graph;

// 隊列結構體
typedef struct queue {
    int data[MAX_N];
    int head, tail;
} Queue;

// 初始化鄰接表
void init(Graph* G, int n) {
    G->n = n;
    for (int i = 0; i < n; i++) {
        G->head[i] = NULL;
    }
}

// 添加無向邊
void add_edge(Graph* G, int u, int v) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = v;
    node->next = G->head[u];
    G->head[u] = node;

    node = (Node*)malloc(sizeof(Node));
    node->val = u;
    node->next = G->head[v];
    G->head[v] = node;
}

// 初始化隊列
void init_queue(Queue* Q) {
    Q->head = Q->tail = 0;
}

// 入隊
void enqueue(Queue* Q, int val) {
    Q->data[Q->tail++] = val;
}

// 出隊
int dequeue(Queue* Q) {
    return Q->data[Q->head++];
}

// 判斷隊列是否為空
int is_empty(Queue* Q) {
    return Q->head == Q->tail;
}

// 廣度優先搜尋
void bfs(Graph* G, int start) {
    Queue Q;
    int visited[MAX_N] = {0};  // 标記是否已通路過
    init_queue(&Q);
    enqueue(&Q, start);
    visited[start] = 1;

    while (!is_empty(&Q)) {
        int cur = dequeue(&Q);
        printf("%d ", cur);

        Node* p = G->head[cur];
        while (p != NULL) {
            if (!visited[p->val]) {
                visited[p->val] = 1;
                enqueue(&Q, p->val);
            }
            p = p->next;
        }
    }
}

// 主函數
int main() {
    Graph G;
    int n, m;  // n為節點數，m為邊數
    scanf("%d%d", &n, &m);
    init(&G, n);

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(&G, u, v);
    }

    bfs(&G, 0);  // 從0節點開始進行廣度優先搜尋

    return 0;
}

以上是一個使用鄰接表實作的BFS示例代碼，其中使用了一個隊列結構體，用于存儲需要進行擴充的節點。首先将起始節點加入隊列中，并标記為已通路過，然後不斷從隊列中取出一個節點，将其相連的未通路過的鄰居節點加入隊列，直到隊列為空為止。這樣周遊的過程就是一個層層擴充的過程，是以BFS也被稱為“寬度優先搜尋”。

上面的代碼實作了一個簡單的BFS算法，它可以接受從标準輸入讀入的圖的描述，以及起始節點，然後列印出從起始節點開始的BFS周遊結果。其中，節點使用0~n-1的整數表示，圖的描述使用每行兩個整數u和v表示一條無向邊。

二叉查找樹（Binary Search Tree）

二叉查找樹是一種基于二分查找的資料結構，它具有以下性質：

左子樹上所有節點的值均小于它的根節點的值
右子樹上所有節點的值均大于它的根節點的值
左右子樹都是二叉查找樹

以下是一個簡單的二叉查找樹實作示例代碼：

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

typedef struct node {
    int value;
    struct node *left;
    struct node *right;
} Node;

void insert(Node **root, int value) {
    if (*root == NULL) {
        *root = (Node*)malloc(sizeof(Node));
        (*root)->value = value;
        (*root)->left = NULL;
        (*root)->right = NULL;
    } else {
        if (value < (*root)->value) {
            insert(&((*root)->left), value);
        } else {
            insert(&((*root)->right), value);
        }
    }
}

void inorder_traversal(Node *root) {
    if (root != NULL) {
        inorder_traversal(root->left);
        printf("%d ", root->value);
        inorder_traversal(root->right);
    }
}

int main() {
    Node *root = NULL;
    insert(&root, 5);
    insert(&root, 3);
    insert(&root, 7);
    insert(&root, 1);
    insert(&root, 4);
    insert(&root, 6);
    insert(&root, 8);
    inorder_traversal(root);
    return 0;
}

以上代碼中，二叉查找樹使用遞歸實作。insert函數用于向二叉查找樹中插入一個節點，若目前節點為空，則将新節點插入；否則，根據目前節點的值和待插入節點的值大小關系，遞歸調用insert函數。inorder_traversal函數用于中序周遊二叉查找樹，即先周遊左子樹，然後通路根節點，最後周遊右子樹。在程式結束前，需要顯式釋放記憶體。

哈希表（Hash Table）

哈希表是一種基于哈希函數實作的資料結構，它具有快速查找和插入的特點。在C語言中，可以使用數組和連結清單來實作哈希表。

以下是一個簡單的哈希表實作示例代碼：

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

#define TABLE_SIZE 10

typedef struct node {
    int key;
    int value;
    struct node *next;
} Node;

Node *hash_table[TABLE_SIZE];

int hash(int key) {
    return key % TABLE_SIZE;
}

void insert(int key, int value) {
    int index = hash(key);
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->key = key;
    new_node->value = value;
    new_node->next = NULL;
    if (hash_table[index] == NULL) {
        hash_table[index] = new_node;
    } else {
        Node *current = hash_table[index];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
    }
}

int search(int key) {
    int index = hash(key);
    Node *current = hash_table[index];
    while (current != NULL) {
        if (current->key == key) {
            return current->value;
        }
        current = current->next;
    }
    return -1;
}

int main() {
    insert(1, 10);
    insert(11, 20);
    insert(21, 30);
    printf("%d\n", search(1));
    printf("%d\n", search(11));
    printf("%d\n", search(21));
    return 0;
}

以上代碼中，哈希表使用連結清單解決哈希沖突，每個連結清單節點包含一個鍵值對。hash函數用于計算鍵值對應的哈希值，insert函數用于向哈希表中插入一個鍵值對，若目前位置為空，則直接插入；否則，将新節點插入到連結清單末尾。search函數用于在哈希表中查找指定鍵值的值，若存在則傳回其值，否則傳回-1。

這些常用的C語言資料結構、算法和功能代碼示例，涵蓋了常見的資料結構和算法，能夠滿足許多實際應用的需求。需要注意的是，在實際使用時，需要根據具體情況進行優化和改進，以适應不同的應用場景。

9個常用資料結構與算法的C語言代碼實作

動态數組（Dynamic Array）

連結清單（Linked List）

棧（Stack）

隊列（Queue）

二叉樹（Binary Tree）

快速排序（Quick Sort）

廣度優先搜尋（Breadth-First Search）

二叉查找樹（Binary Search Tree）

哈希表（Hash Table）

繼續閱讀

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

基礎算法之二分查找

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

poj3249

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

PAT 1089 Insert or Merge[難]

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器