当前位置：文档之家 › 数据结构课程设计-一元多项式计算器

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

  • 格式：doc
  • 大小：186.30 KB
  • 文档页数：11

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

一、 需求分析 1. 问题描述 设计一个一元稀疏多项式简单计算器。 2. 基本要求 一元稀疏多项式简单计算器的基本功能是： (1)输入并建立多项式。 (2)输出多项式，输出形式为整数序列：n, c1, e1, c2, e2, ········,cn, en ，其中n是多项式的项数，ci,ei分别是第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中的每个元素包含一个表示系数的实数和表示指数的整数} 数据关系：R1={ai-1,ai∈D,且ai-1中的指数基本操作： Insert(p,h) 初始条件：h已存在。 操作结果：插入p项。 CreateLinklist(head, m) 操作结果：建立一个头指针为head、项数为m的一元多项式。 DestroyLinklist( p) 初始条件：一元多项式p已存在。 操作结果：销毁一元多项式p。 PrintLinklist( P) . . 初始条件：一元多项式p已存在。 操作结果：输出一元多项式p。 Compare(a,b) 初始条件：项a,b已存在。 操作结果：比较a,b中x的指数的大小。 AddLinklist(pa,pb) 初始条件：一元多项式pa,pb已存在。 操作结果：完成一元多项式pa,pb的相加运算。 SubtractionLinklist(Sa,Sb) 初始条件：一元多项式Sa,Sb已存在。 操作结果：完成一元多项式Sa,Sb的相减运算。 } ATD Ploynomial

三、详细设计（源代码） （使用C语言） #include #include #define maxlen 10 #define large 999

typedef struct Linklistomial { float coef; int expn; struct Linklistomial *next; }Linklistomial,*Linklist;//结点类型，指针类型

