王剑编程网

分享专业编程知识与实战技巧

2025年03月29日

9个常用数据结构与算法的C语言代码实现

动态数组（Dynamic Array）

动态数组是一种可以自动调整大小的数组，具有可变长度。在C语言中，可以使用指针和内存动态分配函数（如malloc和realloc）实现动态数组。

以下是一个简单的动态数组实现示例代码：

#include 
#include 

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 
#include 

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 
#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 
#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 
#include 

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 

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 
#include 

#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 
#include 

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 
#include 

#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语言数据结构、算法和功能代码示例，涵盖了常见的数据结构和算法，能够满足许多实际应用的需求。需要注意的是，在实际使用时，需要根据具体情况进行优化和改进，以适应不同的应用场景。

标签：c语言代码大全 

作者:ggcool , 分类:技术教程 , 浏览:4 , 评论:0

控制面板
您好，欢迎到访网站！
  查看权限
网站分类
最新留言