C语言线性表的链式表示及实现详解

什么是线性表

线性表是一种在计算机科学中常见的数据结构，它由一组连接在一起的元素组成，每个元素都包含前后指针以指向相邻的元素，从而构成一个连续的线性序列。线性表可以用来存储和处理一般数据集合。

链式存储结构

线性表的链式存储结构是由若干个结构体组成的链表，每个结构体都称为一个节点。每个节点包含两个字段：一个数据域用来存放数据元素，一个指针域指向下一个结点。

例如一个单链表的节点可以定义为：

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

其中 val 为数据域，next 为指针域，用于指向下一个节点。

初始化线性表

下面是一个初始化线性表（单链表）的示例代码：

ListNode* initList() {
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));  // 分配一个头结点
    head->next = NULL;  // 头结点指针域初始化为NULL
    return head;
}

这个函数返回头结点指针，头结点不存放数据。

插入元素

插入元素是对线性表进行修改的操作，其实现分为两个步骤：创建新节点和连接节点。

例如，在单链表中插入元素 x 时，需要新建一个节点将值 x 存放在数据域中，然后将新节点插入到目标节点 p 的后面。

void insertNode(ListNode* p, int x) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 创建新节点并存储值x
    node->val = x;
    node->next = p->next;  // newNode的下一个节点指针指向p的下一个节点
    p->next = node;  // p的下一个节点指向newNode
}

删除元素

删除元素时，需要找到待删结点之前的结点，修改待删结点之前的结点的指针域，使其跳过待删结点指向待删结点的下一个结点。

例如，在单链表中删除目标节点 p 时，需要找到目标节点之前的节点 pre，然后将 pre->next 指向 p->next。

void deleteNode(ListNode* p) {
    ListNode* pre = head;
    while(pre->next != p) pre = pre->next;  // 找到p之前的结点pre
    pre->next = p->next; // pre的下一个节点指向p的下一个节点
    free(p); // 释放p
}

示例说明

示例1

假设我们要实现一个班级名单的单链表，链表中的节点包含学生姓名和学生编号。可以用下列结构体来表示一个学生的信息：

typedef struct Student {
    char name[20];
    int id;
} Student;

我们可以定义一个函数来创建一个空的班级名单：

ListNode* initClass() {
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));  // 分配一个头结点
    head->next = NULL;  // 头结点指针域初始化为NULL
    return head;
}

我们可以创建一个名单，并在其中插入若干个学生信息：

ListNode* class = initClass();
Student stu1 = {"Alice", 10001};
Student stu2 = {"Bob", 10002};
Student stu3 = {"Charlie", 10003};
insertNode(class, &stu1);
insertNode(class, &stu2);
insertNode(class, &stu3);

插入完毕后，班级名单中包含了3个学生的信息。如果我们想要删除第二个学生的信息，可以使用下列代码：

deleteNode(class->next->next); // 删除第二个学生

示例2

假设我们要实现一个网页的浏览记录，我们可以用单链表存储URL和浏览时间。

我们可以定义一个下列结构体来表示一个浏览记录：

typedef struct WebPage {
    char url[100];
    time_t time;
} WebPage;

我们可以创建一个名单，并在其中插入若干个浏览记录：

ListNode* webHistory = initList();
WebPage page1 = {"http://www.baidu.com", time(NULL)};
WebPage page2 = {"http://www.google.com", time(NULL)};
WebPage page3 = {"http://www.github.com", time(NULL)};
insertNode(webHistory, &page1);
insertNode(webHistory, &page2);
insertNode(webHistory, &page3);

插入完毕后，网页浏览记录中包含了3个浏览记录。我们可以使用下列代码删除第二个浏览记录：

deleteNode(webHistory->next->next);

总结

这篇攻略详细介绍了C语言线性表的链式存储结构，以及对其进行初始化、插入元素、删除元素的操作方法。上面的示例代码展示了两个实例，为读者提供了更具体且实用的参考资料。