约瑟夫环问题-循坏单链表算法

Love The Way You Lie 2023-01-14 07:58 117阅读 0赞

【算法】由于约瑟夫环问题本身具有循环性质，考虑采用循环单链表。求解约瑟天环问题的基本思想是：设置一个计数器count和工作指针p，当计数器累加到m时删除结点p。为了统一对链表中任意结点进行计数和删除操作，循环单链表不带头结点；为了便于删除操作，设两个工作指针pre和p，指针pre指向结点p的前驱结点；为了使计数器从1开始计数，采用尾指针指示的循环单链表，将指针pre初始化为指向终端结点，将指针p初始化为指向开始结点，如图所示。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODQ4MzYx_size_16_color_FFFFFF_t_70]  
这是约瑟夫环的初始状态

设函数Joseph求解约瑟夫环问题，算法用伪代码描述如下  
算法：Joseph（rear，m）  
输入：尾指针指示的循环单链表rear，密码m  
输出：约瑟夫环的出环顺序  
1.初始化：pre=rear；p=rear->next；count=1；  
2.重复下述操作，直到链表中只剩一个结点：  
2.1如果count小于m，则  
2.1.1工作指针pre和p后移；  
2.1.2 count+十；  
2.2否则，执行下述操作：  
2.2.1输出结点p的数据域；  
2.2.2删除结点p；  
2.2.3p指向pre的后继结点；count=1重新开始计数；  
3.输出结点p的数据域，删除结点p；  
【程序】主函数首先输入约瑟夫环的长度n和密码m，然后调用围效Creat建立的由尾指针指示的循环单链表，最后调用函数Joseph输出出环的顺序。程序如下：

#include<stdio.h>
    #include<malloc.h>
    typedef struct Node		//定义单链表的结点Node
    {
        
    	int date;
    	struct Node *next;
    }Node;
    Node* Great(int n);		//函数声明，构造尾指针指示的约瑟夫环
    void Joseph(Node *rear,int m);//函数声明，构造出环的顺序 
    
    int main()
    {
        
    int n,m;
    
    Node *near = NULL;		//定义尾指针near并初始化为空
    printf("请输入约瑟夫环的长度：");
    scanf("%d", &n);
    printf("请输入密码：");
    scanf("%d",&m);
    rear=Great(n);
    Joseph(rear,m);
    return 0;
    }
    
    Node* Creat(int n)
    {
        
    	Node* rear = NULL, * s;
    	int i;
    	rear = (Node*)malloc(sizeof(Node));
    	rear->data = 1;
    	rear->next = rear;
    	for (i = 2; i <= n; i++)
    	{
        
    		s = (Node*)malloc(sizeof(Node));
    		s->data = i;
    		s->next = rear->next;
    		rear->next = s;
    		rear = s;
    	}
    	return rear;
    }
    void Joseph（Node *rear,int m）
    {
            //函数定义，形参rear为循环单链表的尾指针，形参m为密码 
    	Node * pre = rear, *p = rear->next;
    	int count = 1;
    	printf("出环的顺序是：");
    	while (p->next！ - p)
    	{
        
    		if (count < m) {
             // 计数器未累加到密码值
    			pre = p; p = p->next;   // 将工作指针pxe和p分别后移
    			count++;
    		}
    		else {
        
    			printf("%-3d"，p->data);     //宽度3位左对齐输出出环的编号
    			pre->next = p->next；	//将结点p摘链
    			free(p);
    			p = pre->next; //工作指针p后移，但pxe不动
    			count = 1;// 计数器从1开始重新计数
    		}
    	}
    	printf("%-3d\n", p->data);
    	free(p);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODQ4MzYx_size_16_color_FFFFFF_t_70]: /images/20221022/9582c9867c3d412ea44d1e7ba5dbc237.png