数据结构课程设计一元稀疏多项式计算器_一元稀疏多项式计算器数据结构

目录

一元稀疏多项式计算器............................... 1

一、问题分析和任务定义.............................. 1

1.1 课程目的....................................... 1

1.2 任务需求....................................... 1

二、 数据结构的选择和概要设计........................ 2

2.1一元多项式的建立................................ 2

2.2创建一个一元多项式............................... 2

2.3 多项式相加...................................... 2

2.4 多项式相减...................................... 3

三、 编码实现..................................... 4

3.1一元多项式的建立................................ 4

3.2创建一个一元多项式............................... 4

3.3打印多项式...................................... 5

3.4 多项式相加...................................... 5

3.5 多项式相减...................................... 6

四、实验结果测试结果及其分析......................... 7

4.1调试分析........................................ 7

五、参考文献..................................... 10

完整资料私信我：

 

一元稀疏多项式计算器

一、问题分析和任务定义

1.1 课程目的

设计一个一元稀疏多项式简单计算器。

1.2 任务需求

基本要求：

(1) 输入并建立多项式 ；

(2) 输出多项式，输出形式为整数序列：n，cl，el，c2，e2，…，cn，en，其中n是多项式的项数，ci 和ei，分别是第 i 项的系数和指数，序列按指数降序排列；

(3) 多项式a和b相加，建立多项式a +b；

(4) 多项式a和b相减，建立多项式a -b 。

测试数据：

(1)(2x+5x8－3.1x11) + (7－5x8+11x9)=(－3.lx11+11x9+2x+7)

(2)(6x-3－x+4.4x2－1.2x9) －(-6x-3+5.4x2－x2+7.8x15)

=(-7.8x15-1.2x9+12x-3-x)

(3)(1 +x + x2+x3+x4+x5)+(-x3－x4)=(1+x+x2+x5)

(4)(x+x3)+(-x－x3)=0

(5)(x+x100)+(x100 +x200)=(x+2x100+x200)

(6)(x+x2+x3)+0=x+x2+x3

(7) 互换上述测试数据中的前后两个多项式

• 数据结构的选择和概要设计

2.1一元多项式的建立

使用带头结点的单链表存储多项式，插入查找和删除较为方便。数据域中存 储系数和指数，指针域指向下一个节点的位置。

 

2.2创建一个一元多项式

1. 首先确定好多项式的项数m，新建立一个节点node，用来存贮读入的系    数coef和项数expn。

(2)再使用尾插法来添加多项式的每一项，如果输入的系数是0，就不存储该       项。

2.3 多项式相加

1. 建立三个多项式Pa，Pb，Pc，其中Pc用于存放前两个多项式的和。
2. 指针p1和p2初始化，分别指向Pa和Pb首节点的下一个节点，P3指向和多项式的头节点
3. 当指针p1和p2均未达到表尾时，则循环比较p1和p2所指节点对应的指

数值。

 

     （p1->expn与p2->expn），有下列三种情况:

1. 当p1->expn==p2->expn时，则将两个节点中的系数相加

    *若和不为0，则把p1与p2的系数相加，存到p3指向的节点，再把p1或p2的指数存到p3中，全部向后移动一个节点。

*若和为0，则p1和p2向后移动一个节点。

1. 当p1->expn<p2->expn时，则应摘取p2所指的节点插入到p3指向的节    点中。
2. 当p1->expn>p2->expn时，则则应摘取p1所指的节点插入到p3指向的    节点中。

1. 将非空多项式的剩余段插入到p3所指的节点。

2.4 多项式相减

多项式的相减实现起来步骤相对简单，只需要把多项式Pb中每一项的系数取反，再相加就可以了。

1. 初始化p2与node节点分别指向多项式Pb的第一项。
2. 用node节点使Pb每一项的系数取反。
3. 再调用多项式相加函数，计算结果放在Pc里。
4. 最后用p2把Pb中每一项的系数还原。

• 编码实现

3.1一元多项式的建立

结构体的定义

3.2创建一个一元多项式

3.3打印多项式

void PrintPolyn(LS *h)

{

    LS *p = h;

    int count = 1;            //设置一个变量用于控制打印符号

    while (p->next != NULL)

    {

        p = p->next;

        if (count != 1 && p->coef > 0)  //打印符号

        {

            printf("+");

        }

        if (p->expn == 0) // 如果指数为0只打印系数

        {

            printf("%g", p->coef);

        }

        else if (p->expn == 1)

        {

            printf("%gx", p->coef);

        }

        else

        {

            printf("%gx^%d", p->coef, p->expn);

        }

        count++;

    }

    printf("\n");

}

3.4 多项式相加

多项式相加的代码如下：

 

3.5 多项式相减

多项式相减代码部分：

四、实验结果测试结果及其分析

4.1调试分析

注：本次测试多项式的输入和输出都是按照指数的降序排列的。

测试数据：

(1)(2x+5x8－3.1x11) + (7－5x8+11x9)=(－3.lx11+11x9+2x+7)

(2)(6x-3－x+4.4x2－1.2x9) －(-6x-3+5.4x2－x2+7.8x15)

=(-7.8x15-1.2x9+12x-3-x)

 

1. (1 +x + x2+x3+x4+x5)+(-x3－x4)=(1+x+x2+x5)

 

 

(4)(x+x3)+(-x－x3)=0

 

1. (x+x100)+(x100 +x200)=(x+2x100+x200)

（6）(x+x2+x3)+0=x+x2+x3

 

• 参考文献

1. 严蔚敏.数据结构C语言版[M].清华大学出版社，2007.
2. 董丽薇.“数据结构”课程教学方法的改进[J].沈阳师范大学学报(自然科学版)，2012.
3. WingJM.ComputationalThinking.CommunicationsoftheACM，2006，49(3)：33-35.
4. MarkM.Meerschaert.数学建模方法与分析[M].第2版.刘来福，杨淳，黄海洋，译.北京：机械工业出版社，2005.
5. 刘昕，石乐义，元雪东.面向计算思维的数据结构课程教学改革[J].计算机教育，2013，(196)16：35-38.
6. 姚诗斌.数据库系统基础.计算机工程与应用，1981 年第8期
7. 王昆仑，李红．数据结构与算法．北京:中国铁道出版社，2006年5月
8. 范德宝，于晓聪，丁伟祥.提高数据结构课程教学效果的探讨[J].黑龙江科技信息，2007.
9. 高贤强，化希耀，陈立平.引入计算思维的《数据结构》教学改革研究[J].现代计算机：专业版，2015
10. 潘彦.算法设计与分析基础[M].北京:清华大学出版社,2007.1