数据结构是计算机科学的核心基础之一，它决定了数据的组织、存储和操作方式。在C语言中，我们可以通过指针和结构体等特性灵活地实现各种数据结构。本文将详细介绍三种基础数据结构——链表、栈和队列的C语言实现，包括它们的原理、实现方式以及应用场景。

一、链表(Linked List)

1.1 链表的基本概念

链表是一种线性数据结构，不同于数组的连续内存存储，链表中的元素（称为节点）通过指针链接在一起。每个节点包含两部分：

  • 数据域：存储实际数据

  • 指针域：存储指向下一个节点的地址

链表的优势在于可以动态地分配内存，不需要预先知道数据量的大小，插入和删除操作的时间复杂度为O(1)（在已知位置的情况下）。

1.2 单向链表的完整实现

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

// 链表节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// 在链表尾部插入节点
void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

// 删除节点
void deleteNode(Node** head, int data) {
    if (*head == NULL) return;
    
    if ((*head)->data == data) {
        Node* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    
    Node* current = *head;
    while (current->next != NULL && current->next->data != data) {
        current = current->next;
    }
    
    if (current->next != NULL) {
        Node* temp = current->next;
        current->next = current->next->next;
        free(temp);
    }
}

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

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

int main() {
    Node* head = NULL;
    
    insertAtTail(&head, 1);
    insertAtTail(&head, 2);
    insertAtTail(&head, 3);
    insertAtHead(&head, 0);
    
    printf("链表: ");
    printList(head);
    
    deleteNode(&head, 2);
    printf("删除2后的链表: ");
    printList(head);
    
    freeList(head);
    return 0;
}

1.3 链表的应用场景

链表特别适合以下场景：

  • 需要频繁插入和删除操作

  • 数据量不确定或经常变化

  • 不需要随机访问元素

  • 实现其他数据结构如栈、队列、哈希表等

二、栈(Stack)

2.1 栈的基本概念

栈是一种后进先出(LIFO)的数据结构，只允许在一端（称为栈顶）进行插入和删除操作。栈的基本操作包括：

  • Push：将元素压入栈顶

  • Pop：弹出栈顶元素

  • Peek/Top：查看栈顶元素但不弹出

2.2 基于数组的栈实现

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack* stack) {
    stack->top = -1;
}

bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

bool isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack* stack, int value) {
    if (isFull(stack)) {
        printf("栈已满，无法入栈\n");
        return;
    }
    stack->data[++stack->top] = value;
}

int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无法出栈\n");
        exit(1);
    }
    return stack->data[stack->top--];
}

int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空\n");
        exit(1);
    }
    return stack->data[stack->top];
}

int main() {
    Stack stack;
    initStack(&stack);
    
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    
    printf("栈顶元素: %d\n", peek(&stack));
    
    printf("出栈顺序: ");
    while (!isEmpty(&stack)) {
        printf("%d ", pop(&stack));
    }
    printf("\n");
    
    return 0;
}

2.3 基于链表的栈实现

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

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

typedef struct {
    StackNode* top;
} LinkedStack;

void initLinkedStack(LinkedStack* stack) {
    stack->top = NULL;
}

bool isEmpty(LinkedStack* stack) {
    return stack->top == NULL;
}

void push(LinkedStack* stack, int value) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}

int pop(LinkedStack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无法出栈\n");
        exit(1);
    }
    StackNode* temp = stack->top;
    int data = temp->data;
    stack->top = stack->top->next;
    free(temp);
    return data;
}

int peek(LinkedStack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空\n");
        exit(1);
    }
    return stack->top->data;
}

void freeStack(LinkedStack* stack) {
    while (!isEmpty(stack)) {
        pop(stack);
    }
}

int main() {
    LinkedStack stack;
    initLinkedStack(&stack);
    
    push(&stack, 100);
    push(&stack, 200);
    push(&stack, 300);
    
    printf("栈顶元素: %d\n", peek(&stack));
    
    printf("出栈顺序: ");
    while (!isEmpty(&stack)) {
        printf("%d ", pop(&stack));
    }
    printf("\n");
    
    return 0;
}

2.4 栈的应用场景

栈在计算机科学中有广泛应用：

  • 函数调用和递归实现

  • 表达式求值和语法分析

  • 括号匹配检查

  • 浏览器的前进后退功能

  • 内存管理中的调用栈

三、队列(Queue)

3.1 队列的基本概念

