约瑟夫问题——循环单链表

资讯 2023-12-06 17:27:48

代码:

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int DataType;
#define ListSize 100
//线性表的链表存储类型 
typedef struct Node{
	DataType data;
	struct Node *next;
}ListNode,*LinkList;
LinkList CreateCycList(int n){
	LinkList head=NULL;
	ListNode *s,*r;
	int i;
	for(i=1;i<=n;i++){
		s=(ListNode*)malloc(sizeof(ListNode));
		s->data=i;
		s->next=NULL;
		if(head==NULL){
			head=s;
		} else{
			r->next=s;
	}
			r=s;
	}
	r->next=head;
	return head;
}
//在由n个人围成的圆圈中,从第k个人开始报数,报数为m的人出列 
void Josephus(LinkList h,int n,int m,int k){
	ListNode *p,*q;
	int i;
	p=h;
	for(i=1;i<k;i++){
		q=p;
		p=p->next;
	} 
	while(p->next!=p){
		for(i=1;i<m;i++){
			q=p;
			p=p->next;
		} 
		q->next=p->next;
		printf("%4d",p->data);
		free(p);
		p=q->next;
	}
	printf("%4d\n",p->data);
}
int main(){
	LinkList head;
	int n,k,m;
	printf("输入圈中人的个数n:");
	scanf("%d",&n);
	printf("输入开始报数的序号k:");
	scanf("%d",&k);
	printf("报数为m的人出列m:");
	scanf("%d",&m);
	head=CreateCycList(n);
	Josephus(head,n,m,k);
	return 1;
}

截图:
约瑟夫问题——循环单链表

声明:该文观点仅代表作者本人,必看呐发布平台,仅提供信息存储空间服务。