数据结构和算法之一——线性表_3_链式存储结构_2_循环链表

1. 循环链表定义

单循环链表

将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表成为单循环链表,简称循环链表。

(注:这里并不是说循环链表一定要有头结点。但是对于空链表，则需要有头结点表示该存储方式为一个链表，且“head->next == head”)

2. 循环链表操作

1）初始化循环链表：见例1.

//例1
Status ds_init(Node **node)
{
    *node = (Node *)malloc(sizeof(Node));
    (*node)->Next = *node;
}

2）插入元素：见例2.

//例2
Status ds_insert(Node **node, int i, Elemtype n)
{
    Node *target, *temp,*p;
    int j;
    target = *node;
    temp = (Node *)malloc(sizeof(Node));
    temp->Data = n;
    
    if(i == 1)
    {
        while(target && target->Next != *node)
        {
            target = target->Next;
        }
        temp->Next = *node;
        target->Next = temp;
        *node = temp;
    }
    else
    {
        for(j = 1; j < i-1; j++)
        {
            target = target->Next;
        }
        temp->Next = target->Next;
        target->Next = temp;
    }
}

3）删除元素：例3

//例3
Status ds_delete(Node **node, int i)
{
    Node *target, *temp;
    int j;
    target = *node;

    if(i == 1)
    {
        for(; target->Next != *node; target = target->Next)
            ;
        printf("123\n");
        temp = *node;
        target->Next = (*node)->Next;
        *node = target->Next;
    }
    else
    {
        for(j = 1; j < i-1; j++)
        {
            target = target->Next;
        }
        if(target->Next == *node)
        {
            temp = *node;
            target->Next = (*node)->Next;
            *node = target->Next;
        }
        else
        {
            temp = target->Next;
            target->Next = temp->Next;
        }
    }
    printf("The delete data is: %d\n", temp->Data);
    
}

//例4，总体框架代码
#include<stdio.h>
#include<stdlib.h>

typedef int Elemtype;
typedef int Status;

typedef struct LinkList
{
    Elemtype Data;
    struct LinkList *Next;
}Node;

Status vist(Node *node)
{
    printf("%d ", (node)->Data);
}

Status travellist(Node *node)
{
    Node *temp;
    temp = node;
    vist(temp);
    temp = (node)->Next;

    while(temp && temp != node)
    {
        vist(temp);
        temp = temp->Next;
    }
    printf("\n");
}

Status ds_init(Node **node)
{
    *node = (Node *)malloc(sizeof(Node));
    (*node)->Next = *node;
}

Status ds_creatlinklist(Node **node)
{
    int data;
    Node *Target, *temp;
    printf("Please input the node data: ");
    scanf("%d", &data);
    (*node)->Data = data;

    printf("If you input 0, the process of creating linklist will be stopped!\n");
    while(1)
    {   
        printf("Please input the node data: ");
        scanf("%d", &data);
        if(data == 0)
        {
            break;
        }
        for(Target = (*node); Target->Next != (*node); Target = Target->Next )
            ;
        temp = (Node *)malloc(sizeof(Node));
        temp->Data = data;
        temp->Next = *node;
        Target->Next = temp;
    }
}

Status ds_insert(Node **node, int i, Elemtype n)
{
    Node *target, *temp,*p;
    int j;
    target = *node;
    temp = (Node *)malloc(sizeof(Node));
    temp->Data = n;
    
    if(i == 1)
    {
        while(target && target->Next != *node)
        {
            target = target->Next;
        }
        temp->Next = *node;
        target->Next = temp;
        *node = temp;
    }
    else
    {
        for(j = 1; j < i-1; j++)
        {
            target = target->Next;
        }
        temp->Next = target->Next;
        target->Next = temp;
    }
}

Status ds_delete(Node **node, int i)
{
    Node *target, *temp;
    int j;
    target = *node;

    if(i == 1)
    {
        for(; target->Next != *node; target = target->Next)
            ;
        printf("123\n");
        temp = *node;
        target->Next = (*node)->Next;
        *node = target->Next;
    }
    else
    {
        for(j = 1; j < i-1; j++)
        {
            target = target->Next;
        }
        if(target->Next == *node)
        {
            temp = *node;
            target->Next = (*node)->Next;
            *node = target->Next;
        }
        else
        {
            temp = target->Next;
            target->Next = temp->Next;
        }
    }
    printf("The delete data is: %d\n", temp->Data);
    
}