队列是一种先进先出(FIFO)的数据结构，允许在一端（队尾）插入元素，在另一端（队首）删除元素。基本操作包括：

  • Enqueue：将元素加入队尾

  • Dequeue：从队首移除元素

  • Front：查看队首元素但不移除

3.2 基于数组的循环队列实现

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

#define QUEUE_SIZE 5

typedef struct {
    int data[QUEUE_SIZE];
    int front;
    int rear;
} CircularQueue;

void initQueue(CircularQueue* queue) {
    queue->front = -1;
    queue->rear = -1;
}

bool isEmpty(CircularQueue* queue) {
    return queue->front == -1;
}

bool isFull(CircularQueue* queue) {
    return (queue->rear + 1) % QUEUE_SIZE == queue->front;
}

void enqueue(CircularQueue* queue, int value) {
    if (isFull(queue)) {
        printf("队列已满，无法入队\n");
        return;
    }
    
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    
    queue->rear = (queue->rear + 1) % QUEUE_SIZE;
    queue->data[queue->rear] = value;
}

int dequeue(CircularQueue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队\n");
        exit(1);
    }
    
    int value = queue->data[queue->front];
    
    if (queue->front == queue->rear) {
        queue->front = -1;
        queue->rear = -1;
    } else {
        queue->front = (queue->front + 1) % QUEUE_SIZE;
    }
    
    return value;
}

int front(CircularQueue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空\n");
        exit(1);
    }
    return queue->data[queue->front];
}

int main() {
    CircularQueue queue;
    initQueue(&queue);
    
    enqueue(&queue, 1);
    enqueue(&queue, 2);
    enqueue(&queue, 3);
    enqueue(&queue, 4);
    enqueue(&queue, 5);
    
    printf("队首元素: %d\n", front(&queue));
    
    printf("出队顺序: ");
    while (!isEmpty(&queue)) {
        printf("%d ", dequeue(&queue));
    }
    printf("\n");
    
    return 0;
}

3.3 基于链表的队列实现

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

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

typedef struct {
    QueueNode* front;
    QueueNode* rear;
} LinkedQueue;

void initLinkedQueue(LinkedQueue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

bool isEmpty(LinkedQueue* queue) {
    return queue->front == NULL;
}

void enqueue(LinkedQueue* queue, int value) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    
    if (isEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

int dequeue(LinkedQueue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队\n");
        exit(1);
    }
    
    QueueNode* temp = queue->front;
    int value = temp->data;
    
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    
    free(temp);
    return value;
}

int front(LinkedQueue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空\n");
        exit(1);
    }
    return queue->front->data;
}

void freeQueue(LinkedQueue* queue) {
    while (!isEmpty(queue)) {
        dequeue(queue);
    }
}

int main() {
    LinkedQueue queue;
    initLinkedQueue(&queue);
    
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    
    printf("队首元素: %d\n", front(&queue));
    
    printf("出队顺序: ");
    while (!isEmpty(&queue)) {
        printf("%d ", dequeue(&queue));
    }
    printf("\n");
    
    return 0;
}

3.4 队列的应用场景

队列在计算机科学中应用广泛：

  • CPU任务调度

  • 打印机任务队列

  • 消息队列系统

  • 广度优先搜索(BFS)算法

  • 网络数据包传输

四、三种数据结构的比较

特性 数组 链表 栈 队列
访问方式 随机访问 顺序访问 LIFO FIFO
插入/删除 O(n) O(1) O(1) O(1)
访问元素 O(1) O(n) 仅栈顶 仅队首/队尾
内存分配 静态 动态 均可 均可
内存使用 紧凑 额外指针 取决于实现 取决于实现

总结

本文详细介绍了C语言中三种基础数据结构——链表、栈和队列的实现方法。每种数据结构都有其特点和适用场景：

  1. 链表：适合频繁插入删除的场景，内存利用率高但访问效率较低

  2. 栈：后进先出特性，适合需要"撤销"操作的场景

  3. 队列：先进先出特性，适合任务调度等公平性场景

理解这些基础数据结构对于学习更复杂的算法和数据结构至关重要。在实际编程中，应根据具体需求选择合适的数据结构，有时还需要结合多种数据结构来解决复杂问题。

希望通过本文的介绍，读者能够掌握这些基础数据结构的C语言实现，并能在实际项目中灵活运用。

# 数据结构 # c语言 # 链表
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

avatar 魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。

avatar 魔乐社区
cover

小杰机器学习（seven）——贝叶斯分类

avatar 魔乐社区