通信工程11级C语言课程设计任务书及报告书格式
注意事项：
1、每个同学只选择其中一题作为课程设计题目，独立完成该题的全部设计内容（每个题的选题人数不能超过10人）；
2、一旦选定之后不再更改；
3、每个题目前面“*”的个数是题目的难易程度和工作量的大小综合考虑。“*”的数量代表了不同题目的计算系数。其中“***”的计算系数为1，“****”的计算系数为1.1，“*****”计算系数为1.15，“******”计算系数为1.2。“**”的计算系数为0.9，“*”的计算系数为“0.85”。
4、课程设计的成绩由答辩成绩、报告成绩两部分组成，各占50%。学生的成绩按以下公式进行计算：总成绩=答辩成绩*计算系数+报告成绩
如果某同学计算出来的成绩超过100分时，按100分计。
如果某同学在答辩成绩、报告成绩都及格的情况下，计算出来的总成绩不及格，按60分计。
如果某同学答辩成绩、答辩成绩*计算系数都不及格时，学生成绩不及格。
5、书写报告时，1班的指导教师:李益才，2班指导教师：谭晋，3班指导教师：黄大荣。
6、时间及地点安排
辅导时间：17周星期一、星期五下午，18周星期二下午，18周星期四上午。
地点：计算机和语音大楼406和407
答辩检查时间：18周星期四上午8：00起（部分提前做好的也可以在星期二答辩）。
***1. Huffman编解码
要求: a. 随机输入一段英文(含标点、空格以及大小写的区分，标点仅限逗号“，”和句点“.”)；
b. 统计各种符号出现的频度；
c. 进行Huffman编码（以二进制01代码输出）；
d. 以上一步的输出（二进制序列）作为输入进行解码，恢复原英文；
e. 比较输入和输出，统计出错的个数。
前缀码、Huffman编码算法：
前缀码：给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。
哈夫曼（Huffman）算法可用来设计前缀编码，用该算法构造一棵有n个叶子（每个叶子具有一个权值）的二叉树的过程如下：
（1）根据n个权值{w1，w2，…，wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。
（2）在F中选取两棵根结点的权值最小的树作为左右子树来构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树结点的根结点的权值之和。
（3）在F中删除这两棵树，同时将新得到的二叉树加入F中。
（4）重复（2）和（3），直到F中只含一棵树时为止。称这棵树为最优二叉树（或哈夫曼树）。
如果约定将每个结点的左分支表示字符“0”，右分支表示字符“1”，则可以把从根结点到某叶子结点的路径上分支字符组成的字符串作为该叶子结点的编码。
对于所有可能传输的字符，令每个字符对应一个叶结点，权值为其出现的频率，那么根据哈夫曼算法构造出二叉树后，就得到了每个字符的二进制编码。
根据构造过程可知，这种编码方案得到的字符的编码长度的数学期望值为最小，因此这种编码方案是一个最优前缀码。在构造过程中，每次都是选取两棵最小权值的二叉树进行合并。
****2. 简易计算器设计
要求：
a. 用户输入一表达式，表达式为四则运算表达式（只含加、减、乘、除以及括号）；
b. 判断用户输入的表达式正确与否，如错则报错，否则进行表达式值的计算并给出结果；
c. 数据可以是任意实数。
表达式求值的过程：
表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子。这里介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。
要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如，要对下面的算术表达式求值：
4 + 2 × 3 - 10/5
首先要了解算术四则运算的规则。即：
（1）先乘除，后加减； （2）从左算到右； （3）先括号内，后括号外。
由此，这个算术表达式的计算顺序应为
4 + 2 × 3 - 10/5 = 4 + 6 - 10/5 = 10 - 10/5 = 10 - 2 = 8
算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。
任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的，我们称它们为单词。一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符3类；基本界限符有左右括号和表达式结束符等。为了叙述的简洁，我们仅讨论简单算术表达式的求值问题。这种表达式只含加、减、乘、除4种运算符。读者不难将它推广到更一般的表达式上。
我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述3条运算规则，在运算的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系至多是下面3种关系之一:
θ1<θ2 θ1的优先权低于θ2
θ1=θ2 θ1的优先权等于θ2
θ1>θ2 θ1的优先权高于θ2
表1定义了算符之间的这种优先关系。
表1 算符间的优先关系
由规则（3），+、-、*和/为θ1时的优先性均低“（”但高于“）”，由规则（2），当θ1=θ2时，令θ1>θ2，“#”是表达式的结束符。为了算法简洁，在表达式的最左边也虚设一个“#”构成整个表达式的一对括号。表中的“（”=“）”表示当左右括号相遇时，括号内的运算已经完成。同理，“#”=“#”表示整个表达式求值完毕。“）”与“（”、“#”与“）”以及“（”与“#”之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误。在下面的讨论中，我们暂假定所输入的表达式不会出现语法错误。
为实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想的：
（1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；
（2）依次读入表达式中每个字符，若是操作数则进 OPND 栈，若是运算符则和 OPTR 栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即 OPTR 栈的栈顶元素和当前读入的字符均为“#”）。
以下算法描述了这个求值过程。
OperandType EvaluateExpression(){
// 算术表达式求值的算符优先算法。设 OPTR 和 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 '<': // 栈顶元素优先权低
Push(OPTR,c); c = getchar();
break;
case '=': // 脱括号并接收下一字符
Pop(OPTR,x); c = getchar();
break;
case '>': // 退栈并将运算结果入栈
Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
}// switch
}// while
return GetTop(OPND);
}// EvaluateExpression
算法中还调用了两个函数。其中Precede是判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间优先关系的函数；Operate为进行二元运算 aθb的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算的结果。
*****3. 五子棋游戏
要求：
a. 棋盘为19*19，按五子棋的游戏规则进行；
b. 对奕双方是用户和电脑；
c. 考虑到界面问题，棋盘界面及用户的输入可采用如下输入方式：
a 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
要求：
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. 由计算机随机出四张牌。
c. 用户输入能算出24的表达式（只能用加、减、乘、除及括号组成的四则运算）。
d. 计算机检验用户给出的表达式正确与否（包括是否用计算机所给出的四张牌），并根据该表达式计算出值，判断用户的方法是否正确。
e. 表达式求值算法参考2题
***5. 乘法器、除法器
要求：乘法器
a. 乘数与被乘数的位数是不少于35位的无符号整数；
b. 输入乘数和被乘数，计算出精确的结果值。
除法器：
a、被除数的位数不少于50，除数的位数不多于50位；
b、算出的结果①为商和余数②商，保留到小数点后50位。
***6．用单链表实现一元高次多项式的加法、乘法和除法
****7. 稀疏矩阵
要求：
1、包括稀疏矩阵的压缩与还原
输入一个稀疏矩阵，用常规的方式存放，然后将其压缩成三元组表的形式；
输入一个稀疏矩阵，用三元组表的方式存放，然后将其还原成常规方式
2、稀疏矩阵的转置
输入一个稀疏矩阵，以三元组表的方式存放，将其进行转置操作之后输出；
3、两个稀疏矩阵的乘法
输入两个可以相乘的稀疏矩阵，均以三元组表的方式存放，将它们的乘积输出。
注 意：假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元顺序表。
#define maxsize 10000
typedef int datatype;
typedef struct{
int i,j;
datatype v;
}triple;
typedef struct{
triple data[maxsize];
int m,n,t;
}tripletable;
图1
设A为tripletable型的结构变量，图1所示的稀疏矩阵的三元组的表示如下：
i j v
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。
一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n，即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的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。
按这种方法设计的算法，其基本思想是：对A中的每一列 col(0≦col≦n-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的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。
为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。
为此，需要设置两个一维数组num[0..n]和cpot[0..n]
num[0..n]：统计M中每列非零元素的个数，num[col]的值可以由A的第二列求得。
cpot[0..n]：由递推关系得出M中的每列第一个非零元素在B中的位置。
算法通过cpot数组建立位置对应关系：
cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1]
2<=cpl<=a.n
例如：前面所给出的矩阵M和相应的三元组A可以求得num[col]和 cpot[col]的值如下：
col 1 2 3 4 5 6 7
num[col] 2 2 2 1 0 1 0
cpot[col] 1 3 5 7 8 8 9
带行表的三元组
有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下：
#define maxrow 100
typedef struct{
triple data[maxsize];
int rpos[maxrow];
int n,m,t;
}rtripletable
稀疏矩阵相乘的基本思想是：对于M中每个元素M，找到N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。
***9.学生成绩管理系统
分别用指针、链表、文件三种方式编程实现学生信息的简单管理。要求用函数实现以下各功能并在主函数中进行调用。
1、存储10个以上学生的基本数据（包括学号、姓名、性别和5门课的成绩）
2、输出全部学生信息（按指定课程成绩降序排列，按平均成绩降序排列）
3、查找指定学生的信息
4、修改指定学生的信息
5、删除指定学生的信息
6、在指定的学生前或后再插入一个学生的信息。
7、统计指定课程不及格的人数。
**10. 家族树
一个家族可以用一棵树来表示，如：
其在计算机内的存储可以采用顺序存储结构，也可以采用链式存储结构，可以采用孩子兄弟法存储，也可以采用双亲表示法存储，请选择一种存储结构，对于任意输入的该家族中的一个人名，请给出该人员是这个家族的第几代人，他的双亲是谁，他的亲兄弟姐妹分别是哪些人，他的堂兄弟姐妹双是哪些，他的子女有哪些？
*11. 采用高斯先列主元消元法求解线性方程组AX=b
要求：1、输入一个线性方程组存入到二维数组中；
2、利用高斯消元法解方程组；
3、输出解得的结果。
方法说明（以4阶为例）：
（1）第1步消元——在增广矩阵（A，b）第一列中找到绝对值最大的元素，将其所在行与第一行交换，再对（A，b）做初等行变换使原方程组转化为如下形式：
，注：“*”代表非0。
（2）第2步消元——在增广矩阵（A，b）中的第二列中（从第二行开始）找到绝对值最大的元素，将其所在行与第二行交换，再对（A，b）做初等行变换使原方程组转化为：
（3）第3步消元——在增广矩阵（A，b）中的第三列中（从第三行开始）找到绝对值最大的元素，将其所在行与第二行交换，再对（A，b）做初等行变换使原方程组转化为：
（4）按x4 à x3à x2à x1 的顺序回代求解出方程组的解。
***12. 图书管理系统
分别用指针、链表、文件三种方式编程实现图书信息的简单管理。要求用函数实现以下各功能并在主函数中进行调用。
1、存储10本以上图书的基本数据（包括图书编号、图书名称、图书单价、数量、出版社）
2、按要求输出图书信息（按图书价格降序排列，按书名首字母升序排列）
3、查找指定图书的信息
4、修改指定图书的信息
5、删除指定图书的信息
6、在指定的图书前或后再插入一个图书的信息
7、统计指定出版社的图书数量
***13．工资管理系统
分别用指针、链表、文件三种方式编程实现工资信息的简单管理。要求用函数实现以下各功能并在主函数中进行调用。
1、存储10个以上员工工资的基本数据（包括员工编号、姓名、应发工资、实发工资、岗位津贴、工龄工资、代扣税、公积金）
2、按要求输出员工工资信息（按应发工资降序排列，按工龄工资升序排列）
3、查找指定员工的工资信息
4、修改指定员工的工资信息
5、删除指定员工的工资信息
6、在指定的员工前或后再插入一个员工的工资信息
7、统计实发工资大于2000的人数
***14．仓库管理系统
分别用指针、链表、文件三种方式编程实现仓库信息的简单管理。要求用函数实现以下各功能并在主函数中进行调用。
1、存储10个以上物品的基本数据（包括物品货号、名称、单价、库存数量、品牌）
2、按要求输出物品信息（按物品价格降序排列，按库存数量升序排列）
3、查找指定物品的信息
4、修改指定物品的信息
5、删除指定物品的信息
6、在指定的物品前或后再插入一个物品的信息
7、统计指定品牌的物品数量
***15．药房管理系统
（如药品按编号分类，库存情况，销售情况，药品保质期等）
分别用指针、链表、文件三种方式编程实 现药品信息的简单管理。要求用函数实现以下各功能并在主函数中进行调用。
1、存储10个以上药品的基本数据（包括药品编号、名称、单价、库存数量、药品保质期、品牌）
2、按要求输出药品信息（按药品价格降序排列，按药品保质期升序排列）
3、查找指定药品的信息
4、修改指定药品的信息
5、删除指定药品的信息
6、在指定的药品前或后再插入一个物品的信息
7、统计指定品牌的药品数量
****16、读入一个C语言源程序（XXXX.cpp），统计其中的用户自定义标识符号的个数，并列出用户自定义的标识符号。
******17、读入一个C语言源程序（XXXX.cpp），对其中的所有符号进行分割，即分割出其中的标识符号、数据、各种符号等。（其中数据识别一个人，数据包括整数，浮点数，科学计数法的数据，各种进制数据）
**18、表达式的表示有三种形式：前缀表达式、中缀表达式和后缀表达式，输入表达式的一种形式，输出其另处两种形式。
*19、矩阵中填数，当给出n*n的矩阵，要求用程序填入下列形式的数（用数组、指针两种方法完成）
（此处为n=5的形式，n也可以为其它的值）
（后面为课程设计报告书格式）
重庆交通大学信息科学与工程学院
课程设计报告
班 级：
姓名 （学号）：
实验项目名称：
实验室(中心)：信息科学与工程学院信息技术实验室
指 导 教 师 ：
实验完成时间： 20## 年 6 月 28 日
一、题目（课程设计题目，正式报告中，括号中的字应删除）
二、功能描述（对系统要实现的功能进行描述，正式报告中，括号中的字应删除）
三、概要设计（根据功能描述，建立系统的体系结构，即将整个系统分解成若干子功能模块，并用框图表示各功能模块之间的衔接关系，并简要说明各模块的功能。，正式报告中，括号中的字应删除）
四、详细设计（详细说明各功能模块的实现过程，包括用流程图对算法进行描述，所用到的数据结构等，正式报告中，括号中的字应删除）
五、测试结果及存在的问题（说明系统的运行效果（附上运行界面图片）、存在哪些不足以及预期的解决办法，正式报告中，括号中的字应删除）
六、课程设计心得体会（谈谈自己在课程设计过程中的心得体会，正式报告中，括号中的字应删除）
七、附录（附上本文完成的代码，正式报告中，括号中的字应删除）