[笔记]指针与双向链表

双向链表:可进行双向访问

单链表中,每个结点有一个指向其后继结点的指针,整个单链表只沿着一个方向操作,那么双向链表,顾名思义,在它的结点中,不仅包含直接后继结点的地址指针,还包含它的直接前驱结点地址指针

我们来看一段代码,从代码中去了解链表的创建与链接(下列使用双向循环链表)

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

void init_f(void);/*初始化链表,创建第一空结点为HEAD*/
void insert_f(void);/*插入函数*/
void delete_f(void);/*删除函数*/
void display_f(void);/*输出函数*/
void modify_f(void);/*修改函数*/

struct student
{
    char name[20];
    int score;
    struct student* llink;/*结点左链接*/
    struct student* rlink;/*结点右链接*/
};
struct student* ptr, * head, * tail, * current_n, * prev;
int main()
{
    char option1;
    init_f();
    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':
            insert_f();
            break;
        case '2':
            delete_f();
            break;
        case '3':
            display_f();
            break;
        case '4':
            modify_f();
            break;
        case '5':
            printf("欢迎使用\n");
            return 0;
        }
    }
}
void init_f(void)/*设一head,将左右链接均指向自身*/
{
    ptr = (struct student*)malloc(sizeof(struct student));

    strcpy(ptr->name, "0");

    ptr->llink = ptr;
    ptr->rlink = ptr;

    head = ptr;

    tail = ptr;

}
/*按分数高低添加*/
void insert_f(void)
{
    char s_temp[4];
    ptr = (struct student*)malloc(sizeof(struct student));

    printf("\n学生姓名:");
    gets(ptr->name);
    printf("学生分数:");
    gets(s_temp);
    ptr->score = atoi(s_temp);

    prev = head;
    current_n = head->rlink;

    while ((current_n != head) && (current_n->score = ptr->score))
    {
        prev = current_n;
        current_n = current_n->rlink;
    }

    ptr->rlink = current_n;
    ptr->llink = prev;

    prev->rlink = ptr;
    current_n->llink = ptr;
    printf("添加成功");
}

void delete_f(void)
{
    char del_name[20], ans;
    int count = 0;

    if (head->rlink == head)
    {
        printf("\n没有该学生信息");
    }
    else
    {
        printf("\n输出删除学生的姓名:");
        gets(del_name);
        
        prev = head;

        current_n = head->rlink;
        
        while ((current_n != head) && (strcmp(current_n->name, del_name) != 0))
        {
            prev = current_n;
            current_n = current_n->rlink;
        }
        if (current_n != head)
        {
            printf("确定是否删除Y/N");
            ans = _getch();
            if (ans == 'Y' || ans == 'y')
            {
                prev->rlink = current_n->rlink;

                current_n->rlink->llink = prev;

                free(current_n);

                printf("\n 学生%s已经删除", del_name);
            }
        }
        else
            printf("\n未找到该学生信息");
    }
}
void modify_f(void)
{
    int count = 0;
    char n_temp[20], s_temp[4];

    if (head->rlink == head)
    {
        printf("\n没有学生信息");
    }
    else
    {
        printf("请输入需要修改的学生姓名:\n");

        gets(n_temp);

        current_n = head->rlink;

        while ((current_n != head) && (strcmp(current_n->name, n_temp) != 0))
        {
            prev = current_n;
            current_n = current_n->rlink;
        }
        if (current_n != head)
        {
            printf("\n***********************************\n");
            printf("学生姓名:%s\n", current_n->name);
            printf("学生分数:%d\n", current_n->score);
            printf("***********************************\n");

            printf("请输入新的学生分数:");
            gets(s_temp);
            current_n->score = atoi(s_temp);

            printf("\n修改后\n");
            printf("学生姓名:%s\n", current_n->name);
            printf("学生分数:%d\n", current_n->score);
        }
        else
        {
            printf("\n未找到%s的学生信息", n_temp);
        }
    }
}

void display_f(void)
{
    int count = 0;

    if (head->rlink == head)
    {
        printf("\n未找到学生信息\n");
    }
    else
    {
        current_n = head->rlink;
        while (current_n != head)
        {
            printf("\n-----------------------\n");
            printf("\n学生姓名:%s\n", current_n->name);
            printf("学生分数:%d\n", current_n->score);
            printf("-----------------------\n");
            count++;
            current_n = current_n->rlink;

            if (count % 20 == 0)
            {
                _getch();
            }
        }
    }
    printf("\n共找到%d名学生信息", count);
}

我们继续一个函数一个函数的剖析

先看结构体定义:

img

  • 与单链不同的是,结构体内多了一个结点,分为了左右链接结点
  • 同时程序定义了五个指针型结构体变量,通过这五个指针来操作链表

img

  1. 程序首先为ptr开辟了一段内存
  2. 随后将ptr的数据域中的name赋值为0
  3. 将ptr的左右指针指向自身
  4. 然后将head指针指向ptr,tail指针指向ptr

此函数位于主函数开头,从这儿我们可以知道,ptr(1)作为头结点,head始终指向头结点

img

在初始化的时候,左右两指针指向它本身

这时候一个双向链表就创建好了,我们来看看它如何链接结点

注:在下列模拟中,ptr每一次分配的内存是没有名字的,为了直观的理解代码运作过程,结合图形,我将会将第一次ptr分配的称作ptr(1),第二次ptr创建的称作ptr(2)

第一次创建:

img

第一步,为ptr分配一片内存, 创建一个新的结点

img

然后将数据载入进入,我们输入:Axuan,99

再操作prev和current_n指针,看图操作:

  • 让prev管理头结点,然后让current_n管理头结点的右指针域