Status ds_length(Node **node)
{
    int i;
    Node *target;
    
    target = *node;
    for(i = 1; target->Next != *node; target->Next)
    {
        target = target-> Next;
        i++;
    }
    printf("The length is: %d\n", i);
    return i;
}

Status ds_treble(Node **node)
{
    Node *target, *temp;
    int i;
    target = *node;

    for(i = 1; i < 2; i++)
    {
        target = target->Next;
    }
    temp = target->Next;
    target->Next = temp->Next;
    *node = temp->Next;
}

void main()
{
    Node *node;
    int len = 0;
    int num, pos;
    char operation;
    
    ds_init(&node);
    printf("1.初始化链表 \n\n2.插入结点 \n\n3.删除结点 \n\n#.退出 \n\n请选择你的操作：");
    while(operation != '#')
    {
        scanf("%c", &operation);
        switch(operation)
        {
            case '1':
                ds_creatlinklist(&node);
                travellist(node);
                printf("\n");
                break;

            case '2':
                printf("Please input the number that you want insert:");
                scanf("%d", &num);
                printf("Please input the postion that you want insert:");
                scanf("%d", &pos);
                ds_insert(&node, pos, num);
                travellist(node);
                printf("\n");
                break;      
        
            case '3':
                printf("Please input the number that you want delete:");
                scanf("%d", &num);
                ds_delete(&node, num);
                travellist(node);
                printf("\n");
                break;
        }
    }

}

3. Josephus问题：

在罗马人占领乔塔帕特后, 39 个犹太人与Josephus 及他的朋友躲到一个洞中, 39 个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式, 41 个人排成一个圆圈,由第 1 个人开始报数,每报数到第 3 人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而 Josephus和他的朋友并不想遵从, Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16 个与第 31 个位置,于是逃过了这场死亡游戏。见例5.

//例5
#include<stdio.h>
#include<stdlib.h>

typedef int Elemtype;
typedef int Status;

typedef struct LinkList
{
    Elemtype Data;
    struct LinkList *Next;
}Node;

Status vist(Node *node)
{
    printf("%d ", (node)->Data);
}

Status travellist(Node *node)
{
    Node *temp;
    temp = node;
    vist(temp);
    temp = (node)->Next;

    while(temp && temp != node)
    {
        vist(temp);
//printf("$$$$$$$$$$");
        temp = temp->Next;
    }
    printf("\n");
}

Status ds_init(Node **node)
{
    *node = (Node *)malloc(sizeof(Node));
    (*node)->Next = *node;
}

Status ds_creatlinklist(Node **node)
{
    int data = 1;
    Node *Target, *temp;
    (*node)->Data = data;

    for(data = 2; data <42; data++)
    {   
        for(Target = (*node); Target->Next != (*node); Target = Target->Next )
            ;
        temp = (Node *)malloc(sizeof(Node));
        temp->Data = data;
        temp->Next = *node;
        Target->Next = temp;
    }
}



Status ds_length(Node **node)
{
    int i;
    Node *target;
    
    target = *node;
    for(i = 1; target->Next != *node; target->Next)
    {
        target = target-> Next;
        i++;
    }
    return i;
}

Status ds_josephus(Node **node)
{
    Node *target, *temp;
    int i;
    target = *node;

    for(i = 1; i < 2; i++)
    {
        target = target->Next;
    }
    temp = target->Next;
    target->Next = temp->Next;
    *node = temp->Next;
}

void main()
{
    Node *node;
    int len = 0;

    
    ds_init(&node);


    ds_creatlinklist(&node);
    travellist(node);
    printf("\n");
    len = ds_length(&node);

    while(len > 2)
    {
        ds_josephus(&node);
        len = ds_length(&node);
    }
    travellist(node);
}
//输出：
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 33 34 35 36 37 38 39 40 41 

16 31

4. 两个循环链表连接问题

//例6
#include<stdio.h>
#include<stdlib.h>

typedef int Elemtype;
typedef void Status;

