数据结构实系数一元多项式运算实验报告

2010级计算机科学与技术（非师范）

100704033

鲁静

2011年10月14日星期五

1、需求分析

实现实系数一元多项式的创建，打印以及两个一元多项式的加、减、乘运算。

（1）程序所能达到的功能：

a．实现一元多项式的输入；

b．实现一元多项式的输出；

c．计算两个一元多项式的和并输出结果；

d．计算两个一元多项式的差并输出结果； e．计算两个一元多项式的积并输出结果；

（2）输入的形式和输入值的范围：

输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以0 0为结束标志，结束一个多项式的输入。 输入形式：

2 3 -1 2 3 0 1 2

0 0 -2 1 -3 3 -1 -1 0 0

输入值的范围：系数为int型，指数为float型。

（3）输出的形式：

要求：第一行输出多项式1； 第二行输出多项式2；

第三行输出多项式1与多项式2相加的结果多项式； 第四行输出多项式1与多项式2相减的结果多项式； 第五行输出多项式1与多项式2相乘的结果多项式 注： 多项式的每一项形如：2.0x^3,注意指数应保留一位小数；

多项式按照升幂次序排列；

系数为1的非零次项应略去系数，系数为0的项不能出现在结果中；

指数为0的项应只输出系数；

多项式的第一项系数符号为正时，不要输出“+”，其他项要输出“+”，“-”符号。 输出形式：

3.0+2.0x^3 -x^-1-2.0x-3.0x^3

-x^-1+3.0-2.0x-x^3 x^-1+3.0+2.0x+5.0x^3

-3.0x^-1-6.0x-2.0x^2-9.0x^3-4.0x^4-6.0x^6

2、概要设计

抽象数据类型一元多项式的定义如下：

