C语言 动态链表

文章目录

前言

大家好~
在学习C语言的过程中，动态链表的相关操作总是会把我弄得有点晕。思路是有的，但是写完代码之后就很容易被自己绕晕。
于是今天想把我在链表的创建、输出、插入删除的过程中出现的问题总结一下，理清一下自己的思路，防止以后再犯同样的错。

关于链表

链表是一种常见的重要的数据结构。
它是动态地进行存储分配的一种结构。链表有一个头指针变量，它存放一个地址，该地址指向一个元素。
链表中每一个元素称为结点，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。
可以看出，头指针 head 指向第一个元素，第一个元素又指向第二个元素……
直到最后一个元素，该元素不再指向其他元素，它称为表尾，它的地址部分放一个 NULL（表示空地址）链表到此结束。

可以得出：

1. 链表中各元素在内存中可以不是连续存放的，要找某一元素，必须先找到上一个元素，根据它提供的下一元素地址才能找到下一个元素。
2. 如果不提供头指针 head 则整个链表无法访问。

题目

动态建立一个长度为4的链表，用于存储学生的信息（姓名与学号），并输出；且实现插入与删除功能，所有功能通过写成函数来实现。

C语言代码

PS：我使用的是 Visual Studio 2019，里面的scanf_s就等同于scanf，但字符串的输入需要在后面标注字符串的大小，否则系统会报错，调试不了。

引入函数：

#include"stdio.h"#include"stdlib.h"#include"string.h"#define LEN sizeof(struct student)

定义结构体：

typedefstruct student
{char name[20];int num;struct student* next;}STU;int n =0;

下面是具体的代码，我将其分成了四个板块：

一、动态链表的创建

代码如下：

STU*create(){
    STU* p1,* p2,* head;char name[20];int num;
    head =NULL;
    p1 = p2 =(STU*)malloc(LEN);//开创一个空间用于存放结构体内的数据printf("请输入学号与姓名：（格式：学号，姓名）\n");scanf_s("%d,%s",&p1->num,&p1->name,20);while(p1->num !=0)//num=0时，链表创建结束{
        n++;//输入了多少个学生的数据if(n ==1)
            head = p1;//把第一个结点的地址赋给head指针else
            p2->next = p1;//如果输入的不是第一个结点的数据，就让其内的next指针指向下一个结点的开头
        p2 = p1;//p2指针移动到p1指针处（下一个结点的开头）
        p1 =(STU*)malloc(LEN);//p1又指向新开创结点的开头scanf_s("%d,%s",&p1->num,&p1->name,20);}
    p2->next =NULL;//如果输入的num=0，跳出循环，最后一个结点的next指针指向空指针（即指向NULL值）return head;//返回第一个结点的地址（这样才能找到后面的所有结点）}

二、动态链表的输出

代码如下：

voidprint(STU* head)//输出学生信息的函数{
    STU* p;
    p = head;//p取head的地址之后，二者同时指向第一个结点的开头
    n ==0;printf("\n");if(head !=NULL){do{printf("学号：%d 姓名：%s\n", p->num, p->name);
            p = p->next;//把next的地址（即下一个结点的开头）赋给p
            n++;}while(p !=NULL);}printf("\n现在共有%d个学生的信息：\n", n);}

三、动态链表的插入

（1）找到位置p（ai-1）
（2）生成新结点s，数据域赋值
（3）新结点指针域指向ai（ai的地址存放在ai-1的指针域）
（4）ai-1的指针域指向新结点s

代码如下：

STU*insert_link(STU* head)//插入结点的函数{
    STU* p;printf("请输入需要插入数据的位置：\n");int m;scanf_s("%d",&m);
    p = head;//p与head指向第一个结点的开头int i =1;//插入位置printf("请输入需要插入的数据 : （格式：学号，姓名）\n");
    STU* j;
    j =(STU*)malloc(LEN);scanf_s("%d,%s",&j->num,&j->name,20);if(m ==1)//如果要在第一个位置插入数据{
        j->next = head;//新的结点的next指针直接指向头结点，新的数据就会成为第一个结点
        head = j;//head指针又指向第一个结点的开始return head;//返回插入数据后的头结点}else{while(i < m -1)/*m-1意味着：如果要在第5个位置插入数据，
            则需要让第4个结点的next指向插入数据的开头*/{
            p = p->next;//循环找到需要插入数据的上一个结点的next所在位置
            i++;}}
    j->next = p->next;//把p的next地址赋给j的next地址，即新的结点可插入两个结点的中间
    p->next = j;//p的next指向j的地址return head;//返回第一个结点的地址}

四、动态链表的删除

（1）找到要删除的结点前一个结点p（原因是删除结点的位置在前一个结点的指针域）
（2）把p->next指向ai的下一个结点（把ai从链上摘除）
（3）释放ai空间

