C语言程序设计课程设计题目

1、通信工程10级C语言课程设计任务书各位同学可以自由组合，不超过以下题目中所规定的人数进行选题（不允许重复选题）。辅导时间：另定地点：软件中心（语音楼8楼）答辩检查时间：18周星期五上午8：00起1. Huffman编解码（1人）要求: a. 随机输入一段英文(含标点、空格以及大小写的区分，标点仅限逗号“，”和句点“.”)； b. 统计各种符号出现的频度； c. 进行Huffman编码（以二进制01代码输出）； d. 以上一步的输出（二进制序列）作为输入进行解码，恢复原英文； e. 比较输入和输出，统计出错的个数。前缀码、Huffman编码算法：前缀码：给定一个序列的集合，若不存在一个序列是另一

2、个序列的前缀，则该序列集合称为前缀码。哈夫曼（Huffman）算法可用来设计前缀编码，用该算法构造一棵有n个叶子（每个叶子具有一个权值）的二叉树的过程如下：（1）根据n个权值w1，w2，wn构成n棵二叉树的集合F=T1，T2，Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。（2）在F中选取两棵根结点的权值最小的树作为左右子树来构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树结点的根结点的权值之和。（3）在F中删除这两棵树，同时将新得到的二叉树加入F中。（4）重复（2）和（3），直到F中只含一棵树时为止。称这棵树为最优二叉树（或哈夫曼树）。如果约定将每个结点

3、的左分支表示字符“0”，右分支表示字符“1”，则可以把从根结点到某叶子结点的路径上分支字符组成的字符串作为该叶子结点的编码。对于所有可能传输的字符，令每个字符对应一个叶结点，权值为其出现的频率，那么根据哈夫曼算法构造出二叉树后，就得到了每个字符的二进制编码。根据构造过程可知，这种编码方案得到的字符的编码长度的数学期望值为最小，因此这种编码方案是一个最优前缀码。在构造过程中，每次都是选取两棵最小权值的二叉树进行合并。 2. 简易计算器设计（1人）要求： a. 用户输入一表达式，表达式为四则运算表达式（只含加、减、乘、除以及括号）； b. 判断用户输入的表达式正确与否，如错则报错，否则进行表达式值

4、的计算并给出结果； c. 数据可以是任意实数。表达式求值的过程：表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子。这里介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如，要对下面的算术表达式求值： 4 + 2 3 - 10/5首先要了解算术四则运算的规则。即：（1）先乘除，后加减； （2）从左算到右； （3）先括号内，后括号外。由此，这个算术表达式的计算顺序应为 4 + 2 3 - 10/5 = 4 + 6 - 10/5 = 10 - 10/5 = 10

5、- 2 = 8算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的，我们称它们为单词。一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符3类；基本界限符有左右括号和表达式结束符等。为了叙述的简洁，我们仅讨论简单算术表达式的求值问题。这种表达式只含加、减、乘、除4种运算符。读者不难将它推广到更一般的表达式上。我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述3条运算规则，在运算的每一步中，任意

6、两个相继出现的算符1和2之间的优先关系至多是下面3种关系之一: 12 1的优先权高于2表1定义了算符之间的这种优先关系。表1 算符间的优先关系由规则（3），+、-、*和/为1时的优先性均低“（”但高于“）”，由规则（2），当1=2时，令12，“#”是表达式的结束符。为了算法简洁，在表达式的最左边也虚设一个“#”构成整个表达式的一对括号。表中的“（”=“）”表示当左右括号相遇时，括号内的运算已经完成。同理，“#”=“#”表示整个表达式求值完毕。“）”与“（”、“#”与“）”以及“（”与“#”之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误。在下面的讨

7、论中，我们暂假定所输入的表达式不会出现语法错误。为实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想的：（1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）依次读入表达式中每个字符，若是操作数则进 OPND 栈，若是运算符则和 OPTR 栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即 OPTR 栈的栈顶元素和当前读入的字符均为“#”）。以下算法描述了这个求值过程。OperandType EvaluateExpression() / 算术表达式求值的算符优先算法。设 OPTR

