經典算法問題之約瑟夫問題

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct Node;//聲明節點

typedef struct Node *PtrToNode;

typedef PtrToNode Position;

typedef PtrToNode Head;

typedef PtrToNode List;

//節點定義

struct Node{

 int No;//編号

 char name[10];//名稱

 Position next;

};

List createLink(int num)

{

 Head head = NULL,p = NULL,q = NULL;

 int i=1;

 char name[10];

 head = (Position)malloc(sizeof(struct Node));//建立頭節點 

 head->No = 1;

 p=head;

 printf("請輸入第1個人名稱: \n");

 scanf("%s",name);

 strcpy(p->name,name);

 for(i=2;i<=num;i++)

 {

  q = (Position)malloc(sizeof(struct Node));

  if(q==0)return 0;

  p->next = q;

  p = q;

  p->No = i;

  printf("請輸入第%d個人名稱: \n",i);

  scanf("%s",&name);

  strcpy(p->name,name);

 }

 p->next = head;//讓最後一個節點的指針指回頭結點

 return head;//将頭節點傳回

}

void jose(Position p,int num,int n)

{

 int i,j = 0;

 Position q = NULL;

 for(i = 1;i<=num;i++)

 {

   //找到要被删除節點的上一個節點儲存在p中

   for(j=1;j<n-1;j++)

   {

    p = p->next;

   }

   q = p->next;//将需要删除的節點暫時儲存在q中，此時p表示要删除節點的上一個節點

   //将p->next(要删除的節點)從連結清單中删除

   p->next = q->next;

   p = p->next;

   printf("第%3d個出圈的是:%3d,name is %s\n",i,q->No,q->name);

   free(q);//釋放所占記憶體空間

  printf("\n");

 }

}

int main()

{

 Head head = createLink(15);

 jose(head,15,4);

 system("PAUSE");

return 1;

}

//執行效果如下圖所示: