求循环节

求循环节

• 题目信息
• • 输入
  • 输出
  • 要求
  • 前置代码
• 解答

对于任意的真分数 N/M （ 0

输入

N M

输出

整个循环节

要求

编写一个尽可能高效的查找循环节起始点的函数： NODE * find( NODE * head, int * n )。函数的返回值为循环节的起点（即图中的指针p），n为循环节的长度。请同时提交将分数转换为小数的函数 change( int n, int m, NODE * head ) 。

前置代码

#include
#include
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;
}
/* Here is waiting for you. void change( int n, int m, NODE * head ) { } NODE * find( NODE * head, int * n ) { } */


void change(int n, int m, NODE *head)
{ // 2/7 = 0.285714
NODE **array;//开辟一个数组，数组的内容是链表
NODE *p = head;//将head引向p
array = (NODE **) malloc(sizeof(NODE *) * m);//开辟的数组大小为链表头节点的大小*m，此处相当于开辟了7个
for (int k = 0; k < m; k++)
array[k] = NULL;
while (n != 0)
{
if (n * 10 % m == 0)
{ //恰好整除
p->next = (NODE *) malloc(sizeof(NODE));
p->next->data = n * 10 / m;
p->next->next = NULL;
n = 0;
}
else
{ //未整除情况
if (array[n] == NULL)
{ //该余数是第一次出现
array[n] = p->next = (NODE *) malloc(sizeof(NODE));//为后续下一个节点开辟空间，
// 同时也在array数组中记录下了是否出现过这个余数
p->next->data = n * 10 / m;//下一个节点的数据为第一次的除数2
n = n * 10 % m;//n此时被改变为余数
p = p->next;//p挪向下一个节点
}
else
{ //该余数不是第一次出现，则发现循环节
p->next = array[n];
n = 0;
}
}
}
}
NODE *find(NODE *head, int *n)
{
NODE *p, *q;
p = q = head->next;//p和q均指向head
while (p != NULL && q != NULL)
{
p = p->next;
q = q->next;
if (q != NULL)//q一次向后移动两个
q = q->next;
if (p == q)
break;//找到重合点则退出
}
if (q == NULL)
{ //如果q一直指向最后还没有找到重合的点那么就不循环了
*n = 0;
return NULL;
}
int ring = 1;
while (q->next != p)
{ //求环长
q = q->next;//q走的快，让q再走回来
ring++;
}
int count = 0;
q = p = head->next;//再一次从头开始
while (count < ring)
{ //p先向前走循环节步长的长度
count++;
p = p->next;
}
while (p != q)
{ //如果pq不相等说明未找到恰好一起的地方，还在前面非循环节的位置
p = p->next;
q = q->next;
}
*n = ring;
return p;
}