重写约瑟夫回环（循环单链表）

墨蓝 2024-04-17 21:13 70阅读 0赞

> **问题描述**
> 
> 设有n个人围坐在圆桌周围，现从某个位置m（1≤m≤n）上的人开始报数，报数到k的人就站出来。下一个人，即原来的第k+1个位置上的人，又从1开始报数，再报数到k的人站出来。依此重复下去，直到全部的人都站出来为止。试设计一个程序求出出列序列。

> **思路**
> 
>  *  子问题1：查找第一个报数为 k 的？
>  *  子问题2：何时退出？

#ifndef JOSEPH_CLINKLIST_H
    #define JOSEPH_CLINKLIST_H
    
    // 循环链表
    // 最后一个结点的指针指向头结点
    // 
    // 有时候可以设置尾指针，更方便表的连接操作
    typedef struct Node
    {
    	int elem;
    	struct Node * next;
    }clinklist, *pclinklist;
    
    pclinklist clinklist_create(int size);
    void clinklist_insert(pclinklist list, int locate, int elem);
    void clinklist_delete_location(pclinklist list, int locate);
    void clinklist_delete(pclinklist list, pclinklist node);
    void clinklist_display(pclinklist list);
    pclinklist clinklist_find(pclinklist list, int location);
    int clinklist_is_tail(pclinklist list, pclinklist node);
    int clinklist_is_head(pclinklist head, pclinklist node);
    int clinklist_is_empty(pclinklist list);
    int clinklist_size(pclinklist list);
    void clinklist_update_head(pclinklist list);
    
    #endif

#include <stdio.h>
    #include <stdlib.h>
    #include "joseph.h"
    
    int main() {
    	int size = 0;
    	int m = 0;
    	int k = 0;
    
    	pclinklist list = NULL;
    
    	printf("输入人数 n ：");
    	scanf_s("%d", &size);
    
    	if (size == 0)
    		return -1;
    
    	printf("输入报数起点 m ：");
    	scanf_s("%d", &m);
    
    	if (m <= 0 || m > size)
    		return -2;
    
    	printf("输入报数到几退出 k ：");
    	scanf_s("%d", &k);
    
    	// 极端情况考虑，k > n , k = n, k = 1
    	if (k == 0)
    		return -3;
    
    	list = clinklist_create(size);
    	clinklist_display(list);
    
    	// 找到 m 点
    	pclinklist node = clinklist_find(list, m - 1);
    	printf("开始从 %d 报数\n", node->elem);
    
    	int index = 1;
    	while (!clinklist_is_empty(list))
    	{
    		if (index == k)
    		{
    			printf("第 %d 号选手遗憾出局\n", node->elem);
    			pclinklist new_node = node->next;
    			
    			clinklist_delete(list, node);
    			
    			node = new_node;
    			if (clinklist_is_head(list, node))
    				node = node->next;
    			index = 1;
    		}
    		else
    		{
    			node = node->next;
    			if (clinklist_is_head(list, node))
    				node = node->next;
    			index++;
    		}
    	}
    	return 0;
    }
    
    pclinklist clinklist_create(int size)
    {
    	pclinklist node, head;
    	head = (pclinklist)malloc(sizeof(clinklist));
    
    	// 头结点 elem 表示链表大小，头结点 next 指向第一个元素
    	head->elem = size;
    	head->next = NULL;
    
    	node = head;
    
    	for (int i = 0; i < size; i++)
    	{
    		node->next = (pclinklist)malloc(sizeof(clinklist));
    		node = node->next;
    		node->elem = i + 1;
    		node->next = NULL;
    	}
    	node->next = head;
    
    	return head;
    }
    
    void clinklist_display(pclinklist plist)
    {
    	pclinklist head = plist;
    	pclinklist node = head->next;
    	while (1)
    	{
    		if (clinklist_is_head(head, node))
    			break;
    
    		printf("%d\t", node->elem);
    		node = node->next;
    	}
    	printf("\n");
    }
    
    void clinklist_insert(pclinklist plist, int location, int elem)
    {
    	pclinklist head = plist;
    	pclinklist inode = NULL;
    	int size = clinklist_size(plist);
    
    	if (location < 0 || location > size)
    		return;
    
    	inode = (pclinklist)malloc(sizeof(clinklist));
    	inode->elem = elem;
    
    	if (location == 0)
    	{
    		inode->next = head->next;
    		head->next = inode;
    	}
    	else
    	{
    		pclinklist node = clinklist_find(plist, location - 1);
    		pclinklist next = node->next;
    		node->next = inode;
    		inode->next = next;
    	}
    	clinklist_update_head(head);
    }
    
    void clinklist_delete_location(pclinklist plist, int location)
    {
    	pclinklist head = plist;
    	int size = clinklist_size(plist);
    
    	if (location < 0 || location >= size)
    		return;
    
    	if (location == 0)
    	{
    		pclinklist dnode = head->next;
    		head->next = dnode->next;
    		free(dnode);
    	}
    	else
    	{
    		pclinklist node = clinklist_find(plist, location - 1);
    		pclinklist dnode = node->next;
    		node->next = dnode->next;
    		free(dnode);
    	}
    	clinklist_update_head(head);
    }
    
    void clinklist_delete(pclinklist plist, pclinklist node)
    {
    	pclinklist prior = plist;
    
    	do
    	{
    		if (node == prior->next)
    		{
    			prior->next = node->next;
    			free(node);
    			break;
    		}
    		prior = prior->next;
    	} while (!clinklist_is_head(plist, prior));
    
    	clinklist_update_head(plist);
    }
    
    pclinklist clinklist_find(pclinklist list, int location)
    {
    	pclinklist head = list;
    	pclinklist node = head->next;
    
    	if (location == 0)
    		return node;
    	else
    	{
    		while (location != 0)
    		{
    			if (clinklist_is_head(head, node)) break;
    
    			node = node->next;
    			location--;
    		}
    
    		if (location != 0)
    			return NULL;
    
    		return node;
    	}
    }
    
    int clinklist_is_tail(pclinklist head, pclinklist node)
    {
    	return (clinklist_is_empty(head) || node->next == head) ? 1 : 0;
    }
    
    int clinklist_is_head(pclinklist head, pclinklist node)
    {
    	return (head == node) ? 1 : 0;
    }
    
    int clinklist_is_empty(pclinklist list)
    {
    	return list == list->next;
    }
    
    int clinklist_size(pclinklist list)
    {
    	return list->elem;
    }
    
    void clinklist_update_head(pclinklist list)
    {
    	pclinklist head = list;
    	pclinklist node = head->next;
    	int size = 0;
    	while (node != head)
    	{
    		size++;
    		node = node->next;
    	}
    	head->elem = size;
    }