[计算机]一元多项式相加完整实验报告

[计算机]一元多项式相加完整实验报告一元多项式的相加

一实验内容

根据所学的数据结构中线性结构(线性表)的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加

二需求分析

1掌握线性结构的逻辑特性和物理特性。

2建立一元多项式。

3将一元多项式输入，并存储在内存中，并按照指数降序排列输出多项式。 4能够完成两个多项式的加减运算，并输出结果。

三概要设计

1 本程序所用到的抽象数据类型:

typedef OrderedLinkList polynomial;

// 用带表头结点的有序链表表示多项式

结点的数据元素类型定义为:

typedef struct { // 项的表示

oat flcoef; // 系数

int expn; // 指数 term, ElemType;

Void 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 存储结构

一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。

序数coef 指数exp 指针域next

创建一元多项式链表，对运算中可能出现的各种情况进行分析，实现一元多项式的相加相减操作。

3 模块划分

a) 主程序;2)初始化单链表;3)建立单链表; 4)相加多项式 4 主程序流程图

开始

申请结点空间

输入多项式各项的系数X，指数Y

输出已输出的多项式

否

是否输入正确

合并同类项

结束

四详细设计

根据一元多项式相加的运算规则:对于两个一元多项式中所有指数相

同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项，对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。

核心算法PolyAdd是把分别由pa和pb所指的两个多项式相加，结果为

pa所指的多项式。运算规则如下:相加时，首先设两个指针变量qa和qb分别从多项式的首项开始扫描(见图2-5-1)，比较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指向的链表即为两个多项式之和。

五源程序代码

#include

#include

#include

#define NULL 0

typedef struct NODE {

float coef; //系数

int expn; //指数

struct NODE *next;

}NODE;

NODE *Creat(int n);

void print(NODE *head);

NODE *AddPolyn(NODE *head1, NODE *head2); NODE *Delfirst(NODE *head, NODE *q);

void InsertBefore(NODE *p1, NODE *p2);

int compare(int a, int b);

main()

{

NODE *head1, *head2, *head3;

int n1, n2;

printf("请输入你需要的多项数的数目 n1 : "); scanf("%d", &n1);

head1 = Creat(n1);

printf("第一个多项式的显示 : \n");

print(head1);

printf("\n请输入你需要的多项数的数目 n2 : "); scanf("%d", &n2);

head2 = Creat(n2);

printf("\n第二个多项式的显示 : \n");

print(head2);

head3 = AddPolyn(head1, head2);

printf("\n合并后的多项式的显示 : \n");

print(head3);

printf("\n");

}

/*创建链表*/

NODE *Creat(int n)

{

NODE *current, *previous, *head;

int i;

head = (NODE *)malloc(sizeof(NODE)); /*创建头结点*/

previous = head;

for(i = 0; i < n; i++)

{

current = (NODE *)malloc(sizeof(NODE));

printf("请输入系数和指数 : ");

scanf("%f%d", ¤t->coef, ¤t->expn);

previous->next = current;

previous = current;

}

previous->next = NULL;

return head;

}

/*一元多项式的想加，总体考虑，可分qa的指数比qb小，或等于pb(如果系数相加等于0和不等于0),或大于pb

里面由InsertBefore和Delfirst两个小模块组成一部分*/

NODE *AddPolyn(NODE *head1, NODE *head2)

{

NODE *ha, *hb, *qa, *qb;

int a, b;

float sum;

ha = head1; /*ha和hb指向头结点*/

hb = head2;

qa = ha->next; /*qa和qb指向头结点的下一个结点*/ qb = hb->next;

while(qa && qb) /*qa和qb均非空*/

{

a = qa->expn;

b = qb->expn;

switch(compare(a, b)) {

case -1 : /*qa->expn < qb->expn*/

ha = qa;

qa = qa->next;

break;

case 0 :

sum = qa->coef + qb->coef; /*系数的和*/

if(sum != 0.0) { /*如果不是0.0*/

qa->coef = sum; /*改变系数*/

ha = qa;

}else {

free(Delfirst(ha, qa));

}

free(Delfirst(hb, qb));

qa = ha->next;

qb = hb->next; /*qb释放后要重新赋值*/

break;

case 1 : /*如果qa-> expn > qb -> expn*/

Delfirst(hb, qb);

InsertBefore(ha, qb); /*把qb插入到ha下一个结点之前*/ qb = hb->next;

ha = ha->next;

break;

}

}

if(qb)

ha->next = qb; /*插入剩余的pb*/

free(head2);

return head1;

}

