一元稀疏多项式计算器实验(报告程序)

Data Structure.实习报告

【实习一线性表、堆栈和队列的应用】

一元稀疏多项式运算器

Xiaohui Huang

China University of Geosciences(Wuhan) , Wuhan,

Wuhan , Hubei Province , China ;

Email : hxh1994@/hxh20111003570@

1.问题描述

设计一个一元稀疏多项式简单计算器。要求为：

（1）输入并建立两个多项式；

（2）多项式a与b相加，建立和多项式c；（3）多项式a与b相减，建立和多项式d；（4）输出多项式a,b,c,d。输出格式：比如多项式a为：A(x)=c1x e1+ c2x e2+…+ c m x em，其中，c i 和e i分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e2＜…＜e m。

2.设计

◆设计思想

我们知道，一个一元多项式可表示为

A(x)=a0+a1x+a2x2+⋯+a n x n 其中，a0、a1、a2、…、a n为多项式的系数，惟一确定了这个多项式，而每一项的指数这隐藏在系数a i的序号中了。那么我们可以使用线性表(a0、a1、a2、…、a n)来表示。

设A=(a0、a1、a2、…、a n)，

B=(b0、b1、b2、…、b n)，则多项式的加法就相当于A+B=C，其中，C=(c0、c1、c2、…、c n)，其中c i=a i+b i。

◆概要设计

从设计思想我们可以得知我们这个程序的主要功能是模拟计算器的加法和减法功能。那么问题就归结于创建两个线性表，通过线性表相对应元素的相加减来模拟计算器的功能。

数据结构实习报告——一元稀疏多项式运算

器的设计

一、引言

在计算机科学领域中，数据结构是研究数据组织、存储和管理的关键概念之一。在本次实习中，我设计并实现了一个一元稀疏多项式运算器，旨在使用适当的数据结构和算法来高效地进行多项式的加法、减法和乘法运算。本报告将详细介绍该运算器的设计思路、算法实现以及性能评估。

二、设计思路

1. 多项式的表示

在设计多项式运算器时，首先需要确定多项式的表示方法。为了高效地处理稀

疏多项式，我选择使用链表作为基本数据结构。每个节点包含多项式的系数和指数，并通过指针连接在一起形成链表。这种表示方法可以有效地处理稀疏多项式，减少了不必要的空间浪费。

2. 多项式的输入和输出

为了方便用户输入和输出多项式，我设计了简单的交互界面。用户可以通过命

令行输入多项式的系数和指数，并选择进行的运算操作。运算结果将直接在命令行中输出。

三、算法实现

1. 多项式的加法

多项式的加法是指将两个多项式相加得到一个新的多项式。为了实现这个功能，我设计了一个算法如下：

- 创建两个空的链表，分别表示两个多项式。

- 逐个读取用户输入的系数和指数，并将其插入到相应的链表中。

- 对两个链表进行遍历，根据指数的大小关系进行合并操作。

- 将合并后的结果链表输出。

2. 多项式的减法

多项式的减法是指将一个多项式减去另一个多项式得到一个新的多项式。为了

实现这个功能，我设计了一个算法如下：

- 创建两个空的链表，分别表示两个多项式。

- 逐个读取用户输入的系数和指数，并将其插入到相应的链表中。

- 对第二个链表中的每个节点的系数取相反数。

课程设计报告

1.需求分析

【问题描述】

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

【基本要求】

一元稀疏多项式基本功能包括：

1)输入并建立多项式；

2)输出多项式，输出形式为整数序列：n, c1, e1, c2, e2, … , c n, e n，其中n是多项式

的项数，c i和e i分别是第i项的系数和指数，序列按指数降序排列；

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

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

【测试数据】

1)(2x+5x8-3.1x11)+(11x9-5x8+7)=(-3.1x11+11x8+2x+7)

2)(-1.2x9+6x-3+4.4x2-x)-(7.8x15+4.4x2-6x-3)=(-7.8x15-1.2x9+12x-3-x)

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

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

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

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

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

2.概要设计

