用面向過程的程式設計方式（C），對某個給定的n=8與m=3，給出被淘汰出列的旅客編號，以及最終的倖存者。

用面向物件的程式設計風格（C++），重新處理該約瑟夫問題。

談談這兩種程式設計風格的優點。

二、用C語言解約瑟夫問題

1、單鏈表的建立與輸出

#include<stdio.h>

#include<malloc.h>

#define NULL 0

struct node{ /*定義結構體*/

int data;

struct node *next;

};

typedef struct node NODE;/*將該結構體設定成自定義型別*/

NODE *head;/*定義一個指向該結構體的頭指標*/

NODE *create(int n)/*建立具有n個結點的單鏈表*/

{

NODE *p;

int i=1;

head=(NODE *)malloc(sizeof(NODE));

head->next=NULL;

while(i<=n)

{

p=(NODE *)malloc(sizeof(NODE));

p->data=n+1-i;

p->next=head->next;

head->next=p;

i++;

}

return(head);

}

void output(NODE *point)/*輸出該連結串列資料域內的值*/

{

NODE *p;

p=point->next;

while(p!=NULL)

{

printf("%d ",p->data);

p=p->next;

}

printf("\n");

}

如果我們寫一段main()函式

void main()

{

head=create(8);

output(head);

}

便可以完成建立和輸出單鏈表的工作。

如果將上述建立單鏈表與輸出單鏈表的工作儲存為標頭檔案link1.h,那麼在今後需要建立輸出類似的單鏈表時，只需寫以下主函式即可。

#inlucde “link1.h”

void main()

{

head=create(8);

output(head);

}

2、迴圈單向連結串列的建立與輸出

明白了帶頭指標的單向連結串列的建立與輸出，只需作簡單修改便可處理迴圈單向連結串列的相關問題。這裡我們建立一個新的標頭檔案link2.h，它包含以下幾段程式碼。

#include<stdio.h>

#include<malloc.h>

struct node{

int data;

struct node *next;

};

typedef struct node NODE;

NODE *head;

NODE *create(int n)

{

NODE *p;

int i=1;

p=head=(NODE *)malloc(sizeof(NODE));

head->next=head;/*造迴圈連結串列時頭指標的指標域設定*/

while(i<=n)

{

p->data=n+1-i;

p->next=head->next;

head->next=p;

i++;

p=(NODE *)malloc(sizeof(NODE));

}

return(head);

}

void output(NODE *point,int n) /*n表示欲輸出多少個結點，由於該連結串列是迴圈的，可輸出無窮項*/

{

NODE *p;

int i=1;

p=point->next;

while(i<=n)

{

printf("%d ",p->data);

p=p->next;

i++;

}

printf("\n");

}

在標頭檔案link2.h中增添新函式del(int n,int m),這裡的形參n代表起始結點，m代表報數值。

void del(int n,int m)

{

int i;

NODE *p,*q;

p=head;

/*將指標移到起始結點，即第n個結點*/

i=0;

while(i<n)

{

p=p->next;

i++;

}

while(p->next!=p)

{

i=1;

while(i<m)/*找到符合報數值結點的前一個結點,即第m-1個結點*/

{

p=p->next;

i++;

}

q=p->next;

printf("%d ",q->data);

p->next=q->next;

free(q);

}

printf("\nonly one %d",p->data);/*輸出僅剩的結點*/

}

4、解決約瑟夫問題的主函式

#include <link2.h>

void main()

{

/*number結點個數,item輸出結點的個數,location報數的起始位置,callnum報數值*/

int number,item,location,callnum;

printf("\ninput nose number=");

scanf("%d",&number);

printf("\noutput item=");

scanf("%d",&item);

head=create(number);

output(head,item);

printf("\ninput location=");

scanf("%d",&location);

printf("\ninput callnum=");

scanf("%d",&callnum);

del(location,callnum);

}

三、以類作為結點來處理約瑟夫問題（準C++程式設計風格）

1、以類作結點的連結串列建立

#include <iostream.h>

class Node

{

private:

int data;

Node *next;

public:

Node(){data=0;next=NULL;}

void SetData(int new_data){data=new_data;}

void SetNext(Node *new_next){next=new_next;}

int GetData(){return data;}

Node *GetNext(){return next;}

};

void main()

{

Node *head=NULL,*p,*q;

for(int i=1;i<9;i++)

{

p=new Node;

p->SetData(i);

if(head==NULL)

head=p;

else

q->SetNext(p);

q=p;

}

q=head;

do

{

cout<<"該遊客編號為:"<<q->GetData()<<endl;

q=q->GetNext();

}while(q!=NULL);

q=head;

do

{

q=q->GetNext();

delete head;

head=q;

}while(q!=NULL);

}

2、以類作結點的迴圈連結串列的建立

#include <iostream.h>

class Node

