双向循环链表

数据结构 › C
,
·本篇:530字 大约需要: 2分钟

前言

双向循环链表的实现及合并

编程语言：C

双向循环链表

双向循环链表的定义

  • 在循环链表每个结点中，再设置一个指向其前驱结点的指针域
  • 双向循环链表解决了单链表查找上一结点最坏时间复杂度为O(n)的缺点

基本操作实现

  • 结构代码
1
2
3
4
5
6
7
8
9
10
11
12
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define sf scanf
#define pf printf

typedef struct DuNode
{
    int data;
    struct DuNode *prior;
    struct DuNode *next;
} Node;
  • 初始化头结点
1
2
3
4
5
6
void InitHead(Node *p)
{
    p->data = 0;
    p->prior = p;
    p->next = p;
}
  • 在双向循环链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱
  • 随机初始化一个双向循环链表，表头的数据域存储表长信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void RandDuLinkList(Node *p)
{
    Node *q = p;
    while(q->next != p) q = q->next;
    srand((unsigned) time(0));
    int length = rand() % 10 + 10;
    p->data += length;
    while(length--)
    {
        Node *temp = (Node *) malloc(sizeof(struct DuNode));
        temp->data = rand() % 100;
        temp->prior = q;
        temp->next = p;
        q->next = temp;
        q = q->next;
        p->prior = q;
    }
    pf("当前表中一共有%d位元素\n", p->data);
}
  • 合并两个双向循环链表
1
2
3
4
5
6
7
8
9
10
11
12
13
void DDuLinkMerge(Node *L1, Node *L2)
{
    Node *p = L1, *q = L2->next;
    while(p->next != L1) p = p->next;
    p->next = q;
    q->prior = p;
    while(q->next != L2) q = q->next;
    q->next = L1;
    L1->prior = q;
    L1->data += L2->data;
    free(L2);
    L2 = NULL;
}
  • 合并两个有序(升序)双向循环链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void DDuOrderLinkMerge(Node *L1, Node *L2)
{
    Node *p = L1->next, *person = L1, *q = L2->next, *temp;
    while(p != L1 && q != L2)
    {
        if(p->data >= q->data)
        {
            temp = q;
            q = q->next;
            temp->next = p;
            temp->prior = person;
            person->next = temp;
            person = person->next;
        }
        else
        {
            person = p;
            p = p->next;
        }
    }
    if(p == L1)
    {
        person->next = q;
        q->prior = person;
        while(q->next != L2) q = q->next;
        q->next = L1;
        L1->prior = q;
    }
    L1->data += L2->data;
    free(L2);
    L2 = NULL;
}

总结

  • 其它操作实现并不复杂，双向循环链表只是比单链表多了一个前驱指针