8、 和 OPND 分别为运算符栈和运算数栈，OP 为运算符集合。 InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c = getchar(); while(c!=# | GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c); c = getchar(); / 不是运算符则进栈 else switch(Precede(GetTop(OPTR),c) case : / 退栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,the

9、ta,b); break; / switch / while return GetTop(OPND); / EvaluateExpression算法中还调用了两个函数。其中Precede是判定运算符栈的栈顶运算符1与读入的运算符2之间优先关系的函数；Operate为进行二元运算 ab的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算的结果。3. 五子棋游戏（1人）要求： a. 棋盘为19*19，按五子棋的游戏规则进行；b. 对奕双方是用户和电脑；c. 考虑到界面问题，棋盘界面及用户的输入可采用如下输入方式： a

10、b c d e f g h I j k l m n o p q r s a b c d e o f xxo g o h i j k l m n o p q r s 现在该“x”方下，请输入坐标： d. 由电脑判断胜负。4. 速算24（1人）要求： a. 一副牌54张牌，黑桃（SA，SK，SQ，SJ，S10，S2），红桃（HA，HK，HQ，HJ，H10，H2），方块（DA，DK，DQ，DJ，D10，D2），草花（CA，CK，CQ，CJ，C10，C2）以及大鬼Q1和小鬼Q2。其中，A，K，Q，J及Q1，Q2的点值分别为：1，13，12，11，1，1。其余点值就是牌值。 b. 由计算机随机出四张牌。

11、 c. 用户输入能算出24的表达式（只能用加、减、乘、除及括号组成的四则运算）。 d. 计算机检验用户给出的表达式正确与否（包括是否用计算机所给出的四张牌），并根据该表达式计算出值，判断用户的方法是否正确。 e. 表达式求值算法参考2题5. 乘法器、除法器（各1人，计2人）要求：乘法器a. 乘数与被乘数的位数是不少于35位的无符号整数；b. 输入乘数和被乘数，计算出精确的结果值。除法器：a、被除数的位数不少于50，除数的位数不多于50位；b、算出的结果为商和余数商，保留到小数点后50位。6. 二进制多项式（此处特指系数为1或0的多项式，如）的乘法器与除法器（1人）要求：a. 二进制多项式是指系

12、数为1或0的多项式。b. 输入两个二进制多项式，计算并输出两个多项式的积。c. 输入两个二进制多项式，计算并输出第一个多项式除以第二个多项式后的商和余式。注意：此处涉及到二进制运算有：1+1=0，1+0=1，0+1=1，0+0=0； 1*1=1，1*0=0，0*1=0，0*0=0；没有减法，直接将减号变成加号即可。6、多项式的加法、乘法和除法（1人）7. 稀疏矩阵（1人）要求：1、包括稀疏矩阵的压缩与还原 输入一个稀疏矩阵，用常规的方式存放，然后将其压缩成三元组表的形式； 输入一个稀疏矩阵，用三元组表的方式存放，然后将其还原成常规方式 2、稀疏矩阵的转置 输入一个稀疏矩阵，以三元组表的方式存放

13、，将其进行转置操作之后输出； 3、两个稀疏矩阵的乘法 输入两个可以相乘的稀疏矩阵，均以三元组表的方式存放，将它们的乘积输出。注意：假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元顺序表。 #define maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple;typedef struct triple datamaxsize; int m,n,t; tripletable;图1 设A为tripletable型的结构变量，图1所示的稀疏矩阵的三元组的表示如下： i j v

14、 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。 一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。 将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。 由于A的列是B的行，因此，按a.data的列序转置，

