数据结构-->双向循环链表实现功能

发布于:2023-01-22 ⋅ 阅读:(10) ⋅ 点赞:(0) ⋅ 评论:(0)

目录

一、基础概念

二、适用场景

三、双向循环链表功能


一、基础概念

对链表而言,双向均可遍历是最方便的,另外首尾相连循环遍历也可大大增加链表操作的便捷性。因此,双向循环链表,是在实际运用中是最常见的链表形态。

 

二、适用场景

经过单链表、双链表的学习,可以总结链表的适用场合:
       
 1.适合用于节点数目不固定,动态变化较大的场合。
        2.适合用于节点需要频繁插入、删除的场合。
        3.适合用于对节点查找效率不十分敏感的场合 。

三、双向循环链表功能

1结构体节点设计

typedef struct node
{
    int data; 
    //指向前缀节点的指针
    struct node * prev;  
    //指向后缀节点的指针
    struct node * next;  
}node;   //node == struct node

2.初始化

node *initList(void)
{
    //在堆空间里面开辟新的内存
    node *new = malloc(sizeof(node));
    //判断是否开辟成功,开辟失败后返回提示
    if(new == NULL)
    {
        printf("malloc fail\n");
        return NULL;
    }
    //开辟的空间数据初始化为0
    new->data = 0;
    //双向循环链表,单个节点也是循环链表
    new->next = new;
    new->prev = new;

    return new;
}

3.将新节点插入到链表的首部

void insertHead_1(node *head,  node *new)
{
    new->next = head->next;
    head->next->prev = new;
    new->prev = head;
    head->next = new;
}

4.将新节点插入到链表的尾部

void insertHead_2(node *head,  node *new)
{
    new->prev = head->prev;
    head->prev->next = new;
    head->prev = new;
    new->next = head;
}

5.查找数据

node *find_data(node  *head, int data)
{
    node *p = NULL;
    for(p = head->next; p != head ; p = p->next)
    {
        //判断节点的数据是否等于 查看的数据,如果是,返回节点
        if(p->data == data)
        {
            return p;
        }
    }

    return NULL;
}

6.节点删除 

node *del_node(node *head, int data)
{
    node *del;
    del = find_data(head, data);
    if(del == NULL)
    {
        printf("链表当中没有此数据节点\n");
        return NULL;
    }
    //将点解下来
    del->next->prev = del->prev;
    del->prev->next = del->next;

    //把解下来的节点前后都指向自己
    del->next=del;
    del->prev=del;
    return del;

}

7.打印数据

void display(node *head)
{
    node *p;
    for(p = head->next; p != head; p=p->next)
    {
        printf("%d\t", p->data);
    }
    printf("\n");
}

8.移动数据头插

void move_front(node *head)
{
    int  data1, data2;
    node *move, *basic;
    printf("请输入数据要插入哪个前面:");
    scanf("%d", &data1);
    move=find_data(head,data1);
    if (move==NULL)
    {
        printf("找不到该数据");
        return;
    }

    printf("请输入需要移动的数据:");
    scanf("%d", &data2);
    basic=del_node(head,data2);
    if (move==NULL)
    {
        printf("找不到该数据");
        return;
    }
    insertHead_2(move,basic);
    printf("插入成功");

    return;          
}

9.移动数据尾插

void move_behind(node *head)
{
    int  data1, data2;
    node *move, *basic;
    printf("请输入数据要插入哪个后面:");
    scanf("%d", &data1);
    move=find_data(head,data1);
    if (move==NULL)
    {
        printf("找不到该数据");
        return;
    }

    printf("请输入需要移动的数据:");
    scanf("%d", &data2);
    basic=del_node(head,data2);
    if (move==NULL)
    {
        printf("找不到该数据");
        return;
    }
    insertHead_1(move,basic);
    printf("插入成功");

    return;
}

10.双向循环链表的销毁

void destroy(node *head)
{
    node *p=head->next;
    while(p!=head)
    {
        node *pp=p;
        p=p->next;
        free(pp);
    }
    head->next=head;
    head->prev=head;
    printf("已经成功摧毁\n");
}

 完整代码

#include <stdio.h>

#include <stdlib.h>

//结构体节点设计

typedef struct node

{

    int data;

    //指向前缀节点的指针

    struct node * prev;  

    //指向后缀节点的指针

    struct node * next;  

}node;   //node == struct node

//函数声明

node *initList(void);

void insertHead_1(node *head,  node *new);

void insertHead_2(node *head,  node *new);

node *find_data(node  *head, int data);

node *del_node(node *head, int data);

void display(node *head);

void move_front(node *head);

void move_behind(node *head);

void destroy(node *head);

int main(void)

