双向循环链表

在结构体中加入了一个指向前驱结点的指针，参照单向循环链表思路，使得在双向循环链表中每一个结点都有前驱结点和后继结点。

双向循环链表结构体声明

typedef struct dl_link{
    data_t data;
    struct dl_link* front;
    struct dl_link* next;
}DLLINK;

双向循环链表的操作

基本操作：创建、插入（头插/尾插）、删除、遍历（打印）、查找、修改等。

创建一个双向循环链表表头

DLLINK *creat()
{
    DLLINK *h = (DLLINK*)malloc(sizeof(DLLINK));
    memset(&(h->data),0,sizeof(data_t));
    h->front = h;
    h->next = h;
    return h;
}

初始化头结点前驱指针和后继指针均指向头结点自身

创建一个数据结点

DLLINK *creatNode(data_t val)
{
    DLLINK *node = (DLLINK*)malloc(sizeof(DLLINK));
    node->data = val;
    node->front = NULL;
    node->next = NULL;
    return node;
}

头插法插入

void insert(DLLINK *h,data_t val)
{
    DLLINK *node = creatNode(val);
    node->next = h->next;
    h->next->front = node;
    h->next = node;
    node->front = h;
}

1、创建一个新结点

2、修改指针的指向，先建立第一个数据结点和新结点的联系，再建立头结点和新结点的联系，保证不断链

尾插法插入

void tailInsert(DLLINK *h,data_t val)
{
    DLLINK *node = creatNode(val);
    h->front->next = node;
    node->front = h->front;
    node->next = h;
    h->front = node;
}

1、创建一个新结点

2、修改指针的指向，先建立新结点和最后一个数据结点的指针联系，再建立新结点和头结点的联系，保证不断链

头删法删除

void deleteHead(DLLINK *h)
{
    DLLINK *temp = h->next;
    h->next = temp->next;
    temp->next->front = h;
    free(temp);
}

删除第一个数据结点，要先建立头结点和第一个数据结点的后继结点的指针联系，再free动态分配的内存空间

尾删法删除

void deleteTail(DLLINK *h)
{
    DLLINK *temp = h->front;
    temp->front->next = h;
    h->front = temp->front;
    free(temp);
}

删除最后一个数据结点，要先建立头结点和最后一个数据结点的前驱结点的指针联系，再释放最后一个结点空间

顺序遍历（打印）

void printOrder(DLLINK *h)
{
    DLLINK *temp = h;
    while(h->next != temp)
    {
        h = h->next;
        printf("%d ",h->data);
    }
    putchar(10);
}

逆序遍历（打印）

void printReversed(DLLINK *h)
{
DLLINK *temp = h;
while(h->front != temp)
{
h = h->front;
printf("%d ",h->data);
}
putchar(10);
}

顺序遍历的出发点是头结点的后继结点即第一个数据结点，遍历直到回到头结点

逆序遍历的出发点是头结点的前驱结点即最后一个数据结点，遍历直到回到头结点

示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int data_t;
typedef struct dl_link{
    data_t data;
    struct dl_link* front;
    struct dl_link* next;
}DLLINK;

DLLINK *creat();
DLLINK *creatNode(data_t val);
void insert(DLLINK *h,data_t val);
void tailInsert(DLLINK *h,data_t val);
void deleteHead(DLLINK *h);
void deleteTail(DLLINK *h);
void printReversed(DLLINK *h);
void printOrder(DLLINK *h);

int main(int argc, const char *argv[])
{
    DLLINK *h = creat();
    insert(h,1);//头插
    printOrder(h);//顺序打印
    insert(h,2);//头插
    printOrder(h);//顺序打印
    insert(h,3);//头插
    printOrder(h);//顺序打印
    tailInsert(h,4);//尾插
    printOrder(h);//顺序打印
    tailInsert(h,5);//尾插
    printOrder(h);//顺序打印
    tailInsert(h,6);//尾插
    printOrder(h);//顺序打印

    deleteHead(h);//头删
    printOrder(h);//顺序打印
    deleteTail(h);//尾删
    printOrder(h);//顺序打印

    printReversed(h);//逆序打印
    return 0;
}
//创建一个双向循环链表表头
DLLINK *creat()
{
    DLLINK *h = (DLLINK*)malloc(sizeof(DLLINK));
    memset(&(h->data),0,sizeof(data_t));
    h->front = h;
    h->next = h;
    return h;
}
//创建一个数据节点
DLLINK *creatNode(data_t val)
{
    DLLINK *node = (DLLINK*)malloc(sizeof(DLLINK));
    node->data = val;
    node->front = NULL;
    node->next = NULL;
    return node;
}
//头插法插入一个数据节点
void insert(DLLINK *h,data_t val)
{
    DLLINK *node = creatNode(val);
    node->next = h->next;
    h->next->front = node;
    h->next = node;
    node->front = h;
}
//尾插法
void tailInsert(DLLINK *h,data_t val)
{
    DLLINK *node = creatNode(val);
    h->front->next = node;
    node->front = h->front;
    node->next = h;
    h->front = node;
}
//头删法
void deleteHead(DLLINK *h)
{
    DLLINK *temp = h->next;
    h->next = temp->next;
    temp->next->front = h;
    free(temp);
}
//尾删法
void deleteTail(DLLINK *h)
{
    DLLINK *temp = h->front;
    temp->front->next = h;
    h->front = temp->front;
    free(temp);
}
//遍历打印（逆序）
void printReversed(DLLINK *h)
{
    DLLINK *temp = h;
    while(h->front != temp)
    {
        h = h->front;
        printf("%d ",h->data);
    }
    putchar(10);
}
//遍历打印（顺序）
void printOrder(DLLINK *h)
{
    DLLINK *temp = h;
    while(h->next != temp)
    {
        h = h->next;
        printf("%d ",h->data);
    }
    putchar(10);
}

结果

1
2 1
3 2 1
3 2 1 4
3 2 1 4 5
3 2 1 4 5 6
2 1 4 5 6
2 1 4 5
5 4 1 2

本文链接：https://shengto.top/data_structure/146.html

转载时须注明出处及本声明

Last modification：2021 年 03 月 25 日 23 : 32 : 49
© 允许规范转载