目录

问题描述

题目：

前置代码： 

题目分析

头部代码：

main函数： 

子函数： 

1、输出函数void outputring( NODE * ); 

2、把整数变小数的void change( int , int , NODE * );  

解题方法

总结

---

这篇文章是我开始系统学习算法时为记录学习过程写的，比较适合小白，大佬请跳过。不当之处请大家批评指正。

问题描述

题目：

 

前置代码： 

#include <stdio.h>  
#include <stdlib.h>  
typedef struct node  
{   int         data;  
    struct node * next;  
} NODE;  
  
NODE * find( NODE * , int * );  
void outputring( NODE * );  
void change( int , int , NODE * );  
void outputring( NODE * pring )  
{   NODE * p;  
    p = pring;  
    if ( p == NULL )  
        printf("NULL");  
    else  
        do  {   printf("%d", p->data);  
            p = p->next;  
        } while ( p != pring );  
    printf("\n");  
    return;  
}  
  
int main()  
{   int n, m;  
    NODE * head, * pring;  
  
    scanf("%d%d", &n, &m);  
    head = (NODE *)malloc( sizeof(NODE) );  
    head->next = NULL;  
    head->data = -1;  
  
    change( n, m, head );  
    pring = find( head, &n );  
    printf("ring=%d\n", n);  
    outputring( pring );  
  
    return 0;  
}  

题目分析

头部代码：

#include <stdio.h>  
#include <stdlib.h>  
typedef struct node  //定义结构体
{   int  data;     //整型元素
    struct node * next;  //指向下一个结点的指针
} NODE;  

main函数： 

int main()  
{   int n, m;  
    NODE * head, * pring;  
  
    scanf("%d%d", &n, &m);  
    head = (NODE *)malloc( sizeof(NODE) );  //为头结点开辟存储空间
    head->next = NULL;   // 头结点后连NULL
    head->data = -1;     //头结点元素设为-1，表示不包含在真正的元素内
  
    change( n, m, head );  //整数变小数（跟上一题一样）
    pring = find( head, &n );   //找到循环节开始处
    printf("ring=%d\n", n);  //打印循环节长度
    outputring( pring );   //输出循环节
  
    return 0;  
}  

子函数： 

1、输出函数void outputring( NODE * ); 

void outputring( NODE * pring )  //输出函数
{   NODE * p;  
    p = pring;  
    if ( p == NULL )  //如果循环节头指针为NULL，直接输出
        printf("NULL");  
    else  
        do  {   printf("%d", p->data);  //如果循环节存在，则输出循环节部分
            p = p->next;   //p指针后移
        } while ( p != pring );   //直到顺着环又移到循环节头指针pring为止
    printf("\n");  
    return;  
}  

2、把整数变小数的void change( int , int , NODE * );  

见上一篇博客：https://blog.csdn.net/caswind/article/details/133436826?spm=1001.2014.3001.5502

解题方法

我们需要编写找到循环头的函数void outputring( NODE * pring )  

我们由上一篇博客中的change函数可以知道，我们已经获得了循环节的头部指针位置bef和下一次循环的头部指针位置aft。

如果bef>aft，说明不存在循环节。我们只需要将循环节长度定为0，将循环节头指针定为NULL，输出即可。

如果bef<aft，说明存在循环节。此时需要让指针定为到循环节头位置，即bef处。循环节长度即为aft-bef。

代码如下：

NODE * find( NODE * head, int * n ) 
{ 
	int i;
	NODE *t=(NODE*)malloc(sizeof(NODE)); 
	t=head->next;  //让头指针从第一个元素开始往后走
	if(bef>aft)   //循环节不存在的时候
	{
		*n=0;
		return NULL;
	}
	else if(bef<aft)  //循环节存在的时候
	{
		for(i=0;i<bef;i++)  //找到循环节头的位置
		{
			t=t->next;
		}
		*n=aft-bef;  //循环节长度
		return t;  //返回循环节头指针
	}
} 

总结

这道题继承了上一道题的思路。在整数变小数，把小数链表都设置好了之后，分类讨论。

没有循环节的时候，直接让循环节长度为0，循环节头指针为NULL。

有循环节的时候，借助上一题中定义的change函数中的bef和aft变量，找到循环节头位置，并计算循环节长度即可。