[笔记]指针与单向链表

前言:妈的老子终于写到链表来了!!!!进入数据结构了!!!卧槽我好想快点写完然后写Linux啊!!!!此文引用了CSDN的部分文章,进行整理,侵权立删

本文重点,请认真阅读!

为什么要使用链表

在未学习链表时,我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快,但是它的弊端也很明显:

  1. 使用前需声明数组的长度,一旦声明长度就不能更改
  2. 插入和删除操作需要移动大量的数组元素,效率慢
  3. 只能存储一种类型的数据.

链表则可以实现以上这些数组所不具备的功能,此时引入了结构体来实现创建链表的操作。

链表的特点:

  1. n个节点离散分配
  2. 每一个节点之间通过指针相连
  3. 每一个节点有一个前驱节点和一个后继节点
  4. 首节点没有前驱节点,尾节点没有后继节点

首先先定义一个简单的结构体

struct link
{
    int data;//声明数据域
    struct link* p; //定义指针域,存储直接后继的节点信息

};

数据域的内容可以自己指定,指针域用来存放下一个节点的地址。

单向链表:只能单方向进行(补充笔记)

首节点:存放第一个有效数据的节点

头节点:在单链表的第一个结点之前附设一个结点,它没有直接前驱,称之为头结点,头结点的数据域可以不存储任何信息,指针域指向第一个节点(首节点)的地址。头结点的作用是使所有链表(包括空表)的头指针非空

头指针:指向头节点的指针

尾节点:存放最后一个有效数据的节点

尾指针:指向尾节点的指针

img这张图可以全部说明单向链表惹

其实在咱们学习结构体自引用的时候就接触到了链表 ,只不过在自引用的同时多出了头指针。在等待用户输入值前,头指针指向空,待用户输入值后,头指针指向该节点,判断该结点的指针域是否还有数据,若为NULL,则将它设为尾结点。

每一次的添加数据,指针都将在堆内申请一片对应结构体的内存空间,将此次存储的值存入此内存空间内,由于在堆内,程序结束之前,不释放会会一直存在,在增改删查里边就很好理解了:利用循环遍历链表,实现不同的操作

结构体一般为全局变量类型,因为在实现不同功能的时候,都需要调用它,结构体分为数据域和指针域两个区域,利用指针申请节点

当类型名过长时,一般使用typedef为结构体创建别名,方便调用

还是利用代码讲解通俗易懂:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>


/*------------声明功能函数----------------*/
void insere_func(void);
void sort_func(void);
void delete_func(void);
void display_func(void);
void modify_func(void);
void anykey_func(void);

/*-----------创建结构体与链表节点----------*/

struct student
{
    char name[20];
    int score;
    struct student* next;
};

struct student* ptr,
    * head,
    * current,
    * prev;


/*---------------定义主函数----------------*/
int main()
{
    char option1;
    
    /*定义头指针,头指针指针域指向NULL*/
    head = (struct student*)malloc(sizeof(struct student));
    head->next = NULL;

    /*创建一个死循环*/
    while (1)
    {
        printf("\n");
        printf("***********************\n");

        printf("1.插入\n");
        printf("2.删除\n");
        printf("3.查看\n");
        printf("4.修改\n");
        printf("5.退出\n");

        printf("***********************\n");
        printf("请输入序号后按下回车");

        option1 = _getche();

        switch (option1)
        {
        case '1':
            insere_func();
            break;
        case '2':
            delete_func();
            break;
        case '3':
            display_func();
            break;
        case '4':
            modify_func();
            break;
        case '5':
            printf("欢迎使用\n");
            return 0;
    
        }
    }
}
/*---------------定义功能函数-------------------*/
/*添加是以分数的高低加以排序*/
void insere_func(void)
{
    char s_temp[4];
    
    ptr = (struct student*)malloc(sizeof(struct student));
    
    printf("\n");
    printf("Student name:");
    gets(ptr->name);
    printf("Student score:");
    gets(s_temp);
    
    ptr->score = atoi(s_temp);

    prev = head;
    current = head->next;

    while ((current != NULL) && (current->score>ptr->score))
    {
        prev = current;
        current = current->next;
    }

    ptr->next = current;
    prev->next = ptr;
    printf("添加成功\n");
}

