一元多项式和停车场

实验内容

一．实验内容

1)实现一元多项式的相加

1实验目的：

（1）熟练掌握链表结构及有关算法的设计；

（2）掌握用链表表示特定形式的数据的方法，并能编写出有关运算的法。

2 实验要求：一元多项式求和。

把任意输入的两个多项式La，Lb输出，将这两个多项式求和并输

出其结果。

3 实验说明：

一元多项式可以用单链表表示，结点结构图示如下：

coef exp next

一元多项式链表的结点结构

2)停车场的管理

基本要求：

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。对每次输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车

场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴

纳的费用（便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。二．程序的设计思想

1）一元多项式相加的主要算法

1.工作指针pa和pb初始化；

2. while（pa存在且pb存在）执行下列三种情形之一

a. 如果pa->expn>pb->expn，则指针pa后移;

b. 如果pa->expnexpn，则

1 将结点pb插入到结点pa之前；

2 指针pb指向原指结点的下一个结点；

c. 如果pa->expn=pb->expn，则

1 pa->coef =pa->coef+pb->coef，求出合并后的系数；

2 如果pa->coef ==0，则执行下列操作，否则指针pa后移;

(1) 删除结点pa；

(2) 使指针pa指向它原指结点的下一个结点；

3 删除结点pb；

d .使指针pb指向它原指结点的下一个结点；

3. 如果pb不为空，将结点pb链接在第一个单链表的后面；

2）停车场的管理的主要思想

I.主函数部分：

对象：栈，队列；

目的：创建栈和队列并调用函数对停车场管理系统进行模拟；

要点：对栈和队列进行初始化。

II．被调函数部分：

对象：栈和队列中的结点（亦即车辆的信息）；

目的：将结点存放到栈和队列中，并作出正确的处理；

要求：根据各结点的信息，调用相应的函数或者语句，将结点入栈入队，出栈或者出队。三．编程过程中遇到的问题及解决办法

1）一元多项式

在本次试验中，我遇到过很多问题，比如链表定义之后的调用，怎样用最简单的语言实现尽量多的功能。直到完成该实验，我仍然在考虑该程序可能的优化方案，比如可以加上一个排序算法，根据指数的大小将多项式的项数进行排序，那么用户在输入时就不必考虑输入的顺序问题；再比如当用户的输入出现错误，输入了字母、符号等类型，程序如果可以提示错误并允许用户重新输入，那么除了用ASCAll码还有别的方法实现么，哪种比较简单。

2）停车场的管理

该程序在大方向上的调试是比较顺利的，只是在细节上出现了一些问题，当车辆在离开停车场时，便道中的车辆进入以后停车场内仍然显示有空位，经过多次调试才发现我在让便道中的车辆进入时没有将停车场中的栈的状态进行更改，只需将其top家1即可。

四．程序的闪光点(自我评价)

1）一元多项式

优点：用链表的方式表示一元多项式的各项数据，简单且易于实现；在输入的过程中考虑到各项的指数大小，减少了合并算法的时间；界面简单明了，可多次运算。

缺点：用户的输入过程需要非常注意，给用户带来不便。

2）停车场的管理

优点：用栈和队列来模拟停车场让整个问题显得简单，易于实现；

缺点：栈和队列这两个数学模型用在停车场管理上还是有失妥当的，现实中停车场出

口入口不可能为同一处，不可能当一辆车要离开，在它后面进来的车必须为它让路，因

此无法用栈的“后进先出”原则来模拟；而且没有考虑便道上的车在等待过程中可以中

途开走等情况，而这些都无法用队列的“先进先出”原则来模拟。五．程序源代码(以文件为单位提供)

1）一元多项式

#include

using namespace std;

typedef struct LNode

{ //项的表示，多项式的项作为LinkList的数据元素

float coef; //系数

double expn; //指数

struct LNode *next;

}LNode;

void output()

