数据结构 多项式求导

孝感学院计算机科学系11级课程设计课程设计报告

题目：多项式求导

班级：1017142

学号：101714201

姓名：

指导教师：李志敏

2012年2月12日

目录

1需求分析 (3)

1.1功能需求分析 (3)

1.2设计平台 (3)

2概要设计 (3)

2.1涉及到的知识基础(概述) (5)

2.2定义的函数的部分功能 (7)

3详细设计和实现 (7)

3.1功能模块 (7)

3.2系统流程图 (8)

4调试与操作说明 (9)

5、总结 (10)

6. 参考文献 (10)

7、源程序 (11)

1需求分析

1.1功能需求分析

1.本演示程序中，多项式的系数为浮点型，指数为整型。输入多项式时，先输入多项式的项数系数和指数，该多项式若为0，则输入0。多项式的输出形式为类数学表达式且按指数降序排列，系数值为1的非零次项的输出形式中略去系数1。

2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。

3.程序执行的命令：

输入为一个一元多项式，按照降幂依次输入每个单项式的系数和指数，并以-1 -1作为结束。系数和指数均为整数，指数不小于0。

1.2设计平台

Visual C++ 6.0 , Windows XP平台，

2概要设计

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

1.有序表的抽象数据类型定义为：

ADT List{

数据对象：D={a i|ai∈Elemset,i=1,2,…，n,n≥0}

数据关系：R1={|ai-1,ai∈D,i=2,…,n}

基本操作：

PolyNode *p,*q,*r,*head;

操作结果:构造一个空的线性表。。

Listinsert(&L,i,e)

初始条件:线性表L存在，0≤i≤L的元素个数。

操作结果:在L中第i个位置之后插入新的结点e。

}ADT List

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

ADT polyn{

数据对象:D={ai,bi|ai为不为0的实数，bi为整数，i=2,…,n}

数据关系:R1={ai，bi}

基本操作：

Output(PolyNode*head)

操作结果:创建一个多项式链表，输出多项式。

PolyNode * Plus(PolyNode *A,PolyNode *B)

初始条件:多项式链表L1,L2存在。

操作结果:创建一新多项式链表L，其结点为L1，L2相加。

poly *qiudao(poly *p)

初始条件:多项式链表L存在。

操作结果:创建一新多项式链表P，其结点为L结点的导数。

}ADT polyn

本程序包涵四个模块:

主程序模块：

main(){

初始化；

start：

接受命令;

switch(){

处理命令；

goto strat；

}

}

2）多项式单元模块：实现多项式的抽象数据类型；3）线性表单元模块：实现线性表的抽象数据类型；4）结点结构单元模块：定义线性表的结点结构；

各模块之间的调用关系如下:

图2-1 模块调用关系2.1涉及到的知识基础(概述)

1.结点类型、指针类型

typedef struct polynode

{

i nt c;

i nt e;

s truct polynode *next;

} poly;

2.线性表设计

p=h;

while(p->next!=NULL && e<=p->next->e) p=p->next; //如果输入的指数小于p的下一个接点，p向后指

if (e==p->expn) {p->coef+=c;continue;} //如果相等，直接加上去，继续循环

q=new PolyNode;

q->coef=c,q->expn=e;

if (p->next!=NULL&&e>p->next->expn) //如果p 的后继接点的指数小于输入的指数，插入到p的当前接点之后

{

r=p->next;

p->next=q;

q->next=r;

continue;

}

p->next=q; //如果输入的值小于所有接点，接在最后一个接点之后

p=p->next; p->next=NULL;

3.多项式基本操作部分

poly *qiudao(poly *p)//求导

{

poly *s;

s = p;

while (p)

{

p->c = (p->c)*(p->e);

p->e = (p->e) - 1;

p = p->next;

}

return s;

}

2.2定义的函数的部分功能

在设计程序的时候，考虑到一元稀疏多项式计算器的功能，我们按照其功能划分为几个模块，在程序开始后，先进行多项式的输入,再选择一种运算法则进行运算。然后输出运算结果。具体的模块关系如表程序结构框图:

3详细设计和实现

3.1 功能模块

图3-1 功能图3.2系统流程图

图3-2系统流程图4调试与操作说明

运行结果如图所示

5、总结

