Hrbust报数问题

题目描述

有 N 个人围成一圈，按顺时针给他们编号为 1-N。
紧接着，指定编号为 M 的人开始报数，报数按顺时针进行。
报到 D 的人出列，下一个人重新开始报数。按此规律，每次报到 D 的人都出列。
要求同学编程求出出列的顺序。
输入
输入包括多组测试用例。
对于每组用例，第一行是一个整数 N，表示人数。N<100。
接下来 N 行是每个人的人名。人名为长度不超过 20 连续字符串。
最后是以两个以","分割的整数 M，D。代表从 M 个人开始，每报 D 个数出列。
输出
输出所求的顺序
样例输入
8
Zhao
Qian
Sun
Li
Zhou
Wu
Zheng
Wang
4,4
样例输出
Zheng
Sun
Wang
Zhou
Li
Wu
Qian
Zhao

题目分析

第一种思路：采用队列来解决这个问题，队列利用stl里面queue容器

第二种思路：采用循环链表来解决

第三种思路：用数组来模拟循环链表做这样一件事

另外我必须来说一下，怎样让游标可以在name数组中循环，也就是当指向最后一个数据之后，又会重新回到数组的开头进行循环轮替

（cur + 1） % n 这样一个代码就可以实现，比如当cur游标处在数组中最后一个位置的时候，也就是n-1这样一个位置，也就是说当前游标的下一个游标就是(n - 1 + 1) % n，也就是0，这个时候游标又回到了开头

代码实现

第一种思路代码实现：

demo1.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <queue>

using namespace std;

int main()
{
	int total_num;//总人数
	int start_num;//最起始位置
	int end_num;//每次结束报数位置
	char str[21] = {'\0'};
	//控制下整体的大循环
	while(scanf("%d",&total_num) != EOF) {
		//每次进来定义一个容器
		queue<string> q;
		//循环往里面放值
		while(total_num > 0) {
			scanf("%s",str);
			//输入之后入栈
			q.push(str);		
			total_num--;
		}
		//按照思路，先把第一个开始报数的人找到
		scanf("%d,%d",&start_num,&end_num);
		string top_elem;
		for(int i = 0;i < start_num - 1;i++) {
			//把除了第一个之外的数据都放到队列尾巴上面去
			top_elem = q.front();//栈顶元素
			q.pop();
			q.push(top_elem);
		}
		
		//开始整体执行判断操作
		while(q.size()) {			
			//下面开始进行报数找人
			for(int j = 0;j < end_num;j++) {
				//还是上面的方法
				top_elem = q.front();
				//拿到栈顶往后放
				q.pop();
				q.push(top_elem); 
			}
			//上面循环完了，此时栈顶元素就是我们想要的数
			printf("%s\n",q.front().c_str());
			//并且把这个数据给出栈掉
			q.pop();
		}

	}
	return 0;
}

第二种思路:循环链表代码实现

demo2.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int len = 0;

typedef struct _node{
	char name[21];
	struct _node *next;
}node;


node  *init_node() 
{
	node *p_head = (node *)malloc(sizeof(node));
	if(p_head != NULL) {
		//memset(p_head->name,'\0',sizeof(p_head->name));
		strcpy(p_head->name,"我是头结点");
		p_head->next = p_head;//循环链表指向自己
	}
	return p_head;
}

void insert_node(node *p_head,const char *name) 
{
	if(p_head != NULL && name != NULL) {
		node *p_node = (node*)malloc(sizeof(node));
		if(p_node != NULL) {
			//p_node->name = name;//字符串直接放到数组里面
			strcpy(p_node->name,name);//把name赋值到p_node->name指向的空间
			p_node->next = NULL;
			node *p_move = p_head;
			//把这个结点插入到链表的尾部
			for(int i = 0;i < len;i++) {
				p_move=p_move->next;
			}
			p_move->next = p_node;
			p_node->next = p_head;
			len++;//len是一个全局变量
		}
	}
}

//不要头结点只要数据结点，返回每一个结点地址
//拿到结点地址进行操作
node *insert_node1(node *p_head ,const char *name) 
{
	if(name != NULL) {
		node *p_node = (node *)malloc(sizeof(node));
		if(p_node != NULL) {
			strcpy(p_node->name,name);
			if(len == 0) {
				//说明这是一个头结点
				p_node->next = p_node;
			} else {
				//往下移动到最后一个数据
				if(p_head != NULL) {
					node *p_move = p_head;
					while(p_move->next != p_head){
						//指向最后一个结点
						p_move = p_move->next;
					}
					p_move->next = p_node;
					p_node->next = p_head;
				}
			}
			len++;			
		}
		return p_node;
	}
}