{

cout<<"************************************************"<

cout<<"************1.进行多项式的合并************"<

cout<<"************2.进行下一次合并************"<

cout<<"************0.退出************"<

cout<<"************************************************"<

void creat(LNode *L)

{ //建立多项式，n为多项式的长度

float coef;

double expn;

int m;

LNode *head,*p;

L->next=NULL;

head=L;

cout<<"\n请输入L项的个数的m:"<<"m=";

cin>>m;

cout<<"请输入系数和指数(按系数依次递减的方式输入):"<<'\n';

for(int i=1;i<=m;i++)

{//多项式的建立方法

p=(LNode*)malloc(sizeof(LNode));

cin>>coef>>expn;

p->coef=coef;

p->expn=expn;

p->next=NULL;

L->next=p;

L=p;

}

}

void add(LNode *pa,LNode *pb)

{ //用于链表的合并使用完成多项式的相加运算float sum;

LNode *p,*q,*pre,*temp;

p=pa->next;

q=pb->next;

pre=pa;

while(p!=NULL&&q!=NULL)

{

if(p->expn>q->expn)

{

pre->next=p;

pre=pre->next;

p=p->next;

}

else if(p->expn==q->expn)

{

float sum=0;

sum=p->coef+q->coef;

if(sum!=0) {

p->coef=sum;

pre->next=p;

pre=pre->next;

p=p->next;

temp=q;

q=q->next;

delete temp;

}

else

{

temp=p->next;

delete p;

p=temp;

temp=q->next;

delete q;

q=temp;

}

}

else

{

pre->next=q;

pre=pre->next;

q=q->next;

}

}

if(p!=NULL) //将多项式A中剩余的结点加入到和多项式中pre->next=p;

else

pre->next=q;

}

void print(LNode *L)

{//多项式的输出函数

int n; //n为多项式的长度

LNode *p;

p=L->next;

n=0;

while(p)

{

n++;

if(n==1)

cout<coef<<"*x^"<expn;

else if(p->coef>0)

{

n++;

cout<<"+";

cout<coef<<"*x^"<expn;

}

else

{

n++;

cout<coef<<"*x^"<expn;

}

p=p->next;

}

}

int fn(LNode *Lb,LNode *La)

{ //多项式函数的调用

creat(La);

creat(Lb);

cout<<"\nLa=";

print(La);

cout<<"\nLb=";

print(Lb);

add(La,Lb);

cout<<"\nLc=";

print(La);

cout<

return 0;

}

void main()

{

LNode *La,*Lb;

int n;

output();

La=(LNode*)malloc(sizeof(LNode));

Lb=(LNode*)malloc(sizeof(LNode));

wei:while(1)

{cin>>n;

switch (n)

{

case 1: {fn(La,Lb);goto wei;}

case 2: {fn(La,Lb); goto wei;}

case 3:break;

default:{cout<<"input error!"<

break;

}

}

2）停车场的管理

#include

#include

#include

#include

using namespace std;

#define n 2

#define MAXSIZE 14

#define fee 1000

struct QNode

{ //链队结点的类型

int data;

QNode *next;

};

struct car //用该结构体来存放车编号和时间信息

{

int num;

clock_t time;

};

struct stack //用该栈来模拟停车场

{

car G[n];

int top;

};

struct car1 //用该结构体来存放临时让出的车辆的编号以及时间信息{

int num1;

clock_t time1;

};

struct stack1 //用该栈来模拟临时让出的车辆的停靠场地

{

car1 H[MAXSIZE];

int top1;

};

struct Queue //用该链队来模拟便道

{

QNode *front,*rear;

int num2;

};

void putout()

{

cout<<"**************************************************"<<'\n';

cout<<"* 停车场管理系统*"<<'\n';

cout<<"* 说明：1 显示停车场当前车辆数*"<<'\n';

cout<<"* 2 有新车(一辆)进入停车场*"<<'\n';

cout<<"* 3 某车要出停车场*"<<'\n';

cout<<"* 4 退出*"<<'\n';

cout<<"**************************************************"<<'\n'; }

void enter(car a,stack *s,Queue *q)

{// 实现车辆进入(默认为每次进一辆车)时的操作

a.time = clock();

if(s->top==n-1)

{//有车进入时先看停车场是否满，如已满，则需进入便道等待

cout<<"停车场已满,请入便道等待"<

QNode *c;

c=(QNode*)malloc(sizeof(QNode));

c->data = n;

(q->num2)++;

c->next = NULL;

q->rear = c;

cout<<"便道上车辆的数量为:"<num2<<'\n';

}

else

{

(s->top)++;

(s->G[s->top]).num = a.num - 1;

(s->G[s->top]).time = a.time;

cout<<"该车的停车编号为"<<((s->G[s->top]).num)%n<

}

}

void exit(stack *s,Queue *q,car b)

{//实现车辆离开时的操作

int i,j;

float y;

double duration;

QNode *p;

stack1 *k;

cout<<"请输入要离开的车辆编号：";

cin>>b.num;

b.time = clock();

if(b.num==(s->G[s->top]).num+1) //若待离开车为最后进停车场的车的情况

{//直接计算停车时间，费用并离去

duration = (double)(b.time-(s->G[s->top]).time) / CLOCKS_PER_SEC;

y=fee*duration/3600;

cout<<"该车停车的总时间(/千分之一小时)是："<

s->top--;

cout<<"场内已有空位，请便道中的车辆进入\n";

if(q->num2==0)

{//若便道上无车，函数返回

cout<<"便道是空的\n";

}

else

{//若便道上有车，第一辆车进停车场

cout<<"停车场内已有空位，请便道上第一辆车进入"<

p=(QNode*)malloc(sizeof(QNode));

p = q->front->next;

(q->front)++;

(s->G[s->top]).num=p->data; //并存入其车牌编号及进停车场的时间

(s->G[s->top]).time = clock();

(s->top)++;

cout<<"该车的编号为"<

delete p;

(q->num2)--;

if(q->front->next==NULL)

q->rear=q->front; //此时便道上无车

}

}

else //待离开的车不是最后进停车场的那辆车的情况{

for(i=0;itop;i++) //先找到待离开车在停车场中的位置

{

if((s->G[i]).num!=b.num) continue;

else break;

}

if(i>=s->top)

{

cout<<"车号输入错误!\n";

}

duration = (double)(b.time-(s->G[s->top]).time) / CLOCKS_PER_SEC;

y=fee*duration/3600; //计算待离开车的停车时间并计算费用

cout<<"该车停车的总时间(/千分之一小时)是："<

k=(stack1 *)malloc(sizeof(stack1)); //设立一个新栈临时停放为该车离开而让路的车辆

k->top1=-1;

for(j=s->top;j>i;j--)

{

k->top1++;

(k->H[k->top1]).num1=(s->G[j]).num;

(k->H[k->top1]).time1=(s->G[j]).time;

(s->top)--;

}

(s->top)--;

cout<<"车已退出，请临时栈道中的车辆进场"<

while(k->top1>=0) //将临时栈道中的车重新开入停车场中

{

(s->top)++;

(s->G[s->top]).num=(k->H[k->top1]).num1;

(s->G[s->top]).time=(k->H[k->top1]).time1;

(k->top1)--;

}

if(q->num2==0)

{//若便道上无车，则返回2，无车开入停车场中

cout<<"便道是空的\n";

}

else

{//若便道上有车，则第一辆车开入停车场中

cout<<"停车场内已有空位，请便道上第一辆扯进入"<

p=(QNode*)malloc(sizeof(QNode));

p = q->front;

(q->front)++;

(s->G[s->top]).num=p->data;

(s->G[s->top]).time=b.time;

delete p;

(s->top)++;

(q->num2)--;

if(q->front->next==NULL)

q->rear=q->front;

}

}

}

void elapsed_time()

{

printf("Elapsed time:%u secs.\n",clock()/CLOCKS_PER_SEC);

}

void main()

{

int m;

stack *s;

Queue *q;

QNode *p;

car a;

s=(stack*)malloc(sizeof(stack));

s->top = -1;

q=(Queue*)malloc(sizeof(Queue));

p=(QNode*)malloc(sizeof(QNode));

p->next = NULL;

q->front = q->rear =p;

q->num2 = 0;

a.num=0;

a.time = clock();

putout();

cout<<"停车场能容纳的总的车数n为2";

while (1)

{

w: cout<<"\n请输入要执行的操作：";

cin>>m;

switch(m)

{

case 1:cout<<"当前已停车辆数为:"<top+1<

case 2:++(a.num);enter(a,s,q);goto w;

case 3:exit(s,q,a);goto w;

case 4:break;

}

break;

}

}

实验总结

在本次试验中，我们学习和实践了链表结构、栈与队列的结构和其相关运算，基本掌握链表结构、栈与队列的结构及有关算法的设计；大致掌握了用链表表示特定形式的数据的方法，用栈和队列实现现实问题，并能编写出有关程序的算法。在这一次编写程序的过程中，我更深层次的体会到了扎实的学习基础对于编程设计的必要性，在本次设计中我还是遇到过很多问题，在解决的过程中，发现原因都处在最简单也最基础的地方，而这些地方往往又是容易被忽略的，所以良好的写程序的习惯就显得非常必要，这也是我们一直都在强调和努力的地方。

顺序链式一元多项式加法、减法、乘法运算的实现

1.1设计内容及要求 1)设计内容 （1）使用顺序存储结构实现多项式加、减、乘运算。 例如： 10321058)(2456+-+-+=x x x x x x f ,x x x x x x g +--+=23451020107)( 求和结果：102220128)()(2356++-+=+x x x x x g x f （2）使用链式存储结构实现多项式加、减、乘运算， 10305100)(1050100+-+=x x x x f ，x x x x x x g 320405150)(10205090+++-= 求和结果：1031040150100)()(102090100++-++=+x x x x x x g x f 2）设计要求 （1）用C 语言编程实现上述实验内容中的结构定义和算法。 （2）要有main()函数，并且在main()函数中使用检测数据调用上述算法。 （3）用switch 语句设计如下选择式菜单。 ***************数据结构综合性实验**************** *******一、多项式的加法、减法、乘法运算********** ******* 1.多项式创建 ********** ******* 2.多项式相加 ********** ******* 3.多项式相减 ********** ******* 4.多项式相乘 ********** ******* 5.清空多项式 ********** ******* 0.退出系统 ********** ******* 请选择（0—5） ********** ************************************************* *请选择（0-5）: 1.2数据结构设计 根据下面给出的存储结构定义： #define MAXSIZE 20 //定义线性表最大容量

一元多项式加减乘除运算

中国计量学院实验报告 实验课程：算法与数据结构实验名称：一元二项式班级：学号： 姓名：实验日期： 2013-5-7 一．实验题目： ①创建2个一元多项式 ②实现2个多项式相加 ③实现2个多项式相减 ④实现2个多项式相乘 ⑤实现2个多项式相除 ⑥销毁一元多项式 实验成绩：指导教师：

二．算法说明 ①存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储 空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 ②加法算法

三．测试结果 四．分析与探讨 实验数据正确，部分代码过于赘余，可以精简。 五．附录：源代码#include<> #include<> #include<> typedef struct Polynomial { float coef; int expn; struct Polynomial *next; }*Polyn,Polynomial; 出多项式a和b\n\t2.多项式相加a+b\n\t3.多项式相减a-b\n"); printf("\t4.多项式相除a*b\n\t5.多项式相除a/b\n\t6.销毁多项式\n"); printf("\t7.退出

\n*********************************** ***********\n"); printf("执行:"); scanf("%d",&flag); switch(flag) { case(1): printf("多项式a：");PrintPolyn(pa); printf("多项式b：");PrintPolyn(pb);break; case(2): pc=AddPolyn(pa,pb); printf("多项式a+b：");PrintPolyn(pc); DestroyPolyn(pc);break; case(3): pd=SubtractPolyn(pa,pb); printf("多项式a-b：");PrintPolyn(pd); DestroyPolyn(pd);break; case(4): pf=MultiplyPolyn(pa,pb); printf("多项式a*b：");PrintPolyn(pf); DestroyPolyn(pf);break; case(5): DevicePolyn(pa,pb); break; case(6): DestroyPolyn(pa); DestroyPolyn(pb); printf("成功销毁2个一元二项式\n"); printf("\n接下来要执行的操作:\n1 重新创建2个一元二项式 \n2 退出程序\n"); printf("执行:"); scanf("%d",&i); if(i==1) { // Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf("请输入a的项数:"); scanf("%d",&m); pa=CreatePolyn(pa,m);// 建立多项式a printf("请输入b的项

数据结构中实现一元多项式简单计算

数据结构中实现一元多项式简单计算： 设计一个一元多项式简单的计算器。 基本要求： 一元多项式简单计算器的基本功能为： （1）输入并建立多项式； （2）输出多项式； （3）两个多项式相加，建立并输出和多项式； （4）两个多项式相减，建立并输出差多项式； #include #include #define MAX 20 //多项式最多项数 typedef struct//定义存放多项式的数组类型 { float coef; //系数 int exp; //指数 } PolyArray[MAX]; typedef struct pnode//定义单链表结点类型 { float coef; //系数 int exp; //指数 struct pnode *next; } PolyNode; void DispPoly(PolyNode *L) //输出多项式 { PolyNode *p=L->next; while (p!=NULL) { printf("%gX^%d ",p->coef,p->exp); p=p->next; } printf("\n"); } void CreateListR(PolyNode *&L,PolyArray a,int n) //尾插法建表 { PolyNode *s,*r;int i; L=(PolyNode *)malloc(sizeof(PolyNode)); //创建头结点 L->next=NULL; r=L; //r始终指向终端结点,开始时指向头结点for (i=0;i

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

一元多项式的计算—加，减 摘要(题目)一元多项式计算 任务：能够按照指数降序排列建立并输出多项式； 能够完成两个多项式的相加、相减，并将结果输入； 目录 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) //显示输入的多项式

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