ADT Polynomial{

数据对象: D={a i|a i∈TermSet, i=1,2,…,m,m≥0,TermS et中的每个元素包含一个表示系数的实数和表示指数的整数}

数据对象: R1={<a i,a i-1>|a i,a i-1∈D,且a i-1中的指数值小于ai中的指数,i=2,…,m}

基本操作：

CreatePolyn(void)

Result: 指数由大到小输入m项的系数和指数,建立一元多项式p

1．一元稀疏多项式简单的计算器（实验类型：综合型）

1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器

2）实验要求:

✧采用单链表存储结构一元稀疏多项式

✧输入并建立多项式

✧输出多项式

✧实现多项式加、减运算

3) 实现提示：以两个多项式相加为例

✧结果多项式另存

✧扫描两个相加多项式，若都未检测完：

⏹若当前被检测项指数相等，系数相加，若结果未变成0，

则将结果插入到结果多项式。

⏹若当前被检测项指数不等，则将指数较小者插入到结果

多项式。

若有一个多项式已检测完，则将另一个多项式剩余部分直接连接到结果多项式。

4.一元稀疏多项式简单的计算器（实验类型：综合型）

#include

#include

typedef struct

{

float coef;//系数int expn;//指数

} Term;

typedef struct ploynomial

{

Term term;ploynomial* next;

} ploynomial,*LinkList;

void InitList(LinkList&L)

{

//初始化链表

L= (ploynomial*)malloc(sizeof(ploynomial));//头结点L->term.coef=0.0;

L->term.expn=-1; L->next=NULL;

}

int cmp(Term a,Term b)

{

//比较结点的系数大小函数

if(a.expn>b.expn) return -1;

else if(a.expn==b.expn) return 0; else return 1;

2016-2017学年第二学期学号1608220203 《网络工程》

课程设计报告

题目:一元稀疏多项式计算器

专业:网络工程

班级:网络工程(3)班

姓名:代应豪

指导教师:代美丽

成绩:

[键入文字] [键入文字] [键入文字]

一、问题描述 (3)

二、需求分析 (3)

三、概要设计 (4)

四、详细设计 (5)

五、源代码 (6)

六、程序测试 (19)

七、使用说明 (25)

八、课设总结 (26)

一、问题描述

1.1基本要求

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

(2)输出多项式,输出形式为整数序列:n,c1,e1, c2,e2,,,,,,, cn,en,其中n 是多项式的项数,ci,ei,分别是第i项的系数和指数,序列按指数降序排序;

(3)多项式a和b相加,建立多项式a+b;

(4)多项式a和b相减,建立多项式a-b;

(5)计算多项式在x处的值。

(6)计算器的仿真界面。

1.2设计目的

数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节,对于学生基本程序设计素养的培养和软件工作者工作作风的训练,将起到显著的促进作用

二、需求分析

2.1设计开发环境:

软件方面:系统windows 7编程软件:VC++ 6.0

2.2思路分析:

①一般情况下的一元n次多项式可写成

pn(x)=p1xe1+p2xe2+……+pmxem

其中,p1是指数为ei的项的非零系数,且满足0≦e1<e2<……<em=n ,若用一

个长度为m且每个元素有两个数据项(系数项和指数项)的线性表

数据结构实习报告——一元稀疏多项式运算

器的设计

一、引言

在计算机科学中，数据结构是一种组织和存储数据的方式，它能够高效地操作

和访问数据。在本次实习中，我设计了一个一元稀疏多项式运算器，通过合理选择数据结构来实现多项式的存储和运算，以提高运算效率和减少存储空间的占用。本报告将详细介绍我设计的一元稀疏多项式运算器的实现过程和相关数据结构的选择。

二、问题描述

在数学中，一元稀疏多项式是指只有一个变量，并且大多数系数为0的多项式。我们需要设计一个一元稀疏多项式运算器，实现多项式的加法、减法和乘法运算。三、设计思路

为了实现一元稀疏多项式的高效存储和运算，我选择了链表作为主要的数据结构，并使用链表节点存储多项式的系数和指数。链表的优势在于可以动态地分配内存空间，适应多项式长度的变化。

具体而言，我设计了一个多项式类，其中包含了链表的头指针和尾指针，用于

指向链表的首尾节点。每个链表节点包含了一个系数和一个指数，通过指针连接形成链表结构。这样，我们可以通过遍历链表来实现多项式的存储和运算。

四、数据结构设计

1. 多项式类（Polynomial）

- 成员变量：

- head：链表的头指针，指向链表的首节点

- tail：链表的尾指针，指向链表的尾节点

- 成员函数：

- 构造函数：初始化头指针和尾指针为空

- 析构函数：释放链表的内存空间

- 插入节点函数：将节点按照指数的大小顺序插入链表中 - 加法运算函数：实现多项式的加法运算

- 减法运算函数：实现多项式的减法运算

- 乘法运算函数：实现多项式的乘法运算

- 打印函数：输出多项式的表达式

一元稀疏多项式计算器实习报告[1]实习报告

题目：设计一个一元稀疏多项式计算器

班级: 姓名学号_________完成日期：__

一、课程题目

一元稀疏多项式计算器

二、需求分析

1、一元稀疏多项式简单计算器的功能是：

1.1 输入并建立多项式；

1.2 输出多项式，输出形式为整数序列：n ，c1,e1,c2,e2, ………cn,en,

其中n 是多项式的项数，ci 和ei 分别是第i 项的系数和指数，序列按指数降序排列；

1.3 求多项式a 、b 的导函数；

1.4 计算多项式在x 处的值；

1.5多项式a 和b 相加，建立多项式a+b；

1.6 多项式a 和b 相减，建立多项式a-b 。

2、设计思路:

2.1 定义线性表的动态分配顺序存储结构；

2.2 建立多项式存储结构，定义指针*next

2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构

造的一元多项式

3、测试数据：

（1）、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);

