白骑士的C语言教学高级篇 3.2 高级数据结构

系列目录

上一篇：白骑士的C语言教学高级篇 3.1 高级指针技术

在计算机科学中，数据结构是组织和存储数据的方式，不同的数据结构适用于不同的问题和算法。本节将介绍链表、栈与队列以及树与图，这些高级数据结构在实际编程中非常常用，并且是许多复杂算法的基础。

链表

链表是一种线性数据结构，其中的元素存储在节点中，每个节点包含数据和一个指向下一个节点的指针。链表的优点是插入和删除操作非常高效，但缺点是访问元素的时间复杂度较高，因为需要从头节点开始逐个遍历。

单向链表

只有一个方向的指针，指向下一个节点，例如：

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


typedef struct Node {
    int data;

    struct Node *next;
} Node;


void append(Node **head, int data) {
    Node *new_node = (Node *)malloc(sizeof(Node));

    new_node->data = data;
    new_node->next = NULL;

    if (*head == NULL) {
        *head = new_node;
    } 

    else {
        Node *temp = *head;

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

        temp->next = new_node;
    }
}


void printList(Node *head) {
    while (head != NULL) {
        printf("%d -> ", head->data);

        head = head->next;
    }

    printf("NULL\n");
}


int main() {
    Node *head = NULL;

    append(&head, 1);
    append(&head, 2);
    append(&head, 3);

    printList(head);

    return 0;
}

双向链表

具有两个方向的指针，分别指向前一个节点和后一个节点，例如：

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


typedef struct Node {
    int data;

    struct Node *prev;
    struct Node *next;
} Node;


void append(Node **head, int data) {
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;

    if (*head == NULL) {
        new_node->prev = NULL;

        *head = new_node;
    } 

    else {
        Node *temp = *head;

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

        temp->next = new_node;

        new_node->prev = temp;
    }
}


void printList(Node *head) {
    while (head != NULL) {
        printf("%d -> ", head->data);

        head = head->next;
    }

    printf("NULL\n");
}


int main() {
    Node *head = NULL;

    append(&head, 1);
    append(&head, 2);
    append(&head, 3);

    printList(head);

    return 0;
}

栈与队列

栈

栈（Stack）是一种后进先出（LIFO，Last In First Out）的数据结构，栈的操作主要有两个：‘push‘（入栈）和 ‘pop‘（出栈）。例如：

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


#define MAX 100


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


void push(Stack *stack, int value) {
    if (stack->top < MAX - 1) {
        stack->data[++stack->top] = value;
    } 

    else {
        printf("Stack overflow\n");
    }
}


int pop(Stack *stack) {
    if (stack->top >= 0) {
        return stack->data[stack->top--];
    } 

    else {
        printf("Stack underflow\n");

        return -1;
    }
}


int main() {
    Stack stack;
    stack.top = -1;

    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    printf("Popped: %d\n", pop(&stack));
    printf("Popped: %d\n", pop(&stack));

    return 0;
}

队列

队列（Queue）是一种先进先出（FIFO，First In First Out）的数据结构，队列的操作主要有两个：‘enqueue‘（入队）和 ‘dequeue‘（出队）。例如：

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


#define MAX 100


typedef struct Queue {
    int data[MAX];
    int front;
    int rear;
} Queue;


void enqueue(Queue *queue, int value) {
    if (queue->rear < MAX - 1) {
        queue->data[++queue->rear] = value;

        if (queue->front == -1) {
            queue->front = 0;
        }
    } 

    else {
        printf("Queue overflow\n");
    }
}


int dequeue(Queue *queue) {
    if (queue->front > queue->rear || queue->front == -1) {
        printf("Queue underflow\n");

        return -1;
    } 

    else {
        return queue->data[queue->front++];
    }
}


int main() {
    Queue queue;
    queue.front = -1;
    queue.rear = -1;

    enqueue(&queue, 1);
    enqueue(&queue, 2);
    enqueue(&queue, 3);

    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));

    return 0;
}

树与图

树

树（Tree）是一种层次数据结构，树中的每个节点包含一个数据元素和指向子节点的指针。树的典型应用包括二叉树、二叉搜索树（BST）等。

二叉树是一种特殊的树结构，每个节点最多有两个子节点，例如：

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


typedef struct Node {
    int data;

    struct Node *left;
    struct Node *right;
} Node;


Node* createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}


void inorderTraversal(Node *root) {
    if (root != NULL) {
        inorderTraversal(root->left);

        printf("%d -> ", root->data);

        inorderTraversal(root->right);
    }
}


int main() {
    Node *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Inorder Traversal: ");

    inorderTraversal(root);

    printf("NULL\n");

    return 0;
}

图

图（Graph）是一种更复杂的数据结构，由节点（顶点）和边组成。图可以是有向图或无向图，应用广泛，如社交网络、交通网络等。

邻接矩阵表示法是图的一种表示方法，例如：

#include <stdio.h>


#define MAX 5


void addEdge(int graph[MAX][MAX], int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;  // 如果是无向图
}


void printGraph(int graph[MAX][MAX]) {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            printf("%d ", graph[i][j]);
        }

        printf("\n");
    }
}


int main() {
    int graph[MAX][MAX] = {0};

    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);

    printGraph(graph);

    return 0;
}