环形链表c语言（找出一个带环单链表中是什么地方出现环的）

本文目录

• 找出一个带环单链表中是什么地方出现环的
• 怎样用c语言实现一个环形缓存区！
• 用c语言输出一个整数n和一字符串,将字符串循环左移n个字符

找出一个带环单链表中是什么地方出现环的

请看以下的第1点和第2点:1.判断链表是否有环设置两个指针slow和fast,初始值均指向链表头,slow每次向前走一步,而fast每次向前走两步.如果链表有环,则fast先进入环里,而slow后进入环里,两个指针在环中必定相遇.如果slow与fast没有相遇,fast遍历到链表的尾部,则表示链表没有环.2.链表有环,确定环的入口点设置slow指针指向链表头,fast指向相遇点,每次两个指针都是只走一步,两个指针必定相遇,则相遇第一点为环入口点.( 为什么 两个指针相遇的地方就是环入口点?  先从"判断链表是否有环"的那种情况说起.  假设从链表头到环入口点的距离是x, 在环里两个指针相遇的那点与环入口点的距离是w,  fast指针在环里走了n圈才与slow相遇,环的长度是L,那么,  slow指针在相遇时走过的距离是 x + w  fast指针走过的距离是 x + w + n*L  因为slow每次向前走一步,而fast每次向前走两步,有如下等式:  2 * (x + w) = x + w + n*L  化简得到: x + w = n*L  也就是 x = n*L - w    假设相遇的时候,fast在环内只走了一圈,n=1,代入,得到 x = L - w  现在,slow从链表头开始走,fast继续从相遇点开始走,两个指针都只走一步,  那么,slow走了x,而fast走了(L - w),必定相遇,而且刚好在环入口点.  假设相遇的时候,fast在环内走了超过一圈,那么可以写为:  x = (n-1)*L + (L- w)  那么,slow走了x,而fast走了(n-1)圈后,再走(L - w),必定相遇,而且刚好在环入口点. )3.计算环长在环的入口点设置一个指针和一个计数器,让这个指针在环里面走,每走一步,计数器就加1,当这个指针回到环的入口点的时候,计数器的值就是环长.测试结果:链表1:10 20 30 40 50 20 30 40 50 20 30 40 50 20 30 40 50 20 30 40 ......有环, 环入口点是: 20环长是: 4链表2:1 2 3 4 5链表没有环//C语言测试程序#include 《stdio.h》#include 《stdlib.h》typedef struct Node{    int data;    struct Node *next;}Node,*LinkList;//创建链表(有"环")LinkList CreateLinkWithLoop(){    LinkList head; //链表头    Node *newNode; //新结点    Node *ptr;     //指向当前结点    Node *pEntry;  //指向"环"的入口    newNode=(Node *)malloc(sizeof(Node));    newNode-》data=10;    newNode-》next=NULL;    head=newNode;       //设置链表头    ptr=newNode;    newNode=(Node *)malloc(sizeof(Node));    newNode-》data=20;    newNode-》next=NULL;    ptr-》next=newNode;    ptr=newNode;    pEntry=newNode;  //指向"环"的入口    newNode=(Node *)malloc(sizeof(Node));    newNode-》data=30;    newNode-》next=NULL;    ptr-》next=newNode;    ptr=newNode;    newNode=(Node *)malloc(sizeof(Node));    newNode-》data=40;    newNode-》next=NULL;    ptr-》next=newNode;    ptr=newNode;    newNode=(Node *)malloc(sizeof(Node));    newNode-》data=50;    newNode-》next=pEntry; //产生"环"    ptr-》next=newNode;    ptr=newNode;    return head;}//创建链表(没有"环")LinkList CreateLink(){    LinkList head; //链表头    Node *newNode; //新结点    Node *ptr;     //指向当前结点    int i;    newNode=(Node *)malloc(sizeof(Node));    newNode-》data=1;    newNode-》next=NULL;    head=newNode;       //设置链表头    ptr=newNode;    for(i=2;i《=5;i++)    {        newNode=(Node *)malloc(sizeof(Node));        newNode-》data=i;        newNode-》next=NULL;        ptr-》next=newNode;        ptr=newNode;    }    return head;}//打印链表void PrintLink(LinkList head){    LinkList ptr;    int nCount=0;    ptr=head;    while(ptr!=NULL)    {        printf("%d ",ptr-》data);        ptr=ptr-》next;        nCount++;        if(nCount》=20)        {            printf("......");            break;        }    }    printf("\n");}//判断链表是否有"环",确定"环"的入口点LinkList CheckLinkLoop(LinkList head){    LinkList fast;    LinkList slow;    int isLoop=0;    fast=head;    slow=head;    while(fast != NULL && fast-》next != NULL)    {        //fast每次走两步,slow每次走一步        //当两个指针相等时,表示链表有"环"        slow=slow-》next;        fast=fast-》next-》next;        if(fast == slow)        {            isLoop=1; //1=有环, 0=没有环            break;        }    }    if(isLoop==1) //有"环"时    {        //slow指向链表头,fast指向相遇点,两个指针每次都只走一步        //当两个指针第一次相等时,就是环入口点        slow=head;        while(slow != fast)        {            slow=slow-》next;            fast=fast-》next;        }        return slow;    }    else //没有"环"    {        return NULL;    }}//计算环长int GetLoopSize(LinkList entryNode){    LinkList ptr;    int nCount=0;    ptr=entryNode-》next;    nCount++;    while(ptr!=entryNode)    {        nCount++;        ptr=ptr-》next;    }    return nCount;}int main(){    LinkList head_1;    LinkList head_2;    LinkList ret_1;    LinkList ret_2;    int loopSize_1;    int loopSize_2;    head_1=CreateLinkWithLoop(); //创建链表(有"环")    printf("链表1:\n");    PrintLink(head_1); //打印链表    ret_1=CheckLinkLoop(head_1);    if(ret_1!=NULL)    {        printf("有环, 环入口点是: %d\n",ret_1-》data);        loopSize_1=GetLoopSize(ret_1);        printf("环长是: %d\n",loopSize_1);    }    else    {        printf("链表没有环\n");    }    head_2=CreateLink(); //创建链表(没有"环")    printf("\n链表2:\n");    PrintLink(head_2); //打印链表    ret_2=CheckLinkLoop(head_2);    if(ret_2 != NULL)    {        printf("有环, 环入口点是: %d\n",ret_2-》data);        loopSize_2=GetLoopSize(ret_2);        printf("环长是: %d\n",loopSize_2);    }    else    {        printf("链表没有环\n");    }    return 0;}

怎样用c语言实现一个环形缓存区！

定义个数组如a;用两个head tail 指针存入数据后tail++ 读取数据后head++ 为了循环利用此块空间 做以下处理：存跟读数据时指针处理 tail%10 head%10判断缓存空？tail == head+1判断缓存满？tail == head+9

用c语言输出一个整数n和一字符串,将字符串循环左移n个字符

使用带头结点的环形链表存储字符串，从链表头开始做N次L-》next=L-》next-》next；L=L-》next；此时记录N=L；并输出链表内容（注意跳过头结点，头结点无字符信息），直至L==N；