（2）、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15

)=(-7.8x^15-1.2x^9+12x^-3-x);

（3）、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);

（4）、(x+x^3)+(-x-x^3)=0;

（5）、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);

实习1、一元稀疏多项式计算器

一、需求分析

1. 问题描述

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

2. 基本要求

一元稀疏多项式简单计算器的基本功能是：

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

(2)输出多项式，输出形式为整数序列：n, c1, e1, c2, e2, ········,c n, e n ，其中n是多项式的项数，c i,e i分别是第i项的系数和指数，序列按指数降序排列。

(3)多项式a和b想加，建立多项式a+b 。

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

3. 测试数据

(1) (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+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) 互换测试数据的前后两个多项式。

4. 实现提示

用带表头结点的单链表存储多项式。

二、概要设计

为实现上述程序功能，应用带头结点的单链表存储多项式。为此需要一个抽象数据类型：一元多项式。

1.抽象数据类型一元多项式定义为：

ATD Ploynomial{

数据对象：D={ai|ai∈Termset, i=1,2,3···，m,m≥0 Termset中的每个元素包含一个表示系数的实数和表示指数的整数}

一元稀疏多项式计算器实验报告

级班年月日学号_

1．实验题目

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

2．需求分析

本程序用VC编写，实现一元浮点系数，整数指数稀疏多项式的创建、两个一元多项式相加、两个一元多项式相减、输出一元多项式。

①输入的形式和输入值的围：

A.输入指定的数字，以此选择两个多项式的运算方式，运算方式有两个一元多项式相加、两个一元多项式相减。

B.创建多项式时，需要输入此多项式，每一项的系数和指数。

②输出的形式：每次输入一个完整的多项式后、每次得出多项式运算结果时，会以指定的方式输出多项式。

③程序所能达到的功能：实现一元稀疏多项式的创建、两个一元多项式相加、两个一元多项式相减、输出一元多项式。

④测试数据：

输入数据：

A.出现选择两个多项式的运算方式菜单时，输入1（即使两个多项式相加）；

B.首先输入多项式p的每一项系数和指数，当输入的指数为-5000时，表示该多项式输入完毕，输入的数据依次为：3，3，0，-5000；

C．其次输入多项式q的每一项系数和指数，输入数据依次为：2，2，0，-5000。

输出结果：

多项式q+p的结果为：

多项式为：

3x3+2x2

3．概要设计

1)为了实现上述程序功能，需要定义多项式结点的抽象数据类型：

class Term

