游牧学院

9.2 位操作
9.4 C语言中的算法（排序、查找）

C语言中的数据结构：链表、栈、队列

在C语言中，数据结构是组织和存储数据的方式。掌握数据结构的使用对于编写高效的程序至关重要。本文将深入探讨三种基本的数据结构：链表、栈和队列。我们将讨论它们的定义、优缺点、实现方式以及使用场景。

1. 链表

1.1 定义

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的优点在于动态内存分配，能够灵活地增加或删除元素。

1.2 链表的类型

  • 单向链表：每个节点只指向下一个节点。
  • 双向链表：每个节点指向前一个和下一个节点。
  • 循环链表：最后一个节点指向第一个节点。

1.3 示例代码

以下是一个简单的单向链表的实现：

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

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

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表末尾插入节点
void append(struct Node** head_ref, int new_data) {
    struct Node* new_node = createNode(new_data);
    struct Node* last = *head_ref;

    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
}

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

// 主函数
int main() {
    struct Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    printList(head);
    return 0;
}

1.4 优缺点

优点：

  • 动态大小：可以根据需要动态增加或减少节点。
  • 插入和删除操作效率高：在已知位置时，插入和删除操作的时间复杂度为O(1)。

缺点：

  • 额外的内存开销：每个节点需要额外的指针存储空间。
  • 随机访问效率低：访问特定元素的时间复杂度为O(n)。

1.5 注意事项

  • 确保在使用完链表后释放内存，以避免内存泄漏。
  • 在插入和删除操作时，注意更新指针以保持链表的完整性。

2. 栈

2.1 定义

栈是一种后进先出（LIFO）的数据结构，元素的插入和删除都发生在同一端，称为栈顶。

2.2 示例代码

以下是一个简单的栈的实现：

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

#define MAX 100

// 栈结构
struct Stack {
    int top;
    int arr[MAX];
};

// 创建栈
struct Stack* createStack() {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->top = -1;
    return stack;
}

// 检查栈是否满
int isFull(struct Stack* stack) {
    return stack->top == MAX - 1;
}

// 检查栈是否空
int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

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

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

// 打印栈
void printStack(struct Stack* stack) {
    for (int i = stack->top; i >= 0; i--) {
        printf("%d\n", stack->arr[i]);
    }
}

// 主函数
int main() {
    struct Stack* stack = createStack();
    push(stack, 10);
    push(stack, 20);
    push(stack, 30);
    printStack(stack);
    printf("出栈元素: %d\n", pop(stack));
    printStack(stack);
    return 0;
}

2.3 优缺点

优点：

  • 简单易用：栈的操作简单，易于实现。
  • 适合递归：栈可以用于实现递归算法。

缺点：

  • 固定大小：使用数组实现的栈大小固定，可能导致溢出。
  • 不支持随机访问：只能访问栈顶元素。

2.4 注意事项

  • 在使用栈时，注意栈的溢出和下溢。
  • 可以使用链表实现动态大小的栈。

3. 队列

3.1 定义

队列是一种先进先出（FIFO）的数据结构，元素的插入发生在队尾，删除发生在队头。

3.2 示例代码

以下是一个简单的队列的实现：

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

#define MAX 100

// 队列结构
struct Queue {
    int front, rear;
    int arr[MAX];
};

// 创建队列
struct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = queue->rear = -1;
    return queue;
}

// 检查队列是否满
int isFull(struct Queue* queue) {
    return queue->rear == MAX - 1;
}

// 检查队列是否空
int isEmpty(struct Queue* queue) {
    return queue->front == -1 || queue->front > queue->rear;
}

// 入队
void enqueue(struct Queue* queue, int item) {
    if (isFull(queue)) {
        printf("队列满，无法入队\n");
        return;
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->arr[++queue->rear] = item;
}

// 出队
int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列空，无法出队\n");
        return -1;
    }
    return queue->arr[queue->front++];
}

// 打印队列
void printQueue(struct Queue* queue) {
    for (int i = queue->front; i <= queue->rear; i++) {
        printf("%d\n", queue->arr[i]);
    }
}

// 主函数
int main() {
    struct Queue* queue = createQueue();
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    printQueue(queue);
    printf("出队元素: %d\n", dequeue(queue));
    printQueue(queue);
    return 0;
}

3.3 优缺点

优点：

  • 简单易用：队列的操作简单，易于实现。
  • 适合任务调度：队列可以用于实现任务调度和资源管理。

缺点：

  • 固定大小：使用数组实现的队列大小固定，可能导致溢出。
  • 不支持随机访问：只能访问队头元素。

3.4 注意事项

  • 在使用队列时，注意队列的溢出和下溢。
  • 可以使用循环队列或链表实现动态大小的队列。

总结

链表、栈和队列是C语言中常用的数据结构，各自有其独特的优缺点和适用场景。理解这些数据结构的实现和使用方法，将有助于提高编程能力和解决问题的效率。在实际开发中，选择合适的数据结构可以显著提高程序的性能和可维护性。

9.2 位操作
9.4 C语言中的算法（排序、查找）