约瑟夫环问题：用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。

电玩女神 2023-07-25 08:40 2阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct josephnum
    {
        int num;//1-N连续数字
        struct josephnum *front;//前指针
        struct josephnum *next;//后针域
    }JCN;
    
    void print_help()
    {
    
        puts("****************************"); 
    	puts("1.创建约瑟夫数字");	
        puts("2.查看约瑟夫数字");
    	puts("3.输出约瑟夫环");
        puts("4.查看帮助信息");
        puts("5.退出系统");
        puts("6.清空");
        puts("****************************");
    
    }
    
    void link_insert(JCN **head, JCN *p_new)
    {
        JCN *pb, *pf = *head;
        if (*head == NULL)//空链表时
        {
        	*head = p_new;
    		p_new->next = *head;
    		p_new->front = *head;
        }	
        else//有一个或以上链表时
        {
    		pb = pf->front;
    		pb->next = p_new;
    		p_new->front = pb;
    		p_new->next = pf;
    		pf->front = p_new;
        }
    }
    
    void link_print(JCN *head)
    {
    	JCN *p_mov = head;
    	
        if (head == NULL)
        {
    		return;
        }
    	while (p_mov->next != head)
    	{
    		printf("%d\n",p_mov->num);
    		p_mov = p_mov->next;
    	}
    	printf("%d\n",p_mov->num);
    }
    
    JCN *link_del(JCN **head,JCN *p_del)
    {
    	
    	if(p_del != *head)//删除的不是头节点
    	{
    		p_del->front->next = p_del->next;
    		p_del->next->front = p_del->front;
    	}
    	else//删的就是头节点
    	{
    		if(p_del->next == *head)//只有一个节点
    			*head = NULL;
    		else//一个以上节点
    		{
    			*head = p_del->next;
    			p_del->front->next = p_del->next;
    			p_del->next->front = p_del->front;
    		}
    	}
    		free(p_del);
    	
    }
    
    JCN *link_search(JCN *head, int m)
    {
    	int i;
    	JCN *p_mov = head;
    	
    	p_mov = head->front;
    	while(head != NULL)
    	{
    		i = m;
    		while(i--)
    		{
    			p_mov = p_mov->next;
    		}
    		printf("%d\n",p_mov->num);
    		link_del(&head,p_mov);
    	}
    	printf("\n");
    }
    
    JCN *link_free(JCN *head)
    {
        JCN *pf = head;
    	if (head != NULL)
    	{
    		return NULL;
    	}
        while(pf->next != head)
        {
    		pf = pf->next;
    		free(pf->front);
        }
    	free(pf);
        return NULL;
    }
    
    int get_int(void)//验证输入的类型是否是整数
    {
    	int input;
    	
    	while (scanf("%d",&input) != 1 )
    	{
    		// while ((ch = getchar()) != '\n')//处理错误的输入
    		// {
    			// putchar(ch);//把缓冲区里的内容输出	
    			// setbuf(stdin, NULL);//把缓冲区里的内容清空
    		// }
    		scanf("%*[^\n]%*c");//把缓冲区里的内容清空
    		printf("输入有误.\n请重新输入一个的整数：");
    	}
    
    	return input;
    
    }
    
    int main(void)
    {
        int option, num = 0 , i = 0, m = 0;
        JCN *head = NULL, *p_new= NULL, *ps = NULL; 
    	while(1)
    	{
    		print_help();
    		puts("请输入需要的选项：");
    		option = get_int();
    		switch(option)
    		{
    		    case 1://
    				puts("请输入N:");
    				num = get_int();
    				puts("请输入M:");
    				m = get_int();
    				for(i=1; i<=num; i++)
    				 {				    
    				    p_new = (JCN*)malloc(sizeof(JCN));//申请新的节点
    				    p_new->num = i;//给新申请的节点赋值	
    				    link_insert(&head,p_new);
    				 }
    				break;
    		    case 2://遍历学生
    				link_print(head);
    				break;
    		    case 3://输出约瑟夫环
    				link_search(head,m);
    				//printf("%d\n",ps->num);	
    				break;	 
    		    case 4://帮助
    				print_help();
    				break;
    		    case 5://退出
    				return 0;
    		    case 6://清空链表
    				head = link_free(head);
    				break;
    		}
    	}
    		
    	return 0;
    }