/*比较*/

int compare(int a, int b) {

if(a < b)

return -1;

else if(a > b)

return 1;

else

return 0;

}

/*删除结点q*/

NODE *Delfirst(NODE *p1, NODE *q)

{

p1 -> next = q -> next;

return (q);

}

/*插入结点,引入结点p,可以让p插入到p2和p1之间*/ void InsertBefore(NODE *p1, NODE *p2)

{

NODE *p;

p = p1->next;

p1->next = p2;

p2->next = p;

}

/*打印,为了美观程序分开打印*/

void print(NODE *head)

{

NODE *current;

current = head->next;

while(current->next != NULL)

{

printf("%0.f * x^%d + ", current->coef, current->expn);

current = current -> next;

}

printf("%0.f * x^%d", current->coef, current->expn);

}

六调试分析

如图第八行，如果直接一次性输完两项的次数和项数，还是会显示“请输入系数

和指数”

纠正办法:输入时输完一项的系数和指数，按回车后继续输入。七测试结果输入一个二次三项式X^2+3X^+1，一个三次四项式2X^3+4X^2+X+1 输出如图:

八心得体会

首先，我的C++学的不是很好，因此做这样一个课程设计感觉有点吃力，还好我不断的看书，翻阅资料，询问同学，上网搜索，总算像模像样地把这个程序编的能运行了。功夫不负有心人。

其次，这次编程是我更多地理解掌握了线性链表的逻辑机构和物理特性。对大一时学过的知识有了很好的巩固。困难还是很多的，比如初次运行的时候，好几十个错误，当时真的感到非常崩溃。幸亏我没有放弃，才最终完成。长舒一口气。

最后，通过这次编程，不仅仅考察了我对知识的掌握，更重要的是锻炼了我的思维能力和耐心，在最困难的时候没有放弃，今天才能如此舒心。

数据结构实验报告,一元多项式资料

数据结构课程设计报告

目录 一、任务目标,,,,,,,,,,,, 3 二、概要设计,,,,,,,,,,,, 4 三、详细设计,,,,,,,,,,,, 6 四、调试分析,,,,,,,,,,,, 8 五、源程序代码,,,,,,,,,, 8 六、程序运行效果图与说明,,,,, 15 七、本次实验小结,,,,,,,,, 16 八、参考文献,,,,,,,,,,, 16

任务目标 分析（1） a. 能够按照指数降序排列建立并输出多项式 b.能够完成两个多项式的相加，相减，并将结果输入要求：程序所能达到的功能： a.实现一元多项式的输入； b.实现一元多项式的输出； c.计算两个一元多项式的和并输出结果； d.计算两个一元多项式的差并输出结果；除任务要求外新增乘法： 计算两个一元多项式的乘积并输出结果 （2）输入的形式和输入值的范围：输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以0 0 为结束标志，结束一个多项式的输入。 输入形式： 2 3 -1 2 3 0 1 2 0 0 输入值的范围：系数为int 型，指数为float 型 3）输出的形式： 第一行输出多项式1； 第二行输出多项式2； 第三行输出多项式 1 与多项式 2 相加的结果多项式； 第四行输出多项式 1 与多项式 2 相减的结果多项式；第五行输出多项式 1 与多项式 2 相乘的结果多项式 二、概要设计 程序实现 a. 功能：将要进行运算的二项式输入输出；

b. 数据流入：要输入的二项式的系数与指数； c.数据流出：合并同类项后的二项式； d.程序流程图：二项式输入流程图； e.测试要点：输入的二项式是否正确，若输入错误则重新输入

