哈夫曼树带权路径长度_c 哈夫曼树编码_数据结构哈夫曼树编码(8)

实验内容：

利用线性表实现一个一元多项式Polynomial

f(x) = a0 + a1x + a2x2 + a3x3 + … + anxn

要求：

1. 能够实现一元多项式的输入和输出

2. 能够进行一元多项式相加

3. 能够进行一元多项式相减

4. 能够计算一元多项式在x处的值

5. 能够计算一元多项式的导数(选作)

6. 能够进行一元多项式相乘(选作) 7. 编写测试main()函数测试线性表的正确性

2. 程序分析

由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。

两个多项式要进行多次的计算，为了保护原始的数据，方便进行以后的计算，故选择把结果存储在一个新建的链表里。

2.1本程序完成的主要功能：

1. 输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存;多项式

各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容

向屏幕输出。

2. 多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时

要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到

的结果都插入到新的链表中，形成结果多项式。

3. 多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将

指数减1即可，将每项得到的结果插入到结果多项式的链表中。

4. 多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。

2.2存储结构

单链表: 其定义的结点包括三部分：系数、指数以及下一个结点的地址

2.3关键算法分析

[内容要求]

关键算法：

1.一元多项式求和算法:

[1]初始化工作指针p和q,以及p节点前驱节点指针p_prior

[2]若p和q都不为空,则循环以下操作:

[2.1]若p->data.expdata.exp,则p_prior=p;p=p->nenx;

[2.2]否则,若p->data.exp>q->data.exp,则:

[2.2.1]将q结点加入到A链表p结点之前

[2.2.2]q指向B链表的下一个结点

[2.3]否则:p->data.coef=p->data.coef+q->data.coef;

[2.3.1]若p->data.coef为0,则删除结点p

[2.3.2]p指向下一个结点

[2.3.3]删除q结点

[2.3.4]q指向下一个结点

[3]若p为空并且q不为空,则将q结点及其后所有结点追加到A链表的最后端

[4]将B链表 制成空链表

2.一元多项式求导

[1]初始化工作指针p及p_prior

[2]若p不为空,循环以操作

[2.1]若p->data.exp=0;p_prior->next=p->next; p; p=p_prior;

[2.2]否则 p->data.coef*=p->data.exp; p->data.exp--;

3.一元多项式求在X处的值

[1]初始化工作指针p,定义会参数a

[2]若p不为空,循环以下操作

a+=p->data.coef*pow(x,p->data.exp);

p=p->next;

4.输出多项式

[1]获取头结点;

[2]循环n-1次(n为多项式的项数)

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-35162-8.html