接着上面说,说这是最后一个算法题目,这是最后一个题目,也是最复杂的题目,题目如下:
4、算法题目,转圈数M数,最后出局的是哪个数。(题目就是这样非常的简洁,其实就约瑟夫算法)
#include <stdio.h>#include <stdlib.h>typedef struct Link{int data;struct Link *next;} LinkList;LinkList * createLink(int n){printf("enter function createLinkn");LinkList *head, *rear, *new;head = rear = (LinkList *)malloc(sizeof(LinkList));int i = 0;for(i = 0; i< n; i++){new = (LinkList *)malloc(sizeof(LinkList));new->data = i+1;new->next = NULL;rear->next = new;rear = new;}rear->next = head->next;printf("exit function createLinkn");return rear;}LinkList* getJosephus(LinkList* rear, int m){printf("enter function getJosephusn");LinkList *newHead, *newRear, *newLinkList;LinkList *tempList;newHead = newRear = (LinkList *)malloc(sizeof(LinkList));//LinkList *oldHead = rear->next;int i = 0;while(rear != rear->next){//原链表走m-1节点for(i = 0; i < m-1; i++){rear = rear->next;}//原链表删除第m个节点tempList = rear->next;rear->next = tempList->next;tempList->next = NULL;//新链表加入删除的第m个节点newRear->next = tempList;newRear = tempList;}//新链表加入原链表剩下的最后一个节点newRear->next = rear;newRear = rear;newRear->next = newHead->next;printf("exit function getJosephusn");return newRear;}void printJosephus(LinkList* newRear){printf("enter function printJosephusn");//temp2先获取头节点LinkList *temp2 = newRear->next;do{printf("temp2->data=%d,", temp2->data);temp2 = temp2->next;}while(temp2 != newRear->next);//上面如果是头节点则结束循环printf("n");printf("exit function printJosephusn");}int main(){//1/创建5个节点的链表LinkList *oldLinkList = createLink(5);//打印当前链表的情况printJosephus(oldLinkList);//2/进行m循环,也就是约瑟夫循环LinkList *newLinkList = getJosephus(oldLinkList, 3);//打印约瑟夫循环的输出列表printJosephus(newLinkList);}运行情况如下:
root@mkx:~/learn/Josephus# gcc josephus.c -o josephusroot@mkx:~/learn/Josephus# ./josephusenter function createLinkexit function createLinkenter function printJosephustemp2->data=1,temp2->data=2,temp2->data=3,temp2->data=4,temp2->data=5,exit function printJosephusenter function getJosephusexit function getJosephusenter function printJosephustemp2->data=3,temp2->data=1,temp2->data=5,temp2->data=2,temp2->data=4,exit function printJosephusroot@mkx:~/learn/Josephus#5个数,用手画一下,就可以知道,结果是对的。
这道题目,其实就是著名的约瑟夫算法,循环链表实现,是非常经典的实现方法,这里用了循环链表,比如非循环列表多了一个尾节点,这是需要注意的地方:
下面用图就可以非常形象地表现出来:
其关键就是head与rear两个指针,其操作对这两个指针进行操作就可以了。