三次样条插值、拉格朗日插值、herminte插值

三次样条插值： function s=spline(x0,y0,y2l,y2n,x) n=length(x0); km=length(x); a(1)=-0.5; b(1)=3*(y0(2)-y0(1))/(2*(x0(2)-x0(1))); for j=1:n-1 h(j)=x0(j+1)-x0(j); end for j=2:n-1 alpha(j)=h(j-1)/(h(j-1)+h(j)); beta(j)=3*((1-alpha(j))*y0(j)-y(j-1)/h(j-1)+alpha(j)*(y0(j+1)-y0(j))/h(j)); a(j)=-alpha(j)/(2+(1-alpha(j))*a(j-1)); b(j)=(beta(j)-(1-alpha(j))*b(j-1))/(2+(1-alpha(j))*a(j-1)); end m(n)=(3*(y0(n)-y0(n-1))/h(n-1)+y2n*h(n-1)/2-b(n-1))/(2+a(n-1)); for j=(n-1):-1:1 m(j)=a(j)*m(j+1)+b(j); end for k=1:km for j=1:(n-1) if ((x(k)>x0(j))&(x(k)

一元多项式求和

一元多项式求和——链表编程 一．实验名称：一元多项式求和——链表编程。 二．实验环境：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;

数值分析实验报告-插值、三次样条Word版

实验报告：牛顿差值多项式&三次样条 问题：在区间[-1,1]上分别取n=10、20用两组等距节点对龙格函数21()25f x x 作多项式插值及三次样条插值，对每个n 值，分别画出插值函数及()f x 的图形。 实验目的：通过编程实现牛顿插值方法和三次样条方法，加深对多项式插值的理解。应用所编程序解决实际算例。 实验要求： 1． 认真分析问题，深刻理解相关理论知识并能熟练应用； 2． 编写相关程序并进行实验； 3． 调试程序，得到最终结果； 4． 分析解释实验结果； 5． 按照要求完成实验报告。 实验原理： 详见《数值分析 第5版》第二章相关内容。 实验内容： （1）牛顿插值多项式 1.1 当n=10时： 在Matlab 下编写代码完成计算和画图。结果如下： 代码： clear all clc x1=-1:0.2:1; y1=1./(1+25.*x1.^2); n=length(x1); f=y1(:); for j=2:n for i=n:-1:j f(i)=(f(i)-f(i-1))/(x1(i)-x1(i-j+1)); end end syms F x p ; F(1)=1;p(1)=y1(1); for i=2:n F(i)=F(i-1)*(x-x1(i-1)); p(i)=f(i)*F(i); end

syms P P=sum(p); P10=vpa(expand(P),5); x0=-1:0.001:1; y0=subs(P,x,x0); y2=subs(1/(1+25*x^2),x,x0); plot(x0,y0,x0,y2) grid on xlabel('x') ylabel('y') P10即我们所求的牛顿插值多项式，其结果为：P10（x）=-220.94*x^10+494.91*x^8-9.5065e-14*x^7-381.43*x^6-8.504e-14*x^5+123.36*x^4+2.0 202e-14*x^3-16.855*x^2-6.6594e-16*x+1.0 并且这里也能得到该牛顿插值多项式的在[-1，1]上的图形，并和原函数进行对比（见Fig.1）。 Fig.1 牛顿插值多项式（n=10）函数和原函数图形 从图形中我们可以明显的观察出插值函数在两端点处发生了剧烈的波动，产生了极大的误差，即龙格现象，当n=20时，这一现象将更加明显。 1.2 当n=20时： 对n=10的代码进行修改就可以得到n=20时的代码。将“x1=-1:0.2:1;”改为“x1=-1:0.1:1;”即可。运行程序，我们得到n=20时的牛顿插值多项式，结果为：P20(x)= 260188.0*x^20 - 1.0121e6*x^18 + 2.6193e-12*x^17 + 1.6392e6*x^16 + 2.248e-11*x^15 - 1.4429e6*x^14 - 4.6331e-11*x^13 + 757299.0*x^12 + 1.7687e-11*x^11 - 245255.0*x^10 + 2.1019e-11*x^9 + 49318.0*x^8 + 3.5903e-12*x^7 - 6119.2*x^6 - 1.5935e-12*x^5 + 470.85*x^4 + 1.3597e-14*x^3 - 24.143*x^2 - 1.738e-14*x + 1.0 同样的，这里得到了该牛顿插值多项式的在[-1，1]上的图形，并和原函数进行对比（见Fig.2）。

C++一元多项式合并实验报告

实验二一元多项式相加问题本实验的目的是进一步熟练掌握应用链表处理实际问题的能力。 一、问题描述 一元多项式相加是通过键盘输入两个形如P 0+P 1 X1+P 2 X2+···+PnX n的多项式，经过程序运算后在屏幕上输出它 们的相加和。 二、数据结构设计 分析任意一元多项式的描述方法可知，一个一元多项式的每一个子项都由“系数—指数”两部分组成，所以可将它抽象成一个由“系数—指数对”构成线性表，由于对多项式中系数为0的子项可以不记录他的数值，对于这样的情况就不再付出存储空间来存放它了。基于这样的分析，可以采取一个带有头结点的单链表来表示一个一元多项式。具体数据结构定义为： typedef struct node { float ce; //系数域 float ex; //指数域 struct node *next; //指针域 }lnode,*linklist; 三功能（函数）设计 1、输入并建立多项式的功能模块 此模块要求按照指数递增的顺序和一定的输入格式输入各个系数不为0的子项的“系数—指数对”，输入一个子项建立一个相关的节点，当遇到输入结束标志时结束输入，而转去执行程序下面的部分。 屏幕提示： input ce & ex and end with 0： ce=1 ex=2 ce=0 ex=0 //输入结束标志 input ce & ex and end with 0： ce=2 ex=2 ce=0 ex=0 //输入结束标志 输入后程序将分别建立两个链表来描述两个一元多项式： A=X^2 B=2X^2 这两个多项式的相加的结果应该为： C=3X^2 2、多项式相加的功能模块 此模块根据在1中建立的两个多项式进行相加运算，并存放在以C为头指针的一个新建表中。可以采用以下方法进行设计： 开始时a，b分别指向A,B的开头，如果ab不为空，进行判断：如果a所指的结点的指数和b所指的结点的指数相同，将它们的系数相加做成C式中的一项，如果不一样则将小的一项加到C中。 if(a->ex==b->ex) //判断指数是否相等 {s->ce=a->ce+b->ce; if(s->ce!=0) s->ex=a->ex; else delete s; a=a->next; b=b->next; }

插值法实验报告

实验二插值法 1、实验目的： 1、掌握直接利用拉格郎日插值多项式计算函数在已知点的函数值；观察拉格郎日插值的龙格现象。 2、了解Hermite插值法、三次样条插值法原理，结合计算公式，确定函数值。 2、实验要求: 1)认真分析题目的条件和要求，复习相关的理论知识，选择适当的解决方案和算法； 2)编写上机实验程序，作好上机前的准备工作； 3)上机调试程序，并试算各种方案，记录计算的结果（包括必要的中间结果）； 4)分析和解释计算结果； 5)按照要求书写实验报告； 3、实验内容： 1) 用拉格郎日插值公式确定函数值；对函数f(x)进行拉格郎日插值，并对f(x)与插值多项式的曲线作比较。 已知函数表：（0.56160,0.82741）、（0.56280,0.82659）、（0.56401,0.82577）、（0.56521,0.82495）用三次拉格朗日插值多项式求x=0.5635时函数近似值。 2) 求满足插值条件的插值多项式及余项 1) 4、题目：插值法 5、原理： 拉格郎日插值原理： n次拉格朗日插值多项式为：L n (x)=y l (x)+y 1 l 1 (x)+y 2 l 2 (x)+…+y n l n (x)