void delete_func(void)
{
    char del_name[20], ans;
    printf("删除学生姓名:");
    gets(del_name);

    prev = head;
    current = head->next;

    while ((current != NULL) && (strcmp(current->name, del_name) != 0))
    {
        prev = current;
        current = current->next;
    }
    if (current != NULL)
    {
        printf("是否确定删除(Y/N)");
        ans =_getche();
        if (ans == 'Y' || ans == 'y')
        {
            prev->next = current->next;
            free(current);
        }
    }
    else
    {
        printf("没找到关于%s的信息", del_name);
    }
}
void modify_func(void)
{
    char n_temp[20], s_temp[4];
    printf("需要调整的学生姓名:");
    gets(n_temp);
    
    current = head->next;

    while ((current != NULL) && (strcmp(current->name, n_temp)) != 0)
    {
        prev = current;
        current = current->next;
    }

    if (current != NULL)
    {
        printf("\n");
        printf("\n*****************************\n");
        printf("学生姓名:%s\n", current->name);
        printf("学生分数:%d\n", current->score);
        printf("\n*****************************\n");
        printf("请输出新的分数:%d");
        gets(s_temp);
        current->score = atoi(s_temp);
        printf("修改后:\n");
        printf("学生姓名:%s\n", current->name);
        printf("学生分数:%d\n", current->score);
    }
    else
    {
        printf("未找到学生信息\n");
    }
}
void display_func(void)
{
    int count = 0;
    if (head->next == NULL)
    {
        printf("没有记录学生");
    }
    else
    {
        printf("\n");
        printf("\tNAME\tSCORE\n");
        printf("-------------------\n");
        current = head->next;
        while (current != NULL)
        {
            printf("\t%-10s\t%3d\n", current->name,current->score);
            count++;
            current = current->next;
            if (count % 20 == 0)
            {
                _getch();
            }
        }
        
        printf("-------------------\n");
        printf("总共找到%d条学生记录", count);
    }
}

代码较长,我们一个函数一个函数的讲,头文件和函数前置声明就不做剖析了

img

程序定义了一个结构体:

  • 结构体类型为student(数据域)
  • name为成员,char数组类型(数据域)
  • socre为成员,int类型(数据域)
  • next为结构体自引用,为结构体指针类型(指针域)

随后结构体又定义了四个指针变量:看图

img

我们给这四个指针做一个功能的分析:

  • ptr:用于创建新的节点
  • head:用于指向头结点
  • current:用于操作下一个节点
  • prev:用于操作当前节点

进入正题:

img

option1用于输入字符,选择功能调用函数,这个不做详细讲解

重点到它为head分配了一片student结构体的内存,并且将head的指针域指向为NULL这时head指向的这片区域形成头结点

img这时程序中抽象为图

当我们输入1时,执行insere_func();函数,这个函数是个无返回值,无参数的函数,只能用于实现功能!我们继续剖析这个函数:

img

我们先看函数前部分,这儿定义了一个char类型的数组s_temp咱们不管它,输入字符用的

第一次:

重点到ptr,这儿它为ptr申请了一段结构体指针类型的内存空间!

imgptr = (struct student*)malloc(sizeof(struct student));

这时咱们再往下看

  • 这时程序要求用户输入,分别存储进ptr的数据域中的成员:name数组与score
  • 假设我们输入的为:Axuan,99
  • 如下图:

img

输入完成后,这时ptr所指向的内存是有数据的,我们来看下面这段语句

img

这时将prev指向头结点的首地址,current指向头结点的指针域,如下图

img

在这儿比较绕了,深度剖析一下,current和prev均用于操作头结点。不同之处是prev用于操作当前节点,current用于操作下一个节点

我们来看下面的语句:

img

