我知道我的实力对于副站长有点不配,但我还是懂一点点编程和网络的,在我能帮助大家的情况下,我一定尽力而为,在大家能指点我的情况下,也请大家不要看不起我啊...这决对是原创,不是转帖的,大家要是有不懂的欢迎来讨论啊~
/* ==================================================================
* File: ./subject.c
* ------------------------------------------------------------------
* Subject
* ---------
* Question:
* 编制一个求约瑟夫环出列顺序的程序
*
* Requirement Analyse:
* +-[1] 本演示程序中,编号为 1 至 n 的 n 个成员构成单向循环链表,链表的每
* | 一个结点中含有序号和密码两个信息,用户确定最开始的密码值 m,从第一
* | 个成员开始按链表的方向报数,报到 m 的成员出列,将它的密码作为 m 的
* | 新值从下一成员由 1 重新开始报数。如此循环下去,直到所有成员全部出列
* | 为止,即此时链表为空。
* |
* +-[2] 演示程序以用户和计算机的对话方式执行,用户需确定初始密码 m、成员数 n
* | 及每个成员的密码和编号,然后演示程序计算并列出相应的出列顺序。
* |
* +-[3] 程序执行的命令包括:
* | +-(1) 设立结构体,用于存放成员序号、密码信息及指向链表下一成员的指针;
* | +-(2) 构造循环链表;
* | +-(3) 进行出列运算处理并打印至显示终端;
* | +-(4) 程序运行结束,打印 "END"。
* |
* +-[4] 测试数据
* m = 20; n = 7, 成员的密码依次为:3, 1, 7, 2, 4, 8, 4;
* 正确的出列顺序应为:6, 1, 4, 7, 2, 3, 5。
*
* Base Design:
* 为实现上述功能,应以有序单向链表表示 n 个成员。我准备以一个结构体、三个
* 子程序来实现。
* +-[1] 结构体定义:
* | struct Joseph {
* | int num; // 用于存放成员号
* | int password; // 用于存放成员密码
* | struct Joseph *nextPtr; // 指向下一成员的指针
* | }
* |
* +-[2] 基本操作(两个子程序)
* int createlist(void);
* 此函数用作创建单向有序链表,并将用户输入的数值赋给相应的变量,如
* 果操作成功则返回成功信息代码,如果失败则返回相应的出错信息代码。
* ListPtr addnode(ListPtr, int, int);
* 此函数用于增加节点,带入参数依次为 地址指针, 成员号, 密码。
* void outlist(void);
* 此函数用作出列控制,使用递归进行出列操作,直至链表为空时返回。
*
* Particular Design:
*/
#include <stdio.h> // 读入基本输入输出库[printf(), scanf()...]
#include <stdlib.h> // 读入基本函数库[malloc(), exit()...]
#define MaxMember 30 // 定义最大成员数
#define Success 0 // 定义成功返回信息
#define Overflow 1 // 定义用户设定成员数越界错误信息
#define PassNumError 2 // 定义用户设定成员密码出错信息
#define Other 3 // 定义其它错误返回信息
struct Joseph { // 定义结构
int num;
int password;
struct Joseph *nextPtr;
};
typedef struct Joseph List; // 自定义类型 List
typedef List * ListPtr; // 自定义类型 ListPtr
int m, n; // 定义全局整型量,m 为报数,n 为成员数
ListPtr startPtr, endPtr; // 定义链表起始及结束的全局指针
int createlist(void); // 定义子函数
ListPtr addnode(ListPtr, int, int); // 定义子函数
void outlist(ListPtr, ListPtr); // 定义子函数
void main(void)
{
switch(createlist()) { // 对创建链表返回值进行处理
case Success:
printf("Out List: ");
outlist(startPtr, NULL);
printf("\nEND\n");
break;
case Overflow:
printf("Members quantity too big!\n");
break;
case PassNumError:
printf("Password number isn't natural number!\n");
break;
case Other:
printf("Have some wrong, system halt!\n");
break;
}
}
int createlist(void)
{
int i, pass;
ListPtr newPtr = NULL;
printf("Please input members quantity(n <= %d): ", MaxMember);
scanf("%d", &n);
if(n > MaxMember) return(Overflow);
for(i = 0; i < n; i++) {
printf("Please input member %d password: ", i + 1);
scanf("%d", &pass);
if(pass <= 0) return(PassNumError);
newPtr = addnode(newPtr, i + 1, pass); // 增加节点
if(i == 0) startPtr = newPtr; // 链表起始结点地址保存
}
endPtr->nextPtr = startPtr; // 使最后一节点指向起始节点,形成循环链表
printf("Please input start m value: ");
scanf("%d", &m);
return(Success);
}
ListPtr addnode(ListPtr subPtr, int num, int password)
{
if(subPtr != NULL) // 使用递归,向下一节点赋值
subPtr->nextPtr = addnode(subPtr->nextPtr, num, password);
else {
subPtr = (ListPtr)malloc(sizeof(List)); // 按节点所需空间分配内存
subPtr->num = num;
subPtr->password = password;
subPtr->nextPtr = NULL;
endPtr = subPtr; // 链表结束结点地址保存
}
return subPtr;
}
void outlist(ListPtr nowPtr, ListPtr oldPtr)
{
if(nowPtr != nowPtr->nextPtr) { // 当表有两个结点以上时(包括有两个结点)
if(m == 1) { // 当报数停止时,此节点出列
printf("%d ", nowPtr->num);
m = nowPtr->password;
oldPtr->nextPtr = nowPtr->nextPtr; // 将前一节点指向地址改为现节点指向地址
free(nowPtr); // 释放现节点内存空间
outlist(oldPtr->nextPtr, oldPtr); // 递归,进行出列操作
}
else {
m--; // 报数
outlist(nowPtr->nextPtr, nowPtr); // 递归,进行出列操作
}
}
else { // 只有一个结点时
printf("%d", nowPtr->num);
free(nowPtr);
}
}
/* Debug Analyse:
* +-[1] 此代码使用递归简化复杂的循环及判断操作,使程序运行速度提高,代码优
* | 化较好,无冗余代码。
* +-[2] 代码关键部分注释清楚,思路明确,结构完整、清晰,阅读性较高。
* +-[3] 代码模块划分比较合理,各个模块分工明确,便于调试。
*
* User Manual:
* +-[1] 本程序的运行环境为 DOS 操作系统,标准 C 语言编译环境。
* +-[2] 进入 C 环境后调用subject1.c程序,生成可执行文件 subject1.exe,
* | 并执行,按程序提示输入相应数值。
* +-[3] 程序自动执行运算和显示相应的结果。
*
* Test Result:
* +- Test [1]
* | >Please input members quantity(n <= 30): 7
* | >Please input member 1 password: 3
* | >Please input member 2 password: 1
* | >Please input member 3 password: 7
* | >Please input member 4 password: 2
* | >Please input member 5 password: 4
* | >Please input member 6 password: 8
* | >Please input member 7 password: 4
* | >Please input start m value: 20
* | >Out List: 6 1 4 7 2 3 5
* | >END
* |
* +- Test [2]
* | >Please input members quantity(n <= 30): 4
* | >Please input member 1 password: 7
* | >Please input member 2 password: 4
* | >Please input member 3 password: 12
* | >Please input member 4 password: 56
* | >Please input start m value: 5
* | >Out List: 1 2 4 3
* | >END
* |
* +- Test [3]
* >Please input members quantity(n <= 30): 14
* >Please input member 1 password: 5
* >Please input member 2 password: 8
* >Please input member 3 password: 6
* >Please input member 4 password: 8
* >Please input member 5 password: 5
* >Please input member 6 password: 4
* >Please input member 7 password: 6
* >Please input member 8 password: 7
* >Please input member 9 password: 4
* >Please input member 10 password: 3
* >Please input member 11 password: 2
* >Please input member 12 password: 2
* >Please input member 13 password: 8
* >Please input member 14 password: 1
* >Please input start m value: 8
* >Out List: 8 1 6 11 13 10 2 3 14 4 12 7 5 9
* >END
*
* Remark:
* 此代码在完成题目的要求同时,注重资源分配,将使用过的内存地址段及时释放,
* 使系统效率提高,代码健壮性较好。
*
* PS: 在 NetDemon 的再三逼迫下,我只有把原来帮一个朋友写的作业帖上来了...
* 唉,这个职位真不好当,只好请大家见谅了
* ==================================================================
*/
------------------
技术相关的不用找我,我是菜鸟;
空虚的美眉不用找我,我有女友;
无聊的大虾不用找我,我只发呆;
以上皆否的不用找我,我想清静!
[被 xiean 编辑过(日期 08-05-2001)]