{

    //定义局部变量

    char ch;

    int data, ret,q;

    node *head, *new, *find, *del;

    //生产一个双向链表结构体

    head = initList();

    while(1)

    {

        printf("===================操作功能==================\n");

        printf("\t\ta:头插添加数据\n");

        printf("\t\tb:尾插添加数据\n");

        printf("\t\tc:查找数据\n");

        printf("\t\td:删除数据\n");

        printf("\t\tp:显示数据\n");

        printf("\t\tn:节点移动头插\n");

        printf("\t\tm:节点移动尾插\n");

        printf("\t\tt:销毁双向链表\n");

        //等待用户指令输入

        ch = getchar();

        switch (ch)

        {

            //头插添加数据

            case 'a':

                new = initList();

                printf("请输入要头插的数据:");

                scanf("%d", &new->data);

                insertHead_1(head,  new);

                break;

            //尾插添加数据

            case 'b':

                new = initList();

                printf("请输入要尾插的数据:");

                scanf("%d", &new->data);

                insertHead_2(head,  new);

                break;

            //查找数据

            case 'c':

                printf("请输入要查找的数据:");

                scanf("%d", &data);

                find = find_data(head, data);

                if(find == NULL)

                {

                    printf("链表当中没有此数据节点\n");

                }

                else

                {

                    printf("链表当中有此数据节点\n它的节点地址:%p\n", find);

                }

                break;

            //删除数据

            case 'd':

                printf("请输入要删除的数据:");

                scanf("%d", &data);

                del = del_node(head, data);

                if(del != NULL)

                {  

                    free(del);

                    printf("节点删除完成\n");

                }

                break;

            //显示数据

            case 'p':

                display(head);

                break;

            //节点移动头插

            case 'n':

                move_front(head);

                break;

            //节点移动尾插

            case 'm':

                move_behind(head);

                break;

            //销毁双向链表

            case 't':

                destroy(head);

                break;

            default:

                printf("输入格式有误,请重新输入!\n");

                break;

        }

        //去除缓冲区的空格

        while (getchar() != '\n');

    }  

    return 0;

}


 

//初始化,一个新的结构体节点生成

node *initList(void)

{

    //在堆空间里面开辟新的内存

    node *new = malloc(sizeof(node));

    //判断是否开辟成功,开辟失败后返回提示

    if(new == NULL)

    {

        printf("malloc fail\n");

        return NULL;

    }

    //开辟的空间数据初始化为0

    new->data = 0;

    //双向循环链表,单个节点也是循环链表

    new->next = new;

    new->prev = new;

    return new;

}  

// 将新节点插入到链表的首部

void insertHead_1(node *head,  node *new)

{

    new->next = head->next;

    head->next->prev = new;

    new->prev = head;

    head->next = new;

}

// 将新节点插入到链表的尾部

void insertHead_2(node *head,  node *new)

{

    new->prev = head->prev;

    head->prev->next = new;

    head->prev = new;

    new->next = head;

}


 

//查找数据,数据存在返回数据所在的节点地址

node *find_data(node  *head, int data)

{

    node *p = NULL;

    for(p = head->next; p != head ; p = p->next)

    {

        //判断节点的数据是否等于 查看的数据,如果是,返回节点

        if(p->data == data)

        {

            return p;

        }

    }

    return NULL;

}


 

//节点删除

node *del_node(node *head, int data)

{

    node *del;

    del = find_data(head, data);

    if(del == NULL)

    {

        printf("链表当中没有此数据节点\n");

        return NULL;

    }

    //将点解下来

    del->next->prev = del->prev;

    del->prev->next = del->next;

    //把解下来的节点前后都指向自己

    del->next=del;

    del->prev=del;

    return del;

}

//打印数据

void display(node *head)

{

    node *p;

    for(p = head->next; p != head; p=p->next)

    {

        printf("%d\t", p->data);

    }

    printf("\n");

}

//移动数据头插

void move_front(node *head)

{

    int  data1, data2;

    node *move, *basic;

    printf("请输入数据要插入哪个前面:");

    scanf("%d", &data1);

    move=find_data(head,data1);

    if (move==NULL)

    {

        printf("找不到该数据");

        return;

    }

    printf("请输入需要移动的数据:");

    scanf("%d", &data2);

    basic=del_node(head,data2);

    if (move==NULL)

    {

        printf("找不到该数据");

        return;

    }

    insertHead_2(move,basic);

    printf("插入成功");

    return;          

}

//移动数据尾插

void move_behind(node *head)

{

    int  data1, data2;

    node *move, *basic;

    printf("请输入数据要插入哪个后面:");

    scanf("%d", &data1);

    move=find_data(head,data1);

    if (move==NULL)

    {

        printf("找不到该数据");

        return;

    }

    printf("请输入需要移动的数据:");

    scanf("%d", &data2);

    basic=del_node(head,data2);

    if (move==NULL)

    {

        printf("找不到该数据");

        return;

    }

    insertHead_1(move,basic);

    printf("插入成功");

    return;

}

//双向链表的销毁

void destroy(node *head)

{

    node *p=head->next;

    while(p!=head)

    {

        node *pp=p;

        p=p->next;

        free(pp);

    }

    head->next=head;

    head->prev=head;

    printf("已经成功摧毁\n");

}