课程设计成果 学院: 计算机工程学院班级: 13计科一班 学生姓名: 学号: 设计地点（单位）： 设计题目：一元多项式的计算 完成日期：年月日 成绩(五级记分制): _________________ 教师签名:_________________________ 目录 1 需求分析 ......................................................................... 错误!未定义书签。 2 概要设计 ......................................................................... 错误!未定义书签。 2.1一元多项式的建立 ............................................................... 错误!未定义书签。 2.2显示一元多项式 ................................................................... 错误!未定义书签。 2.3一元多项式减法运算 ........................................................... 错误!未定义书签。 2.4一元多项式加法运算 ........................................................... 错误!未定义书签。 2.5 设计优缺点.......................................................................... 错误!未定义书签。3详细设计 .......................................................................... 错误!未定义书签。 3.1一元多项式的输入输出流程图........................................... 错误!未定义书签。 3.2一元多项式的加法流程图................................................... 错误!未定义书签。 3.3一元多项式的减法流程图.................................................. 错误!未定义书签。 3.4用户操作函数....................................................................... 错误!未定义书签。4编码 .................................................................................. 错误!未定义书签。5调试分析 .......................................................................... 错误!未定义书签。4测试结果及运行效果...................................................... 错误!未定义书签。5系统开发所用到的技术.................................................. 错误!未定义书签。参考文献 ............................................................................. 错误!未定义书签。附录全部代码................................................................... 错误!未定义书签。

