单链表知识

只看该作者 · 2024-4-7 12:37

所谓链表，就是由一个个「结点」组成的一个数据结构。每个结点都有「数据域」和「指针域」组成。其中数据域用来存储你想要存储的信息，而指针域用来存储下一个结点的地址。如图：

当然，链表最前面还有一个头指针，用来存储头结点的地址。

这样一来，链表中的每一个结点都可以不用挨个存放，因为有了指针把他们串起来。因此结点放在哪都无所谓，反正指针总是能够指向下一个元素。我们只需要知道头指针，就能够顺藤摸瓜地找到整个链表。

因此对于学籍数据库来说，我们只需要在Info结构体中加上一个指向自身类型的成员即可：

复制

<p>struct Info</p><p>{</p><p>    unsigned long identifier;</p><p>    char name[20];</p><p>    struct Date date;</p><p>    unsigned int years;</p><p>    struct Info* next;</p><p>};</p>

只看该作者 · 2024-4-7 12:38

1、在单链表中插入元素

头插法
这种每次都将数据插入单链表的头部（头指针后面）的插入法就叫头插法。

如果要把学生信息加入到单链表，可以这么写：

复制

void addInfo(struct Info** students)//students是头指针

{

    struct Info* info, *temp;

    info = (struct Info*)malloc(sizeof(struct Info));

    if (info == NULL)

    {

        printf("内存分配失败！\n");

        exit(1);

    }

    

    getInput(info);

    

    if (*students != NULL)

    {

        temp = *students;

        *students = info;

        info->next = temp;

    }

    else

    {

        *students = info;

        info->next = NULL;

    }

}

❝
由于students存放的是头指针，因此我们需要传入它的地址传递给函数，才能够改变它本身的值。而students本身又是一个指向Info结构体的指针，所以参数的类型应该就是struct Info**。

❞
往单链表里面添加一个结点，也就是先申请一个结点，然后判断链表是否为空。如果为空，那么直接将头指针指向它，然后next成员指向NULL。若不为空，那么先将next指向头指针原本指向的结点，然后将头指针指向新结点即可。

那么，打印链表也变得很简单：

复制

void printStu(struct Info* students)

{

    struct Info* info;

    int count = 1;

    

    info = students;

    while (book != NULL)

    {

        printf("Student%d:\n", count);

        printf("姓名：%s\n", info->name);

        printf("学号：%d\n", info->identifier);

        info = info->next;

        count++;

    }

}

想要读取单链表里面的数据，只需要迭代单链表中的每一个结点，直到next成员为NULL，即表示单链表的结束。

最后，当然还是别忘了释放空间：

复制

void releaseStu(struct Info** students)

{

    struct Info* temp;

    

    while (*students != NULL)

    {

        temp = *students;

        *students = (*students)->next;

        free(temp);

    }

}

尾插法
与头插法类似，尾插法就是把每一个数据都插入到链表的末尾。

复制

void addInfo(struct Info** students)

{

    struct Info* info, *temp;

    info = (struct Info*)malloc(sizeof(struct Info));

    if (info == NULL)

    {

        printf("内存分配失败！\n");

        exit(1);

    }

    

    getInput(info);

    

    if (*students != NULL)

    {

        temp = *students;

        *students = info;

        //定位到链表的末尾的位置

        while (temp->next != NULL)

        {

            temp = temp->next;

        }

        //插入数据

        temp->next = info;

        info->next = temp;

    }

    else

    {

        *students = info;

        info->next = NULL;

    }

}

这么一来，程序执行的效率难免要降低很多，因为每次插入数据，都要先遍历一次链表。如果链表很长，那么对于插入数据来说就是一次灾难。不过，我们可以给程序添加一个指针，让它***都指向链表的尾部，这样一来，就可以用很少的空间换取很高的程序执行效率。

代码更改如下：

复制

void addInfo(struct Info** students)

{

    struct Info* info, *temp;

    static struct Info* tail;//设置静态指针

    info = (struct Info*)malloc(sizeof(struct Info));

    if (info == NULL)

    {

        printf("内存分配失败！\n");

        exit(1);

    }

    

    getInput(info);

    

    if (*students != NULL)

    {

        tail->next = info;

        info->next = NULL;

    }

    else

    {

        *students = info;

        info->next = NULL;

    }

}

只看该作者 · 2024-4-7 12:39

2、搜索单链表

单链表是我们用来存储数据的一个容器，那么有时候需要快速查找信息就需要开发相关搜索的功能。比如说输入学号，查找同学的所有信息。

复制

struct Info *searchInfo(struct Info* students, long* target)

{

    struct Info* info;

    info = students;

    while (info != NULL)

    {

        if (info->identifier == target)

        {

            break;

        }

        info = info->next;

    }

    

    return book;

};



