链表实现约瑟夫环

左手的ㄟ右手 2022-04-22 12:06 194阅读 0赞

#include<stdio.h>
    #include<malloc.h>
    
    #define false 0;
    #define ok 1;
    
    typedef struct node
    {
    	int data;
    	int num;
    	struct node * next;
    } node, *linklist;
    
    //初始化链表
    void initlist(linklist * l)
    {
    	* l = (linklist)malloc(sizeof(node));
    	(*l)->next = *l;
    }
    
    //用尾插法建立新链表
    void greatefromtail(linklist l, int n)
    {
    	node * s, * r;
    	int flag = 1;
    	int data, num;
    	int j = 0;
    	r = l;
    	while(flag)
    	{
    		if(j < n)
    		{
    			printf("请输入第%d位密码\n", j+1);
    			scanf("%d", &data);
    			s = (node *)malloc(sizeof(node));
    			s->data = data;
    			s->num = j+1;
    			r->next = s;
    			r = s;
    			j++;
    		}
    		else
    		{
    			flag = 0;
    			r->next = l->next;
    		} 
    	}
    }
    
    //删除链表l中第i个元素
    linklist dellist(linklist l, int * a)
    {
    	node * pre, * r, *s;
    	int j = 1;
    	pre = l;
    	if(*a == 1)
    	{
    		s = pre;
    		while(s->next != pre)
    		{
    			s = s->next;
    		}
    		*a = pre->data;
    		s->next = pre->next;
    		return pre;
    	}
    	else
    	{
    		while(j < *a-1)
    		{
    			pre = pre->next;
    			j++;
    		}
    		r = pre->next;
    		*a = r->data; 
    		pre->next = r->next;
    		return r;
    	}
    }
    
    int main(void)
    {
    	int n,m; //总人数n,初始报人数及后续密码存放m
    	int i = 0,j = 0;
    	linklist l, q;  //原链表头指针
    	node * r; //删除的的节点存放r,建立输出链表中间变量s
    	
    	printf("请输入总人数n\n");
    	scanf("%d", &n);
    	printf("请输入初始报数人数m\n");
    	scanf("%d", &m);
    
    	initlist(&l); //初始化原链表
    	greatefromtail(l, n); //尾插法建立链表
    	q = l->next;
    
    	for(i = 0; i < n; i++)
    	{
    		r = dellist(q, &m);
    		printf("%2d", r->num);
    		q = r ->next;
    	}
    	return 0;
    }