欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【链表】双向链表:双向循环链表

程序员文章站 2024-03-06 08:27:55
...

写在前面的话:

  1. 版权声明:本文为博主原创文章,转载请注明出处!
  2. 博主是一个小菜鸟,并且非常玻璃心!如果文中有什么问题,请友好地指出来,博主查证后会进行更正,啾咪~~
  3. 每篇文章都是博主现阶段的理解,如果理解的更深入的话,博主会不定时更新文章。
  4. 本文最后更新时间:2020.4.30

正文开始

在单链表中,我们设了next指针,这使得我们查找下一个结点的时间复杂度为O(1),但是如果我们想要查找的是上一个结点,那么最坏的时间复杂度为O(n),因为我们每次都要从头开始遍历查找。

为了克服单向性这一缺点,便有人设计出了双向链表。双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。

双向循环链表中的指针都是成对出现的:你的next指向我,我的prior指向你。

1. 定义数据结构

/* =================
 定义链表数据结构
================= */
struct node
{
    int num;
    struct node *prior;    //prior存放上一个结点的地址
    struct node *next;     //next存放下一个结点的地址
};

2. 设头结点

#include <stdio.h>
#include <stdlib.h>

/* =================
 定义链表数据结构
================= */
struct node
{
    int num;
    struct node *prior;    //prior存放上一个结点的地址
    struct node *next;     //next存放下一个结点的地址
};

typedef struct node Node;
typedef Node * Dlink;

/* ===============
 功能:设头结点
 返回:void
=============== */
void init_d_link(Dlink *head)
{
    *head = (Dlink)malloc(sizeof(Node));  //为头结点分配空间

    (*head)->prior = *head;
    (*head)->next = *head;
}

int main()
{
    Dlink head;
    init_d_link(&head);

    return 0;
}

3. 插入

3.1 头插

#include <stdio.h>
#include <stdlib.h>

/* =================
 定义链表数据结构
================= */
struct node
{
    int num;
    struct node *prior;    //prior存放上一个结点的地址
    struct node *next;     //next存放下一个结点的地址
};

typedef struct node Node;
typedef Node * Dlink;

/* ===============
 功能:设头结点
 返回:void
=============== */
void init_d_link(Dlink *head)
{
    *head = (Dlink)malloc(sizeof(Node));  //为头结点分配空间

    (*head)->prior = *head;
    (*head)->next = *head;
}

/* =====================
 功能:从头部插入结点
 返回:void
===================== */
void insert_head_node(Dlink newnode,Dlink head)
{
    newnode->next = head->next;
    head->next->prior = newnode;

    head->next = newnode;
    newnode->prior = head;
}

/* ================
 功能:打印链表
 返回:void
================ */
void display_link(Dlink head)
{
    Dlink temp = head->next;
    while (temp != head)     //遍历链表
    {
        printf("%d\n", temp->num);
        temp = temp->next;
    }
}

int main()
{
    Dlink head;
    Dlink newnode;

    init_d_link(&head);

    for (int i = 0; i < 10; i++)
    {
        newnode = (Dlink)malloc(sizeof(Node));  //为结点分配空间
        newnode->num = i + 1;                   //为结点数据域赋值
        insert_head_node(newnode, head);        //头插
    }

    printf("头插后的链表为 : \n");
    display_link(head);                         //打印链表

    return 0;
}

运行结果:

头插后的链表为 : 
10
9
8
7
6
5
4
3
2
1

3.2 尾插

#include <stdio.h>
#include <stdlib.h>

/* =================
 定义链表数据结构
================= */
struct node
{
    int num;
    struct node *prior;    //prior存放上一个结点的地址
    struct node *next;     //next存放下一个结点的地址
};

typedef struct node Node;
typedef Node * Dlink;

/* ===============
 功能:设头结点
 返回:void
=============== */
void init_d_link(Dlink *head)
{
    *head = (Dlink)malloc(sizeof(Node));  //为头结点分配空间

    (*head)->prior = *head;
    (*head)->next = *head;
}

/* =====================
 功能:从尾部插入结点
 返回:void
===================== */
void insert_tail_node(Dlink newnode, Dlink head)
{
    head->prior->next = newnode;
    newnode->prior = head->prior;

    newnode->next = head;
    head->prior = newnode;
}

/* ================
 功能:打印链表
 返回:void
================ */
void display_link(Dlink head)
{
    Dlink temp = head->next;
    while (temp != head)     //遍历链表
    {
        printf("%d\n", temp->num);
        temp = temp->next;
    }
}

int main()
{
    Dlink head;
    Dlink newnode;

    init_d_link(&head);

    for (int i = 0; i < 10; i++)
    {
        newnode = (Dlink)malloc(sizeof(Node));  //为结点分配空间
        newnode->num = i + 1;                   //为结点数据域赋值
        insert_tail_node(newnode, head);        //尾插
    }

    printf("尾插后的链表为 : \n");
    display_link(head);                         //打印链表

    return 0;
}

