1、 题目一题目一 题目题目：约瑟夫环 问题描述问题描述： 编号是 1，2，,n 的 n 个人按照顺时针方向围坐一圈，每个人持有一个 密码（正整 数） 。一开始任选一个正整数作为报数上限值 m,从第一个人开始顺 时针方向自 1 开始顺 序报数，报到 m 时停止报数。报 m 的人出列，将他的密码 作为新的 m 值，从他在顺时 针方向的下一个人开始重新从 1 报数，如此下去， 直到所有人全部出列为止。设计一个 程序来求出出列顺序。 基本要求基本要求： 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编 号。此题所用 的循环链表中不需要“头结点”，请注意空表和非空表的界限。 测试数据测试数
2、据： m 的初值为 20，n=7 ,7 个人的密码依次为 3，1，7，2，4，8，4，首先 m 的值为 6 则 正确的输出应该是 6,1，4,7,2,3,5。 要求要求： 输入数据： 首先输入待处理人员数及他们的密码， 然后输入 m 的初值， 建立单循环链表。 输出形式输出形式： 建立一个输出函数，将正确的出列序列输出。 正文：正文： 一：一：需求分析 (1)输入形式: 首先输入待处理人员数及他们的密码，然后输入 m 的初值，建立单循环链表。 此程序设 ndata = 1; for (i = 2; i password); q-data = i; p-next = q; p = q; p-ne
3、xt = (*L); void Output(LinkList *L, int m, int n) Node *p, *q; int i = 1; p = (*L); printf(“输出出对序列:“); while (n) while (i != m) q = p; p = p-next; i+; printf(“%-3d“,p-data); m = p-password; q-next = p-next; free(p); p = q-next; i = 1; n-; printf(“n“); int main(void) LinkList L; int n, m; printf(“请输入
4、人数:“); scanf(“%d“, getchar(); CreatLinkList( printf(“请输入第一个报号数:“); scanf(“%d“, Output( system(“pause“); return 0; 四、调试分析 程序的编写和调试基本正常。 遇到的问题主要是：指针的指向的边界问题。 本实验采用数据抽象的与模块化程序设计方法。思路清晰，实现时调试顺利，各模块具有很 好的可重用性，得到了一次良好的程序设 计训练。 五、用户使用说明 如何使用，详细步骤 根据提示输入人数和每个人的信息 六、 调试结果 七： 参考文献 1. 严蔚敏, 吴伟民. 数据结构. 清华大学出版社,
5、2005.11 2. 谭浩强. C 语言程序设计. 清华大学出版社, 2005.11 3. 范辉. Visual C+程序设计. 高等教育出版社 题目二题目二 题目题目：哈夫曼编码器 问题描述：问题描述： 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传 输 成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传 来的 数据进行译码（复原） 。试为这样的信息传输写一个哈夫曼编/译码系统。 基本要求：基本要求： 1） I： 初始化（Initialization） 。 从终端读入字符集大小 n， 以及 n 个字符和 n 个权 值， 建立哈夫曼树，并将它
6、存于文件 hfmTree 中。输出哈夫曼树，及各字符对应的编码。 2）E：编码（Encoding）与译码（Decoding） 。 编码（Encoding） 。利用已建好的 哈夫曼树（如不在内存，则从文件 htmTree 中读 入） ，对文件 ToBeTran 中的正文进行 编码，然后将结果存入文件 CodeFile 中。 3） D： 译码 （Decoding） 。 利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码， 结果存入文件 TextFile 中。 4）P：印代码文件（Print） 。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个 代 码。同时将此字符形式的编码写入文件 CodePrint 中。 5）T：印哈夫曼树（Tree Printing） 。将已在内存中的哈夫曼树以直观的方式（树或 凹 入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。 测试数据：测试数据： (1) 利用教科书例6-2中的数据调试程序。 (2) 用下表
