多文件编程考虑如何更好地实现结构化设计,是编制大文件的基础。这里给出一个使用动态内存建立循环链表,实现约瑟夫环的游戏的例子,本程序使用多文件编程。
【例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