{

数据对象：

float coef; 该数据对象为多项式一项中的系数。

int exp; 该数据对象为多项式一项中的指数。

Term* link; 该数据对象为指向下一个多项式结点的指针。

基本操作：

A. Term (float c, int e)

初始条件：无

元稀疏多项式计算器实验报告c编写,附源代

码(1)

实验报告：元稀疏多项式计算器

引言：本次实验是运用C语言编写一个元稀疏多项式计算器，该计算器可以实现多项式的加法、减法、乘法、求导、积分、求值等操作。本次实验旨在通过编写实践，加深对多项式计算的理解和程序设计能力。

一、设计思路及实现方法

1.1 多项式的表示方式

多项式可以用数组来表示，数组的下标表示多项式的幂次，数组的内容表示该幂次项的系数。

例如多项式：2x^4 + 3x^2 + 5可以表示为数组：{0,0,3,0,2,5}。

1.2 多项式的操作函数及实现方法

本次实验实现了以下多项式操作函数：

1）add（多项式加法）：将两个多项式相加并返回结果多项式。

2）subtract（多项式减法）：将两个多项式相减并返回结果多项式。

3）multiply（多项式乘法）：将两个多项式相乘并返回结果多项式。

4）differential（求导）：求一个多项式的导数并返回结果多项式。5）integral（积分）：对一个多项式进行积分并返回结果多项式。

6）evaluate（求值）：给定一个值，计算多项式在该值处的值并返回

结果。

以上操作函数的实现方法都是通过循环遍历数组，并运用相应的多项

式计算公式来计算。

二、程序设计及实验结果

2.1 程序设计

本次实验采用C语言编写完成，主函数的框架如下：

int main(int argc, char const *argv[]) {

// 输入多项式各项系数和幂次

// 调用各个多项式计算函数

// 输出计算结果

return 0;

}

2.2 实验结果

云南大学软件学院实验报告

指导教师：朱艳萍 2009秋季学期

学号：20081120064 姓名：李雪寒

【实验题目】

实验2. 一元稀疏多项式简单计算器

【问题描述】

设计并实现一个一元稀疏多项式的简单计算器。

【基本要求】

一元稀疏多项式简单计算器的基本功能是：

1.输入并建立多项式；

2.输出多项式，序列按指数降序排列；

3.多项式a和b相加，并建立多项式a+b；

4.多项式a和b相减，并建立多项式a-b；

【实现提示】

1.用带头节点的单链表作为多项式的存储结构；

一、【概要设计】

链式存储结构，由于不要求逻辑上相邻的元素在物理上也相邻，因此，能够迅速进行插入或删除操作，而且不像顺序存储结构那样需要移动大量元素，但也没有顺序表那样随机存取的优点。

主程序中通过调用void create(polynmial &L) 创建存储在单链表中的多项式，调用void display(polynmial L); 输出显示多项式，调用void sort(polynmial &L)和void reverse(polynmial &L)对多项式进行排序，使其按降序排列，调用void add(polynmial La,

polynmial Lb, polynmial &Lc) 和void subtract(polynmial La, polynmial Lb, polynmial &Ld) 对两个多项式进行加减操作。

二、【详细设计】

在此次试验中，主要通过以下7个子函数对存储在单链表中的多项式进行操作：void create(polynmial &L) //输入并建立多项式L

一元稀疏多项式计数器预习报告

姓名：刘茂学号222012315220062

一、实验要求

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

(2）输出多项式，输出形式为整数序列:n，c1，e1，c2，e2……cn，en，其中n是多项式的项数,ci，ei分别为第i项的系数和指数.序列按指数降序排列；

（3）多项式a和b相加，建立多项式a+b；

（4)多项式a和b相减，建立多项式a—b。

（5）多项式求值;

(6）多项式求导；

（7）求多项式的乘积。

二、测试数据:

1、（2x+5x^8—3。1x^11）+（7-5x^8+11x^9)=(-3。1x^11+11x^9+2x+7);

2、（6x^—3-x+4。4x^2—1.2x^9+1。2x^9)-(-6x^—3+5.4x^2-x^2+7。8x^15

）=（-7。8x^15—1.2x^9+12x^-3-x);