typedef struct node 
{
    Elemtype data;
    struct node *next;
}Node;

Status InitCirLinkList(Node **head)
{
    *head = (Node *)malloc(sizeof(Node));
    (*head)->next = (*head);
}

Status CreateLinkListTail(Node **head, int n)
{
    Node *target, *temp;
    int i;
    
    target = *head;
    target->data = 1;
    
    for(i = 2; i <= n; i++)
    {
        temp = (Node *)malloc(sizeof(Node));    
        temp->data = i;
        target->next = temp;
        target = target->next;
    }
    target->next = (*head);
}

Status CreateLinkListhead(Node **head, int n)
{
    Node *target, *rear, *temp;
    int i;
    
    rear = *head;
    target = *head;
    target->data = 1;
    
    for(i = 1; i <= n; i++)
    {
        temp = (Node *)malloc(sizeof(Node));    
        temp->data = i;
        temp->next = target;
        target = temp;
    }
    rear->next = target;
    (*head) = target;
}

Status Visit(Node *node)
{
    if(node)
    {
        printf("%d ", node->data);
    }
    printf("\n");
}

Status Traversal(Node **head)
{
    Node *target;
    
    target = *head;
    Visit(target);
    target = target->next;

    while(target && target != *head)
    {
        Visit(target);
        target = target->next;  
    }
}

Status Connect(Node **head1, Node **head2)
{
    Node *target1, *target2;
    
    target1 = *head1;
    target2 = *head2;

    while(target1 && target1->next != *head1)
    {
        target1 = target1->next;
    }
    target1->next = target2;

    while(target2 && target2->next != *head2)
    {
        target2 = target2->next;    
    }
    target2->next = *head1;
}

void main()
{
    Node *L1;
    Node *L2;
    int n1, n2;
    char c;
    
    InitCirLinkList(&L1);
    InitCirLinkList(&L2);
    printf("How many element that you want create for the first LinkList?");
    scanf("%d", &n1);
    CreateLinkListTail(&L1, n1);    
    Traversal(&L1);
    printf("\n");

    printf("How many element that you want create for the second LinkList?");
    scanf("%d", &n2);
    CreateLinkListhead(&L2, n2);    
    Traversal(&L2);     
    printf("\n");

    Connect(&L1, &L2);
    Traversal(&L1);
}

5. 判断链表内部是否有环（例题设置链表为非循环链表）

方法1：利用快慢指针来判定，快慢指针同时遍历链表，快指针的速度是慢指针的速度的2倍。如果，到后面快指针追上慢指针说明有环。见例7.

//例7
Status Fspointer(Node **L)          //利用快慢指针来统计
{
    Node *fast, *slow;
    int step = 0;
    fast = *L;
    slow = *L;
    

    while(fast != NULL && slow != NULL && fast->next != NULL)   /*“fast->next != NULL”是因为fast要跳2格，因此中间不能为空，如果为空则结束*/
    {
        fast = fast->next->next;
        slow = slow->next;
        step++;
        
        if(fast == slow)
        {
            printf("There has loop in this linklist!");
            return;
        }
    }
    printf("There is no loop in this linklist!");
}

方法2：利用计步器step1和step2，step1永远是一直一步步往下走，step2是：当step2的node和step1的node完全相同时，判定step2是不是等于step1，如果相等，则step1++，step2归零，然后继续执行，直到step1走完链表；或者当step2的node等于step1的node，但是step2 != step1，则说明有环。见例8.

//例8
Status Comparestep(Node **L)        //通过设置两个计步器来比较同一点的步数是否相同
{
    int step1, step2;
    Node *p, *q;
    p = *L;
    

    step1 = 0;
    while(p)
    {
        q = *L;
        step2 = 0;
        while(q)
        {
            if(p == q)
            {
                if(step1 == step2)
                {                   
                    break;
                }
                else
                {
                    printf("From the %dth the loop is beginning!", step2);
                    return;
                }
            }
            q = q->next;
            step2++;
        }
        p = p->next;
        step1++;
    }
    printf("There is no loop in this linklist!");
}

//例9，总体框架代码
#include<stdio.h>
#include<stdlib.h>

typedef int Elemtype;
typedef void Status;