执行循环有两个要求,第一个是在头结点后有数据,第二个要求是首元节点中的score数值要大于新节点的score,显然程序的定义是头节点不存放数据,那么第一次输入,头节点是没有连接新的节点的

继续看下一个,这时将新的节点插入进去

img

  • 第一步:将新节点的指针域指向需要插入位置的后置节点
  • 第二步:将新节点的前置结点的指针域指向新节点

先看第一句,如图:

img

由于是第一次输入,头节点后是没链接节点的,所以current所指向为空,这时需要插入新的节点,所以将新节点的指针域指向需要插入位置的后置节点,但是后边没得了,就指向了NULL

再看第二句:

prev->next=ptr,当新节点的指针域操作完毕后,我们需要将需要插入位置的前置节点的指针域指向新节点。

img

红色线条是最后执行的!到这儿第一次的输入就完毕了

线条太多?我们把线条全部擦一下:

img

这样我们可以理解了吧!

第二次:

这时主函数中的while是一个死循环,在执行了第一次insere_func();函数后,再次执行!

img

除了ptr所指向的内存是因为我们动态分配,存放于堆内,其他的数据:s_temp作为一个局部变量在第一次执行结束后已经释放

那么我们这是ptr依旧是指向刚刚那片内存,但是!!它仅仅是指向,要明白,ptr是一个指针,指针是一个变量,它的值是可以改变的!!!

在这之前,它的值是刚刚分配的那片内存的地址!!我们没有释放!!也就是说,在程序结束之前,第一次的数据一直会保存于那片内存!!

再一次的定义了一个s_temp变量后,我们又到了创建新节点的这一步

看图:

img

看到这粉嫩的小箭头了没(它再一次的重复之前的动作分配了结构体大小的内存,并交给ptr管理)ptr指向了刚刚分配的那段内存!!

这时继续重复刚刚输入的数据,我们这次输入Bxuan,105

img

我们来看语句:

img

prev继续指向头节点,current继续指向头节点的指针域

img

这时进入循环,由于有了第一次创建与链接,这时头结点后是有链接节点的

但第二个条件不满足,current管理的是首元结点(第一组),第一组成员score小于第二组score,所以不执行循环(程序开头有个注释:/添加是以分数的高低加以排序/)

直接到下面的:

img

不满足循环,就让这个结点插入到头结点后,先让新结点链接后置节点,让新结点的指针域指向后置节点

在让当前节点的指针域指向新节点

img为了更加易懂,我加上了第一组第二组

prev->next=ptr,由于第二组分数是大于第一组分数的,所以这儿让第二组成为首元节点,插入到第一组和头结点之间

img

到这时,第二组的添加也完成了,我们继续把图片整理下

img

有没有像一个小火车!~一节车厢连着一节车厢!

第三次

经过前面两次,最后一次我就直接到输入数据这儿开讲了

假设我们再次输入Cxuan,100

img

这儿又为ptr分配了一片同样的内存,然后将数据载入进去

img

一样没变,prev管理着头结点,current管理着首元节点

这时要注意了,current不为NULL,且100要小于105,进入循环

img

这时将两个指针向后移动,分别管理下一个结点和下一个结点的指针域

img

prev管理了头结点后的节点,current管理了prev的指针域

img

然后再次进行循环判断,这时current还是不为空,它指向第一组,头指针取到current->score就是第一组中的score作比较,结果是100>99则不执行循环!找到了正确的插入位置

然后进行下一语句:

img

pte->next是第三组的指针域,让他等于第二组的指针域

img

prev->next=ptr,然后第二组的指针域,让他指向第三组

img

最后我们再一次的整理!让各位了解的更加透彻

img

注意:内存不是连续的!

第一函数总结:

第一个函数实现了添加以及排序功能,这排序是不是很熟悉?这就是最常用最简单的插入排序,拿出一个数,对后面的每一个数做比较,如果满足,则交换两者位置,如果不满足,则将这个数放到前数后面。

与之前学的相比,之前利用数组实现是顺序结构,这次只不过利用链式结构实现,实现的原理就是在prev与current指针上,一个管理当前结点,一个管理后置节点