再学完数据结构后做此题，自觉就想到用带头结点的单链表来存储多项式，只需用结点记录多项式的系数和指数，此数据结构即节省空间又好进行操作，且进行运算的主要设计思路也易想到，大体设计结构在较短时间内能够完成。但当设计到具体细节代码时遇到了不少困难，主要困难是进行结点操作时，对指针考虑得不够细致，调试时常出现指针指错的情况，没有认真理清条件层次。完成此程序后，受益匪浅，它巩固了线性表一章学到的知识，而且重温了指针，函数传参等重点知识。尽管对程序进行大量的调试分析修改，可还有些代码写得十分啰嗦，程序也不够健壮，对多项式的操作只限于2个多项式，还有在界面设计上没花太大心思，界面不美观。这些问题在日后还需进行改善。本次课程设计采用C++语言实现.这次设计基本上能实现指导书上的要求。我们可以通过这个程序实现计算器的一些基本功能,实现相关操作。通过本次课程设计,让我进一步了解了c++的一些知识,C/C++的字符串处理功能完全依靠字符串数组来实现，很多在其他高级语言中实现的字符串比较等操作，在这里完全依靠函数来实现，因此调试中字符串处理函数的调试很多本次课程设计培养了我们对这些实际问题的分析能力以及解决一些实际问题的能力。通过编程，巩固了我们对编程思想和写程序的能力。课程设计是对我们的学习很有利的一个环节。在这个阶段，我们学会把理论与实际的结合、懂得人与人沟通的重要性，明白合作的可贵。当然，在编写的过程中也出现了很多问题，但通过调试和看书解决了，大大的提高了我自学的能力，学会了遇到问题，如何利用资源去解决问题也明白了要完成一项设计，首先要有扎实的基础知识，这就要求我们在平时的学习中要不断提高自己。其次，要充分利用身边的各种资源，图书馆有很多相关的书，网上也有不少的知识解答，要好好的利用。第三，要多向身边的同学多请教，在交流中提高自己的实力。理论联系实践，在实践中提高。通过这次课程设计中，我加深了对课本知识的理解。

6. 参考文献

[1]《C++程序设计》钱能清华大学出版社

[2]《C++程序设计试验指导》钱能清华大学出版社

[3]《C程序设计》谭浩强清华大学出版社

[4]《数据结构（C语言版）》严蔚敏吴伟民清华大学出版社7、源程序

#include

#include

typedef struct polynode

{

int c;

int e;

struct polynode *next;

} poly;

poly *creatpoly()

{

poly *p, *q, *h;

q = NULL, h = NULL;

int c;

int e;

while (e!=-1)

{

scanf("%d%d", &c, &e); /*将scanf位置改变下*/

h = (poly*)malloc(sizeof(poly));

h->c = c;

h->e = e;

h->next = NULL;

if (q == NULL)

q = h;

else

p->next = h;

p = h;

}

return q;

}

poly *qiudao(poly *p)

{

poly *s;

s = p;

while (p)

{

p->c = (p->c)*(p->e);

p->e = (p->e) - 1;

p = p->next;

}

return s;

}

void print(poly *p)

{

int i = 0;

if (p->e == - 1)

{

printf("0");

i++;

}

{

while (p->next != NULL)

{

if (p->c != 0)

{

printf("%d %d ", p->c, p->e);

i++;

}

else

;

p = p->next;

}

if (p->next == NULL)

{

if (p->c != 0 && p->e > -1) /*加上约束条件p->e>-1*/

{

printf("%d %d ", p->c, p->e);

i++;

}

else

;

}

if (i == 0)

printf("0");

printf("\n");

}

}

int main()

{

poly *d, *h;

d = creatpoly();

h = qiudao(d);

print(h);

getchar();

getchar();

return 0;

}

数据结构实验多项式加法