void Insert(Linklist p,Linklist h) {// h已存在插入p项 if(p->coef==0) free(p);//系数为0的话释放结点 else { Linklist q1,q2; q1=h; q2=h->next; while(q2&&p->expnexpn) { //查找插入位置 q1=q2; q2=q2->next; } if(q2&&p->expn==q2->expn) { //将指数相同相合并 q2->coef+=p->coef; . . free(p); if(!q2->coef) {//系数为0的话释放结点 q1->next=q2->next; free(q2); } } else { //指数为新时将结点插入 p->next=q2; q1->next=p; } } }

Linklist CreateLinklist(Linklist head,int m) {//建立一个头指针为head、项数为m的一元多项式 int i; Linklist p; p=head=(Linklist)malloc(sizeof(struct Linklistomial)); head->next=NULL; for(i=0;i{ p=(Linklist)malloc(sizeof(struct Linklistomial));//建立新结点以接收数据 printf("请输入第%d项的系数与指数:",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); //调用Insert函数插入结点 } return head; }

void DestroyLinklist(Linklist p) {//销毁多项式p Linklist D1,D2; D1=p; while(D1) { D2=D1->next; free(D1); D1=D2; } }

void PrintLinklist(Linklist P) {//输出一元多项式p Linklist q=P->next; . . int flag=1; //项数计数器 if(!q) { //若多项式为空，输出0 putchar('0'); printf("\n"); return; } while(q) { if(q->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项 if(q->coef!=1&&q->coef!=-1) { //系数非1或-1的普通情况 printf("%g",q->coef); if(q->expn==1) putchar('X'); else if(q->expn) printf("X^%d",q->expn); } else { if(q->coef==1) { if(!q->expn) putchar('1'); else if(q->expn==1) putchar('X'); else printf("X^%d",q->expn); } if(q->coef==-1) { if(!q->expn) printf("-1"); else if(q->expn==1) printf("-X"); else printf("-X^%d",q->expn); } } q=q->next; flag++; } printf("\n"); }

int Compare(Linklist a,Linklist b) . . {//比较a,b中x的指数的大小 if(a&&b) { if(!b||a->expn>b->expn) return 1; else if(!a||a->expnexpn) return -1; else return 0; } else if(!a&&b)//a多项式已空，但b多项式非空 return -1; else//b多项式已空，但a多项式非空 return 1; }

Linklist AddLinklist(Linklist pa,Linklist pb) {//求解并建立多项式a+b，返回其头指针 Linklist qa=pa->next; Linklist qb=pb->next; Linklist headc,hc,qc; hc=(Linklist)malloc(sizeof(struct Linklistomial));//建立头结点 hc->next=NULL; headc=hc; while(qa||qb) { qc=(Linklist)malloc(sizeof(struct Linklistomial)); switch(Compare(qa,qb)) { case 1: { qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; } case 0: { qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; }

合集下载

一元稀疏多项式计算器C语言课程设计

一元稀疏多项式计算器C语言课程设计

2014-2015学年第二学期《软件工程》课程设计报告题目：一元稀疏多项式计算器专业：计算机科学与技术班级：计算机科学与技术（2）班姓名：指导教师：成绩：一、问题描述 (3)二、需求分析 (3)三、概要设计 (4)四、详细设计 (5)五、源代码 (6)六、程序测试 (18)七、使用说明 (24)八、课设总结 (25)一、问题描述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.02.2思路分析：①一般情况下的一元n次多项式可写成pn(x)=p1xe1+p2xe2+……+pmxem其中，p1是指数为ei的项的非零系数，且满足0≦e1<e2<……<em=n ,若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表（（p1,e1）,(p2,e2),……,(pm,em)）便可惟一确定多项式pn(x)。

②用两个带表头结点的单链表分别存储两个多项式③根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；④只需要将第二个多项式的系数改为其相反数，然后根据一元多项式相加的运算规则便可以得到其相应的“差多项式”三、概要设计图3-1功能模块图为实现上述程序功能，用带表头结点的单链表存储多项式。

一元稀疏多项式计算器数据结构

一元稀疏多项式计算器数据结构

一元稀疏多项式计算器数据结构一元稀疏多项式计算器是一种用于计算多项式的工具，该工具可以用于代数计算、数学分析以及计算机科学中的算法设计。

它可以通过一种特殊的数据结构来存储多项式，并可以对其进行加法、减法、乘法、除法等运算。

这种数据结构被称为稀疏多项式，它是一种基于链表的数据结构。

在稀疏多项式中，每个节点表示一个单项式，节点的数据包含该单项式的系数和指数。

在一个稀疏多项式中，只有少数几个节点表示一个多项式，这就是稀疏性的来源。

稀疏多项式的加法和减法非常简单，只需要对两个多项式的对应节点进行加减即可。

而稀疏多项式的乘法需要更复杂的算法。

乘法的过程中需要将两个多项式的每个单项式乘起来，并将同类项合并成一个新的多项式。

这个过程涉及到大量的链表操作，但只要注意一些细节，将会得到正确的结果。

除了基本的加法、减法、乘法运算，一元稀疏多项式计算器还有一个非常重要的运算，那就是求导。

求导是一种将多项式每个单项式的指数减一，并将系数乘以指数的运算。

它常用于解决微积分、概率论等问题。

求导操作可以通过修改节点的指数和系数来实现。

在计算机科学中，稀疏多项式可以用于设计高效的算法，例如在数论、密码学、图像处理、计算器表达式求值等方面。

稀疏多项式的优点在于它可以有效地节省存储空间和计算时间。

通过动态链表的形式，可以轻松地添加、删除节点，使得稀疏多项式非常适合用于处理大规模的数据。

总的来说，一元稀疏多项式计算器是一种非常实用的工具。

它可以用于解决多项式运算问题，并可以为计算机科学方面的算法设计提供很大的帮助。

通过了解这种数据结构，我们可以更深入地理解代数学、微积分学等数学原理，并且能够更好地应用于实际问题中。

一元稀疏多项式计算器(数据结构)

一元稀疏多项式计算器(数据结构)

院系：计算机科学学院专业：软件工程年级： 2013级课程名称：数据结构姓名：韦宜（201321092034）指导教师：宋中山2015年 12 月 15日题目：设计一个一元稀疏多项式简单计算器班级：软件工程1301 姓名：韦宜学号：201321092034 完成日期：12月15日一、需求分析问题描述：设计一个一元多项式加法器基本要求：输入并建立多项式；(2)两个多项式相加；(3)输出多项式：n, c1, e1, c2, e2, …cn , en, 其中，n是多项式项数，ci和ei分别是第 i 项的系数和指数，序列按指数降序排列。

(4)计算多项式在x处的值；(5)求多项式的导函数。

软件环境：Windows，UNIX，Linux等不同平台下的Visual C++ 6.0硬件环境: 512MB内存,80Gb硬盘,Pentium4 CPU,CRT显示器。

概要分析本程序有五个函数：PolyNode *Input()(输入函数)；PolyNode *Deri(PolyNode *head)（求导函数）；PolyNode * Plus(PolyNode *A,PolyNode *B)（求和函数）；void Output(PolyNode*head)（输出函数）；int main()（主函数）本程序可使用带有附加头结点的单链表来实现多项式的链表表示，每个链表结点表示多项式的一项，命名为node，它包括两个数据成员：系数coef和指数exp，他们都是公共数据成员，*next为指针域，用链表来表示多项式。

适用于不定的多项式，特别是对于项数再运算过程中动态增长的多项式，不存在存储溢出的问题。

其次，对于某些零系数项，在执行加法运算后不再是零系数项，这就需要在结果多项式中增添新的项；对于某些非零系数项，在执行加法运算后可能是零系数项，这就需要在结果多项式中删去这些项，利用链表操作，可以简单的修改结点的指针以完成这种插入和删除运算（不像在顺序方式中那样，可能移动大量数据项）运行效率高。

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

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

#include<stdio.h>#include<malloc.h>#include<stdlib.h>//定义多项式的项typedef struct Polynomial{float coef;int expn;struct Polynomial *next;}*Polyn,Polynomial;void Insert(Polyn p,Polyn h){if(p->coef==0) free(p);//系数为0的话释放结点 else{Polyn q1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->expn){//查找插入位置q1=q2;q2=q2->next;}if(q2&&p->expn==q2->expn){//将指数相同相合并q2->coef+=p->coef;free(p);if(!q2->coef){//系数为0的话释放结点q1->next=q2->next;free(q2);}}else{//指数为新时将结点插入p->next=q2;q1->next=p;}}}Polyn CreatePolyn(Polyn head,int m){//建立一个头指针为head、项数为m的一元多项式Polyn p;p=head=(Polyn)malloc(sizeof(struct Polynomial));head->next=NULL;for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据printf("请输入第%d项的系数与指数:",i+1);scanf("%f %d",&p->coef,&p->expn);Insert(p,head); //调用Insert函数插入结点}return head;}void DestroyPolyn(Polyn p){//销毁多项式pPolyn q1,q2;q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;q2=q2->next;}}void PrintPolyn(Polyn P){Polyn q=P->next;int flag=1;//项数计数器if(!q){ //若多项式为空，输出0putchar('0');printf("\n");return;}while(q){if(q->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项 if(q->coef!=1&&q->coef!=-1){//系数非1或-1的普通情况printf("%g",q->coef);if(q->expn==1) putchar('X');else if(q->expn) printf("X^%d",q->expn);}else{if(q->coef==1){if(!q->expn) putchar('1');else if(q->expn==1) putchar('X');else printf("X^%d",q->expn);}if(q->coef==-1){if(!q->expn) printf("-1");else if(q->expn==1) printf("-X");else printf("-X^%d",q->expn);}}q=q->next;flag++;}printf("\n");}int compare(Polyn a,Polyn b){if(a&&b){if(!b||a->expn>b->expn) return 1;else if(!a||a->expn<b->expn) return -1;else return 0;}else if(!a&&b) return -1;//a多项式已空，但b多项式非空else return 1;//b多项式已空，但a多项式非空}Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多项式a+b，返回其头指针 Polyn qa=pa->next;Polyn qb=pb->next;Polyn headc,hc,qc;hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点hc->next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(struct Polynomial));switch(compare(qa,qb)){case 1:{qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;}case 0:{qc->coef=qa->coef+qb->coef;qc->expn=qa->expn;qa=qa->next;qb=qb->next;break;}case -1:{qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;}}if(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}else free(qc);//当相加系数为0时，释放该结点}return headc;}Polyn SubtractPolyn(Polyn pa,Polyn pb){//求解并建立多项式a-b，返回其头指针Polyn h=pb;Polyn p=pb->next;Polyn pd;while(p){ //将pb的系数取反p->coef*=-1;p=p->next;}pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next) //恢复pb的系数p->coef*=-1;return pd;}int ValuePolyn(Polyn head,int x){//输入x值，计算并返回多项式的值Polyn p;int i;int sum=0,t;for(p=head->next;p;p=p->next){t=1;for(i=p->expn;i!=0;){if(i<0){t/=x;i++;}//指数小于0，进行除法else{t*=x;i--;}//指数大于0，进行乘法}sum+=p->coef*t;}return sum;}Polyn Derivative(Polyn head){//求解并建立导函数多项式，并返回其头指针Polyn q=head->next,p1,p2,hd;hd=p1=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hd->next=NULL;while(q){if(q->expn!=0){ //该项不是常数项时p2=(Polyn)malloc(sizeof(struct Polynomial));p2->coef=q->coef*q->expn;p2->expn=q->expn-1;p2->next=p1->next;//连接结点p1->next=p2;p1=p2;}q=q->next;}return hd;}Polyn MultiplyPolyn(Polyn pa,Polyn pb){//求解并建立多项式a*b，返回其头指针Polyn hf,pf;Polyn qa=pa->next;Polyn qb=pb->next;hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点hf->next=NULL;for(;qa;qa=qa->next){for(qb=pb->next;qb;qb=qb->next){pf=(Polyn)malloc(sizeof(struct Polynomial));pf->coef=qa->coef*qb->coef;pf->expn=qa->expn+qb->expn;Insert(pf,hf);//调用Insert函数以合并指数相同的项}}return hf;}void main(){int m,n,a,x;char flag;Polyn pa=0,pb=0,pc;printf(" 欢迎使用多项式操作程序\n\n");printf("请输入a的项数:");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多项式aprintf("请输入b的项数:");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多项式b//输出菜单printf("*******************************************************\n");printf(" * 多项式操作程序*\n");printf(" * *\n");printf(" * A:输出多项式 B:输出多项式 b*\n");printf(" * *\n");printf(" * C:输出a的导数 D:输出b的导数*\n");printf(" * *\n");printf(" * E:代入x的值计算a F:代入x的值计算b*\n");printf(" * *\n");printf(" * G:输出a+b H:输出a-b*\n");printf(" * *\n");printf(" * I:输出a*b J:退出程序*\n");printf(" * *\n");printf("*******************************************************\n");while(a){printf("\n请选择操作：");scanf(" %c",&flag);//空格符号一定要注意switch(flag){case'A':case'a':{printf("\n 多项式a=");PrintPolyn(pa);break;}case'B':case'b':{printf("\n 多项式b=");PrintPolyn(pb);break;}case'C':case'c':{pc=Derivative(pa);printf("\n 多项式a的导函数为：a'=");PrintPolyn(pc);break;}case'D':case'd':{pc=Derivative(pb);printf("\n 多项式b的导函数为：b'=");PrintPolyn(pc);break;}case'E':case'e':{printf("输入x的值：x=");scanf("%d",&x);printf("\n x=%d时，a=%d\n",x,ValuePolyn(pa,x));break;}case'F':case'f':{printf("输入x的值：x=");scanf("%d",&x);printf("\n x=%d时，b=%d\n",x,ValuePolyn(pb,x));break;}case'G':case'g':{pc=AddPolyn(pa,pb);printf("\n a+b=");PrintPolyn(pc);break;}case'H':case'h':{pc=SubtractPolyn(pa,pb);printf("\n a-b=");PrintPolyn(pc);break;}case'I':case'i':{pc=MultiplyPolyn(pa,pb);printf("\n a*b=");PrintPolyn(pc);break;}case'J':case'j':{printf("\n 感谢使用此程序！\n");DestroyPolyn(pa);DestroyPolyn(pb);a=0;break;}default:printf("\n 您的选择错误，请重新选择!\n");}}}。