循环链表

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

前言

循环链表的实现及合并

编程语言：C

循环链表

循环链表的定义

  • 将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
  • 循环链表解决了如何从链表当中一个结点出发，访问到链表的全部结点

基本操作实现

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

typedef struct Node
{
    int data;
    struct Node *next;
} Node;
  • 初始化头结点
1
2
3
4
5
void InitHead(Node *p)
{
    p->data = 0;
    p->next = p;
}

  • 循环链表和单链表的差异就是终端结点的指针端指向的是头结点

  • 原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束

  • 当然也可以不用头结点，而改用尾指针的形式，这样就可以既O(1)的访问到第一个结点，也可以O(1)的访问到最后一个结点

  • 随机初始化一个链表，表头的数据域存储表长信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void RandLinkList(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 Node));
        temp->data = rand() % 100;
        temp->next = p;
        q->next = temp;
        q = q->next;
    }
    pf("当前表中一共有%d位元素\n", p->data);
}
  • 合并两个循环链表
1
2
3
4
5
6
7
8
9
10
11
void LinkCircular(Node *L1, Node *L2)
{
    Node *p = L1, *q = L2;
    while(p->next != L1) p = p->next;
    p->next = q->next;
    while(q->next != L2) q = q->next;
    q->next = L1;
    L1->data += L2->data;
    free(L2);
    L2 = NULL;
}

总结

  • 循环链表解决了单链表从当中一个结点出发，无法访问到单链表的全部结点的问题
  • 循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束
  • 将头结点改为尾指针不仅在查找第一和最后一个结点很方便，在合并循环链表时也非常方便