数据结构实验报告 实验名称：多项式加减法 学号：1200310419 姓名：林强 实验日期：2015.5.05 一、实验目的 通过实现多项式的加减法，对链表有更深入的了解 二、实验具体内容 1、实验题目1： （1）题目设计一个一元稀疏多项式简单的加减法计算器 实现要求： 一元稀疏多项式简单计算器的基本功能是： （1）输入并建立多项式： 85 17 A+ x + x =； + 3 9 x 7 ) (x 79 8 x B- + = x 22 8 x ) (x （2）输出多项式 （3）多项式A和B相加，建立多项式C＝A＋B，并输出相加的结果多项式C （4）选作：多项式A和B相减，建立多项式C＝A－B，并输出相加的结果多项式D （2）分析 1：本程序的任务是实现两个多项式的加法其中多项式的系数为浮点型， 指数为整数，输出的结果也为系数和指数。 （1）输入的形式和输入值的范围： 输入多项式的系数a和未知数X的指数b，当a和b都为零时，输入结束。输入值的范围：a为实数，b为整数。 （2）输出形式：输出多项式的系数和多项式未知数X的指数即(a,b)形式。 （3）程序所能达到的功能，实现两个多项式的加法，并输出最后的结果 2： 整个程序运行期间实行动态创建节点，一边输入数据， 一边创建节点当将全部数据输入到单链表中后再调用多项式加法这 个函数，并一边实现多项式的相加，一边释放节点，有效防止了 在程序反复运行过程中可能出现系统空间不够分配的现象 （3）实验代码 typedef int Status; #define OVERFLOW -1 #define null 0 typedef struct Lnode{

数据结构-多项式相加

数据结构课程设计 2012年12月 班级：XXX 学号：XXX 姓名： XXX 指导教师：XXX

一元稀疏多项式计算器 【问题描述】 设计一个一元稀疏多项式简单计算器 【基本要求】 一元多项式简单计算器的基本功能是： 1，输入并建立多项式; 2，输出多项式，输出形式为整数序列:n,c1,e1,c2,c2,...,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列; 3,多项式a和b相加，建立多项式a+b; 4,多项式a和b相减，建立多项式a-b. 【算法设计思想】 ①一般情况下的一元n次多项式可写成pn(x)=p1xe1+p2xe2+……+pmxem 其中，p1是指数为ei的项的非零系数，且满足0≦e1

【实现提示】 用带表头结点的单链表存储多项式。 【程序代码】 #include #include typedef struct node { float coef; int expn; struct node *next; }Lnode, *polynmial; void create(polynmial &L); //输入并建立多项式L void display(polynmial L); //显示，输出多项式L void sort(polynmial &L); //多项式L按指数排序 void reverse(polynmial &L); //逆置 void select(); //用户选择加减操作 void add(polynmial La, polynmial Lb, polynmial &Lc); //多项式La,Lb相加void subtract(polynmial La, polynmial Lb, polynmial &Ld); //多项式La减去Lb，结果给Ld void create(polynmial &L) //输入并建立多项式L { int i, n; static struct node *p; scanf("%d", &n); L = (struct node *)malloc (sizeof(struct node)); L->next = NULL; for(i = 0; i < n; i++) { p = (struct node *)malloc(sizeof(struct node)); scanf("%f %d", &p->coef, &p->expn); p->next = L->next; L->next = p; } } void display(polynmial L)//显示，输出多项式L { struct node *p, *q; int flag = 0; int k = 0; q = L->next; while(q)

一元多项式求和

一元多项式求和——链表编程 一．实验名称：一元多项式求和——链表编程。 二．实验环境：Windows Xp ,Vc++6.0。 三．实验目的： 1.掌握一元多项式的链表式存储算法； 2.掌握链表的结构定义； 3.采用尾插法生成单链表。 四．实验内容： 1.一元多项式的表示： 一元多项式可按升幂的形式表示为 12012()n e e e n n P x p p x p x p x =++++…… 其中：i e 为第i 项的指数，i p 是指数i e 的项的系数，且 121i n e e e e <=<=<=<=<=<=……。 则多项式()n P x 可以用一个线性表P 来表示：01(,)m P p p p =, ；同理，多项式 ()n Q x 可表示为01(,,)n Q q q q =…（mcodf=c;

数据结构实验一一元多项式相加

数据结构实验报告实验一：一元多项式相加 姓名：周成 学号： 专业：软件工程 任课教师：马慧珠 2013年12 月01 日

1.实验名称： 一元多项式相加 2.实验目的: 如何使用C语言实现链表的说明、创建以及结点的插入和删除等操作。 3.实验要求： 对一元多项式能实现输入、输出，以及两个一元多项式相加及结果显示。 4.实验内容： 一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项，对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。 核心算法PolyAdd是把分别由pa和pb所指的两个多项式相加，结果为pa所指的多项式。运算规则如下：相加时，首先设两个指针变量qa和qb分别从多项式的首项开始扫描，比较qa和qb所指结点指数域的值，可能出现下列三种情况之一：

（1）qa->exp大于qb->exp,则qa继续向后扫描。 （2）qa->exp等于qb->exp,则将其系数相加。若相加结果不为零，将结果放入qa->coef中，并删除qb所指结点，否则同时删除qa和qb所指结点。 然后qa、qb继续向后扫描。 （3）qa->exp小于qb->exp,则将qb所指结点插入qa所指结点之前，然后qa、qb继续向后扫描。 扫描过程一直进行到qa或qb有一个为空为止，然后将有剩余结点的链表接在结果表上。所得pa指向的链表即为两个多项式之和。 5.实验程序代码及运行结果： #include"" #include<> #include<> #include<> #include<> #define NULL 0 typedef struct NODE {

多项式加法(C语言实现)

多项式加法 #include #include #define Max_Size 100 typedef struct node { float coef; int expn; struct node *next; }PolyNode; int CreCoeStr(float C[]) { char flag; int i=0; do { scanf("%f",&C[i++]); scanf("%c",&flag); } while (flag!='#'); return(i); } void CreExpStr(int E[]) { int i=0; char flag; do { scanf("%d",&E[i++]); scanf("%c",&flag); } while (flag!='#'); } void InitPolyList(PolyNode **sq) { if((*sq=(PolyNode *)malloc(sizeof(PolyNode)))==NULL) exit(1); (*sq)->next=NULL; }

void CreatPolyList(PolyNode **sq,float C[],int E[],int num) { int i; PolyNode *s,*r=*sq; for(i=0;icoef=C[i]; s->expn=E[i]; r->next=s; r=s; } r->next=NULL; } void InsertSortPoly(PolyNode **sq) { PolyNode *p,*q,*r,*u; p=(*sq)->next; (*sq)->next=NULL; while (p) { r=*sq; q=(*sq)->next; while (q&&q->expn<=p->expn) { r=q; q=q->next; } u=p->next; p->next=r->next; r->next=p; p=u; } } void DispList(PolyNode *sq) { PolyNode *p=sq->next; while(p) { printf("(%7.2f,%d)",p->coef,p->expn); p=p->next; }

链表实现多项式相加实验报告

实验报告 课程名称：数据结构 题目：链表实现多项式相加 班级： 学号： 姓名： 完成时间：2012年10月17日

1、实验目的和要求 1）掌握链表的运用方法； 2）学习链表的初始化并建立一个新的链表； 3）知道如何实现链表的插入结点与删除结点操作； 4）了解链表的基本操作并灵活运用 2、实验内容 1）建立两个链表存储一元多项式； 2）实现两个一元多项式的相加； 3）输出两个多项式相加后得到的一元多项式。 3、算法基本思想 数降序存入两个链表中，将大小较大的链表作为相加后的链表寄存处。定义两个临时链表节点指针p,q,分别指向两个链表头结点。然后将另一个链表中从头结点开始依次与第一个链表比较，如果其指数比第一个小，则p向后移动一个单位，如相等，则将两节点的系数相加作为第一个链表当前节点的系数，如果为0，则将此节点栓掉。若果较大，则在p前插入q,q向后移动一个，直到两个链表做完为止。 4、算法描述 用链表实现多项式相加的程序如下： #include #include #include struct node{ int exp; float coef; struct node*next; };

void add_node(struct node*h1,struct node*h2); void print_node(struct node*h); struct node*init_node() { struct node*h=(struct node*)malloc(sizeof(struct node)),*p,*q; int exp; float coef=1.0; h->next=NULL; printf("请依次输入多项式的系数和指数(如:\"2 3\"；输入\"0 0\"时结束):\n"); p=(struct node*)malloc(sizeof(struct node)); q=(struct node*)malloc(sizeof(struct node)); for(;fabs(coef-0.0)>1.0e-6;) { scanf("%f %d",&coef,&exp); if(fabs(coef-0.0)>1.0e-6) { q->next=p; p->coef=coef; p->exp=exp; p->next=NULL; add_node(h,q); } } free(p); free(q); return(h); } void add_node(struct node*h1,struct node*h2) { struct node*y1=h1,*y2=h2; struct node*p,*q; y1=y1->next; y2=y2->next; for(;y1||y2;) if(y1) { if(y2) { if(y1->expexp) y1=y1->next; else if(y1->exp==y2->exp) { y1->coef+=y2->coef; if(y1->coef==0)

多项式求和

数据结构课程设计 题目：多项式运算 学生姓名：熊奉标 学号：10115011046 专业：计算机科学与技术 班级：10级（1）班 指导教师姓名及职称：陈正铭讲师 起止时间：2012 年2 月——2012 年4 月 1 需求分析

1.1 课题背景及意义 本课程设计主要解决一元多项式的运算问题，通过链表的使用，实现对一元多项式的构建、录入、存储、打印、以及之间的运算。在本课程设计中，程序设计语言为C++语言，程序运行平台为Windows/98/2000/XP，程序采用了链表存储方法以及结构化和模块化的设计方法，通过调试运行，可以进行多项式的加、减、乘运算，勉强实现了设计目标，并且经过适当完善后，将可应用到实际中解决某些问题。 一元多项式的运算，虽然无法直接在除数学外的其他领域作出贡献，但是在数学上，它可以为人们解决一些自己动笔动手很难解决的问题，比如说那些很长很长的多项式，用笔算可能要算半天，但是用该程序，只需短短的几秒钟，所以它给人们带来了不少方便，同时相信它也能间接地为其他领域做出贡献。 1.2 课题要求 （1）掌握线性表的创建、插入、删除等基本运算。 （2）掌握线性表的顺序存储结构和链式存储结构 （3）掌握线性表的典型应用—多项式运算(加、减、乘)。 该程序的主要任务是将用户输入的多项式用线性表存储，然后通过对线性表的基本操作，而实现多项式之间的三则运算，把正确结果输出给用户。 1.3 软件格式规定 输入格式：有两类编辑框可供输入，系数编辑框、指数编辑框，在系数编辑框中允许输入浮点型数据，在指数编辑框中只允许输入整型数据。 正确的输入： f(x)=8X^6+4X^5-2X^4-12X^3-1X^1+10X^0 g(x)=2X^3-5X^2+1X^1 正确的输出结果： f(x)+g(x)：结果= 8.00X^6 +4.00X^5 -2.00X^4 -121.00X^3 -5.00X^2 +10.00 f(x)-g(x)：结果= 8.00X^6 +4.00X^5 -2.00X^4 -125.00X^3 +5.00X^2 -2.00X

一元多项式相加完整实验报告

一元多项式相加实验报告 一元多项式的相加

一实验内容 根据所学的数据结构中线性结构（线性表）的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加 二需求分析 1掌握线性结构的逻辑特性和物理特性。 2建立一元多项式。 3将一元多项式输入，并存储在内存中，并按照指数降序排列输出多项式。 4能够完成两个多项式的加减运算，并输出结果。 三概要设计 1 本程序所用到的抽象数据类型： typedef OrderedLinkList polynomial; // 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 term, ElemType; V oid AddPolyn(polynomail&Pa,polynomail&Pb) Position GetHead() Position NextPos(LinkList L,Link p) Elem GetCurElem(Link p) int cmp(term a term b) Status SetCurElem(Link&p, ElemType e) Status DelFirst(Link h, Link &q) Status ListEmpty(LinkList L) Status Append(LinkList&L, Link S) FreeNode() 2 存储结构

一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。 创建一元多项式链表，对运算中可能出现的各种情况进行分析，实现一元多项式的相加相减操作。 3 模块划分 a) 主程序；2）初始化单链表；3）建立单链表； 4）相加多项式 4 主程序流程图 四详细设计 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项，对

一元多项式计算(数据结构课程设计)

一元多项式计算(数据结构课程设计)

一、系统设计 1、算法思想 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。 因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。为了节省空间，我采用两个链表分别存放多项式a 和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。主要用到了单链表的插入和删除操作。

(1)一元多项式加法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。P 的指数小于q的指数的话就应该复制q的节点到多项式中。P的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。 (2)一元多项式的减法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q的节点到多项式中。P的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。 2、概要设计 (1)主函数流程图： （注：a代表第一个一元二次方程，b代表第二个一元二次方程）

一元多项式的运算

数据结构课程设计实验报告 专业班级： 学号： 姓名： 2011年1月1日

题目：一元多项式的运算 1、题目描述 一元多项式的运算在此题中实现加、减法的运算，而多项式的减法可以通过加法来实现（只需在减法运算时系数前加负号）。 在数学上，一个一元n次多项式P n(X)可按降序写成： P n(X)= P n X^n+ P(n-1)X^(n-1)+......+ P1X+P0 它由n+1个系数惟一确定，因此，在计算机里它可以用一个线性表P来表示： P=(P n，P(n-1)，......，P1，P0) 每一项的指数i隐含在其系数P i的序号里。 假设Q m(X)是一元m次多项式，同样可以用一个线性表Q来表示： Q=(q m,q(m-1)，.....，q1，q0) 不是一般性，假设吗吗m

数据结构--线性表的基本运算及多项式的算术运算

数据结构:线性表的基本运算及多项式的算术运算 一、实验目的和要求 实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。 要求： 能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。 二、实验环境(实验设备) X64架构计算机一台，Windows 7操作系统， IDE: Dev C++ 5.11 编译器: gcc 4.9.2 64bit 二、实验原理及内容 程序一：实现顺序表和单链表的实现 本程序包含了四个文件，分别是LinearListMain.cpp，linearlist.h，seqlist.h，singlelist.h。分别是主程序，线性表抽象类，顺序储存线性表的实现，链表储存顺序表的实现。 文件之间的关系图：

本程序一共包含了三个类：分别是LinearList（线性表抽象类），SeqList（顺序储存的线性表），SingleList（链表储存的线性表）。类与类之间的关系图如下： 其实，抽象类LinearList规定了公共接口。分别派生了SeqList类和SingleList。

SingleList类与SingleList类分别实现了LinearList类中的所有接口。 程序代码以及分析： Linearlist类： #include using namespace std; template class LinearList { protected: int n; //线性表的长度 public: virtual bool IsEmpty() const=0; //判读是否是空线性表 virtual int Length() const=0; //返回长度 virtual bool Find(int i,T& x) const=0; //将下标为i的元素储存在x中，成功返回true，否则返回false virtual int Search(T x) const=0; //寻找值是x的元素，找到返回true，否则返回false virtual bool Insert(int i,T x)=0; //在下标为i的元素后面插入x

一元多项式的计算数据结构课程设计

一元多项式的计算—加，减 摘要(题目)一元多项式计算 任务：能够按照指数降序排列建立并输出多项式； 能够完成两个多项式的相加、相减，并将结果输入； 目录 1.引言 2.需求分析 3.概要设计 4.详细设计 5.测试结果 6.调试分析 7.设计体会 8.结束语 一:引言: 通过C语言使用链式存储结构实现一元多项式加法、减法和乘法的运算。按指数

降序排列。 二：需求分析 建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果 三：概要设计 存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 1．单连表的抽象数据类型定义： ADT List{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={| ai-1, ai∈D,i=2,…,n} 基本操作： InitList（＆L） //操作结果：构造一个空的线性表 CreatPolyn(&L) //操作结果：构造一个以单连表存储的多项试 DispPolyn(L) //操作结果：显示多项试 Polyn(&pa,&pb) //操作结果：显示两个多项试相加，相减的结果 } ADT List 2．本程序包含模块： typedef struct LNode //定义单链表 { }LNode,*LinkList; void InitList(LinkList &L) //定义一个空表 { } void CreatPolyn(LinkList &L) //用单链表定义一个多项式 { } void DispPolyn(LinkList L) //显示输入的多项式

两个一元多项式相加-c++版

《数据结构》实验报告 ——两个一元多项式相加 一、实验题目：两个一元多项式相加 二、实验内容： 根据所学的数据结构中线性结构（线性表）的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加 三、设计思想： （1）建立两个顺序列表，分别用来表示两个一元多项式；顺序列表奇数位，存储该多项式的系数；顺序列表的偶数位，存储该相应多项式的指数。 （2）用成员函数merg(qList&l2)实现两多项式的相加。实现的大致方法为：比较第二个多项式列表与第一个多项式列表的偶数位的数值大小（指数），如果 相同，则将他们的前一位数（系数）相加；如果不同，就将他的前一位数（系 数）及它自己（指数）插入第一个多项式列表的后面。 （3）建立函数shu(double a[],int j)实现多项式的输入。 四、源程序代码 #include "stdafx.h" #include using namespace std; template class List { private: Telem * elem; int curlen; int maxlen; public: List(int maxsz=100):maxlen(maxsz) { curlen=0; elem=new Telem{maxlen}; }; List(Telem a[],int n,int maxsz=100):maxlen(maxsz) { curlen=n; elem=new Telem[maxlen]; for(int i=0;i

数据结构多项式求和

数据结构与算法 上机实验报告（一） 上机实验题目：一元多项式的表示及相加 专业班级：信息与计算科学1401班 姓名：邢鑫锋学号：140701211 设计室：理学院机房 上机时间： 2015-11-10 上机学时： 4学时 指导教师：杜洪波成绩：

一.实验目的： 1、进一步熟练掌握应用链表处理实际问题的能力 2、 二.实验内容： 1、一元多项式相加是通过键盘输入两个形如 P0+P1X1+P2X2+。。。+PnXn 的多项式，经过程序运算后在屏幕上输出它们的相加和。 2、 3、 三、程序及注释： #include #include #include typedef struct Node { int Data; Node* next; }SLNode; void listInt(SLNode **T) {if((*T=(SLNode*)malloc(sizeof(SLNode)))==NULL) exit(1); (*T)->next=NULL; }

void Create(SLNode *T,int n) { SLNode *p; int i; p=T; for(i=0;inext=q; printf("请输入链表数据\n"); scanf("%d",&q->Data); p=q; } } void Addtion(SLNode*T,SLNode*B,SLNode*C,int n) { int i; SLNode *p; p=C;

数据结构——一元多项式的建立与相加

#include #include using namespace std; typedef struct PolyNode { int coef; //系数 int expn; //指数 struct PolyNode *next; } *PNode; //多项式结点的指针 void InitPoly(PNode &head,PNode &p) { head=(PNode)malloc(sizeof(struct PolyNode)); head->next=NULL; head->coef=0; head->expn=-1; p=head; } void CreatePoly(PNode &head,int a,int n) { PNode s; s=(PNode)malloc(sizeof(struct PolyNode)); //建立新的结点s->coef=a; s->expn=n; s->next=NULL; head->next=s; head=s; } void PrintPoly(PNode head) { int i=1;//控制第一对系数指数的显示 head=head->next;//指向表头结点的下一个 PNode p; p=head; while ((p->next)!=NULL) { if(i) //显示第一对的时候是不需要显示加号的 { if (p->expn==1) cout<coef<<"x"; else if (p->expn==0) cout<coef<

else cout<coef<<"x^"<expn; i=0; } else { if (p->expn==1) cout<coef<<"+x"; else if (p->expn==0) cout<<"+"<coef<coef<<"x^"<expn; } p=p->next; } cout<next; pb=pb->next; p=pc; while (pa!=NULL && pb!=NULL) { if (pa->expn>pb->expn) { s=(PNode)malloc(sizeof(struct PolyNode)); s->coef=pa->coef; s->expn=pa->expn; s->next=NULL; p->next=s; p=s; pa=pa->next; } else if (pa->expnexpn) { s=(PNode)malloc(sizeof(struct PolyNode)); s->coef=pb->coef; s->expn=pb->expn; s->next=NULL; p->next=s; p=s; pb=pb->next; }

二元多项式相加

华北水利水电大学数据结 构试验报告 ------二元多项式相加 2013160班

/*二元多项式的相加*/ #include #include struct node{ int coefficient; int expoentx; int exponety; struct node *next; }; typedef struct node *ptrtonode; ptrtonode bulidnode( void )//建立多项式链表 { int i, j; ptrtonode head, pnew, p; printf("请输入多项式含有的项数\n"); scanf("%d", &i); getchar(); if( (head = (ptrtonode)malloc( sizeof( struct node ))) == NULL ) return NULL; head->expoentx = 0; head->exponety = 0; head->next = NULL; head->coefficient = i;//将多项式的项数存在首节点 p = head; for( j = 0; j < i; j++ ) { if( (pnew = (ptrtonode)malloc( sizeof( struct node ))) == NULL ) return NULL; printf("请输入系数x和y的次幂中间用空格隔开\n"); scanf("%d%d%d", &pnew->coefficient, &pnew->expoentx, &pnew->exponety); fflush(stdin); p->next = pnew; p = pnew; p->next = NULL; } return head;

多项式加法

班级：信息1301 姓名：胡苗苗 ======== 实习报告一“PolyAdd ”演示程序================== （一）、程序的功能和特点 功能：将两个多项式相加，利用单链表存储多项式，并实现多项式的加法。 特点：利用单链表进行多项式相加时，不生成新的结点，直接在原来的结点上运算。 （二）、程序中的算法设计 1.【逻辑结构与存储结构设计】 逻辑结构：存储多项式的的单链表是线性结构。 存储（物理）结构：存储多项式的的单链表是链式存储结构。 例如： 2.【基本操作设计】 ①public booleaninsertBack(double c,int e) 给存储多项式的单链表的尾部插入一个结点 ②给存储多项式的单链表中插入一个结点 新结点 3.【算法设计】 流程图：

算法描述：构造两个链表类s1，s2，头指针分别为ah，bh，从第一个结点开始比较： （1）如果两个结点的多项式阶数相等，那么把两个系数相加，指数不变赋给s1的第一个结点，指针后移； （2）如果s1的结点阶数小于s2的结点阶数，s1的指针ah后移，判断下一个结点阶数与s2当前阶数大小； （3）如果s1的结点阶数大于s2，那么将s2的当前结点插入s1当前结点的前面。直到s1或s2的指针指向空。 判断s1或者s2指针是否指到末尾： ①若s2指针指空，那么结束程序。 ②若s1指针指空，则把s1 的末尾指针指向s2剩余的部分。 4.【高级语言代码】 多项式加法:自身多项式和ob相加，和为自身 public void addPoly(linkListob) { link ah=first; //自身的第一个结点 link bh=ob.first; //ob的第一个结点 link p,q; //辅助的指针，指向某个结点 //指针ah和bh都没有移到结束处 while(ah!=null&&bh!=null) { if(ah.exp==bh.exp) { //阶数相同 ah.coef+=bh.coef; //改变自身结点系数

数据结构多项式相加实验报告

试验一多项式相加 一. 实验内容： 多项式相加 二.实验目的和要求： 利用双向链表实现通讯录的建立、删除、检索和列表，并可保存至文件，可重新装入。 用链式存储结构实现一元多项式的相加运算。 三．算法思想描述: 1. 以单链表为存储结构插入多项式: 多项式输入：多项式按幂从高到低，以“系数，幂”的格式输入，并以“0，0”结束。 printf("Please input coef:"); scanf("%d",&i); printf("Please input exp: "); scanf("%d",&j); while(i!=0) { q=(pnode)malloc(sizeof(struct node)); q->coef=i; q->exp=j; p->link=q; p=q; printf("Please input coef:"); scanf("%d",&i); printf("Please input exp: "); scanf("%d",&j); } p->link=NULL; 2. 多项式相加单链表合并: 由两个多项式对应的单链表头节点开始，依次扫描各节点。 (1)若两表的节点均非空：比较二者的幂，按幂大者先入表。如果幂相等，则系数相加再入表。具体由以下代码实现： while(p!=NULL && q!=NULL){ if(p->exp==q->exp){ x=p->coef+q->coef; if(x!=0){ s=(pnode)malloc(sizeof(struct node)); s->coef=x;s->exp=p->exp;

r->link=s; r=s; } p=p->link; q=q->link; } else if(p->expexp){ s=(pnode)malloc(sizeof(struct node)); s->coef=q->coef; s->exp=q->exp; r->link=s;r=s; q=q->link; } else{ s=(pnode)malloc(sizeof(struct node)); s->coef=p->coef; s->exp=p->exp; r->link=s;r=s; p=p->link; } (2). 若有一链表已空，则将非空链表插入新表： while(p!=NULL){ s=(pnode)malloc(sizeof(struct node)); s->coef=p->coef; s->exp=p->exp; r->link=s; r=s; p=p->link; } while(q!=NULL){ s=(pnode)malloc(sizeof(struct node)); s->coef=q->coef; s->exp=q->exp; r->link=s; r=s; q=q->link; } 3. 输出合并后的链表: while(head->link!=NULL) { head=head->link; printf(" %d*x^%d",head->coef,head->exp);

常用的一些求和公式

下面是常用的一些求和公式：

a1, a1+d, a1+2d, a1+3d, .... (d为常数) 称为公差为d的等差数列.与等差数列相应的级数称为等差级数，又称算术级数. 通项公式 前n项和 等差中项 a1, a1q, a1q2, a1q3....,(q为常数) 称为公比为q的等比数列.与等比数列相应的级数称为等比级数，又称几何级数. 通项公式 前n项和 等比中项

无穷递减等比级数的和 更多地了解数列与级数：等差数列与等差级数(算术级数) 等比数列 等比数列的通项公式 等比数列求和公式 (1) 等比数列：a (n+1)/an=q (n∈N)。 (2) 通项公式：an=a1×q^(n-1)； 推广式：an=am×q^(n-m)； (3) 求和公式：Sn=n*a1 (q=1) Sn=a1(1-q^n)/(1-q) =(a1-an*q)/(1-q) (q≠1) (q为比值，n为项数） (4)性质： ①若m、n、p、q∈N，且m＋n=p＋q，则am*an=ap*aq； ②在等比数列中，依次每k项之和仍成等比数列. ③若m、n、q∈N，且m+n=2q，则am*an=aq^2 (5) "G是a、b的等比中项""G^2=ab（G ≠ 0）". (6)在等比数列中，首项a1与公比q都不为零. 注意：上述公式中an表示等比数列的第n项。 等比数列 如果一个数列从第2项起，每一项与它的前一项的比等于同一个常数，这个数列就叫做等比数列。这个常数叫做等比数列的公比，公比通常用字母q表示(q≠0)。 （1）等比数列的通项公式是：An=A1*q^（n－1） 若通项公式变形为an=a1/q*q^n(n∈N*),当q＞0时，则可把an看作自变量n的函数，点(n,an)是曲线y=a1/q*q^x上的一群孤立的点。