1. 全栈程序员必看首页

循环链表的实现_建立双向循环链表

全栈程序员-用户IM • • 未分类

循环链表的实现_建立双向循环链表循环链表循环链表是一个收尾相接的链表，将单链表的最后一个指针域改由NULL改为指向表头结点这就是单链式的循环链表，并称为循环单链表带头结点的循环单链表的各种操作的算法实现与带头结点单链表的算法实现

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

循环链表

　　循环链表是一个收尾相接的链表，将单链表的最后一个指针域改由NULL改为指向表头结点这就是单链式的循环链表，并称为循环单链表

　　循环链表的实现_建立双向循环链表

　　带头结点的循环单链表的各种操作的算法实现与带头结点单链表的算法实现类似，差别仅在于算法判别当前结点p是否为尾结点的条件不同。单链表中的判别条件为p!=NULL或p->next!=NULL，而单循环链表判别条件是p!=L或p->next!=L

　　在循环单链表中附设尾指针有时候比附设头指针更简单。如：在用头指针的循环单链表中找a1的时间复杂度是O(1),找an需要从头找到尾，时间复杂度是O(n),如果用为指针rear，找开始结点和终端结点的存储位置分别是rear->next->next和rear。

　　建立循环单链表

void CreatCLLinkList(CLLinkList CL) 
{
    Node *rear,*s;
    rear=CL;//rear指针动态指向当前表尾，其初始值指向头结点 
    int flag=1;
    int x;
    printf("Please input data and enter 0 end:\n");
    while(flag)
    {
        scanf("%d",&x);
        if(x!=0)
        {
            s=(Node *)malloc(len);
            s->data=x;
            rear->next=s;
            rear=s;
        }
        else
        {
            flag=0;
            rear->next=CL;//最后一个节点的next域指向头结点 
        }
    }
}

　　循环单链表的插入

#include<stdio.h>
#include<stdlib.h>
#define len sizeof(Node)

typedef struct Node
{
    int data;
    struct Node *next;    
}Node,*CLLinkList;

void InitCLLinkList(CLLinkList *CL)
{
    *CL=(CLLinkList)malloc(len);
    (*CL)->next=*CL;
}

void CreatCLLinkList(CLLinkList CL) 
{
    Node *rear,*s;
    rear=CL;//rear指针动态指向当前表尾，其初始值指向头结点 
    int flag=1;
    int x;
    printf("Please input data and enter 0 end:\n");
    while(flag)
    {
        scanf("%d",&x);
        if(x!=0)
        {
            s=(Node *)malloc(len);
            s->data=x;
            rear->next=s;
            rear=s;
        }
        else
        {
            flag=0;
            rear->next=CL;//最后一个节点的next域指向头结点 
        }
    }
}

void PrintCLLinkList(CLLinkList CL)
{
    Node *p;
    p=CL->next;
    printf("You input data is:\n");
    for(;p!=CL;p=p->next)
    {
        printf("%-3d",p->data);
    }
    printf("\n");
}

void InCLLinkList(CLLinkList CL,int i,int x)
{
    Node *p,*s;
    int k=0;
    p=CL;
    if(i<=0)
    {
        printf("You enter location illegal:\n");
        return;
    }
    while(p->next!=CL&&k<i-1)
    {
        k++;
        p=p->next;
    }
    if(p==CL)
    {
        printf("The insert position is not reasonable:\n");
        return;
    }
    s=(Node *)malloc(len);
    s->data=x;
    s->next=p->next;
    p->next=s;
    printf("Insert successfully\n");
}

void Print_CLLinkList(CLLinkList CL)
{
    Node *p;
    p=CL->next;
    printf("Now you input data is:\n");
    for(;p!=CL;p=p->next)
        printf("%-3d",p->data);
}

int main()
{
    int i,x;
    CLLinkList CL;
    InitCLLinkList(&CL);
    CreatCLLinkList(CL);
    PrintCLLinkList(CL);
    
    printf("Please enter the location you want to insert:\n");
    scanf("%d",&i);
    printf("Please enter the values you want to insert:\n") ;
    scanf("%d",&x);

    InCLLinkList(CL,i,x);
    Print_CLLinkList(CL);
    free(CL);
    return 0;
}

　　循环单链表的删除

#include<stdio.h>
#include<stdlib.h>
#define len sizeof(Node)
typedef struct Node
{
    int data;
    struct Node *next;
}Node,*LinkList;

void InitCLLinkList(LinkList *CL)
{
    *CL=(LinkList)malloc(len);
    (*CL)->next=*CL;
}
void CreatCLLinkList(LinkList CL)
{
    int flag=1,x;
    Node *rear,*s;
    rear=CL;
    printf("Please input data and enter 0 end:\n");
    while(flag)
    {
        scanf("%d",&x);
        if(x!=0)
        {
            s=(Node *)malloc(len);
            s->data=x;
            rear->next=s;
            rear=s;
        }
        else
        {
            rear->next=CL;
            flag=0;
        }
    }
}

void DeleCLLinkList(LinkList CL,int i)
{
    Node *p,*r;
    p=CL;
    int k=0;
    if(i<0)
    {
        printf("You enput i illegal!\n");
        return;
    }
    while(p->next!=CL&&k<i-1)
    {
        p=p->next;
        k++;
    }
    if(p->next==CL)
    {
        printf("Delete Node i illegal!\n");
        return;
    }
    r=p->next;
    p->next=r->next;
    free(r);
}