ADT Polynomial{

数据对象：D={ai| ai ∈TermSet,i=1,2,„,m,m≥0

TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数}

数据关系：R1={< ai-1,ai >| ai-1 , ai ∈D,且ai-1 中的指数值＜ai 中的

指数值，i=2,„,n}

基本操作：sort(Polyn & h); //对多项式进行排序

print(Polyn h); //输出多项式

delZeroCoef(Polyn & h); //判断系数为零的情况 merge(Polyn & h); //合并指数相同的项 createList(); //创建多项式

addPoly(Polyn h1,Polyn h2); //多项式相加 subPoly(Polyn h1,Polyn h2); //多项式相减 multPoly(Polyn h1,Polyn h2); //多项式相乘 } ADT Polynomial

多项式的抽象数据类型的定义：

typedef struct Polynomial //结点类型 {

float coef; //系数 int exp; //指数 struct Polynomial * next; }PolyNode,*Polyn;

主程序的

开始 流程图：

输入两个多项式h1,h2 判断h1,h2系数是否为0 调用print()函数，输出，合并过并排好序的h1,h2 调用addPoly(h1,h2)，合并并输出 调用subPoly(h1,h2),合并并输出 调用multPoly(h1,h2),合并并输出

结束

3、详细设计

伪码算法：

主函数：

int main() {

Polyn h1=createList();//创建多项式1 Polyn h2=createList();//创建多项式2 print(h1); //输出多项式1 print(h2); //输出多项式2

addPoly(h1,h2); //实现多项式1和2的相加，并输出 subPoly(h1,h2); //实现多项式1和2的相减，并输出 multPoly(h1,h2); //实现多项式1和2的相乘，并输出 return 0; }

分支函数：

void sort(Polyn & h); //排序

void print(Polyn h); //输出多项式

void delZeroCoef(Polyn & h);//判断处理系数为0的情况

void merge(Polyn & h); //合并多项式 Polyn createList(); //创建多项式

void addPoly(Polyn h1,Polyn h2);//两个多项式相加并输出 void subPoly(Polyn h1,Polyn h2);//两个多项式相减并输出

void multPoly(Polyn h1,Polyn h2);//两个多项式相乘并输出

函数的调用关系：

createList merge delZeroCoef

main print addPoly subPoly multPoly merge print merge print merge print sort

4、调试分析

a．调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析:

在输入诸如“0,3”，“2,0”时，程序无法正常运行或总是出错.

解决：对指数或系数为0的情况应单独讨论。为此，建立了delZeroCoef函数来解决问题。

b．算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想:

时间复杂度和空间复杂度：

设两个多项式分别用m,n来表示，T()表示时间复杂度，O()表示空间复杂度，那么：

sort(Polyn & h)：T(m*m),T(n*n)；O(m),O(n)。 print(Polyn h)：T(m),T(n)；O(1),O(1)。 delZeroCoef(Polyn & h)：T(m),T(n)；O(1),O(1)。 merge(Polyn & h)：T(m*m),T(n*n)；O(1),O(1)。 createList()：T(m),T(n)；O(1),O(1)。

addPoly(Polyn h1,Polyn h2)：T(m),T(n)；O(1),O(1)。 subPoly(Polyn h1,Polyn h2)：T(m),T(n)；O(1),O(1)。 multPoly(Polyn h1,Polyn h2)：T(m),T(n)；O(1),O(1)。

改进设想：

可以在原来的基础上改进程序，或者设计一些新的算法，尽量减小时间复杂度和空间复杂度。

c．经验和体会:

1.这次用链表来解决问题让我的收获很大，对链表的构建更加熟练，对链表的向前推进把握的更加准确，在调试代码，检验的时候，曾遇到很大的阻碍，但解决问题后，自己也收获了很多。

2.通过本次实验，我发现自己分析问题不是很全面，容易

忽略一些细节，以后分析问题时要仔细考虑认真分析，避免细节上的错误。

3.在设计该算法时，由于过于依赖书本上的例子，导致很多不必要的麻烦，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。

5、测试数据与测试结果

第一组数据：

输入：

2 4 3 2 1 5 2 3 0 0 5 3 2 3 6 5 3 6 7 4 4 8 0 0

输出：

3.0x^2+2.0x^3+2.0x^4+x^5

7.0x^3+7.0x^4+6.0x^5+3.0x^6+4.0x^8

3.0x^2+9.0x^3+9.0x^4+7.0x^5+3.0x^6+4.0x^8 3.0x^2-5.0x^3-5.0x^4-5.0x^5-3.0x^6-4.0x^8

21.0x^5+35.0x^6+46.0x^7+42.0x^8+25.0x^9+24.0x^10+11.0x^11+8.0x^12+4.0x^13

Press any key to continue

第二组数据：

输入：

4 6 0 4 3 3 5 2 4 1 0 0 2 0 3 5 3 6 4 7 0 0

输出：

4.0x+5.0x^2+3.0x^3+4.0x^6 2.0+3.0x^5+3.0x^6+4.0x^7

2.0+4.0x+5.0x^2+3.0x^3+3.0x^5+7.0x^6+4.0x^7 -2.0+4.0x+5.0x^2+3.0x^3-3.0x^5+x^6-4.0x^7

8.0x+10.0x^2+6.0x^3+20.0x^6+27.0x^7+40.0x^8+29.0x^9+12.0x^10+12.0x^11+12.0x^12+16.0x^13

Press any key to continue

第三组数据：

输入：

-2 1 2 -3 3 0 9 5 7 -4 0 0 -6 5 0 8 5 -6 -3 4 9 0 0 0

输出：

7.0x^-4+2.0x^-3+3.0-2.0x+9.0x^5 5.0x^-6+9.0-3.0x^4-6.0x^5

5.0x^-6+7.0x^-4+2.0x^-3+12.0-2.0x-3.0x^4+3.0x^5 -5.0x^-6+7.0x^-4+2.0x^-3-6.0-2.0x+3.0x^4+15.0x^5

35.0x^-10+10.0x^-9+15.0x^-6-10.0x^-5+63.0x^-4+18.0x^-3+45.0x^-1+6.0-6

6.0x-12.0x^2-9.0x^4+69.0x^5+12.0x^6-27.0x^9-.0x^10 Press any key to continue

第四组数据：

输入：

3 -9 -7 8 -2 -4 7 8 0 3 -1 0 0 0 2 -3 -4 3 1 0 0 -5 0 0

输出：

3.0x^-9-2.0x^-4-1.0 2.0x^-3+1.0-4.0x^3

3.0x^-9-2.0x^-4+2.0x^-3-4.0x^3

3.0x^-9-2.0x^-4-2.0x^-3-2.0+4.0x^3

6.0x^-12+3.0x^-9-4.0x^-7-12.0x^-6-2.0x^-4-2.0x^-3+8.0x^-1-1.0+4.0x^3 Press any key to continue

第五组数据：

输入：

1 -1 -1 1 0 0 1 -1 -1 -1 0 0

输出：

x^-1-x 0

x^-1-x x^-1-x

0

Press any key to continue