{

private:

int data;

Node *next;

public:

Node(){data=0;next=NULL;}

void SetData(int new_data){data=new_data;}

void SetNext(Node *new_next){next=new_next;}

int GetData(){return data;}

Node *GetNext(){return next;}

};

void main()

{

Node *head,*p,*q;

head=new Node;

q=p=head;

for(int i=1;i<=8;i++)

{

p->SetData(i);

p->SetNext(head);

q->SetNext(p);

q=p;

p=new Node;

}

q=head;

i=1;

do

{

cout<<"該遊客編號為:"<<q->GetData()<<endl;

q=q->GetNext();

i++;

}while(i<=10);

}

3、解決約瑟夫問題

#include <iostream.h>

class Node

{

private:

int data;

Node *next;

public:

Node(){data=0;next=NULL;}

void SetData(int new_data){data=new_data;}

void SetNext(Node *new_next){next=new_next;}

int GetData(){return data;}

Node *GetNext(){return next;}

};

void main()

{

Node *head,*p,*q;

head=new Node;

q=p=head;

for(int i=1;i<=8;i++)

{

p->SetData(i);

p->SetNext(head);

q->SetNext(p);

q=p;

p=new Node;

}//

p=head;

i=1;

while(i<=8)

{

cout<<p->GetData()<<" "<<endl;

p=p->GetNext();

i++;

}//輸出

cout<<endl;

p=head;

while(p->GetNext()!=p)

{

i=1;

while(i<2)

{

i++;

}

q=p->GetNext();

p->SetNext(q->GetNext());//將q指標域所指結點的地址賦給p的指標域

p=p->GetNext();

delete q;

}//做迴圈數數出局遊戲

cout<<"\nLast One "<<p->GetData()<<endl;

}

四、用標準的面向物件程式設計風格處理約瑟夫問題（C++程式設計風格）

//#include "stdafx.h"

#include "iostream.h"

//#define NULL 0

class Node

{

private:

int data;

Node *next;

public:

Node(){data=0;next=NULL;}

Node *Create(int n);//建立含n個結點的迴圈連結串列

void Output(Node *p,int n);//輸出迴圈連結串列頭結點為p的後n個結點的資訊

Node *Move(Node *p,int n);//將頭結點指標前移到n

//從頭結點為p的迴圈鏈開始，所用的計數為n進行約瑟夫實驗

void Josephus(Node *p,int n);

};

Node *Node::Create(int n)

{

Node *head,*p,*q;

head=new Node;

q=p=head;

for(int i=1;i<=n;i++)

{

p->data=i;

p->next=head;

q->next=p;

q=p;

p=new Node;

}

return head;

};

void Node::Output(Node *p,int n)

{

int i=1;

while(i<=n)

{

cout<<p->data<<" ";

p=p->next;

i++;

}

};

Node *Node::Move(Node *p,int n)

{

if(n>1)

{

int i=1;

while(i<n)

{

p=p->next;

i++;

}

}

return p;

};

void Node::Josephus(Node *p,int n)

{

Node *q;

while(p->next!=p)

{

p=Move(p,n-1);

q=p->next;

cout<<q->data<<" ";

p->next=q->next;

p=p->next;

delete q;

}

cout<<"\nLast One "<<p->data<<endl;

};

void main()

{ Node A,*head;

head=A.Create(8);

cout<<"\nCirclist is ";

A.Output(head,10);

head=A.Move(head,1);

cout<<"\nJosephus result is "<<endl;

A.Josephus(head,3);

}

五、對兩種程式設計風格的評述

在進行面向過程的程式設計時，一般首先考慮程式所要實現的功能，然後設計為實現這些功能所必須採取的步驟，這些步驟就是過程。如果一個過程比較複雜而不能直接使用已有的抽象進行實現，則對這個過程進行分解，使分解之後的每一步（更低階的過程）能夠直接對應著一條語句。透過將分解之後的一系列過程封裝在一個函式抽象中，程式設計師在特定的時刻只關心有限的細節，這個新的函式抽象比其較低階的抽象更接近問題求解的過程，因而，能夠很好地對映問題求解中的過程。如果這個過程出現在許多問題求解中，那麼，這個函式抽象就可能被重複利用。

函式是面向過程程式設計的基礎，按照結構化程式設計的思想，又可將完成某一複雜工作的函式放在一個頭檔案，便於我們多次複用。

面向過程的程式設計方法與面向物件的程式設計方法的根本區別在於對待資料和函式的關係上。

在面向過程的程式設計中，資料只被看作是一種靜態的結構，它只有等待呼叫函式來對它進行處理。

在面向物件的程式設計中，將資料和對該資料進行合法操作的函式封裝在一起作為一個類的定義。另外，封裝還提供了一種對資料訪問嚴格控制的機制。因此，資料將被隱藏在封裝體中，該封裝體透過操作介面與外界交換資訊。

面向物件的思想需要在實踐中不斷摸索和體會，在以後的程式設計中，可主動運用這種思想去實踐。