void PrintCLLinkList(LinkList CL)
{
    Node *p;
    for(p=CL->next;p!=CL;p=p->next)    
    {
        printf("%3d",p->data);
    }
}
int main()
{
    LinkList CL;
    int i;
    InitCLLinkList(&CL);
    CreatCLLinkList(CL);
    
    printf("Please enter the i node you want to delete:\n");
    scanf("%d",&i);
    DeleCLLinkList(CL,i);
    printf("The list after deleting is:\n");
    PrintCLLinkList(CL);
    free(CL);
    
    return 0;
}

　　合并循环单链表

　　　　方法一：先找到两个链表LA，LB的表尾，分别用p，q指向它，然后将第一个链表的表尾与第二个链表的第一个结点连起来，修改第二个表的尾q，使它的链域指向第一个表头

//头指针合并循环链表 
#include<stdio.h>
#include<stdlib.h>
#define len sizeof(Node)

typedef struct Node
{
    int data;
    struct Node *next;
}Node,*CLLinkList;

void InitCL_aLinkList(CLLinkList *CL_a)
{
    *CL_a=(CLLinkList)malloc(len);
    (*CL_a)->next=*CL_a;
}

void InitCL_bLinkList(CLLinkList *CL_b)
{
    *CL_b=(CLLinkList)malloc(len);
    (*CL_b)->next=*CL_b;
}

void CreatCL_aLinkList(CLLinkList CL_a)
{
    Node *p,*s;
    int x,flag=1;
    p=CL_a;
    printf("Please input A data and enter 0 end:\n");
    while(flag)
    {
        scanf("%d",&x);
        if(x!=0)
        {
            s=(Node *)malloc(len);
            s->data=x;
            p->next=s;
            p=s;
        }
        else
        {
            p->next=CL_a;
            flag=0;
        }
    }
}

void CreatCL_bLinkList(CLLinkList CL_b)
{
    Node *p,*s;
    int x,flag=1;
    p=CL_b;
    printf("Please input B data and enter 0 end:\n");
    while(flag)
    {
        scanf("%d",&x);
        if(x!=0)
        {
            s=(Node *)malloc(len);
            s->data=x;
            p->next=s;
            p=s;
        }
        else
        {
            p->next=CL_b;
            flag=0;
        }
    }
}

CLLinkList MergeCLLinkList(CLLinkList CL_a,CLLinkList CL_b)
{
    Node *p,*q;
    p=CL_a;
    q=CL_b;
    while(p->next!=CL_a)//找到LA的表尾，用p指向它 
        p=p->next;
    while(q->next!=CL_b)//找到LB的表尾，用q指向它
        q=q->next;
    q->next=CL_a;//修改LB的表尾指针，使之指向表LA的头结点 
    p->next=CL_b->next;    //修改LA的表尾指针，CL_b->next的意思是跳过CL_b头结点
    free(CL_b);
    return CL_a;
}

void PrintCLLinkList(CLLinkList CL)
{
    printf("CL list is:\n");
    for(Node *p=CL->next;p!=CL;p=p->next)
        printf("%-3d",p->data);
    printf("\n");
}

int main()
{
    CLLinkList CL_a,CL_b,CL;
    InitCL_aLinkList(&CL_a);
    InitCL_bLinkList(&CL_b);
    
    CreatCL_aLinkList(CL_a);
    CreatCL_aLinkList(CL_b);
    
    CL=MergeCLLinkList(CL_a,CL_b);
    PrintCLLinkList(CL_a);
    free(CL_a);
    return 0;
}

　　　　方法二：若采用尾指针设置，无需遍历找到尾结点，只需修改尾指针的指示域即可

CLLinkList MergeCLLinkList(CLLinkList RA,CLLinkList RB)
{
    Node *p=RA->next;//保存RA的头结点地址 
    RA->next=RB->next->next;//RB的头结点练到RA的终端结点之后
    RB->next=p;//将RA的头结点链到RB的终端结点之后
    free(RB->next);//释放RB的头结点 
    return RB;//返回新的链表的尾指针 
}

　　循环链表求长度

#include<stdio.h>
#define len sizeof(Node)
#include<stdlib.h>
typedef struct Node
{
    int data;
    struct Node* next;
}Node,*LinkList;

void InitCLLinkList(LinkList *CL)
{
    *CL=(LinkList)malloc(len);
    (*CL)->next=*CL;
}

//尾插法创建循环链表 
void CreatCLLinkList(LinkList CL)
{
    Node *s,*rear;
    int flag=1;
    rear=CL;
    printf("please input datas and input 0 over:\n");
    int x;    
    while(flag)
    {
        scanf("%d",&x);
        if(x!=0)
        {
           s=(Node *)malloc(len);
        s->data=x;
        rear->next=s;
        rear=s;
        }
        else
        {
            flag=0;
            rear->next=CL;
        }
    }
}

int LengthCLLinkList(LinkList CL)
{
    int i=0;
    Node *p;
    p=CL->next;
    while(p!=CL)
    {
        i++;
        p=p->next;
    }
    return i;
}

int main()
{
    LinkList CL;
    int length;
    InitCLLinkList(&CL);
    CreatCLLinkList(CL);
    length=LengthCLLinkList(CL);
    printf("The length of the circular list is:%d\n",length);
    free(CL) ;
    return 0;
}

 

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/167334.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号