spy 发表于 2015-3-27 16:53:30

关于Josephus问题2

#include <stdio.h>
#include <malloc.h>
struct Node
{
    int data;
    struct Node *prior, *next;
};

void CreateLoopList(struct Node **, int);
void SolveJosephus(struct Node *);
void ListTraverse(struct Node *);
void main()
{
    int n =10;
    struct Node *head = NULL;
    CreateLoopList(&head, n);
    ListTraverse(head);
    SolveJosephus(head);
}

void CreateLoopList(struct Node **head, int n)
{
    int i = 1;
    struct Node *p, *q;
    *head = (struct Node*)malloc(sizeof(struct Node));
    p = *head;
    q = (struct Node *)malloc(sizeof(struct Node));
    p->next = q;
    p = q;
    p->data = i++;
    while(i<=n)
    {
      q = (struct Node *)malloc(sizeof(struct Node));
      p->next = q;
      q->prior = p;
      p = q;
      p->data = i++;
    }
    p->next = (*head)->next;
    (*head)->next->prior = p;
}

void ListTraverse(struct Node *head)
{
    struct Node *p, *q;
    p = q = head->next;
    do
    {
      printf("%d ", p->data);
      p = p->next;
    }while(p!=q);
    printf("\n\n");
    do
    {
      printf("%d ", q->prior->data);
      q = q->prior;
    }while(q!=p);
    printf("\n");
}

void SolveJosephus(struct Node *head)
{
    int i=1, j, m;
    struct Node *p , *q;
    q = head->next;
    p = q->prior;
    while(p!=p->next)
    {
      printf("请输入第%2d个人的密码作为报数的上限值: \n", i);
      scanf("%d", &m);
      j = 1;
      while(j++%m)
      {
            p = p->next;
      }
      q = p->next;
      p->next = q->next;
      printf("第%2d个人出队\n", q->data);
      i = q->data;
      free(q);
    }
    printf("第%2d个人出队\n", p->data);
}

vanentu 发表于 2015-5-26 01:32:39

:shock:

溯月0503 发表于 2015-6-5 17:09:40

{:1_1:}
页: [1]
查看完整版本: 关于Josephus问题2