活用内核链表解决约瑟夫斯问题

男娘i 2022-06-09 14:52 188阅读 0赞

约瑟夫斯问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为“约瑟夫环”，也有的地方叫做“丢手绢”。

问题是这样的：  
有编号从`1`到`n`的`n`个人围坐成一圈。从编号为`1`的人开始报数，报到`m`的人出局，下一位再从 `1` 开始报数，报到 `m` 的人出局，……如此持续，直到剩下一人为止，假设此人的原始编号是`x`。给定 `n`和 `m`，求出`x`。

关于这个问题，我已经写了一篇博客。  
[http://blog.csdn.net/longintchar/article/details/75150621][http_blog.csdn.net_longintchar_article_details_75150621]

因为最近在看内核链表，想把内核链表用起来，我又想到了约瑟夫环。  
假设`n=8, m=3`，那么淘汰顺序应该是3 、6、 1、 5 、2 、8 、4，最后剩下7号。

代码如下。

#include <stdio.h>
    #include "list.h"
    
    #define N 8 //N为总人数
    #define M 3 //从1开始报数，报M的人出局
    
    
    struct person_info {
        int data;              //记录编号
        struct list_head list; //内核链表
    };
    
    struct person_info person[N] = {
       0}; //N个人
    
    int main(void)
    {
        LIST_HEAD(head); //定义并且初始化头结点
    
        int i;  
        //双向循环链表的尾插
        for (i = 0; i < N; ++i) {
            person[i].data = i+1;  //编号从1开始，所以+1
            list_add_tail(&person[i].list, &head);
        } 
    
        struct person_info *p_person = NULL;
        struct list_head *cur = NULL;
        struct list_head *tmp = NULL;
        int count = 0;  //用来计数
    
        //安全遍历节点，报数到M时删除结点，直到只剩一个结点
        //循环停止条件是剩下一个人
        while( (&head)->next->next != (&head) ){
            list_for_each_safe(cur, tmp, &head){    
                ++count;//模拟计数
                if (M == count) 
                {   //小指针转大指针
                    p_person = container_of(cur, struct person_info, list);
                    printf("del:%d\n", p_person->data);
                    list_del(cur); //删除结点
                    count = 0;     //重新计数
                }
            }       
        }
    
        //打印最后一个人的编号
        p_person = container_of((&head)->next, struct person_info, list);
        printf("winner:%d\n", p_person->data);
    
        return 0;
    }

程序运行结果是：

> del:3  
> del:6  
> del:1  
> del:5  
> del:2  
> del:8  
> del:4  
> winner:7

需要说明的是，以上代码包含的头文件`"list.h"`去哪里找呢？当然是内核源码了。

方便起见，我把相关代码扒拉出来，略微修改，组成了一个小而美的`"list.h"`。有了这个头文件，即使到了单片机上，内核链表也是可以用的。

#ifndef _LIST_H
    #define _LIST_H
    /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/stddef.h */
    
    //求偏移量
    #define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)
    
    
    /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/kernel.h */
    
    /** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */
    
    //小指针转大指针
    #define container_of(ptr, type, member) ({          \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})
    
    
    /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/types.h */
    struct list_head {
        struct list_head *next, *prev;
    };
    
    /* /usr/src/linux-headers-4.8.0-36-generic/include/linux/list.h */
    
    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    
    
    //以下这个宏用来定义并且初始化头结点
    #define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)
    
    
    /* kernel 3.14 */
    static inline void __list_add(struct list_head *new,
                      struct list_head *prev,
                      struct list_head *next)
    {
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;      //kernel 4.8中 这句话是 WRITE_ONCE(prev->next, new);
    }   
    
    
    /** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head, head->next); //头插
    }
    
    
    /** * list_add_tail - add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head->prev, head); //尾插
    }
    
    
    
    /* * Delete a list entry by making the prev/next entries * point to each other. * * This is only for internal list manipulation where we know * the prev/next entries already! */
    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
        next->prev = prev;
        prev->next = next;       //WRITE_ONCE(prev->next, next);
    }
    
    
    static inline void list_del(struct list_head *entry)
    {
        __list_del(entry->prev, entry->next);
        //entry->next = LIST_POISON1;
        //entry->prev = LIST_POISON2;
    }
    
    
    /** * list_empty - tests whether a list is empty * @head: the list to test. */
    static inline int list_empty(const struct list_head *head)
    {
        return head->next == head;
        //return READ_ONCE(head->next) == head;
    }   
    
    
    
    /** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */
    #define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)
    
    
    
    
    /** * list_for_each_safe - iterate over a list safe against removal of list entry * @pos: the &struct list_head to use as a loop cursor. * @n: another &struct list_head to use as temporary storage * @head: the head for your list. */
    #define list_for_each_safe(pos, n, head) \
        for (pos = (head)->next, n = pos->next; pos != (head); \
            pos = n, n = pos->next)
    
    
    
    /** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. */
    #define list_entry(ptr, type, member) \
        container_of(ptr, type, member)
    
    /** * list_first_entry - get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. * * Note, that list is expected to be not empty. */
    #define list_first_entry(ptr, type, member) \
        list_entry((ptr)->next, type, member)
    
    
    
    /** * list_next_entry - get the next element in list * @pos: the type * to cursor * @member: the name of the list_head within the struct. */
    #define list_next_entry(pos, member) \
        list_entry((pos)->member.next, typeof(*(pos)), member)
    
    /** * list_for_each_entry - iterate over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */
    #define list_for_each_entry(pos, head, member)              \
        for (pos = list_first_entry(head, typeof(*pos), member);    \
             &pos->member != (head);                    \
             pos = list_next_entry(pos, member))    
    
    
    /** * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. */
    #define list_for_each_entry_safe(pos, n, head, member)          \
        for (pos = list_first_entry(head, typeof(*pos), member),    \
            n = list_next_entry(pos, member);           \
             &pos->member != (head);                    \
             pos = n, n = list_next_entry(n, member))
    
    
    
    /** * list_for_each_entry_from - iterate over list of given type from the current point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate over list of given type, continuing from current position. */
    
    //从pos指向的结构体开始遍历
    #define list_for_each_entry_from(pos, head, member)             \
        for (; &pos->member != (head);                  \
             pos = list_next_entry(pos, member))    
    
    
    
    /** * list_for_each_entry_safe_from - iterate over list from current point safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate over list of given type from current point, safe against * removal of list entry. */
    #define list_for_each_entry_safe_from(pos, n, head, member)             \
        for (n = list_next_entry(pos, member);                  \
             &pos->member != (head);                        \
             pos = n, n = list_next_entry(n, member))   
    
    
    
    /** * list_for_each_entry_continue - continue iteration over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Continue to iterate over list of given type, continuing after * the current position. */
    
    //从pos的下一个开始遍历
    #define list_for_each_entry_continue(pos, head, member)         \
        for (pos = list_next_entry(pos, member);            \
             &pos->member != (head);                    \
             pos = list_next_entry(pos, member))
    
    /** * list_for_each_entry_safe_continue - continue list iteration safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate over list of given type, continuing after current point, * safe against removal of list entry. */
    #define list_for_each_entry_safe_continue(pos, n, head, member)         \
        for (pos = list_next_entry(pos, member),                \
            n = list_next_entry(pos, member);               \
             &pos->member != (head);                        \
             pos = n, n = list_next_entry(n, member))
    
    
    #endif

[http_blog.csdn.net_longintchar_article_details_75150621]: http://blog.csdn.net/longintchar/article/details/75150621