15、所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。按这种方法设计的算法，其基本思想是：对A中的每一列 col(0coln-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。 i j v 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关

16、系装入三元组。可见，位置关系是此种算法的关键。为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 为此，需要设置两个一维数组num0.n和cpot0.nnum0.n：统计M中每列非零元素的个数，numcol的值可以由A的第二列求得。cpot0.n：由递推关系得出M中的每列第一个非零元素在B中的位置。 算法通过cpot数组建立位置对应关系： cpot1=1 cpotcol=cpotcol-1+numcol-1 2=cpl=a.n

17、 例如：前面所给出的矩阵M和相应的三元组A可以求得numcol和 cpotcol的值如下： col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9带行表的三元组有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下：#define maxrow 100 typedef struct triple datamaxsize; int rposmax

18、row; int n,m,t; rtripletable稀疏矩阵相乘的基本思想是：对于M中每个元素M，找到N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。8.编写一个猜数字游戏（1人）有一定的容错功能，界面友好，功能齐全。游戏规则：a，随机生成一个四位数，各位上的数字不重复,从1到9。b，按以下提示猜出这个四位数。c，每次猜测输入的数据给出类似的提示*A*B。d，其中A前的*代表你本次猜对了多少个数字。e，其中

19、B前的*代表你本次猜对的数字并且位置正确的个数。9. 图书管理系统（3人）能够完成图书馆日常操作，数据要能够保存，能够随时取出，并在任何操作后都能保持信息完整性，具体内容如下：l 图书管理 添加图书增加新的图书，同时需检查新书的图书编号是否在原图书当中存在，若是则应取消添加并提示重新输入。 查询图书通过书编号查询图书信息。 修改图书通过编号查询该图书，若找到则允许修改，否则提示无该图书信息。 删除图书资料 通过编号查询该图书，若找到则允许删除，否则提示无该图书信息。删除对象包括该图书资料以及“借还书登记”中的相关记录。l 图书借还 借书1. 判断所借书籍号是否存在，若不存在重新输入书籍号。2.

20、 判断该借书证号是否存在，若不存在重新输入借书证号。3. 判断该书籍是否已借出，若是则不允许执行借书操作。4. 借书处理包括在“借还书登记”中增加该借书情况，在该图书信息中加上“已借”标记。 还书()1. 判断所借书是否存在，若不存在重新输入书籍。2. 判断该书是否已借出，若不是则不允许执行还书操作。3. 借书处理包括在“借还书登记”中增加该还书情况，在该图书信息中加上“未借”标记。 历史查询可根据日期、书编号、查询所有符合的借还书记录。l 证件管理 添加读者增加新读者，同时需检查该读者编号是否在所有借书证当中存在，若是则应取消添加并提示重新输入。 查询读者资料通过借书证号查询读者信息。 修改

21、读者资料通过借书证号查询该读者，若找到则允许修改，否则提示无该读者资料。 删除读者资料1. 通过借书证号查询该读者，若找到则允许删除，否则提示无该读者资料。2. 通过借书证号查询该读者是否仍借有书籍，若有，则应归还书籍才可进行删除操作。3. 删除对象包括该读者资料以及“借还书登记”中的相关记录。l 基本数据结构l 图书结构体struct book char num4;/* 书编号*/ char name20;/*书名*/char pub_co20; /*出版社*/char auther10; /*作者*/ float price;/*价格*/ char per_num5;/借书证号*/ cha

22、r borrow;/*借出否，1:借出；0:未借出*/ ;l 读者结构体struct certchar per_num5;/*借书证号*/ char name20;/*姓名*/ char sex;/*性别,M表示男，G表示女*/ int age;/*年龄*/;l 日期结构体struct timeint year;/*年*/int minth; /*月*/int date; /*日*/;l 借书情况结构体struct card char per_num5;/*借书证号*/ struct time br_time;/*借还书日期*/ char event;/*借还书，其中1：表示借，0：表示还*/

23、 char num4;/*图书编号*/;l 多个数据的组织形式对于多本图书资料，可采用“图书结构体“数组来组织存放。对于多个读者，可采用“读者结构体”数组来组织存放。对于多条借还书记录，可采用“借书情况结构体”数组来组织存放。10. 家族树（1人）一个家族可以用一棵树来表示，如：ABCDEFGHIJK其在计算机内的存储可以采用顺序存储结构，也可以采用链式存储结构，可以采用孩子兄弟法存储，也可以采用双亲表示法存储，请选择一种存储结构，对于任意输入的该家族中的一个人名，请给出该人员是这个家族的第几代人，他的双亲是谁，他的亲兄弟姐妹分别是哪些人，他的堂兄弟姐妹双是哪些，他的子女有哪些？11. 采用高

24、斯先列主元消元法求解线性方程组AX=b（1人）要求：1、输入一个线性方程组存入到二维数组中； 2、利用高斯消元法解方程组； 3、输出解得的结果。方法说明（以4阶为例）：（1）第1步消元在增广矩阵（A，b）第一列中找到绝对值最大的元素，将其所在行与第一行交换，再对（A，b）做初等行变换使原方程组转化为如下形式：，注：“*”代表非0。（2）第2步消元在增广矩阵（A，b）中的第二列中（从第二行开始）找到绝对值最大的元素，将其所在行与第二行交换，再对（A，b）做初等行变换使原方程组转化为：（3）第3步消元在增广矩阵（A，b）中的第三列中（从第三行开始）找到绝对值最大的元素，将其所在行与第二行交换，再对

25、（A，b）做初等行变换使原方程组转化为：（4）按x4 x3 x2 x1 的顺序回代求解出方程组的解。12、通信录管理系统（3人）用C/C+设计出模拟手机通信录管理系统，实现对手机中的通信录进行管理。功能要求:（1）查看功能选择此功能时，列出下列三类选择。A 办公类 B 个人类 C 商务类 ，当选中某类时，显示出此类所有数据中的姓名和电话号码）（2）增加功能能录入新数据一个结点包括：姓名、电话号码、分类（可选项有：A 办公类 B 个人类 C 商务类）、电子邮件）。例如杨春 商务类 当录入了重复的姓名和电话号码时，则提示数据录入重复并取消录入；当通信录中超过15条信息时，存

26、储空间已满，不能再录入新数据；录入的新数据能按递增的顺序自动进行条目编号。（3）拔号功能能显示出通信录中所有人的姓名，当选中某个姓名时，屏幕上模拟打字机的效果依次显示出此人的电话号码中的各个数字，并伴随相应的拔号声音。（4）修改功能选中某个人的姓名时，可对此人的相应数据进行修改（5）删除功能选中某个人的姓名时，可对此人的相应数据进行删除，并自动调整后续条目的编号。13. 优先级调度模拟（1人）A. PQ算法(Priority Queue):每个队列赋予不同的优先级,每次需要调度时,具有最高优先级的非空队列中的分组最先被服务.B. QLT算法(Queue Length Threshold)给每个

27、队列设置阈值,需要进行调度时从最高优先级开始比较队列的长度和调度阈值.当最高优先级队列的长度大于其调度阈值时,该队列头部的分组首先被服务;当最高优先级队列的长度小于调度阈值时,检查具有次优先级的其他队列.要求：调度算法的队列有5个，即有5个优先级，其初始队列长度各不相同，并在每次调度之后又有新的任务随机进入0个或多个队列。14. 轮询调度算法模拟（1人）C. RR算法(Round Robin)只是简单地对所有队列进行轮循调度,每次调度发送一个分组,使得不同队列在某种程度上”平等”地使用带宽资源.D. WRR算法给队列赋予不同的权值,代表一次完整循环队列被服务的分组数,同时设置计数器,初始化为权值.每次轮循时,计数器为非零的队列允许发送一个分组并计数器减1,直到所有计数器均为0时重置权值.要求：调度算法的队列有5个，其初始队列长度各不相同，并在每次调度之后又有新的任务随机进入0个或多个队列。15.