【C语言】malloc动态链表。N个人围成一圈，从第1个人开始顺序报号1、2、3。凡报到“3”都退出圈子，找出最后留在圈子中的人原来的序号。要求用链表实现。出圈顺序

小半 • 2023年1月24日下午2:13 • 数据结构 • 阅读 254

解题思路：定义一个结构体，它包含序号num和指向自己的结构体指针。编写一个返回值为结构体指针的的函数来返回链表的头指针，该函数中利用malloc函数来建立一个动态链表，建立链表的过程中同时也给节点num赋值，从1~13。编写另一个函数，该函数通过调用上一个建立链表的函数得到链表的头指针，然后对该链表进行操作，输出每次出局的人的序号，并输出最终留下来的人的序号。详细部分见代码注释。

编写程序：

#include<stdio.h>
#include<stdlib.h>
#define N 13				//圈子中的人数 
#define M 3 				//循环报数数 

struct Quan {				//定义结构体
	int num;				//数据域（圈子中的人的序号）
	struct Quan *next;		//指针域（构建链表）
};

struct Quan *creat(void);			//函数申明
void find(struct Quan *head);		//函数声明
int main() {
	find(creat());						//调用creat函数构建动态链表，并返回链表头指针	return 0;							//做find函数参数
}

/*——构建动态链表函数——*/
struct Quan *creat(void) {				//返回值是一个结构体指针
	int i;
	struct Quan *head=NULL,*p1,*p2;		//定义三个结构体指针
	p1=p2=(struct Quan *)malloc(sizeof(struct Quan));	//用malloc函数申请一个大小为结构体长度的内存空间，并强制住转换为结构体类型的指针
	head=p1;				//当前的p1为头指针
	for(i=0; i<N; i++) {
		p1->num=i+1;		//给上一个结构体中的num赋值
		p1=(struct Quan *)malloc(sizeof(struct Quan));	//申请一个新的动态内存，同样转换为结构体指针给p1
		p1->num=0;			//先给num赋0
		p2->next=p1;		//让上一个结构体中的指针p2指向next并将刚才的p1赋给p2
		p2=p1;				//让p2指到当前结构体变量中
	}
	p2->next=NULL;			//链表尾部指针指空
	return (head);			//返回链表头指针
}

/*——计算、输出结果函数——*/
void find(struct Quan *head) {
	int i,count=0,sum=0;			//定义循环变量、两个计数器、
	struct Quan *p;				//定义一个 结构体指针
	printf("出局顺序：");
	while(1) {
		if(sum==N-1)break;			//若剩下一个人了就终止循环
		for(i=1,p=head; i<N+1; i++,p=p->next) {		//指针每次指向链表头部
			if(p->num!=0)			//若当前序号不为0（这个人没有出局）
				count++;			//报数一次
			if(count==M) {				//如果报到了3
				printf("%d,",p->num);	//输出这个人的序号
				p->num=0;				//这个人出局了，让他的序号为0
				sum++;					//记录出局人数
				count=0;				//报数重置为0
			}
		}
	}
	for(i=1,p=head; i<N+1; i++,p=p->next) {				//从表头找这最终没有出局的人
		if(p->num)										//这个人序号不为0
			printf("\n最后留下的是%d号\n",p->num);	//输出它的序号
	}
}

程序运行测试：