//根据节点地址删除数据
char* delete_node(node *p_head,node *p_node) 
{
	char *res = NULL;
	if(p_head != NULL && p_node != NULL && len > 0) {
		res = p_node->name;//字符串
		node *p_move = p_head;
		//移动到p_node的上一个节点
		while(p_move->next != p_node) {
			p_move = p_move->next;
		}
		p_move->next = p_node->next;
		len--;
	}
	return res;
}

//这里的删除操作我们是不需要头结点的
//为什么不需要头结点
//因为头结点也很有可能被删除
char *delete_node1(node *p_node) 
{
	char *res = NULL;
	//只需要移动到上一个结点然后进行删除操作就可以了
	if(p_node != NULL) {
		res = p_node->name;//这里返回一个字符串
		node *p_move = p_node;
		while(1) {
			if(p_move->next == p_node) {
				//程序跳出
				break;
			}	
			p_move = p_move->next;
		}
		//只要程序跳出之后，说明就已经指向了上一个删除结点上一个节点
		p_move->next = p_node->next;
		len--;
	}
	return res;
}


//打印数据
void print_node(node *p_head) 
{
	if(p_head != NULL && len > 1) {
		node *p_move = p_head->next;
		printf("%p %s %p\n",p_head,p_head->name,p_head->next);
		while(p_move != p_head) {
			printf(" %p %s %p\n",p_move,p_move->name,p_move->next);
			p_move = p_move->next;	
		}
	}
}


int main()
{	
	int total_num;
	scanf("%d",&total_num);
	char str[21] = {'\0'};
	scanf("%s",str);//数组作为参数会退化成为一级指针
	node *p1 = insert_node1(NULL,str);
	while(total_num > 1) {
		scanf("%s",str);
		insert_node1(p1,str);
		total_num--;
	}
	//确定好开始循环的指针位置
	int start,step_over;
	node *p_move = p1;//移动结点开始肯定是头结点
	scanf("%d,%d",&start,&step_over);
	for(int i = 0;i < start - 1;i++) {
		//开始进行移动
		p_move = p_move->next;
	}
	while(len) {
		for(int j = 0;j < step_over - 1;j++) {
			p_move = p_move->next;
		}
		char * res=delete_node1(p_move);//把这个节点删除，len会自动减少	
		//销毁了之后，给p_move重新赋上新值就可以了
		p_move = p_move->next;//p_node结点被删了,指向p_node结点的下一个结点
		printf("%s\n",res);
	}
	return 0;
}

这里循环链表我在多说一句，我想利用自己写的库来做，也就是自己写的一个循环链表容器解决问题

第三种思路代码实现

demo3.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


//定义整体输入的数据大小
#define MAX_N 100
//定义字符串的最大长度
#define MAX_LEN 20

//定义数组来存储要进行出列大的字符串信息
char name[MAX_N][MAX_LEN + 1];
//定义一个标记数组来标记数组里面的每一个人是否已经出列
int out[MAX_N];
int n;//总人数

int main()
{
	//整体循环
	while(scanf("%d",&n) != EOF) {
		//循环输入数据到name数组里面
		for(int i = 0;i < n;i++) {
			scanf("%s",name[i]);
		}
		//初始化out数组这片空间
		//全部初始化为0表示没哟出队列
		memset(out,0,sizeof(out));
		int cur = 0;//游标开始的位置，每次前进两个游标
		int out_len = 0;//代表出对的个数，如果全部出队之后，个数应该是等于n
		int start_index,end_step;
		scanf("%d,%d",&start_index,&end_step);
		while(out_len < n) {
			int step = 0;
			while(step < end_step) {
				//让cur不断往下面前进，这也是它循环真正目的
				cur = (cur + 1) % n;
				//判断一下标记是否是有效前进值
				if(!out[cur]) {
					step++;
				}
			}
			//上面就会移动到我们需要出队的数据里面
			//把这个位置标记改了
			out[cur] = 1;
			out_len++;
			printf("%s\n",name[cur]);
		}
	}
	return 0;
}