一元多项式求和

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

数据结构一元多项式报告

一元多项式计算： 程序要求： 1）、能够按照指数降序排列建立并输出多项式； 2）、能够完成两个多项式的相加、相减，并将结果输入。 概要设计： 1.功能：将要进行运算的多项式输入输出。 2.数据流入：要输入的多项式的系数与指数。 3.数据流出：合并同类项后的多项式。 4.程序流程图：多项式输入流程图如图3.2.1所示。 5.测试要点：输入的多项式是否正确，若输入错误则重新输入 2、多项式的加法 （1）功能：将两多项式相加。 （2）数据流入：输入函数。 （3）数据流出：多项式相加后的结果。 （4）程序流程图：多项式的加法流程图如图3.2.2所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。

3、多项式的减法 （1）功能：将两多项式相减。 （2）数据流入：调用输入函数。 （3）数据流出：多项式相减后的结果。 （4）程序流程图：多项式的减法流程图如图3.2.3所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。

详细代码： #include #include #include using namespace std; struct Node { float coef;//结点类型 int exp; }; typedef Node polynomial;

struct LNode { polynomial data;//链表类型 LNode *next; }; typedef LNode* Link; void CreateLink(Link &L,int n); void PrintList(Link L); void PolyAdd(Link &pc,Link pa,Link pb); void PolySubstract(Link &pc,Link pa,Link pb); void CopyLink(Link &pc,Link pa); void PolyMultiply(Link &pc,Link pa,Link pb); int JudgeIfExpSame(Link pa,Link e); void DestroyLink(Link &L); int CompareIfNum(int i); void DestroyLink(Link &L) { Link p; p=L->next; while(p) { L->next=p->next; delete p; p=L->next; } delete L; L=NULL; } //创建含有n个链表类型结点的项，即创建一个n项多项式void CreateLink(Link &L,int n) { if(L!=NULL) { DestroyLink(L); } Link p,newp; L=new LNode; L->next=NULL; (L->data).exp=-1;//创建头结点 p=L; for(int i=1;i<=n;i++) { newp=new LNode; cout<<"请输入第"<

C语言一元多项式计算

C语言一元多项式计算集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#

#include <> #include <> #include <> #define LEN sizeof(node) //结点构造 typedef struct polynode { int coef; //系数 int exp; //指数 struct polynode *next; }node; node * create(void) { node *h,*r,*s; int c,e; h=(node *)malloc(LEN); r=h; printf("系数："); scanf("%d",&c); printf("指数："); scanf("%d",&e); while(c!=0) { s=(node *)malloc(LEN); s->coef=c; s->exp=e; r->next=s; r=s; printf("系数："); scanf("%d",&c); printf("指数："); scanf("%d",&e); } r->next=NULL; return(h);

} void polyadd(node *polya, node *polyb) { node *p,*q,*pre,*temp; int sum; p=polya->next; q=polyb->next; pre=polya; while(p!=NULL&&q!=NULL) { if(p->exp>q->exp) { pre->next=p; pre=pre->next; p=p->next; } else if(p->exp==q->exp) { sum=p->coef+q->coef; if(sum!=0) { p->coef=sum; pre->next=p;pre=pre->next;p=p->next; temp=q;q=q->next;free(temp); } else { temp=p->next;free(p);p=temp; temp=q->next;free(q);q=temp; } } else { pre->next=q; pre=pre->next; q=q->next; } } if(p!=NULL) pre->next=p; else pre->next=q; } void print(node * p) {

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

#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; }

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

一元多项式求和问题的研究与实现 学生姓名：指导老师： 摘要在数学上，一个一元多项式可按升幂表示为：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 时间性能分析 所谓时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。

一元多项式计算问题课程设计

长沙学院课程设计说明书 题目一元多项式计算问题系(部) 计算机系 专业(班级) 10级软件D班 姓名向栋良 学号2010022D08 指导教师邓旭东 起止日期2011.9.4-2011.9.8

课程设计任务书 课程名称：数据结构与算法 设计题目：一元多项式计算问题 已知技术参数和设计要求： 问题描述： 设计一个稀疏多项式简单计算器 基本要求： (1)输入并分别建立多项式A和B (2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2……，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列 (3)完成两个多项式的相加、相减，并将结果输出； 测试数据： (1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2 (2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7 (3) A+B A=x3+x1B=-x3-x1 (4) A+B A=0 B=x7+x5+x3+x1 (5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x 选作内容： （1）.多项式在x=1时的运算结果 （2）求多项式A和B的乘积 设计工作量： 40课时 日期节次地点设计方式9月4日（周日）1-4 科1408 讲授内容 9月4日（周日）5-8 科1608 答疑 9月5日（周一）1-4科1408上机调试 9月5日（周一）5-8 科1608 答疑 9月6日（周二）1-4科1408上机调试 9月6日（周二）5-8 科1608 答疑 9月7日（周三）1-4科1408上机调试 9月7日（周三）5-8 科1608 答疑 9月8日（周四）1-4科1608答疑 9月8日（周四）5-8 科1408 答辩

一元多项式计算器

一元多项式计算器 目录 摘要 (1) 1绪论 (1) 2系统分析 (1) 2.1功能需求 (1) 2.2数据需求 (1) 2.3性能需求 (1) 3总体设计 (2) 3.1系统设计方案 (2) 3.2功能模块设计 (2) 4详细设计 (3) 4.1建立多项式 (4) 4.2多项式相加 (4) 4.3多项式相减 (5) 4.4多项式相乘 (5) 4.5计算器主函数 (6) 5调试与测试 (7) 5.1调试 (7) 5.2测试 (8) 6结论 (9) 结束语 (9) 参考文献 (9) 附录1－用户手册 (10) 附录2－源程序 (12)

摘要 随着生活水平的提高，现代科技也日益发达。日常生活中多位计算再所难免，因此设计一个简单计算器可解决许多不必要的麻烦。 开发这样一个程序主要运用了C的结点，链表等方面知识。系统主要实现了多项式的建立，多项式的输入输出，以及多项式加减乘等运算。 报告主要从计算器的程序段，对输入输出数据的要求，计算器的性能，以及总体的设计来介绍此计算器程序的实现过程。 关键词：多项式；链表；结点 1绪论 随着日益发达的科技，计算器已应用于各行各业。设计一个计算器需要运用C中多方面知识，更是以多项式的建立，输入输出，以及结点，链表为主。（扩充） 任务书。。。。。 2系统分析 2.1 功能需求 多项式的建立多项式输入输出多项式加减乘等运算 2.2数据需求 在输入过程中，首先要确定输入的数据，数据不能是字母，只能是数字。不能连续输入数据，必须按要求配以空格输入要计算的数据。 (1) 链节节点数字 (2) 数字 2.3 性能需求 系统必须安全可靠，不会出现无故死机状态，速度不宜过慢。

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

项目一一元多项式的计算问题 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所示，图中的长方框表示已被释放的结点。

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

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

一实验内容 根据所学的数据结构中线性结构（线性表）的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加 二需求分析 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代表第二个一元二次方程）

一元多项式相家问题

一元多项式相加问题 # 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

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

一元多项式的运算

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

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