//#define LINKLIST_SIZE 15;

typedef struct node
{
    Elemtype data;
    struct node *next;
}Node;

Status vist(Node *node)
{
    printf("%d ", (node)->data);
}

Status TravelList(Node *node)
{
    Node *temp;
    temp = node;
    vist(temp);
    temp = (node)->next;

    while(temp && temp != node)
    {
        vist(temp);
        temp = temp->next;
    }
    printf("\n");
}


Status InitLinkList(Node **L)
{
    (*L) = (Node *)malloc(sizeof(Node));
    (*L)->next = NULL;
}

Status CrearteLinkListTail(Node **L)    //尾插法。创建有环单链表
{
    Node *target, *temp;
    int i;

    target = *L;
    target->data = rand()%100+1;


    for(i = 2; i <= 15; i++)
    {
        temp = (Node *)malloc(sizeof(Node));
        temp->data = rand()%100+1;
        target->next = temp;
        target = target->next;
    }
    target->next = (*L)->next->next->next;
}

Status CreateLinkListHead(Node **L)     //头插法，创建无环单链表
{
    Node *target, *temp;
    int i;
    
    target = *L;
    target->data = rand()%100+1;

    for(i = 2; i <= 15; i++)
    {
        temp = (Node *)malloc(sizeof(Node));
        temp->data = rand()%100+1;
        temp->next = target;
        target = temp;
    }
    *L = target;
}

Status Comparestep(Node **L)        //通过设置两个计步器来比较同一点的步数是否相同
{
    int step1, step2;
    Node *p, *q;
    p = *L;
    

    step1 = 0;
    while(p)
    {
        q = *L;
        step2 = 0;
        while(q)
        {
            if(p == q)
            {
                if(step1 == step2)
                {                   
                    break;
                }
                else
                {
                    printf("From the %dth the loop is beginning!", step2);
                    return;
                }
            }
            q = q->next;
            step2++;
        }
        p = p->next;
        step1++;
    }
    printf("There is no loop in this linklist!");
}

Status Fspointer(Node **L)          //利用快慢指针来统计
{
    Node *fast, *slow;
    int step = 0;
    fast = *L;
    slow = *L;
    

    while(fast != NULL && slow != NULL && fast->next != NULL)   //“fast->next != NULL”是因为fast要跳2格，因此中间不能为空，如果为空则结束
    {
        fast = fast->next->next;
        slow = slow->next;
        step++;
        
        if(fast == slow)
        {
            printf("There has loop in this linklist!");
            return;
        }
    }
    printf("There is no loop in this linklist!");
}

Status ClearLinkList(Node **L)
{
    Node *target, *temp;
    target = *L;

    while(target)
    {
        temp = target;
        target = target->next;
        free(temp);
    }
}


void main()
{
    Node *L;
    char operation;
    
    InitLinkList(&L);
    printf("\n1.创建有环链表（尾插法） \n2.创建无环链表（头插法） \n3.判断链表是否有环 \n#.退出 \n\n请选择你的操作：\n");

    while(operation != '#')
    {
        scanf("%c", &operation);
        switch(operation)
        {
            case '1':
                CrearteLinkListTail(&L);
                printf("\n");
                break;
            case '2':
                CreateLinkListHead(&L);
                printf("\n");
                break;
            case '3':
                printf("Method one!   ");
                Comparestep(&L);
                printf("\n");
                printf("Method two!   ");
                Fspointer(&L);  
                printf("\n");
                break;
            case '#':
                exit(0);
        }       
    }   
}

5. 拉丁方阵

拉丁方阵是一种 n×n 的方阵,方阵中恰有 n 种不同的元素,每种元素恰有 n 个,并且每种元素在一行和一列中 恰好出现一次。见例10.

//例10，核心代码
Status TraversalList(Node **node)
{
    Node *target;

    target = *node;
    Visit(target);
    target = target->next;
    
    while(target != *node)
    {
        Visit(target);
        target = target->next;
    }   
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,088评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,715评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,361评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,099评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 60,987评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,063评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,486评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,175评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,440评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,518评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,305评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,190评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,550评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,880评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,152评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,451评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,637评论 2赞 335

推荐阅读更多精彩内容