n=1时，称为线性插值， L 1(x)=y (x-x 1 )/(x -x 1 )+y 1 (x-x )/(x 1 -x )=y +(y 1 -x )(x-x )/(x 1 -x ) n=2时，称为二次插值或抛物线插值， L 2(x)=y (x-x 1 )(x-x 2 )/(x -x 1 )/(x -x 2 )+y 1 (x-x )(x-x 2 )/(x 1 -x )/(x 1 -x 2 )+y 2 (x -x 0)(x-x 1 )/(x 2 -x )/(x 2 -x 1 ) n=i时， Li= （X-X0）……(X-X i-1)(x-x i+1) ……(x-x n) （X-X0）……(X-X i-1)(x-x i+1) ……(x-x n) 6、设计思想： 拉格朗日插值法是根据n + 1个点x0, x1, ... x n(x0 < x1 < ... x n)的函数值f (x0), f (x1) , ... , f (x n)推出n次多項式p(x)，然后n次多項式p (x)求出任意的点x对应的函数值f (x)的算法。 7、对应程序： 1 ) 三次拉格朗日插值多项式求x=0.5635时函数近似值 #include"stdio.h" #define n 5 void main() { int i,j; float x[n],y[n]; float x1; float a=1; float b=1; float lx=0; printf("\n请输入想要求解的X：\n x="); scanf("%f",&x1); printf("请输入所有点的横纵坐标：\n"); for(i=1;i

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

