C语言数据结构之单链表存储详解

什么是单链表

链表是一种非顺序存储的数据结构，其每个节点都保存下一个节点的地址。单链表是最简单的链表，每个节点只包含下一个节点的地址。

单链表节点的定义

单链表的节点定义一般包括两个部分：数据域和指针域。数据域存放节点的数据，指针域存放下一个节点的地址。

以下是单链表节点的定义：

typedef struct node {
    int data;           // 数据域
    struct node *next;  // 指针域
} Node, *LinkList;

这里使用typedef和LinkList是为了方便使用。详情可以参考代码。

单链表的基本操作

头插法创建单链表

头插法是一种从前往后建立单链表的方法，每次新建节点都插入到链表的头部。

LinkList createList() {
    LinkList L = NULL;      // 头节点
    Node *s = NULL;         // 新建节点
    int x = 0;              // 输入的数据
    scanf("%d", &x);
    while (x != -1) {
        s = (Node*)malloc(sizeof(Node));    // 新建节点
        s->data = x;        // 节点赋值
        s->next = L;        // 插入到链表头部
        L = s;              // 更新头指针为新建节点
        scanf("%d", &x);
    }
    return L;
}

以上代码是使用头插法创建单链表的实现。程序首先输入第一个数据，然后循环输入数据并新建节点，每次将新节点插入到头部。这里需要注意的是如果有一个数据为-1，那么循环结束，返回头节点。

尾插法创建单链表

尾插法是一种从后往前建立单链表的方法，每次新建节点都插入到链表的尾部。

LinkList createList() {
    LinkList L = NULL;      // 头节点
    Node *s = NULL;         // 新建节点
    Node *r = NULL;         // 指向链表的尾部
    int x = 0;              // 输入的数据
    scanf("%d", &x);
    while (x != -1) {
        s = (Node*)malloc(sizeof(Node));    // 新建节点
        s->data = x;        // 节点赋值
        if (L == NULL) {    // 链表为空，新节点就是链表的头节点
            L = s;
            r = s;
        } else {            // 新节点插入到链表的尾部
            r->next = s;
            r = s;
        }
        scanf("%d", &x);
    }
    if (r != NULL) {    // 这里需要判断一下，以免链表为空
        r->next = NULL;
    }
    return L;
}

以上代码是使用尾插法创建单链表的实现。程序首先输入第一个数据，然后循环输入数据并新建节点，每次将新节点插入到尾部。这里需要注意的是如果有一个数据为-1，那么循环结束。最后需要判断一下链表是否为空，如果不为空则设置尾部指针为空指针。

遍历单链表

遍历单链表就是依次输出每个节点的数据。

void printList(LinkList L) {
    Node *p = NULL;     // 遍历指针
    p = L;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

以上代码是遍历单链表的实现。程序创建了一个指针p用于遍历单链表，当p指向空指针时遍历结束。

单链表的应用举例

静态链表

静态链表是一种使用数组来模拟的链表。静态链表的一个显著特点是可以随机访问节点。

以下是静态链表节点定义：

typedef struct snode {
    int data;
    int next;
} SNode;

静态链表的代码实现和单链表基本相同，只是在创建节点的时候需要使用数组下标代替地址。

void createSList(SNode s[], int *p) {
    int x = 0;              // 输入数据
    scanf("%d", &x);
    while (x != -1) {
        s[*p].data = x;
        s[*p].next = *p + 1;
        *p++;
        scanf("%d", &x);
    }
    s[*p].next = -1;
}

void printSList(SNode s[], int p) {
    while (s[p].next != -1) {
        printf("%d ", s[p].data);
        p = s[p].next;
    }
    printf("%d\n", s[p].data);
}

以上代码实现了静态链表的创建和遍历。程序使用数组来保存静态链表，p代表数组下标，每次新增节点的地址都是p+1。静态链表的遍历需要使用数组下标代替指针指向节点位置。

单链表的逆序输出

单链表的逆序输出不需要改变节点的位置，只需要修改遍历顺序。这可以通过使用递归函数来实现。

void reversePrint(Node *L) {
    if (L == NULL) {
        return;
    }
    reversePrint(L->next);
    printf("%d ", L->data);
}

以上代码实现了单链表逆序输出的功能。reversePrint函数使用递归的形式来遍历链表，当遇到空指针时递归结束。同时，printf函数在递归函数后面执行，所以输出顺序就是逆序的了。

结论

以上是C语言单链表存储的详细攻略。单链表是一种比较简单的数据结构，可以用来解决许多实际问题。在实际应用中，我们需要灵活使用各种算法和技巧来处理单链表。