运行结果:

尾插后的链表为 : 
1
2
3
4
5
6
7
8
9
10

3.3 从中间插入

#include <stdio.h>
#include <stdlib.h>

/* =================
 定义链表数据结构
================= */
struct node
{
    int num;
    struct node *prior;    //prior存放上一个结点的地址
    struct node *next;     //next存放下一个结点的地址
};

typedef struct node Node;
typedef Node * Dlink;

/* ===============
 功能:设头结点
 返回:void
=============== */
void init_d_link(Dlink *head)
{
    *head = (Dlink)malloc(sizeof(Node));  //为头结点分配空间

    (*head)->prior = *head;
    (*head)->next = *head;
}

/* =====================
 功能:从尾部插入结点
 返回:void
===================== */
void insert_tail_node(Dlink newnode, Dlink head)
{
    head->prior->next = newnode;
    newnode->prior = head->prior;

    newnode->next = head;
    head->prior = newnode;
}

/* =====================
 功能:从中间插入结点
 返回:是否成功
===================== */
int insert_mid_node(Dlink newnode, Dlink head,int num)
{
    Dlink temp = head->next;
    while (temp != head)        //遍历链表
    {
        if (temp->num == num)   //判断是否是要找的结点
        {
            newnode->next = temp->next;
            temp->next->prior = newnode;

            temp->next = newnode;
            newnode->prior = temp;

            return 0;
        }
        temp = temp->next;
    }

    return -1;
}

/* ================
 功能:打印链表
 返回:void
================ */
void display_link(Dlink head)
{
    Dlink temp = head->next;
    while (temp != head)    //遍历链表
    {
        printf("%d\n", temp->num);
        temp = temp->next;
    }
}

int main()
{
    Dlink head;
    Dlink newnode;

    init_d_link(&head);

    for(int i = 0; i < 10; i++)
    {
        newnode = (Dlink)malloc(sizeof(Node));  //为结点分配空间
        newnode->num = i + 1;                   //为结点数据域赋值
        insert_tail_node(newnode, head);        //尾插
    }

    newnode = (Dlink)malloc(sizeof(Node));      //为新结点分配空间
    newnode->num = 11;                          //数据域赋值
    insert_mid_node(newnode, head, 5);          //在数据域为5的结点后插入新结点

    printf("从中间插入后的链表为 : \n");
    display_link(head);                         //打印链表

    return 0;
}

运行结果:

从中间插入后的链表为 : 
1
2
3
4
5
11
6
7
8
9
10

4. 删除结点

#include <stdio.h>
#include <stdlib.h>

/* =================
 定义链表数据结构
================= */
struct node
{
    int num;
    struct node *prior;    //prior存放上一个结点的地址
    struct node *next;     //next存放下一个结点的地址
};
 
typedef struct node Node;
typedef Node * Dlink;
 
/* ===============
 功能:设头结点
 返回:void
=============== */
void init_d_link(Dlink *head)
{
    *head = (Dlink)malloc(sizeof(Node));  //为头结点分配空间

    (*head)->prior = *head;
    (*head)->next = *head;
}
 
/* =====================
 功能:从尾部插入结点
 返回:void
===================== */
void insert_tail_node(Dlink newnode, Dlink head)
{
    head->prior->next = newnode;
    newnode->prior = head->prior;
 
    newnode->next = head;
    head->prior = newnode;
}
 
/* ===============
 功能:删除结点
 返回:是否成功
=============== */
int delete_node(int num, Dlink head)
{
    Dlink temp = head->next;
    while (temp != head)         //遍历链表
    {
        if (temp->num == num)    //判断是否是要删除的结点
        {
            temp->prior->next = temp->next;
            temp->next->prior = temp->prior;
 
            free(temp);         //释放
            temp = NULL;        //置空
 
            return 0;
        }
        temp = temp->next;
    }
 
    return -1;
}
 
/* ================
 功能:打印链表
 返回:void
================ */
void display_link(Dlink head)
{
    Dlink temp = head->next;
    while (temp != head)     //遍历链表
    {
        printf("%d\n", temp->num);
        temp = temp->next;
    }
}
 
int main()
{
    Dlink head;
    Dlink newnode;
 
    init_d_link(&head);

    for(int i = 0; i < 10; i++)
    {
        newnode = (Dlink)malloc(sizeof(Node));  //为结点分配空间
        newnode->num = i + 1;                   //为结点数据域赋值
        insert_tail_node(newnode, head);        //尾插
    }
    
    delete_node(7, head);                       //删除数据域为7的结点
    
    printf("删除数据域为7的结点后的链表为 : \n");
    display_link(head);                         //打印链表
 
    return 0;
}

运行结果:

删除数据域为7的结点后的链表为 : 
1
2
3
4
5
6
8
9
10

相关文章

【链表】单链表:不带表头结点
【链表】单链表:带表头结点
【链表】单链表:单循环链表