void printInfo(struct Info* info)

{

    ...

}

...



int main(void)

{

    ...

    printf("\n请输入学生学号：");

    scanf("%d", input);

    info = searchInfo(students, input);

    if (info == NULL)

    {

        printf("抱歉，未找到相关结果！\n");

    }

    else

    {

        do

        {

            printf("相关结果如下：\n");

            printInfo(book);

        } while ((info = searchInfo(info->next, input)) != NULL);

    }

    

    releaseInfo(...);

    return 0;

}

只看该作者 · 2024-4-7 12:40

3、插入结点到指定位置

到了这里，才体现出链表真正的优势。

设想一下，如果有一个有序数组，现在要求你去插入一个数字，插入完成之后，数组依然保持有序。你会怎么做？

没错，你应该会挨个去比较，然后找到合适的位置（当然这里也可以使用二分法，比较节省算力），把这个位置后面的所有数都往后移动一个位置，然后将我们要插入的数字放入刚刚我们腾出来的空间里面。

你会发现，这样的处理方法，经常需要移动大量的数据，对于程序的执行效率来说，是一个不利因素。那么链表，就无所谓。反正在内存中，链表的存储毫无逻辑，我们只需要改变指针的值就可以实现链表的中间插入。

复制

//Example 03

#include <stdio.h>

#include <stdlib.h>



struct Node

{

    int value;

    struct Node* next;

};



void insNode(struct Node** head, int value)

{

    struct Node* pre;

    struct Node* cur;

    struct Node* New;



    cur = *head;

    pre = NULL;



    while (cur != NULL && cur->value < value)

    {

        pre = cur;

        cur = cur->next;

    }



    New = (struct Node*)malloc(sizeof(struct Node));

    if (New == NULL)

    {

        printf("内存分配失败！\n");

        exit(1);

    }

    New->value = value;

    New->next = cur;



    if (pre == NULL)

    {

        *head = New;

    }

    else

    {

        pre->next = New;

    }

}



void printNode(struct Node* head)

{

    struct Node* cur;



    cur = head;

    while (cur != NULL)

    {

        printf("%d ", cur->value);

        cur = cur->next;

    }

    putchar('\n');

}



int main(void)

{

    struct Node* head = NULL;

    int input;



    printf("开始插入整数...\n");

    while (1)

    {

        printf("请输入一个整数，输入-1表示结束：");

        scanf("%d", &input);

        if (input == -1)

        {

            break;

        }

        insNode(&head, input);

        printNode(head);

    }



    return 0;

}

运行结果如下：

复制

//Consequence 03

开始插入整数...

请输入一个整数，输入-1表示结束：4

4

请输入一个整数，输入-1表示结束：5

4 5

请输入一个整数，输入-1表示结束：3

3 4 5

请输入一个整数，输入-1表示结束：6

3 4 5 6

请输入一个整数，输入-1表示结束：2

2 3 4 5 6

请输入一个整数，输入-1表示结束：5

2 3 4 5 5 6

请输入一个整数，输入-1表示结束：1

1 2 3 4 5 5 6

请输入一个整数，输入-1表示结束：7

1 2 3 4 5 5 6 7

请输入一个整数，输入-1表示结束：-1

只看该作者 · 2024-4-7 12:41

4、删除结点

删除结点的思路也差不多，首先修改待删除的结点的上一个结点的指针，将其指向待删除结点的下一个结点。然后释放待删除结点的空间。

复制

...

void delNode(struct Node** head, int value)

{

    struct Node* pre;

    struct Node* cur;

    

    cur = *head;

    pre = NULL;

    while (cur != NULL && cur->value != value)

    {

        pre = cur;

        cur = cur->next;

    }

    if (cur == NULL)

    {

        printf("未找到匹配项!\n");

        return ;

    }

    else

    {

        if (pre == NULL)

        {

            *head = cur->next;

        }

        else

        {

            pre->next = cur->next;

        }

        free(cur);

    }

}

只看该作者 · 2024-4-10 12:52

链表最前面还有一个头指针，用来存储头结点的地址。

只看该作者 · 2024-4-10 13:52

链表就是由一个个「结点」组成的一个数据结构

只看该作者 · 2024-4-10 15:21

链表的增删改查都是基本操作，还需要多加熟练

只看该作者 · 2024-4-14 15:21

中国龙芯CDX 发表于 2024-4-10 15:21
链表的增删改查都是基本操作，还需要多加熟练

非常正确

只看该作者 · 2024-4-15 09:53

链表是不是跟数据库的做法差不多？

只看该作者 · 2024-4-19 18:46

链表中的每一个结点都可以不用挨个存放，因为有了指针把他们串起来。

只看该作者 · 2024-4-21 12:20

其中数据域用来存储你想要存储的信息，而指针域用来存储下一个结点的地址。