这决对是原创,不是转帖的,大家要是有不懂的欢迎来讨论啊~
/* ==================================================================
* 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)]
------------------
天涯孤旅何时才能停止!
带着最终的信念飘零尘世!
只对着一屡屡的清风痴迷!
这就是我-千年纪风-与风作伴的天涯浪子...
------------------
技术相关的不用找我,我是菜鸟;
空虚的美眉不用找我,我有女友;
无聊的大虾不用找我,我只发呆;
以上皆否的不用找我,我想清静!
/* File: Code.c
*
* Question:
* 编号为 1, 2, 3, ......, n 的 n 个人按顺时针方向围坐一圈,
* 每人持有一个密码(正整数),一开始任选一个正整数作为报数的上
* 限值 m,从第一个人开始按顺时针方向自一开始顺序报数,报到 m 时
* 停止报数。报 m 的人出列,将他的密码作为新的 m 值,从他在顺时
* 针方向上的下一个人开始重新从 1 报数,如此下去直到所有人全部出
* 列为止。设计一个程序求出出列顺序。
*
* Base Request:
* 利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各
* 人的编号。
*
* Test Data:
* m 的初值为 20;n = 7, 7个人的密码依次为:3,1,7,2,4,8,4
* (正确的出列顺序为:6,1,4,7,2,3,5)。
*
* Actualize Clew:
* 程序运行后,首先要求用户指定初始报数上限值,然后读取各人
* 的密码。设 n <= 30。此题所用的循环链表中不需要“头结点”,请
* 注意空表和非空表的界限。
*
*
* 本代码已经过 Turbo C 2.0, Turbo C 3.0, Borland C++ 3.1 编译通过
* Writed by xiean at 2000-6
*/
#include <stdio.h> // printf() scanf() 函数头文件
#include <stdlib.h> // exit() 函数头文件
#define MaxMember 30 // 定义 MaxMember 为最大成员数
// 定义结构
struct CodeData {
int pass; // 持有密码
int out; // 是否出列
} member[MaxMember];
// 主函数体
void main(void)
{
// i 和 j 为循环控制变量,member_num 为题中的 n,m 为题中的 m
// n 为出列控制变量,k 为出列次序变量
int i, j, member_num, m, n, k;
// 获得成员数 member_num
printf("\nPlease input members quantity(n <= %d): ", MaxMember);
scanf("%d", &member_num);
// 如果成员数超过最大上限,而出错退出程序
if(member_num > MaxMember) {
printf("Members quantity too big!\n");
exit(0);
}
// 初始结构,使 member[i].pass 为密码,member[i].out 为出列判定
for(i = 0; i < member_num; i++) {
printf("Please input member %d password: ", i + 1);
scanf("%d", &member[i].pass);
member[i].out = 0;
}
// 获取初始 m 值
printf("Please input start m value: ");
scanf("%d", &m);
// 打印出列顺序
printf("\nOut List: ");
k = m % member_num; // 顺时针第 k 个成员出列
j = 0;
for(i = 0; i < member_num; i++) {
n = 0;
while(n < k) {
if(!member[j].out) n++; // 如果 member[j] 未出列,则 n 递增
if(n == k) { // member[j] 出列,置出列标识 member[j].out 为真
printf("%d ", j + 1);
member[j].out = 1;
break;
}
j++;
if(j + 1 > member_num) j = 0; // 如果超出范围则清零
}
// 这里取 k 值加判断是为了防止如 7 % 0 非法情况出现和最后一位数出列优化
// i == member_num - 2 时是最后一位数出列
// i == member_num - 1 时是防止 (member_num - 1 - i) 为 0
if(i >= member_num - 2) k = 1; // 顺时针第 k 个成员出列
else k = member[j].pass % (member_num - 1 - i); // 顺时针第 k 个成员出列
}
// 程序运行结束
printf("\nEND\n");
}
------------------
技术相关的不用找我,我是菜鸟;
空虚的美眉不用找我,我有女友;
无聊的大虾不用找我,我只发呆;
以上皆否的不用找我,我想清静!
------------------
技术相关的不用找我,我是菜鸟;
空虚的美眉不用找我,我有女友;
无聊的大虾不用找我,我只发呆;
以上皆否的不用找我,我想清静!
------------------
技术相关的不用找我,我是菜鸟;
空虚的美眉不用找我,我有女友;
无聊的大虾不用找我,我只发呆;
以上皆否的不用找我,我想清静!
------------------
天涯孤旅何时才能停止!
带着最终的信念飘零尘世!
只对着一屡屡的清风痴迷!
这就是我-千年纪风-与风作伴的天涯浪子...
我可是把这当成我当副站长考题之一的东东啊,如果还是实力不行,我只有再帖帖子了... =~(
------------------
技术相关的不用找我,我是菜鸟;
空虚的美眉不用找我,我有女友;
无聊的大虾不用找我,我只发呆;
以上皆否的不用找我,我想清静!
------------------
天涯孤旅何时才能停止!
带着最终的信念飘零尘世!
只对着一屡屡的清风痴迷!
这就是我-千年纪风-与风作伴的天涯浪子...
------------------
技术相关的不用找我,我是菜鸟;
空虚的美眉不用找我,我有女友;
无聊的大虾不用找我,我只发呆;
以上皆否的不用找我,我想清静!
------------------
天涯孤旅何时才能停止!
带着最终的信念飘零尘世!
只对着一屡屡的清风痴迷!
这就是我-千年纪风-与风作伴的天涯浪子...
但是我也发现有个别地方欠妥,在函数addnode()中,
else后面的
subPtr = (ListPtr)malloc(sizeof(List)); // 按
后面并没有监测malloc()是否执行成功而直接对subPtr进行操作,有可能造成访问空指针~!
改动如下
else {
subPtr = (ListPtr)malloc(sizeof(List)); // 按节点所需空间分配内存
改为
else {
if((subPtr = (ListPtr)malloc(sizeof(List))) == NULL) return(Other); // 按节点所需空间分配内存
这样就可以防止你所说的那种情况了
记住你答应我以后常来啊,嘿嘿
------------------
技术相关的不用找我,我是菜鸟;
空虚的美眉不用找我,我有女友;
无聊的大虾不用找我,我只发呆;
以上皆否的不用找我,我想清静!
我还是第一次到这里来,
我太孤陋寡闻了,想不到
有这等好地方~~~
以后一定长来~~!