10.1.2  一元多项式运算
 一．问题描述
 设计一个简单的一元稀疏多项式加法运算器。
 二．基本要求
 一元稀疏多项式简单计算器的基本功能包括：
 1．按照指数升序次序，输入并建立多项式A与B。
 2．计算多项式A与B的和，即建立多项式A+B。
 3．按照指数升序次序，输出多项式A、B、A+B。
 三．提示与分析
 1．一元n次多项式：P(x,n)=P0+P1X1+P2X2+…+PnXn，其每一个子项都是由“系数”和“指数”两部分来组成的，因此可以将它抽象成一个由“系数、指数对”构成的线性表，其中，多项式的每一项都对应于线性表中的一个数据元素。由于对多项式中系数为0的子项可以不记录它的指数值，对于这样的情况就不再付出存储空间来存放它了；基于此，可以采用一个带有头结点的单链表来表示一个一元多项式。
 2．数据类型定义可描述如下：

 3．基本功能分析
 （1）输入多项式，建立多项式链表
 首先创建带头结点的单链表；然后按照指数递增的顺序和一定的输入格式输入各个系数不为0的子项：“系数、指数对”，每输入一个

子项就建立一个结点，并将其插入到多项式链表的表尾，如此重复，直至遇到输入结束标志的时候停止，最后生成按指数递增有序的链表。
 （2）多项式相加
 多项式加法规则：对于两个多项式中指数相同的子项，其系数相加，若系数的和非零，则构成“和多项式”中的一项；对于指数不同

的项，直接构成“和多项式”中的一项。
 将（1）中单链表表示的两个多项式A和B相加，运算的结果是利用原表空间生成一个新链表，表示和多项式C。运算规则如下：
 设指针pa、pb分别指向多项式链表A、B的第一个结点，比较pa、pb所指两结点中的指数项：
 ① 若pa->exp < pb->exp，则将pa所指结点插入到“和多项式”链表中去；
 ② 若pa->exp > pb->exp，则将pb所指结点插入到“和多项式”链表中去；
 ③ 若pa->exp== pb->exp，则计算系数和pa->coef＋pb->coef，若和非零，插入到“和多项式”链表中去，删除pb所指结点；否则删

除pa、pb所指结点。
 继续比较下一项，重复上述过程，直至A、B中某一链表结束，此时将非空链表中剩余的结点出入到“和多项式”链表即可。
 （3）多项式的输出
 可以在文本界面下，采用类似于数学表达式的方式输出多项式，如多项式A可显示为：
 A=3+6X32X8+12X20
 需要注意：
 系数值为1的非零次项的输出形式中略去系数1，如子项1x8的输出形式为x8，项－1x3的输出形式为－x3。
 多项式的第一项的系数符号为正时，不输出“+”，其它项要输出“+”、“”符号。
 四．测试数据
 1．(x+3x6－8.6x11)+(6－3x6+21x9)=6+x+21x9－8.6x11
 2．(3x－3－x+4.1x2－1.2x9)＋(―3x―3－5.1x2 +7.8x12)=－x－x2－1.2x9+7.8x12
 3．(x+x3)+(―x―x3)=0
 4．(x+x100)+(x100+x200)=(x+2x100+x200)
 5．(x+x2+x3)+0=x+x2+x3
 五．选作内容
 1．计算多项式A与B的差，即建立多项式A－B；
 2．计算多项式A的导函数Aˊ。
 3．计算多项式A与B的积，即建立多项式A×B；
 4．输入多项式时可以按任意次序输入各项的数据，不必按指数有序；在算法中实现建立按指数有序的多项式。
 5．多项式的输出形式采用图形界面，通过调整指数应该出现的坐标位置来表示指数形式，如X+2X2-3X100的形式。

实验三：教学计划编排
一、需求分析
1．程序的功能：
大学中的每个专业都有几十门基础课程，专业课程以及选修课程，学生必须分几个学期完成这些课程才能毕业。教学计划的制定要求合理的编排这些课程，使学生能够顺利的进行学习。（这些课程中，有的是独立于其他课程的基础课，有些却需要其他先行课程。一般4年制本科教学前七个学期进行理论课程的学习，第八个学期实习。必须充分考虑这些因素。）
输入课程的信息，按照顺序排出四学年7个学期中每个学期要修的课程。
2．输入输出的要求:
教学计划的输出：可以将教学计划输出到用户制定的文件中，也可以制定合适的表格显示在屏幕上。
基本要求：各学期课程门数，学分的分布较均匀。
输入课程的信息（序号，名称，学分，先修课程），输出每个学期所要修习科目的课序号。

实验四：哈夫曼编码
一、需求分析
1．程序的功能；
1）初始化：从键盘接收字符集大小n，以及n个字符。
2）建立哈夫曼树：构造哈夫曼树，即将Hnode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存放于文件Htree.txt中。
3）构造哈夫曼编码：先从文件Htree.txt中读入相关的字符信息进行哈夫曼编码，然后将结果存入Hnode.txt中，同时将字符与0，1代码串的一一对应关系打印到屏幕上。
4）编码：利用已构造的哈夫曼编码（Hnode.txt）对文件SourceFile.txt(明文)中的正文进行编码，然后将结果存入文件CodeFile.txt(密文)中。
5）译码：将文件CodeFile.txt(密文)中的代码按照3）中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，进行译码，结果存入文件TextFile.txt(明文)中。（如果正确，TextFile.txt的内容与SourceFile.txt的内容一致。）
6）打印哈夫曼树：从Hnode数组中读入相关的结点信息，一凹入表方式将各个结点及叶子结点的权值和左分支上的0和右分支上的1画出来。
2．输入输出的要求:
从键盘输入字符集大小n，以及n个字符；电文内容由键盘输入，明文，译码，及编码都要保存（即输出）到相应文件中。
3．测试数据。
1）令叶子结点个数N为4，权值集合为{1，3，5，7}，字符集合为{A,B,C,D},且字符集与权值集合一一对应。
2）令叶子结点个数N为7，权值集合为{12，6，8，18，3，20，2}，字符集合为{A,B,C,D,E,F,G},且字符集与权值集合一一对应。
3）自行选定一段英文文本，统计给出的字符集，实际统计字符的频率，建立哈夫曼树，构造哈夫曼编码，并实现其编码和译码

试验五：简单个人图书管理系统

程序的功能
基本要求：保存图书的各种相关信息：出版日期，书号，书名，作者，图书类别编号，价格等。
查找功能：按照多种关键码查找需要的书籍，查找成功后可以修改记录的相关项。
排序功能：按照多种关键码对所有的书籍进行排序，例如按购买日期排序，按图书类别排序等。
显示图书信息。
其他辅助的维护工作。
基本功能：
1）初始化：清空books数组；进入输入状态，接收键盘输入的全部数据，并保存在books数组中，按某种顺序输入记录。
插入：接收从键盘输入的一条新纪录，按某种顺序（如作者，出版日期等）插入到books数组中。
删除：接收从键盘输入的一本书的信息（如书名，书号，作者等），在books数组中查找，如找到则从books数组中删除该记录，否则显示未找到。
更新：接收从键盘输入的一本书的信息，在books数组中查找，如找到则显示该记录的原始数据，并提示键盘输入新数据以替换原有数据，如未找到则显示“未找到”。
统计：统计每类书籍的数量，显示统计结果。
排序：对books数组中所有记录按“类别”排序，类别相同的按“书名”排序（字典序），显示排序结果。
测试数据：读者根据实际情况自行制定。
概要设计
1．本程序所用的抽象数据类型的定义；

2．主模块的流程及各子模块的主要功能；
3．模块之间的层次关系。