代码如下：

STU*delete_link(STU* head)//删除结点的函数{
    STU* p1,* p2;printf("请输入需要删除数据的位置：\n");int m;scanf_s("%d",&m);
    p1 = head;if(m ==1)//如果删除的是第一个结点{
        p2 = p1->next;//直接把下一个地址作为返回值free(p1);//释放内存return p2;}else{int i =1;while(i < m -1){
            p1 = p1->next;
            i++;}
        p2 = p1->next;
        p1->next = p1->next->next;//p1的next指向了需要删除的结点的next指向的结点（即越过了中间需要删除的结点）free(p2);//释放需要删除的结点的空间return head;//返回第一个结点的地址}}

五、总代码

#include"stdio.h"#include"stdlib.h"#include"string.h"#define LEN sizeof(struct student)typedefstruct student
{char name[20];int num;struct student* next;}STU;int n =0;
STU*create(){
    STU* p1,* p2,* head;char name[20];int num;
    head =NULL;
    p1 = p2 =(STU*)malloc(LEN);//开创一个空间用于存放结构体内的数据printf("请输入学号与姓名：（格式：学号，姓名）\n");scanf_s("%d,%s",&p1->num,&p1->name,20);while(p1->num !=0)//num=0时，链表创建结束{
        n++;//输入了多少个学生的数据if(n ==1)
            head = p1;//把第一个结点的地址赋给head指针else
            p2->next = p1;//如果输入的不是第一个结点的数据，就让其内的next指针指向下一个结点的开头
        p2 = p1;//p2指针移动到p1指针处（下一个结点的开头）
        p1 =(STU*)malloc(LEN);//p1又指向新开创结点的开头scanf_s("%d,%s",&p1->num,&p1->name,20);}
    p2->next =NULL;//如果输入的num=0，跳出循环，最后一个结点的next指针指向空指针（即指向NULL值）return head;//返回第一个结点的地址（这样才能找到后面的所有结点）}
STU*insert_link(STU* head)//插入结点的函数{
    STU* p;printf("请输入需要插入数据的位置：\n");int m;scanf_s("%d",&m);
    p = head;//p与head指向第一个结点的开头int i =1;//插入位置printf("请输入需要插入的数据 : （格式：学号，姓名）\n");
    STU* j;
    j =(STU*)malloc(LEN);scanf_s("%d,%s",&j->num,&j->name,20);if(m ==1)//如果要在第一个位置插入数据{
        j->next = head;//新的结点的next指针直接指向头结点，新的数据就会成为第一个结点
        head = j;//head指针又指向第一个结点的开始return head;//返回插入数据后的头结点}else{while(i < m -1)/*m-1意味着：如果要在第5个位置插入数据，
            则需要让第4个结点的next指向插入数据的开头*/{
            p = p->next;//循环找到需要插入数据的上一个结点的next所在位置
            i++;}}
    j->next = p->next;//把p的next地址赋给j的next地址，即新的结点可插入两个结点的中间
    p->next = j;//p的next指向j的地址return head;//返回第一个结点的地址}

STU*delete_link(STU* head)//删除结点的函数{
    STU* p1,* p2;printf("请输入需要删除数据的位置：\n");int m;scanf_s("%d",&m);
    p1 = head;if(m ==1)//如果删除的是第一个结点{
        p2 = p1->next;//直接把下一个地址作为返回值free(p1);//释放内存return p2;}else{int i =1;while(i < m -1){
            p1 = p1->next;
            i++;}
        p2 = p1->next;
        p1->next = p1->next->next;//p1的next指向了需要删除的结点的next指向的结点（即越过了中间需要删除的结点）free(p2);//释放需要删除的结点的空间return head;//返回第一个结点的地址}}voidprint(STU* head)//输出学生信息的函数{
    STU* p;
    p = head;//p取head的地址之后，二者同时指向第一个结点的开头
    n ==0;printf("\n");if(head !=NULL){do{printf("学号：%d 姓名：%s\n", p->num, p->name);
            p = p->next;//把next的地址（即下一个结点的开头）赋给p
            n++;}while(p !=NULL);}printf("\n现在共有%d个学生的信息：\n", n);}voidmain(){
    STU* pointer;
    pointer =create();//创建动态链表，返回第一个结点的地址赋给pointer
    n =0;//n清零，为了保证之后函数里，从第一个结点开始遍历print(pointer);//输出链表
    pointer = insert_link (pointer);
    n =0;print(pointer);//输出链表
    pointer =delete_link(pointer);
    n =0;print(pointer);//输出链表free(pointer);//释放占用的内存system("pause");}

总结

以上就是关于动态链表的一些具体操作，在整理之后，我对链表的结构和一些内容也有了更加深入的了解。
如果大家对于这个内容和代码还有更好的建议，请多多指正~谢谢！