实验报告 课程名称：数据结构 题目：链表实现多项式相加 班级： 学号： 姓名： 完成时间：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)

一元多项式求和问题的研究与实现

一元多项式求和问题的研究与实现 学生姓名：指导老师： 摘要在数学上，一个一元多项式可按升幂表示为：A(x)=a0+a1x+a2x2+……+anxn，它由n+1个系数唯一确定，一元多项式求和实质上是合并同类项的过程。在实际应用中，多项式的指数可能很高且变化很大，在表示多项式的线性表中就会存在很多零元素。因此，采用单链表来存储一个一元多项式的每一个非零项的系数和指数，即每一个非零项对应单链表中的一个结点，且单链表按指数递增有序排列，就可实现两个一元多项式求和问题。程序通过调试运行，能基本达到设计要求，解决问题。 关键词数据结构；一元多项式；单链表；结点

1 引言 一个一元多项式可按升幂表示为：A(x)=a0+a1x+a2x2+……+a n x n，它由n+1个系数唯一确定。因此，可以用一个线性表(a0，a1，a2，……，an)来表示，每一项的指数i隐含在其系数ai的序号里。若有A(x)= a0+a1x+a2x2+……+a n x n和B(x)=b0+b1x+b2x2+……+b m x m，一元多项式求和也就是求A(x)=A(x)+B(x)，这实质上是合并同类项的过程。 1.1 设计目的 设计合理数据结构表示一元多项式，并设计高效算法实现两个一元多项式相加。 1.2 设计要求 本课程设计要求用C++实现两个一元多项式的求和问题，用带头结点的单链表村存储多项式。基本功能要求如下： 1．输入并建立多项式，输入形式为整数序列n，x1，y1，x2，y2，……，x n，y n。其中n是多项式的项数，x i和y i分别是第i项的系数和指数。 2．输出多项式，按指数升序排列。 3．多项式A(x)和B(x)相加，建立多项式A(x)+B(x)，输出相加的多项式，形式为类数学表达式。 2 需求分析 2.1 输入形式和输入值的范围 从键盘依次输入两个多项式的项数，系数和指数。系数为任意整数，项数和指数为大于等于0的整数。 2.2 输出形式 从屏幕输出，显示用户输入的多项式，并显示两多项式相加后的多项式和值。2.3 时间性能分析 所谓时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。

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

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

一实验内容 根据所学的数据结构中线性结构（线性表）的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加 二需求分析 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 主程序流程图 四详细设计 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项，对

一元多项式的运算

数据结构课程设计实验报告 专业班级： 学号： 姓名： 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

用多项式模型进行数据拟合实验报告(附代码)

