C语言数据结构超详细讲解单向链表

标题：C语言数据结构超详细讲解单向链表

简介

本文主要介绍C语言中的单向链表数据结构，包括单向链表的基本操作及其实现方式。学习本文需要读者已经掌握C语言基础知识。

单向链表概述

单向链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两个部分：数据部分和指向下一个节点的指针。最后一个节点的指针为空指针，即指向NULL。单向链表的头节点没有数据，只有指针。

以下是一个单向链表的示意图：

头节点 → 节点1 → 节点2 → 节点3 → NULL

单向链表的基本操作

1. 创建单向链表

创建单向链表包括两个步骤：创建头节点、添加节点。

创建头节点：

struct Node *head;
head = (struct Node *)malloc(sizeof(struct Node));
head->data = 0; // 头结点没有实际的数据，设为0
head->next = NULL;

添加节点：

struct Node *p, *q;
int n, data, i;
printf("请输入节点个数n：");
scanf("%d", &n);
q = head;
for (i = 1; i <= n; i++) {
    p = (struct Node *)malloc(sizeof(struct Node));
    printf("请输入第%d个节点的值：", i);
    scanf("%d", &data);
    p->data = data;
    p->next = NULL;
    q->next = p;
    q = p;
}

2. 遍历单向链表

遍历单向链表：

struct Node *p;
p = head->next; // 从第一个节点开始遍历
while(p) {
    printf("%d ", p->data);
    p = p->next;
}

3. 获取单向链表的长度

获取单向链表的长度：

int length(struct Node *head) {
    int len = 0;
    struct Node *p;
    p = head->next;
    while(p) {
        len++;
        p = p->next;
    }
    return len;
}

4. 插入节点

插入节点包括两种情况：插入到头节点之后、插入到指定位置之后。

插入头节点之后：

void insert(struct Node *head, int data) {
    struct Node *p;
    p = (struct Node *)malloc(sizeof(struct Node));
    p->data = data;
    p->next = head->next;
    head->next = p;
}

插入指定位置之后：

void insert(struct Node *head, int pos, int data) {
    struct Node *p, *q;
    int i;
    p = head;
    for (i = 1; i < pos; i++) {
        p = p->next;
        if (p == NULL) {
            printf("插入位置无效\n");
            return;
        }
    }
    q = (struct Node *)malloc(sizeof(struct Node));
    q->data = data;
    q->next = p->next;
    p->next = q;
}

5. 删除节点

删除节点包括两种情况：删除节点本身、删除指定位置的节点。

删除节点本身：

void delete(struct Node *head, struct Node *p) {
    struct Node *q;
    q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);
    q = NULL;
}

删除指定位置的节点：

void delete(struct Node *head, int pos) {
    struct Node *p, *q;
    int i;
    p = head;
    for (i = 1; i < pos; i++) {
        p = p->next;
        if (p == NULL) {
            printf("删除位置无效\n");
            return;
        }
    }
    q = p->next;
    p->next = q->next;
    free(q);
    q = NULL;
}

示例说明

示例1

假设现在有一个单向链表：

头节点 → 节点1 → 节点2 → 节点3 → NULL

现在需要在节点2和节点3之间插入一个值为4的节点。代码如下：

insert(head, 3, 4);

插入后单向链表变为：

头节点 → 节点1 → 节点2 → 节点4 → 节点3 → NULL

示例2

现在有一个单向链表：

头节点 → 节点1 → 节点2 → 节点3 → NULL

现在需要删除节点2。代码如下：

delete(head, head->next);

删除后单向链表变为：

头节点 → 节点1 → 节点3 → NULL