C数据结构之单链表详细示例分析

介绍

在C和数据结构中，单链表是一个非常有用的数据结构，可以用来存储一个列表的元素。单链表由节点构成，每个节点包含一个指向下一个节点的指针和一个存储数据的值。本文将详细介绍单链表的各个方面，包括创建、插入、删除和遍历节点。同时提供两个实际的应用例子：一个是使用单链表实现的简单画图程序，另一个是使用单链表实现的简单图书馆管理系统。

创建单链表

单链表的创建过程包括两个主要步骤：申请空间和初始化指针。具体过程如下：

struct Node {
    int data;
    struct Node* next;
}

struct Node* createNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

struct Node* createList(int* data, int n) {
    struct Node* head = createNode(data[0]);
    struct Node* tail = head;
    for (int i = 1; i < n; i++) {
        struct Node* node = createNode(data[i]);
        tail->next = node;
        tail = node;
    }
    return head;
}

上面的代码中，首先定义了每个节点的结构体，并利用malloc函数申请空间来存储节点的数据和指针，然后通过初始化指针，将节点组装成链表。其中，createNode函数创建一个新的节点，createList函数创建新的链表，其中data是存储的数据，n是节点的数目，head是指向链表头节点的指针，tail是当前尾节点的指针。

例如，创建一个包含5个元素的链表：

int a[5] = { 1, 2, 3, 4, 5 };
struct Node* head = createList(a, 5);

插入节点

在单链表中插入一个新节点，需要考虑两个主要问题：插入位置和插入元素。一般来说，插入位置可以分为两种情况：在链表头插入和在链表中间或尾部插入。具体插入代码如下：

struct Node* insertAtHead(struct Node* head, int data) {
    struct Node* node = createNode(data);
    node->next = head;
    return node;
}

struct Node* insertAtTail(struct Node* head, int data) {
    struct Node* node = createNode(data);
    if (head == NULL) {
        return node;
    }
    struct Node* p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = node;
    return head;
}

struct Node* insertAtIndex(struct Node* head, int index, int data) {
    struct Node* node = createNode(data);
    if (head == NULL) {
        return node;
    }
    if (index == 0) {
        node->next = head;
        return node;
    }
    struct Node* p = head;
    int i = 0;
    while (p != NULL && i < index-1) {
        p = p->next;
        i++;
    }
    if (p == NULL) {
        return head;
    }
    node->next = p->next;
    p->next = node;
    return head;
}

上述代码中，insertAtHead函数在单链表头部插入节点，insertAtTail函数在单链表尾部插入节点，insertAtIndex函数插入到指定位置。其中，head是指向链表头节点的指针，data是存储的数据，index是插入的位置。如果head为空，则创建新的头节点并返回。

例如，在单链表的尾部插入一个新节点：

int a[5] = { 1, 2, 3, 4, 5 };
struct Node* head = createList(a, 5);
head = insertAtTail(head, 6);

删除节点

在单链表中删除节点，同样需要考虑两个主要问题：删除位置和删除元素。一般来说，删除位置可以分为两种情况：删除第一个节点和删除中间或尾部节点。具体删除代码如下：

struct Node* deleteAtHead(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    struct Node* p = head->next;
    free(head);
    return p;
}

struct Node* deleteAtIndex(struct Node* head, int index) {
    if (head == NULL) {
        return NULL;
    }
    if (index == 0) {
        struct Node* p = head->next;
        free(head);
        return p;
    }
    struct Node* p = head;
    int i=0;
    while (p != NULL && i < index-1) {
        p = p->next;
        i++;
    }
    if (p == NULL || p->next == NULL) {
        return head;
    }
    struct Node* q = p->next->next;
    free(p->next);
    p->next = q;
    return head;
}

上述代码中，deleteAtHead函数删除单链表的头节点，deleteAtIndex函数删除指定位置的节点。其中，head是指向链表头节点的指针，index是删除的位置。如果head为空，则返回NULL。

例如，从单链表中删除第4个节点：

int a[5] = { 1, 2, 3, 4, 5 };
struct Node* head = createList(a, 5);
head = deleteAtIndex(head, 3);

遍历节点

