C语言实现循环链表解决n个小孩问题

问题描述

功能描述(Description)：有n个小孩子，按顺时针方向围成一个圆。老师指定从第m(m<n)个小孩开始报数，按顺序1，2，3…… 数到k个小孩时，该小孩子退到圈外，然后从报数为k的下一个小孩子开始报数。如此重复下去，直到所有小孩都出列，求小孩的出列顺序。

解题思路

构造一个循环链表,表示围成圈的孩子。 /* 链表的节点 */ typedef struct _TAG_LinkedNode { Data data;//数据 _TAG_LinkedNode* next;//指向下一个节点 }Node, *PNode; .每次找到一个孩子,就让其从当前链表退出，并加入新链表

直接上代码吧

/* 第二阶段（指针链表章节）考核题: 有n个小孩子，按顺时针方向围成一个圆。老师指定从第m(m<n)个小孩开始报数，按顺序1，2，3…… 数到k个小孩时， 该小孩子退到圈外， 然后从报数为k的下一个小孩子开始报数。如此重复下去，直到所有小孩都出列，求小孩的出列顺序。 要求： 1.m、n、k用键盘输入 2.禁止使用数组 3.打印输出小孩顺序要求后面使用一个函数集中打印，不能一边处理报数同时打印，打印输出小孩的编号(编号从1开始) */ #include "stdafx.h" #include "assert.h" #include<stdlib.h> #include<iostream> #define NOT_NUMBER -1 #define INIT_ERROR -3 #define BAD_INPUT -4 #define MALLOC_FAILED -5 #define REMOVE_FAILED -6 using namespace std; typedef int Data; /* 链表的节点 */ typedef struct _TAG_LinkedNode { Data data;//数据 _TAG_LinkedNode* next;//指向下一个节点 }Node, *PNode; PNode init(int listLength); PNode Add(PNode pTargetNode, PNode pNewNode); PNode Remove(PNode *pInputStart, int step); void Destory(PNode target); void Foreach(PNode head); int CheckAndConvert(const char *str, int *num); void Input(); /* 接受键盘输入,并初始化 m,n,k的值 */ void Input(int *m, int *n, int *k) { char buff[128] = { 0 };//接收字符缓冲区 printf("请输入从第几个小孩开始m:"); scanf("%[^\n]", buff); while (CheckAndConvert(buff, m) != 0) { printf("请输入从第几个小孩开始m:"); getchar(); //排除回车符 scanf("%[^\n]", buff); } printf("请输入小孩的个数n:"); getchar(); scanf("%[^\n]", buff); while (CheckAndConvert(buff, n) != 0) { printf("请输入小孩的个数n:"); getchar(); //排除回车符 scanf("%[^\n]", buff); } printf("请输入每次循环找第几个k:"); getchar(); scanf("%[^\n]", buff); while (CheckAndConvert(buff, k) != 0) { printf("请输入每次循环找第几个k:"); getchar(); //排除回车符 scanf("%[^\n]", buff); } } /* 1.初始化链表 2.返回表头 listLength:构造的链表的长度 return:链表的头结点 */ PNode init(unsigned int listLength) { int ret = 0; PNode pHead = NULL; //构造循环链表 for (int i = 0; i < listLength; i++) { //开辟新节点内存 PNode pNewNode = (PNode)malloc(sizeof(Node)); if (pNewNode == NULL) { cout << "内存分配失败" << endl; ret = MALLOC_FAILED; break; } pNewNode->data = i + 1; //将新节点加入head的尾部 head指向最后一个节点 pHead = Add(pHead, pNewNode); } if (ret == MALLOC_FAILED) { //释放资源 Destory(pHead); pHead = NULL; } return pHead; } /* pTargetNode:头节点 pNewNode:要添加的节点 return:新加入的节点 */ PNode Add(PNode pTargetNode, PNode pNewNode) { PNode tHead = pTargetNode; if (pNewNode == NULL) { cout << "添加的节点不能为NULL" << endl; return NULL; } if (tHead != NULL) { pNewNode->next = tHead->next; tHead->next = pNewNode; } else { tHead = pNewNode; //自己指向自己 tHead->next = tHead; } return pNewNode; } /* 1.移动step步长 2.找到pre 3.删除pInputStart,并返回 pInputStart:开始的节点 step:移动的步长 return:删除之后的节点 */ PNode Remove(PNode *pInOutStart, unsigned int step) { PNode pDelPre = NULL; //删除节点的前一个节点 PNode pDel = *pInOutStart; //待删除的节点 if (pDel == NULL) { return NULL; } //1.移动步长,找到pre for (int i = 0; i < step; i++) { pDelPre = pDel; pDel = pDel->next; } //2 step=0 找到pre if (pDelPre == NULL) { pDelPre = pDel; while (pDelPre->next != pDel) { pDelPre = pDelPre->next; } } //仅剩下一个节点时 if (pDelPre == pDel) { *pInOutStart = NULL; } else { pDelPre->next = pDel->next; //更新*pInOutStart到下一个节点 *pInOutStart = pDel->next; } return pDel; } //销毁 释放资源 void Destory(PNode target) { if (target == NULL) { cout << "释放的资源为NULL" << endl; return; } //记录下头节点 PNode tHead = target; PNode move = tHead; //依次释放资源 do { move = tHead->next; free(tHead); tHead = move; } while (tHead != target); } /* 遍历链表 head:头结点 */ void Foreach(PNode head) { if (head == NULL) { cout << "遍历时头结点不能为NULL" << endl; return; } //将head指向第一个元素 head = head->next; //遍历 PNode tHead = head; do { cout << tHead->data << "----"; tHead = tHead->next; } while (tHead != head);//当循环到最初的头节点时退出 cout << endl; } /* 判断输入的是否为数字 并且反转输入为int */ int CheckAndConvert(const char *str, int *num) { int i = 0; int total = 0; if (str == NULL || num == NULL) { cout << "不能传入NULL" << endl; return NOT_NUMBER; } if (str == '\0') { cout << "输入不能为空" << endl; return NOT_NUMBER; } //去除前缀 while (str[i] != '\0' && (str[i] == '\t' || str[i] == ' ')) { i++; } //取数字 while (str[i] != '\0' && str[i] != '\t' && str[i] != ' ') { if (str[i] < '0' || str[i] > '9') { cout << "请输入纯数字.." << endl; return NOT_NUMBER; } else { total *= 10; total = total + (str[i] - '0'); } i++; } //判断后缀 while (str[i] != '\0') { if (str[i] != '\t' && str[i] != ' ') { cout << "请输入纯数字.." << endl; return NOT_NUMBER; } i++; } if (total == 0) { cout << "值不能为0" << endl; return BAD_INPUT; } *num = total; return 0; } int main() { int m = 0; int n = 0; int k = 0; int ret = 0; PNode pOldHead = NULL; //旧节点头 PNode pNewHead = NULL;//新节点头 PNode pTemp = NULL;//临时性指向新开辟内存 //键盘输入 Input(&m, &n, &k); //检查是否满足题目要求 if (m > n) { cout << "m不能大于n" << endl; system("pause"); return BAD_INPUT; } //初始化链表 pOldHead = init((unsigned int)n); if (pOldHead == NULL) { return INIT_ERROR; } //循环m次 head此时为最后一个节点 从第m个孩子开始 pOldHead = pOldHead->next; //指向第一个 for (int i = 0; i < m - 1; i++) { pOldHead = pOldHead->next; } //每次找第k个元素 while (pOldHead != NULL) { unsigned int kStep = k; kStep = (kStep - 1) % n; //从旧链表移除元素 pTemp = Remove(&pOldHead, kStep); if (pTemp == NULL) { cout << "移除链表失败" << endl; ret = REMOVE_FAILED; break; } else { n--; } //将移除的元素加入新链表 pNewHead = Add(pNewHead, pTemp); } if (ret == REMOVE_FAILED) { //释放资源 Destory(pOldHead); Destory(pNewHead); return REMOVE_FAILED; } //遍历新表 cout << "依次退出的是:" << endl; Foreach(pNewHead); //释放资源 Destory(pNewHead); system("pause"); return 0; }