img为了不引起歧义,ptr管理此内存,指向的是它开辟内存的首地址

此时current_n所指向的为ptr(1),prev所指向的为ptr(1)

接下来进入循环判断,current不为空,输入的数据要大于current_n所管理的数据

(循环作用于找到正确的节点)不断让prev指向下一个节点,current指向下一个节点的右指针域

不进入循环,这时候重点来了!链接两个结点!先看代码!

操作新开辟结点的(左右)指针域:

img

我们看第一段和第二段语句,先操作ptr的右指针域

让他等于current_n(前置结点的右指针域)

再操作ptr的左指针域,让他等于prev(前置结点

img

我们再操作一下prev的右指针域!prev->rlink=ptr

(让前置结点的右指针域指向新结点)

让current_n所管理(指向)的区域:current_n->llink=ptr

(让后置节点的左指针域指向新结点)

img

完成了结点的链接!

我们来整理一下图:

img

  • head作为指向头结点的指针,它始终指向头结点通过它可以更好的管理整个链表!带头结点与不带头结点的区别和优劣会在后边详细讲解。
  • current_n指向的是头结点的右指针域。(管理后置结点)
  • prev指向的是头结点。(管理当前节点)
  • 通过这两个结点,来操作左右指针域的链接,从上图可以看到
  • 先让ptr的右指针域指向前置节点的指针域(current_n)
  • 再让ptr的左指针域指向前置结点,完成两结点的链接

在这儿就可以知道:

  • 右指针域的作用是用于链接下一个结点(后置结点)
  • 左指针域的作用是用于链接上一个结点(前置结点)

那么在结点内并可以访问前置结点和后置结点

这儿可以直观的了解到单双两链表的不同之处

单向链表插入: 所有功能只需要操作一个当前节点和后置节点(操作两个指针域)

  • 双向链表插入除了需要考虑当前节点和后置节点,还需要考虑前置结点在链接和删除的时候,如果是循环链表,则需要将尾结点的指针域指向头结点(操作四个指针域)

涉及多个指针操作,具体请看:补充笔记(双向链表基础操作)

插入:第二次创建链接

我们再一次的调用insert_f()函数,再创建一个新的节点。

img

假设这次输入的数据为:Bxuan,78

img

我们依旧从头结点开始,让prev管理头结点, 让current管理头结点的右指针域

从图可知,current_n所管理的是ptr(2),进入循环后判断头结点后是有数据的,则判断头结点后的数据是否大于新结点的数据,99>78

进入循环,让两个操作指针移位,这时prev和current_n指向的是ptr(2)和ptr(1),因为是循环列表,则表尾要链接表头

再次进入循环,显然表头是不存储数据域的,则将ptr(3)进行尾插

img

还是操作新结点的左右两个指针域

  • 将右指针域指向前置节点的右指针域
  • 将左指针链接前置结点

img

这时再将前置节点的右指针域链接ptr

由于是循环链表,所以每一次的插入都要改变表头和表尾的链接,最后再将表头的左指针域链接新结点

就完成了新结点的链接

img

第三次创建

通过上两次的链接,我们已经明白了双向链表是如何插入的,到这里在巩固一下,进行的三次的模拟

  • 第一步:当然还是分配内存,形成新的节点
  • 第二步:当然是输入数据域
  • 第三步:当然是初始化两个操作指针,还是从表头开始

img

程序要求的是降序排列,则进入循环后首先判断头结点后是否有数据

再遍历整个链表找到正确的位置插入

第一遍循环,99>85,将两个操作指针移到下一位:prev跟着current_n一个管理着ptr(2)一个管理ptr(3),再进入循环判断ptr(3)内78要小于85,不进入循环,则找到了正确位置,进行插入

img

重复之前的动作,新操作新结点,让新结点链接前置和后置

img

  • 再让新结点的前置的右指针域链接新结点
  • 让新结点的后置结点的左指针域链接新结点

就完成了结点的链接

img

删除节点

上面我们了解了如何添加结点,如何在指定位置添加,无非就是操作指针域而已,其实删除节点也特简单

img

程序是按名字进行删除的,则我们准备一个临时数组

先判断头结点后是否有数据

如果有,则进入else语句,初始化操作指针,假设我们要输入Cxuan

img

利用while遍历来查找链表内是否有这个数据

有两种结束可能,第一个是遍历到头了还是没满足第二个结束条件,就是整条链表内都没该数据

第二种就是找到了这个数据,可以进行删除

img

我们用if排除第一种可能,找到了数据,经过while循环,prev已经指向了ptr(2),current_n已经指向了ptr(4)

img

这时先断开需要删除的结点与前置结点和后置节点的联系

  • 让prev的右指针域指向ptr(3)
  • 让ptr(3)的左指针域指向ptr(2)
  • 最后回收ptr(4)

img

整理一下图片:

img

修改节点

得知了删除和增加的原理后,剩下的功能就很容易了

img

先判断头结点后是否有数据

如果有,则通过循环找到符合条件的节点,移动操作指针

img

然后通过操作指针修改需要修改的值,即可

查找节点:

img

这个就是从头节点开始遍历所有节点依次输出数据,计数变量count自增,每输出20个数据停止

总结

  • 这里我们只是简单的了解结点的链接和删除通过遍历实现各项功能
  • 详细的链表运用会在数据结构中讲解
  • 主要需要掌握的是指针域的操作,头指针指向头结点,头结点中可存放数据也可不存放
  • 循环链表的表尾右指针域需要指向表头,当然表头的左指针域需要指向表尾
  • 而简单的双向链表则只需要将表头左指针域指向空,表尾右指针域指向空

接下来我们来了解堆栈的实现

本文链接:

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