求循环节

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

题目信息

对于任意的真分数 N/M （ 0 < N < M ），均可以求出对应的小数。如果采用链表存储各位小数，对于循环节采用循环链表表示，则所有分数均可以表示为如下链表形式

输入

N M

输出

整个循环节

要求

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

前置代码

#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; } /* Here is waiting for you. void change( int n, int m, NODE * head ) { } NODE * find( NODE * head, int * n ) { } */ 测试输入期待输出测试用例11 3ring=13测试用例21 8ring=1NULL测试用例329 33ring=187测试用例42 7ring=6285714

解答

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; }