[笔记]指针与双向链表

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

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

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

#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);
}

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

先看结构体定义：