通俗点说就是操作指针域实现各项功能

prev作用于修改当前节点,current作用于修改下一节点!

为什么头结点数据域内不存储数据,因为头节点用于相邻其他节点,打个比方来说,头节点就和火车头一样,头结点可以使用,只是在链表节点的插入,删除操作中极为不便,尤其是双向链表,逻辑通用性不强,处理不好很容易出错

对头指针以及头节点的疑问请看:头指针与头结点补充笔记

while循环的作用是一直在寻找正确的节点进行插入,并让current指向它,如果current指向的节点满足条件,则通过prev进行修改这个节点,通过current修改下一节点

学习到这里,我对单向链表有了一个大致的了解,通过其他功能函数学习逐渐完善!

功能函数(删除节点)

我们继续着结构体声明,定义,主函数定义完头指针,头结点后,录入函数输入数据后,接上图做讲解

先看代码:

img

首先程序定义了两个char类型的元素,一个del_name[20]为数组,ans为普通变量,然后使用gets进行输入数据

prev指向头,current指向 头指针域,从头开始,到这里是否对头节点有点模糊的理解了?

img

假设,我们要删除Cxuan这个数据,这是通过名字来遍历链表,符合要求的时候执行循环体内的删除

当current->next与输入的字符串相等的时候,就不执行,如果不相等,则:

img

移至下一个节点,我们按图来看,不满足条件,则将指针移到下一个节点,依旧是判断current所指向的区域

img

再进入循环,current->name是Cxuan

则不满足条件,跳出循环

img

执行if语句

当我们确定删除后

img

prev->next就指向current->next了,我们用图了解它的运作情况

img

因为要删除包含Cxuan的节点,则要将Cxuan之前的节点与之后的节点相邻,按照图上来说,就是将第三组清楚,将第二组与第一组相邻

此时current还是指向第一节点的指针域,指向第三组,然后free(current)

去释放这段内存,那么就完成了删除的工作

img

这时这一步也就算完成了!

整体简单来说就是,先将current指向链表的第一个存放有数据的节点,接着利用while循环找出欲删除的节点,将prev指向current节点的下一个节点,并回收current节点

其实理解并不难,current指针一直在遍历链表,从头节点的指针域开始遍历,再让prev指向刚刚走过的节点,进而得以控制两节点!

功能函数(修改节点)

我们继续着结构体声明,定义,主函数定义完头指针,头结点后,录入函数输入数据后,删除一个数据,接上图做讲解

img

此时程序当中的走向如图所示,我们看代码:

img

先定义了两个数组,第一个数组我们可以从代码知道用于查找,第二个数组我们可以知道是用于存放临时数据

一样,current指向头结点的指针域,指向第一节点:

然后利用while循环来遍历链表,找到符合条件的节点,假设我们存入n_temp中的值为Axuan

进入判断条件,都满足,则进入循环

将prev和current移至下一个节点

img

再次进入循环,这时strcmp判断两字符串相等,则不进入循环,进入下一语句

img

这时你需要输入新的数据载入临时变量s_temp中,再将他转换十进制整型(atoi)存入current此时指向节点的score成员中去

这时s_temp的值会替换掉原有的值,假设我们输入78

img

修改后:

img

就完成了数据的修改

功能函数(遍历节点)

这应该是一个最简单的了,我们接着上图继续讲解

img

然后看代码:

img

这儿首先判断了头节点后节点是否存在数据,咱们是有数据的,就进入下一段,三个打印就不说了

current=head->next,这时我们可爱的current指针又登场了,它继续指向第一节点

img

然后进入while循环遍历链表:

img

输出节点内的成员后,count作为计数变量,自增一位,然后指针指向下一节点继续进行循环

如果存放到20个节点后结束运算,这一步可有可无,这儿就不细讲了。运行图:

img


到这儿对单向链表已经有了一个简单的理解,咱们进入双向链表

本文链接:

https://nullcode.fun/113.html
1 + 1 =
快来做第一个评论的人吧~