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

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}

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

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

循环链表

建立循环单链表

循环单链表的插入

循环单链表的删除

合并循环单链表

循环链表求长度

关于作者

全栈程序员-站长

发表回复

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

循环链表

建立循环单链表

循环单链表的插入

循环单链表的删除

合并循环单链表

循环链表求长度

关于作者

全栈程序员-站长

相关推荐

ASP.NET知识点总结[通俗易懂]

java培训机构前十_深度java培训学校

IIS服务器实现跨域调用「建议收藏」

Android学习路线(适合学生)

利用JavaScript实现在网页上图片上一张下一张的操作

vba sendkeys用法_setcontent

发表回复

　　建立循环单链表

　　循环单链表的插入

　　循环单链表的删除

　　合并循环单链表

　　循环链表求长度