3、（1+x+x^2+x^3+x^4+x^5）+（—x^3-x^4）=(1+x+x^2+x^5）；

4、（x+x^3）+（—x-x^3）=0;

5、（x+x^100）+（x^100+x^200）=（x+2x^100+x^200）；

6、(x+x^2+x^3）+0=x+x^2+x^3。

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

三、思路分析

用带表头结点的单链表存储多项式.

本程序要求输入并建立多项式,能够降幂显示出多项式,实现多项式相加相减的计算问题，输

采用链表的方式存储链表，定义结点结构体.运用尾差法建立两条单链表，以单链表polyn p 和polyn h分别表示两个一元多项式a和b.

为实现处理，设p、q分别指向单链表polya和polyb的当前项,比较p、q结点的指数项。

一元稀疏多项式计算器实验报告

级班年月日学号_

1．实验题目

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

2．需求分析

本程序用VC编写，实现一元浮点系数，整数指数稀疏多项式的创建、两个一元多项式相加、两个一元多项式相减、输出一元多项式。

①输入的形式和输入值的围：

A.输入指定的数字，以此选择两个多项式的运算方式，运算方式有两个一元多项式相加、两个一元多项式相减。

B.创建多项式时，需要输入此多项式，每一项的系数和指数。

②输出的形式：每次输入一个完整的多项式后、每次得出多项式运算结果时，会以指定的方式输出多项式。

③程序所能达到的功能：实现一元稀疏多项式的创建、两个一元多项式相加、两个一元多项式相减、输出一元多项式。

④测试数据：

输入数据：

A.出现选择两个多项式的运算方式菜单时，输入1（即使两个多项式相加）；

B.首先输入多项式p的每一项系数和指数，当输入的指数为-5000时，表示该多项式输入完毕，输入的数据依次为：3，3，0，-5000；

C．其次输入多项式q的每一项系数和指数，输入数据依次为：2，2，0，-5000。

输出结果：

多项式q+p的结果为：

多项式为：

3x3+2x2

3．概要设计

1)为了实现上述程序功能，需要定义多项式结点的抽象数据类型：

class Term

{

数据对象：

float coef; 该数据对象为多项式一项中的系数。

int exp; 该数据对象为多项式一项中的指数。

Term* link; 该数据对象为指向下一个多项式结点的指针。

基本操作：

A. Term (float c, int e)

初始条件：无

实习一

1．需求分析：

【问题描述】：设计一个一元稀疏多项式简单计算器。

【基本要求】：（1）输入并建立两个多项式；

（2）多项式a 与b 相加，建立和多项式c ；

（3）多项式a 与b 相减，建立和多项式d ；

（4）输出多项式a,b,c,d 。输出格式：比如多项式a 为： ()em m e e x c x c x c x A +++= 2211，其中，i c 和i e 分别为第i 项的系数和指数，且各项按指数的升幂排列，即0≤1e ＜2e ＜…＜m e 。

【开发环境】：

系统：windows7

编程软件：VC++6.0

2.设计：

在数学上，一个n 次一元多项式可表示为

()x p n =0p +x p 1+22x p +…+n n x p

它由(n+1)个系数序列0p 、1p 、…、n p 唯一确定。

因此，在计算机中，可用一个线性表P 表示：

P=(0p ,1p ,…,n p )

其中，i p 代表()x p n 中的i 次项系数。

一般情况下，一元n 次多项式写成：

()em m e e n x p x p x p x p +++= 2211其中，0≤1e ＜2e ＜…＜m e n =且1p ,2p ,0≠m p

记作线性表P=（(1p ,1e ),(2p ,2e )…(m m e p ,)）

其中，元素为二元组（系数，指数）

多项式的单链表示意图:

图示分别为多项式

A(x)=7+3x+9x8+5x17 B(x)=8x+22x7-9x8

两个多项式相加运算规则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复制到“和多项式”中。 两个多项式相减运算规则：两个多项式中所有指数相同的项对应系数相减，若差不为零，则构成“减多项式”中的一项；对于指数不同的项，A 中项复制到“减多项式”中，B 中各项符号变化（原来为“+”的项符号变为“-”；为“-”的项符号变为“+”）复制到“减多项式”中。