实验题目： 用多项式模型进行数据拟合实验 1 实验目的 本实验使用多项式模型对数据进行拟合，目的在于： （1）掌握数据拟合的基本原理，学会使用数学的方法来判定数据拟合的情况； （2）掌握最小二乘法的基本原理及计算方法； （3）熟悉使用matlab 进行算法的实现。 2 实验步骤 2.1 算法原理 所谓拟合是指寻找一条平滑的曲线，最不失真地去表现测量数据。反过来说，对测量 的实验数据，要对其进行公式化处理，用计算方法构造函数来近似表达数据的函数关系。由于函数构造方法的不同，有许多的逼近方法，工程中常用最小平方逼近（最小二乘法理论）来实现曲线的拟合。 最小二乘拟合利用已知的数据得出一条直线或曲线，使之在坐标系上与已知数据之间的距离的平方和最小。模型主要有：1.直线型2.多项式型3.分数函数型4.指数函数型5.对数线性型6.高斯函数型等，根据应用情况，选用不同的拟合模型。其中多项式型拟合模型应用比较广泛。 给定一组测量数据()i i y x ,，其中m i ,,3,2,1,0Λ=，共m+1个数据点，取多项式P （x ），使得 min )]([020 2=-=∑∑==m i i i m i i y x p r ，则称函数P （x ）为拟合函数或最小二乘解，此时，令 ∑==n k k k n x a x p 0 )(，使得min ])([02 002=??? ? ??-=-=∑∑∑===m i n k i k i k m i i i n y x a y x p I ，其中 n a a a a ,,,,210Λ为待求的未知数，n 为多项式的最高次幂，由此该问题化为求),,,(210n a a a a I I Λ=的极值问题。 由多元函数求极值的必要条件：0)(200 =-=??∑∑==m i j i n k i k i k i x y x a a I ，其中n j ,,2,1,0Λ= 得到： ∑∑∑===+=n k m i i j i k m i k j i y x a x )(，其中n j ,,2,1,0Λ=，这是一个关于n a a a a ,,,,210Λ的线 性方程组，用矩阵表示如下所示：

两个一元多项式相加-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

一元多项式相家问题

一元多项式相加问题 # include typedef struct node{ float coef; int exp; int flg; struct node *next; }PolyNode,*PolyList; PolyNode *head_a,*head_b,*head_c; PolyList A,B,C; PolyNode *Creat_PolyNode() { PolyNode *s,*r; PolyList L; float x;int y; L=new PolyNode; L->next=NULL; r=L; cin>>x>>y; while(x||y) //输0的时候输入【0，另一个链表有的指数】{ s=new PolyNode; s->coef=x; s->exp=y; r->next=s; r=s; cin>>x>>y; } r->next=NULL; return L; } void Out_PolyNode(PolyNode *L,float a[100],int b[100]) { PolyNode *p;int i=0,j=0; p=L->next; if(p==NULL) cout<<"0"; while(p) { a[i]=p->coef; b[i]=p->exp; p=p->next; i++,j++; }

for(i=0;inext,q=B->next; while(p&&q) { if(p->exp==q->exp) { s=new PolyNode; s->coef=p->coef+q->coef; if(s->coef==0) { p=p->next; q->flg=1; } else { s->exp=p->exp; r->next=s; r=s; p->flg=1; q->flg=1; p=p->next; q=B->next; } } else if(p->exp!=q->exp&&q->next==NULL) { s=new PolyNode; s->coef=p->coef; s->exp=p->exp; r->next=s; r=s; p->flg=1; p=p->next; q=B->next; } else

三次样条插值方法的应用

CENTRAL SOUTH UNIVERSITY 数值分析实验报告

三次样条插值方法的应用 一、问题背景 分段低次插值函数往往具有很好的收敛性，计算过程简单，稳定性好，并且易于在在电子计算机上实现，但其光滑性较差，对于像高速飞机的机翼形线船体放样等型值线往往要求具有二阶光滑度，即有二阶连续导数，早期工程师制图时，把富有弹性的细长木条（即所谓的样条）用压铁固定在样点上，在其他地方让他自由弯曲，然后沿木条画下曲线，称为样条曲线。样条曲线实际上是由分段三次曲线并接而成，在连接点即样点上要求二阶导数连续，从数学上加以概括就得到数学样条这一概念。下面我们讨论最常用的三次样条函数及其应用。 二、数学模型 样条函数可以给出光滑的插值曲线（面），因此在数值逼近、常微分方程和偏微分方程的数值解及科学和工程的计算中起着重要的作用。 设区间[]b ,a 上给定有关划分b x x n =<<<= 10x a ，S 为[]b ,a 上满足下面条件的函数。 ● )(b a C S ,2∈； ● S 在每个子区间[]1,+i i x x 上是三次多项式。 则称S 为关于划分的三次样条函数。常用的三次样条函数的边界条件有三种类型： ● Ⅰ型 ()()n n n f x S f x S ''0'',==。 ● Ⅱ型 ()()n n n f x S f x S ''''0'''',==，其特殊情况为()()0''''==n n x S x S 。 ● Ⅲ型 ()() 3,2,1,0,0==j x S x S n j j ，此条件称为周期样条函数。 鉴于Ⅱ型三次样条插值函数在实际应用中的重要地位，在此主要对它进行详细介绍。 三、算法及流程 按照传统的编程方法，可将公式直接转换为MATLAB 可是别的语言即可；另一种是运用矩阵运算，发挥MATLAB 在矩阵运算上的优势。两种方法都可以方便地得到结果。方法二更直观，但计算系数时要特别注意。这里计算的是方法一的程序，采用的是Ⅱ型边界条件，取名为spline2.m 。 Matlab 代码如下： function s=spline2(x0,y0,y21,y2n,x) %s=spline2(x0,y0,y21,y2n,x) %x0,y0 are existed points,x are insert points,y21,y2n are the second

[计算机]一元多项式相加完整实验报告

[计算机]一元多项式相加完整实验报告一元多项式的相加 一实验内容 根据所学的数据结构中线性结构(线性表)的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加 二需求分析 1掌握线性结构的逻辑特性和物理特性。 2建立一元多项式。 3将一元多项式输入，并存储在内存中，并按照指数降序排列输出多项式。 4能够完成两个多项式的加减运算，并输出结果。 三概要设计 1 本程序所用到的抽象数据类型: typedef OrderedLinkList polynomial; // 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: typedef struct { // 项的表示 oat flcoef; // 系数 int expn; // 指数 term, ElemType; Void 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 存储结构 一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。 序数coef 指数exp 指针域next 创建一元多项式链表，对运算中可能出现的各种情况进行分析，实现一元多项式的相加相减操作。 3 模块划分 a) 主程序;2)初始化单链表;3)建立单链表; 4)相加多项式 4 主程序流程图 开始 申请结点空间 输入多项式各项的系数X，指数Y 输出已输出的多项式 否 是否输入正确 合并同类项 结束 四详细设计 根据一元多项式相加的运算规则:对于两个一元多项式中所有指数相

数据结构实验报告-一元多项式

数据结构课程设计报告 课题: 一元多项式 姓名： XX 学号： 201417030218 专业班级： XXXX 指导教师： XXXX 设计时间： 2015年12月30日星期三

目录 一、任务目标 (3) 二、概要设计 (4) 三、详细设计 (6) 四、调试分析 (8) 五、源程序代码 (8) 六、程序运行效果图与说明 (15) 七、本次实验小结 (16) 八、参考文献 (16)

一丶任务目标 分析 (1) a.能够按照指数降序排列建立并输出多项式 b.能够完成两个多项式的相加，相减，并将结果输入 要求：程序所能达到的功能： a.实现一元多项式的输入； b.实现一元多项式的输出； c.计算两个一元多项式的和并输出结果； d.计算两个一元多项式的差并输出结果； 除任务要求外新增乘法： 计算两个一元多项式的乘积并输出结果 （2）输入的形式和输入值的范围： 输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以0 0为结束标志，结束一个多项式的输入。 输入形式： 2 3 -1 2 3 0 1 2 0 0 输入值的范围：系数为int型，指数为float型 （3）输出的形式： 第一行输出多项式1； 第二行输出多项式2； 第三行输出多项式1与多项式2相加的结果多项式； 第四行输出多项式1与多项式2相减的结果多项式； 第五行输出多项式1与多项式2相乘的结果多项式

二、概要设计 程序实现 a. 功能：将要进行运算的二项式输入输出； b. 数据流入：要输入的二项式的系数与指数； c. 数据流出：合并同类项后的二项式； d. 程序流程图：二项式输入流程图； e. 测试要点：输入的二项式是否正确，若输入错误则重新输入。

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

项目一一元多项式的计算问题 1.1设计题目与要求 1.1.1设计题目 1）一元多项式计算 任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入； 基本要求：在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；本程序关键点是如何将输入的两个多项式相加、相减操作。 ①如何将输入的一元多项式按指数的降序排列 ②如何确定要输入的多项式的项数； ③如何将输入的两个一元多项式显示出来。 ④如何将输入的两个一元多项式进行相加操作。 ⑤如何将输入的两个一元多项式进行相减操作。 本程序是通过链表实现一元多项式的相加减操作。 1.1.2、任务定义 此程序需要完成如下的要求：将多项式按照指数降序排列建立并输出，将两个一元多项式进行相加、相减操作，并将结果输入。 a：输入多项式的项数并建立多项式； b：输出多项式，输出形式分别为浮点和整数序列，序列按指数升序排列； c：多项式a和b相加，建立多项式a+b； d：多项式a和b相减，建立多项式a-b。 e：多项式的输出。 1.2 数据结构的选择和概要设计： 1.2.1数据结构的选用 A:基于链表中的节点可以动态生成的特点，以及链表可以灵活的添加或删除节点的数据结构，为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属；例如，图1中的两个线性链表分别表示一元多项式 和一元多项式。从图中可见，每个结点表示多项式中的一项。

图1 多项式表的单链存储结构 B：本设计使用了以下数据结构： typedef struct node{ int xs; /*系数*/ int zs; /*指数*/ struct node * next; /*next指针*/ }Dnode,* Dnodelist; C：设计本程序需用到八个模块，用到以下八个子函数如下： 1.Dnodelist Creat_node(void) /*链表初始化*/ 2.int Insert_node(Dnodelist D,int xs,int zs) /*插入函数*/ 3.Dnodelist Creat_Dmeth(int length) /*创建多项式*/ 4.Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多项式相加*/ 5.Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多项式相减*/ 6.Dnodelist select(Dnodelist D1,Dnodelist D2) /*选择函数*/ 7void Show(Dnodelist D) /*显示（输出）函数*/ 8void main()主程序模块调用链一元多项式的各种基本操作模块。 1.2.2 多项式的输入 先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它； 1.2.3 两个多项式的加法 “和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下： 假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况： ①指针A所指结点的指数值<指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去； ②指针A所指结点的指数值>指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去； ③指针A所指结点的指数值=指针B所指结点的指数值，则将两个结点中的系数相加， 若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。

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

数据结构实验报告实验一：一元多项式相加 姓名：周成 学号： 13083511 专业：软件工程 任课教师：马慧珠 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"stdafx.h" #include #include #include #include #define NULL 0 typedef struct NODE { float coef; //系|ì数oy int expn; //指?数oy struct NODE *next; }NODE; NODE *Creat(int n); void print(NODE *head); NODE *AddPolyn(NODE *head1, NODE *head2); NODE *Delfirst(NODE *head, NODE *q); void InsertBefore(NODE *p1, NODE *p2); int compare(int a, int b); /*创???建?§链￠??表à¨a*/ NODE *Creat(int n) { NODE *current, *previous, *head; int i; head = (NODE *)malloc(sizeof(NODE)); /*创???建?§头a?¤结¨￠点ì?*/ previous = head; for(i = 0; i < n; i++)