C语言数据结构之单向链表详解分析

什么是单向链表？

单向链表是一种常见的数据结构，它由一系列节点（或称单元）组成，每个节点都包含两个数据域：数据和指针。其中，数据用于存储具体的数据信息，指针则用于指向下一个节点。这样，一个链表就可以看做是由一个一个节点链接而成的数据结构。而单向链表中的指针只能指向下一个节点，因此被称为单向链表。

如何使用单向链表？

单向链表通常用于需要频繁插入、删除节点的场景，因为这种情况下使用数组等静态数据结构会导致效率低下。另外，链表还可以根据需求来灵活扩充大小，可以节省空间。

单向链表的实现

单向链表的实现主要包括链表的初始化、节点的插入、节点的删除、查找节点等功能。

链表的初始化

初始化需定义一个链表头结点，头节点的作用主要为了方便链表中节点的插入、删除等操作。

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

LinkList InitList() {
    LinkList head = (LinkList)malloc(sizeof(Node)); // 动态分配头结点的内存空间
    head->next = NULL;
    return head; // 返回头结点
}

节点的插入

节点的插入需要根据插入位置创建新节点，然后将其连接到链表中。

void InsertNode(LinkList head, int pos, int elem) {
    Node *p = head;
    for (int i = 1; i < pos; i++) {
        if (p == NULL) return;
        p = p->next; // 找到需要插入的位置
    }
    Node *newNode = (Node *)malloc(sizeof(Node)); // 动态分配一个新节点
    newNode->data = elem;
    newNode->next = p->next; // 将新节点插入到链表中
    p->next = newNode;
}

节点的删除

删除节点同样需要找到节点位置，然后将其从链表中删除。

bool DeleteNode(LinkList head, int pos) {
    Node *p = head;
    for (int i = 1; i < pos; i++) {
        if (p == NULL) return false;
        p = p->next; // 找到需要删除的位置
    }
    if (p == NULL || p->next == NULL) return false;
    Node *temp = p->next; // 将节点从链表中删除
    p->next = temp->next;
    free(temp);
    return true;
}

查找节点

查找节点需要遍历整个链表，直到找到目标节点。

Node *GetNode(LinkList head, int pos) {
    Node *p = head;
    for (int i = 1; i <= pos; i++) {
        if (p == NULL || p->next == NULL) return NULL;
        p = p->next; // 遍历链表，直到找到目标节点
    }
    return p;
}

示例

示例1

现在我们需要用单向链表实现一个存储10个元素的列表，列表中元素分别为1, 3, 5,..., 19。可以通过以下方式实现：

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

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

LinkList InitList() {
    LinkList head = (LinkList)malloc(sizeof(Node)); // 动态分配头结点的内存空间
    head->next = NULL;
    return head; // 返回头结点
}

void InsertNode(LinkList head, int pos, int elem) {
    Node *p = head;
    for (int i = 1; i < pos; i++) {
        if (p == NULL) return;
        p = p->next; // 找到需要插入的位置
    }
    Node *newNode = (Node *)malloc(sizeof(Node)); // 动态分配一个新节点
    newNode->data = elem;
    newNode->next = p->next; // 将新节点插入到链表中
    p->next = newNode;
}

void PrintList(LinkList head) {
    Node *p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    LinkList head = InitList(); // 初始化链表
    for (int i = 1; i <= 10; i++) {
        InsertNode(head, i, 2 * i - 1); // 插入节点
    }
    PrintList(head); // 输出链表
    return 0;
}

输出结果：

1 3 5 7 9 11 13 15 17 19

示例2

现在我们需要实现一个存储学生信息的单向链表。每个学生信息包含学号和姓名两个字段。可以通过以下方式实现：

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

typedef struct student {
    int no; // 学号
    char name[50]; // 姓名
    struct student *next; // 指针域
} Student, *LinkList; 

LinkList InitList() {
    LinkList head = (LinkList)malloc(sizeof(Student)); // 动态分配头结点的内存空间
    head->next = NULL;
    return head; // 返回头结点
}

void InsertStudent(LinkList head, int pos, int no, char *name) {
    Student *p = head;
    for (int i = 1; i < pos; i++) {
        if (p == NULL) return;
        p = p->next; // 找到需要插入的位置
    }
    Student *newStudent = (Student *)malloc(sizeof(Student)); // 动态分配一个新学生
    newStudent->no = no;
    strcpy(newStudent->name, name);
    newStudent->next = p->next; // 将新学生插入到链表中
    p->next = newStudent;
}

void PrintStudent(LinkList head) {
    Student *p = head->next;
    while (p != NULL) {
        printf("学号：%d 姓名：%s\n", p->no, p->name);
        p = p->next;
    }
    printf("\n");
}

int main() {
    LinkList head = InitList(); // 初始化链表
    InsertStudent(head, 1, 101, "小明"); // 插入学生
    InsertStudent(head, 2, 102, "小红");
    InsertStudent(head, 3, 103, "小刚");
    PrintStudent(head); // 输出链表
    return 0;
}

输出结果：

学号：101 姓名：小明
学号：102 姓名：小红
学号：103 姓名：小刚