遍历节点是指访问单链表中所有节点的数据。通常，需要遍历所有节点来完成某些任务，比如输出单链表的所有元素，或者查找单链表中的某个元素。具体遍历代码如下：

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

上述代码中，printList函数输出整个链表的所有元素。其中，head是指向链表头节点的指针。

例如，输出单链表的所有元素：

int a[5] = { 1, 2, 3, 4, 5 };
struct Node* head = createList(a, 5);
printList(head);

示例应用一：使用单链表实现的简单画图程序

这是一个基于单链表实现的简单画图程序，可以支持插入、删除和遍历节点。每个节点包含一个值，此程序使用了结构体作为节点（即“图形”）。程序实现的所有操作都是简单的链表操作，并且完全可扩展。

#include <stdio.h>
#include <stdlib.h>
struct Shape {
    int type;
    int x;
    int y;
    int w;
    int h;
    struct Shape* next;
};
struct Shape* createShape(int type, int x, int y, int w, int h) {
    struct Shape* shape = (struct Shape*)malloc(sizeof(struct Shape));
    shape->type = type;
    shape->x = x;
    shape->y = y;
    shape->w = w;
    shape->h = h;
    shape->next = NULL;
    return shape;
}
struct Shape* insertShape(struct Shape* head, struct Shape* shape) {
    if (head == NULL) {
        return shape;
    }
    struct Shape* p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = shape;
    return head;
}
struct Shape* deleteShape(struct Shape* head, struct Shape* shape) {
    if (head == shape) {
        struct Shape* next = head->next;
        free(head);
        return next;
    }
    struct Shape* p = head;
    while (p->next != NULL) {
        if (p->next == shape) {
            p->next = shape->next;
            free(shape);
            return head;
        }
        p = p->next;
    }
    return head;
}
void printShapes(struct Shape* head) {
    struct Shape* p = head;
    while (p != NULL) {
        printf("%d (%d,%d,%d,%d)\n", p->type, p->x, p->y, p->w, p->h);
        p = p->next;
    }
}

上述代码实现了createShape函数创建一个新的图形，insertShape函数插入一个新的图形节点，deleteShape函数删除一个图形节点，printShapes函数遍历节点并输出所有图形的信息。此示例仅用于演示链表的操作方式。

示例应用二：使用单链表实现的简单图书馆管理系统

这是一个基于单链表实现的图书馆管理系统，可以支持插入、删除和遍历节点。每个节点包含一个值，此程序使用了结构体作为节点（即“图书”）。程序实现的所有操作都是简单的链表操作，并且完全可扩展。

#include <stdio.h>
#include <stdlib.h>
struct Book {
    int id;
    char* title;
    char* author;
    struct Book* next;
};
struct Book* createBook(int id, char* title, char* author) {
    struct Book* book = (struct Book*)malloc(sizeof(struct Book));
    book->id = id;
    book->title = title;
    book->author = author;
    book->next = NULL;
    return book;
}
struct Book* insertBook(struct Book* head, struct Book* book) {
    if (head == NULL) {
        return book;
    }
    struct Book* p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = book;
    return head;
}
struct Book* deleteBook(struct Book* head, int id) {
    if (head == NULL) {
        return NULL;
    }
    if (head->id == id) {
        struct Book* next = head->next;
        free(head);
        return next;
    }
    struct Book* p = head;
    while (p->next != NULL) {
        if (p->next->id == id) {
            struct Book* q = p->next->next;
            free(p->next);
            p->next = q;
            return head;
        }
        p = p->next;
    }
    return head;
}
void printBooks(struct Book* head) {
    struct Book* p = head;
    while (p != NULL) {
        printf("%d (%s,%s)\n", p->id, p->title, p->author);
        p = p->next;
    }
}

上述代码实现了createBook函数创建一个新的图书信息，insertBook函数插入一个新的图书信息节点，deleteBook函数删除一个图书信息节点，printBooks函数遍历节点并输出所有图书信息。此示例仅用于演示链表的操作方式。

结论

单链表是C语言中非常有用的数据结构，可以用于存储各种类型的元素。本文提供了单链表的一些基本操作，包括创建、插入、删除和遍历节点。此外，本文还提供了两个简单的实例应用，可以轻松地扩展和修改以实现各种其他应用。