多文件編程考慮如何更好地實現結構化設計,是編製大文件的基礎。這裡給出一個使用動態內存建立循環鏈表,實現約瑟夫環的遊戲的例子,本程序使用多文件編程。
【例25.7】傳說有30個旅客同乘一條船,因為嚴重超載,加上風浪大作,危險萬分。因此船長告訴乘客,只有將全船一半的旅客投入海中,其餘人才能倖免於難。無奈,大家只得同意這種辦法,並議定30個人圍成一圈,由第一個人數起,依次報數,數到第9人,便把他投入大海中,然後再從他的下一個人數起,數到第9人,再將他扔進大海中,如此循環地進行,直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。由這個傳說產生了約瑟夫環的遊戲。
因為是用申請的連續內存區建立循環鏈表,所以大大簡化了建立的過程。
不失一般性,將30改為一個任意輸入的正整數number,而報數上限(也就是間隔數)為一個任選的正整數interval。
程序允許既可以輸入名字,也可以輸入編號,所以將結構設計為一個字符串數據和指針域即可。
typedef struct node{ char name[15] ; struct node * next ; }ListNode ;
因為程序要適應輸入奇數的情況,所以規定人數為奇數時,生還者比出局者多1個。
主程序設計三個函數求解。
int main ( ) { Initial (); // 取得參加遊戲的人數number 和間隔數interval SetRing (number ); // 根據參加遊戲的人數number 建立循環鏈表 Find (); // 求解 return 0 ; }
求解函數Find包含兩個函數,分別用來求解並輸出出局者和生還者。
void Find () { FindOut (); // 求解並輸出出局名單 PrintLeft (); // 輸出生還者名單 }
建立工程Ring,在其中定義一個頭文件Ring.h,並定義C文件Ring.c和main.c。
1.頭文件Ring.h
使用標準的條件編譯方法建立頭文件。
/***************************** * 建立頭文件 * *****************************/ #if !defined (RING_H ) #define RING_H #include <stdio.h> #include \"string.h\" #include <stdlib.h> struct person { char name[10] ; struct person *next ; } ; struct person *pBegin ; struct person *pCurrent ; struct person *pTmp ; int number ; // 參加人數 int interval ; // 間隔數 void Countx (int m ); // 數間隔數 void Dispx (); // 顯示出局者 void Clsx (); // 刪除出局的結點 void SetRing (int n ); // 建立循環鏈表 void Find (); // 求解 void Initial (); // 接受遊戲的人數和間隔數 void FindOut (); // 找出並輸出出局者 void PrintLeft (); // 輸出存活者 #endif
2.源文件Ring.c
//Ring.c #include \"Ring.h\" /**************************** * SetRing 函數 * * 功能:建立循環鏈表 * * 參數:n 循環鏈表長度 * *****************************/ void SetRing (int n ) { int i ; char s[10] ; pBegin= (struct person * )malloc (n*sizeof (struct person )); pCurrent=pBegin ; for ( i=1 ; i<=n ; i++ , pCurrent=pCurrent->next ) { pCurrent->next=pBegin+i%n ; printf (\" 輸入第%d 個人的名字:\" ,i ); gets (s ); strcpy (pCurrent->name ,s ); } pCurrent=&pBegin[n-1] ; } /***************************** * Countx 函數 * * 功能:間隔計數 * * 參數n : 間隔長度 * ******************************/ void Countx (int m ) { int i ; for (i=0 ; i<m ; i++ ) { pTmp=pCurrent ; pCurrent=pTmp->next ; } } /***************************** * Dispx 函數 * * 功能:輸出出局者信息 * ******************************/ void Dispx () { printf (\"%s \" ,pCurrent->name ); } /***************************** * Clsx 函數 * * 功能:刪除出局者結點 * ******************************/ void Clsx () { pTmp->next=pCurrent->next ; pCurrent=pTmp ; } /********************************* * Initial 函數 * * 功能:接受遊戲的人數和間隔數 * * number :參加遊戲的人數 * * interval :間隔數 * **********************************/ void Initial () { printf (\" 輸入參加遊戲的人數:\" ); scanf (\"%d\" ,&number ); printf (\" 輸入間隔數:\" ); scanf (\"%d\" ,&interval ); getchar (); } /*************************** * Find 函數 * * 功能:求解 * ****************************/ void Find () { FindOut (); // 求解並輸出出局名單 PrintLeft (); // 輸出生還者名單 } /*************************** * FindOut 函數 * * 功能:求解並輸出出局名單 * ****************************/ void FindOut () { int i ; printf (\" 出局名單如下:n\" ); for (i=0 ; i<number/2 ; i++ ) { Countx (interval ); Dispx (); Clsx (); } printf (\"n\" ); } /*************************** * PrintLeft 函數 * * 功能:輸出生還者名單 * ****************************/ void PrintLeft () { int i , tmp ; if ( number %2 == 0 ) tmp = number / 2 ; else tmp= (number +1 ) / 2 ; printf (\"n 生還者如下:n\" ); for (i=0 ; i<tmp ; i++ ) { pTmp=pCurrent ; pCurrent=pTmp->next ; Dispx (); } printf (\"n\" ); }
3.源文件main.c
//main.c #include \"Ring.h\" // 主函數 int main ( ) { Initial (); // 取得參加遊戲的人數number 和間隔數interval SetRing (number ); // 根據參加遊戲的人數number 建立循環鏈表 Find (); // 求解 return 0 ; }
4.組成工程
圖25-1給出它的組成圖。
5.運行實例
輸入參加遊戲的人數: 6 輸入間隔數: 2 輸入第1 個人的名字: 李一明 輸入第2 個人的名字: 王小二 輸入第3 個人的名字: 張 三 輸入第4 個人的名字: 李 四 輸入第5 個人的名字: 王老五 輸入第6 個人的名字: Hob
圖25-1 工程文件組成圖
出局名單如下: 王小二 李 四 Hob 生還者如下: 張 三 李一明 王老五 輸入參加遊戲的人數: 5 輸入間隔數: 2 輸入第1 個人的名字: 李一明 輸入第2 個人的名字: 王小二 輸入第3 個人的名字: 張 三 輸入第4 個人的名字: 李 四 輸入第5 個人的名字: 王老五 出局名單如下: 王小二 李 四 生還者如下: 張 三 李一明 王老五 輸入參加遊戲的人數: 30 輸入間隔數: 9 第1 個人的名字: 1 第2 個人的名字: 2 … // 省去中間過程,主要是驗證後面的約瑟夫環程序 第29 個人的名字: 29 第30 個人的名字: 30 出局名單如下: 9 18 27 6 16 26 7 19 30 12 24 8 22 5 23 生還者如下: 25 28 29 1 2 3 4 10 11 13 14 15 17 20 21