2014-2015学年第二学期学号1308210115
《软件工程》
课程设计报告
题目:一元稀疏多项式计算器
专业:计算机科学与技术
班级:计算机科学与技术(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.0
2.2思路分析:
①一般情况下的一元n次多项式可写成
pn(x)=p1xe1+p2xe2+……+pmxem
其中,p1是指数为ei的项的非零系数,且满足0≦e1 ②用两个带表头结点的单链表分别存储两个多项式 ③根据一元多项式相加的运算规则:对于两个一元多项式中所有指数相同的项,对应系数相加,若其和不为零,则构成“和多项式”中的一项; ④只需要将第二个多项式的系数改为其相反数,然后根据一元多项式相加的运算规则便可以得到其相应的“差多项式” 三、概要设计 图3-1功能模块图 为实现上述程序功能,用带表头结点的单链表存储多项式。元素类型,节点类型,和指针类型:typedef struct Polynomial{ int coe; //系数 int exp;//指数 菜单 加法 AddPo lyn(ma ,mb) 减法Subtrac tPolyn(ma,mb ) 乘法 Multipl yPolyn (ma,m b) 求值ValueP olyn(m a,x) 输入Insert(Polyn p,Poly n h) 除法Device Polyn(ma,mb ) 输出deskto p() struct Polynomial *next; }*Polyn,Polynomial; 各个模块之间的调用如图3-1所示,调用insert ()函数将输入的多项式按降幂排列,通过主函数main ()中swith 语句,选择用户所选择的对应的模块,然后又模块对应的功能函数对用户输入的数据进行相应的操作,最后通过desktop ()模块将最后结果输出。 四、详细设计 图4-1 功能实现流程图 4.1 输入模块 用户可通过本模块来输入一个多项式,在每次输入一个多项式时,本模块会先判断谁否是第一次输入,如果是,创建节点,如果不是则模块会通过判断本次输入的数的指数与第一项输入的指数的大小,如果第一项的指数较大,则刚输入的这一项继续与第二项比较指数,以此类推,如果发 开始运行 多项式加法计算器 求和(差) 求积、商 退出 关闭运行 按任意键退出 输出结果 多项式求积、商 多项式相加求和 (差) 输出求和(差) 结果 建立2个多项式 输入多项式 现刚输入的这一项的指数比比较的这一项的指数要大,则插入比较项的前面。 4.2 求和、差模块 用户通过本模块可以实现两个多项式的求和或差值,此模块先调用输入模块,进行对两个要运算的多项式进行初始化,并按降幂排列。然后将两个多项式的幂进行一个对比,如果第一个数的第一项的系数大于第二个多项式的第一个项的系数,那么直接将第一项赋值于刚开始创建的链表的第一项,作为答案的最后一项,反之亦然,如果第一个数的第一项,与第二个数的第一项的系数相同,那么将两个数的系数与指数分别相加或者相减并将对应值赋值给答案相对应的项。以此类推。最后有输出模块输出最后答案。 4.3求积、商模块 用户可通过该模块实现两个多项式的相乘(相除),此模块先调用输入模块,进行对两个要运算的多项式的初始化,并按降幂排列。然后将第一个数的系数、指数与第二个数的系数、指数分别相乘(相除),相加(相减),并且赋值给答案相应的系数、指数。完成后执行第一个数的第一项与第二个数的第二项进行相应的操作…….执行完之后最后调用输出模块将结果输出到屏幕上。 4.4求值模块 用户可通过此模块实现多项式的求值,此模块调用输入模块,完成相对应的操作,然后需要用户输入此时变量的值,并且将变量的值赋值给变量,最后将答案通过输出模块输出到屏幕上。 五、源代码 #include #include #include typedef struct Polynomial{ int coe; //系数 int exp;//指数 struct Polynomial *next; }*Polyn,Polynomial; Polyn ma,mb; void Insert(Polyn p,Polyn h) { if(p->coe==0) delete p; else{ Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->exp { q1=q2; q2=q2->next; } if(q2&&p->exp==q2->exp) { q2->coe+=p->coe; delete p; if(!q2->coe) { q1->next=q2->next; delete q2;} } else { p->next=q2; q1->next=p; } } } Polyn CreatePolyn(Polyn head,int m) { int i; Polyn p; p=head=new Polynomial; head->next=NULL; for(i=0;i p=new Polynomial;; cout<<"请输入第"< cin>>p->coe; cout<<" 指数:"; cin>>p->exp; Insert(p,head); } return head; } void DestroyPolyn(Polyn p) { Polyn t; while(p!=NULL) { t=p; p=p->next; delete t; } } void PrintPolyn(Polyn Pm) { Polyn qa=Pm->next; int flag=1; if(!qa) { cout<<"0"; cout< return; } while (qa) { if(qa->coe>0&&flag!=1) cout<<"+"; if(qa->coe!=1&&qa->coe!=-1) { cout< if(qa->exp==1) cout<<"X"; else if(qa->exp) cout<<"X^"< } else { if(qa->coe==1) { if(!qa->exp) cout<<"1"; else if(qa->exp==1) cout<<"X"; else cout<<"X^"< } if(qa->coe==-1) { if(!qa->exp) cout<<"-1"; else if(qa->exp==1) cout<<"-X"; else cout<<"-X^"< } } qa=qa->next; flag++; } cout< } int compare(Polyn a,Polyn b) { if(a&&b) { if(!b||a->exp>b->exp) return 1; else if(!a||a->exp else return 0; } else if(!a&&b) return -1; else return 1; } Polyn AddPolyn(Polyn pa,Polyn pb) { Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=new Polynomial; hc->next=NULL; headc=hc; while(qa||qb) { qc=new Polynomial; switch(compare(qa,qb)) { case 1: { qc->coe=qa->coe; qc->exp=qa->exp; qa=qa->next; break; } case 0: { qc->coe=qa->coe+qb->coe; qc->exp=qa->exp; qa=qa->next; qb=qb->next; break; } case -1: { qc->coe=qb->coe; qc->exp=qb->exp; qb=qb->next; break; } } if(qc->coe!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else delete qc; } return headc; } Polyn SubtractPolyn(Polyn pa,Polyn pb) { Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p) { p->coe*=-1; p=p->next; } pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next) p->coe*=-1; return pd; } Polyn MultiplyPolyn(Polyn pa,Polyn pb) { Polyn hf,pf;// Polyn qa=pa->next; //新建一个结点作为pa的后继结点Polyn qb=pb->next; //新建一个结点作为pb的后继结点hf=new Polynomial; hf->next=NULL; while(qa)//使用while循环,使得多项式的每项得以运算{ qb=pb->next; while(qb) { pf=new Polynomial; pf->coe=qa->coe*qb->coe; pf->exp=qa->exp+qb->exp; Insert(pf,hf);//调用插入函数,将新的结点插入到新建链表中,并合并同类项 qb=qb->next; } qa=qa->next; } return hf;//返回所得链表的头指针 } void DevicePolyn(Polyn pa,Polyn pb) { Polyn quotient,remainder,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; quotient=new Polynomial; //建立头结点,存储商 quotient->next=NULL; remainder=new Polynomial; //建立头结点,存储余数 remainder->next=NULL; temp1=new Polynomial; temp1->next=NULL; temp2=new Polynomial; temp2->next=NULL; temp1=AddPolyn(temp1,pa); while(qa!=NULL&&qa->exp>=qb->exp) { temp2->next=new Polynomial; temp2->next->coe=(qa->coe)/(qb->coe); temp2->next->exp=(qa->exp)-(qb->exp); Insert(temp2->next,quotient); pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2)); qa=pa->next; temp2->next=NULL; } remainder=SubtractPolyn(temp1,MultiplyPolyn(quotient,pb)); pb=temp1; cout< PrintPolyn(quotient); cout<<"yushu"< PrintPolyn(remainder); } float ValuePolyn(Polyn head,float x) { Polyn p; p=head->next; float result=0; while(p!=NULL) { result+=(p->coe)*(float)pow(x,p->exp); p=p->next; } return result; } void desktop() { system("cls"); cout< cout<<" **********************************************"< cout<<" ** 1.输出多项式a和b **"< cout<<" ** 2.建立多项式a+b **"< cout<<" ** 3.建立多项式a-b **"< cout<<" ** 4.建立多项式a*b **"< cout<<" ** 5.建立多项式a/b **"< cout<<" ** 6.计算多项式a的值 **"< cout<<" ** 7.退出 **"< cout<<" **********************************************"< cout<<" 执行操作:"; } void input(){ int m,n; //Polyn pa,pb; cout<<"请输入多项式a的项数:"; cin>>m; ma=CreatePolyn(ma,m); cout< cout<<"请输入多项式b的项数:"; cin>>n; mb=CreatePolyn(mb,n);} void main() { //int m,n; float x,result; char key; //Polyn pa,pb; cout< 欢迎您的使用!"< cout<<" 系统正在初始化数据,请稍后..."< _sleep(3*1000); system("cls"); while(key) { desktop(); cin>>key; switch (key) { case'1':input(); cout<<"多项式a:"; PrintPolyn(ma); cout<<"多项式b:"; PrintPolyn(mb); break; case'2':input(); //pc=AddPolyn(pa,pb); cout<<"多项式a:"; PrintPolyn(ma); cout<<"多项式b:"; PrintPolyn(mb); cout<<"多项式a+b:"; PrintPolyn(AddPolyn(ma,mb)); //DestroyPolyn(pc); break; case'3':input(); //pd=SubtractPolyn(pa,pb); cout<<"多项式a:"; PrintPolyn(ma); cout<<"多项式b:"; PrintPolyn(mb); cout<<"多项式a-b:"; PrintPolyn(SubtractPolyn(ma,mb)); //DestroyPolyn(pd); break; case'4':input(); //pd=SubtractPolyn(pa,pb); cout<<"多项式a:"; PrintPolyn(ma); cout<<"多项式b:"; PrintPolyn(mb); cout<<"多项式a*b:"; PrintPolyn(MultiplyPolyn(ma,mb)); //DestroyPolyn(pd); break; case'5':input(); //pd=SubtractPolyn(pa,pb); cout<<"多项式a:"; PrintPolyn(ma); cout<<"多项式b:"; PrintPolyn(mb); cout<<"多项式a/b:"; DevicePolyn(ma,mb); //DestroyPolyn(pd); break; case'6':input(); cout<<"多项式a:"; PrintPolyn(ma); cout<<"输入x的值:x="; cin>>x; result=ValuePolyn(ma,x); cout<<"多项式a的值:"< break; case'7': DestroyPolyn(ma); DestroyPolyn(mb); exit(0); break; default: cout<<"Error!!!"< } cout< system("pause"); } } 六、程序测试 6.1测试软件: Microsoft Visual C++ 6.0 6.2测试的数据: (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= 5x6+4x5+3x4 B= 6x6+5x5 (4) A= 5x6+4x5+3x4 X=2 (5) A/B A=2x2 B=x2+1 6.3测试过程与结果: (1) A= 3x14-8x8+6x2+2 B=2x10+4x8-6x2 A+B=3x14+2x10-4x8+2 图6-1加法测试 (2) A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7 A-B=9x14+3x10-x8+5x6-2 图6-2减法测试图 (3) A= 5x6+4x5+3x4 一元稀疏多项式计数器预习报告 :刘茂学号0062 一、实验要求 (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 结点的指数项。 ①若p->expn 实习一线性表、栈和队列及其应用 ——一元稀疏多项式的加法运算 【问题描述】 设计一个实现一元稀疏多项式相加运算的演示程序。 【基本要求】 (1)输入并建立两个多项式; (2)多项式a与b相加,建立和多项式c; (3)输出多项式a,b,c。输出格式:比如多项式a为:A(x)=c1xe1+ c2xe2+…+ cmxem,其中,ci和ei分别为第i项的系数和指数,且各项按 指数的升幂排列,即0≤e1<e2<…<em。多项式b,c类似输出。 【测试数据】 (1)(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5) (2)(x+x100)+(x100+x200)=(x+2x100+x200) (3)(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11) 一.需求分析 1.输入的形式和输入值的范围: 输入是从键盘输入的,输入的内容为多项式的系数和指数,其中多项式的每一项分别以一个系数和指数的形式输入,不带未知数X,系数为任意的实数,指数为任意的整数。 要结束该多项式的输入时,输入的指数和系数都为0. 2. 输出的形式 从屏幕输出,显示用户输入的多项式,并显示多项式加减以后的多项式的值,并且多项式中将未知数X表示了出来. 形式为:+c1X^e1+c2X^e2+…+ciX^ei+…(ci和ei分别是第i项的系数和指数,序列按指数升序排列。) 当多项式的某一项的系数为+1或者-1时侧该项多项式的输出形式为X^ei或-X^ei; 当该项的系数为正时输出+ciX^ei,当为负数时则输出ciX^ei 3. 程序所能达到的功能 输入并建立多项式,实现一元稀疏多项式的相加并输出。 4. 注意:所有多项式都必须以指数升密形式输入。 5. 测试数据为(1)(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5) (2)(x+x100)+(x100+x200)=(x+2x100+x200) (3)(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11) 二.设计 1.设计思路 华北水利水电学院一元稀疏多项式计算器实验报告 2010~2011学年第一学期 09 级计算机科学与技术专业班级: 2009119 学号: 200911902 姓名:万婷婷 一、实验目的 设计一个医院稀疏多项式简单计算器 熟练掌握线性表的基本操作在两种存储结构上的实现,其中以各种链表的操作和应用 二、实验要求 a)输入并建立多项式 b)输出多项式,输出形式为整数序列:n,c 1,e 1 ,c 2 ,e 2 ……c n ,e n ,其中n是多 项式的项数,c i ,e i 分别为第i项的系数和指数。序列按指数降序排列。 c)多项式a和b相加,建立多项式a+b,输出相加的多项式。 d)多项式a和b相减,建立多项式a-b,输出相减的多项式。 用带表头结点的单链表存储多项式。 测试数据: (1) (2x+5x8-3.1x11)+(7-5x8+11x9) (2) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15) (3)(1+x+x2 +x3 +x4 +x5)+( -x3- x4) (4)(x+x2+x3)+0 (5)(x+x3)-(-x-x-3) (6) (x+x2 +x3 )+0 三、实验内容 主要算法设计 typedef struct Node { float coef; int index; struct Node *next; }LinkList; 本程序涉及到多项式的建立、多项式的输出、两个多项式的相加减。用带头结点的单链表存储多项式; 程序中共定义了5个函数: void Insert(LinkList *p,LinkList *h)//把节点p插入到链表h中LinkList *Creat_L(LinkList *head,int m)//创建一个链表,项数为m void Printf(LinkList *L) LinkList *ADDlist(LinkList *head,LinkList *pb) LinkList *MinusList(LinkList *head,LinkList *pb) 四、程序源代码 #include #include"stdio.h" #include"stdlib.h" #include"conio.h" typedef struct Item{ double coef;//系数 int expn;//指数 struct Item *next; }Item,*Polyn; #define CreateItem(p) p=(Item *)malloc(sizeof(Item)); #define DeleteItem(p) free((void *)p); /************************************************************/ /* 判断选择函数 */ /************************************************************/ int Select(char *str) { char ch; printf("%s\n",str); printf("Input Y or N:"); do{ ch=getch(); }while(ch!='Y'&&ch!='y'&&ch!='N'&&ch!='n'); printf("\n"); if(ch=='Y'||ch=='y') return(1); else return(0); } /************************************************************/ /* 插入位置定位函数 */ /**************************************************************/ int InsertLocate(Polyn h,int expn,Item **p) { Item *pre,*q; pre=h; q=h->next; while(q&&q->expn 云南大学软件学院数据结构实验报告 (本实验项目方案受“教育部人才培养模式创新实验区(X3108005)”项目资助)实验难度: A □ B □ C □ 学期:2012秋季学期 任课教师: 实验题目: 一元稀疏多项式计算器 小组长: 联系电话: 电子邮件: 完成提交时间:2012 年 11 月 10 日 云南大学软件学院2012学年秋季学期 《数据结构实验》成绩考核表 学号: 20111120 姓名:本人承担角色:算法设计整体流程控制 综合得分:(满分100分) 指导教师: 年月日 云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号: 20111120 姓名:本人承担角色:函数实现整体流程控制 综合得分:(满分100分) 指导教师: 年月日 (下面的内容由学生填写,格式统一为,字体: 楷体, 行距: 固定行距18,字号: 小四,个人报告按下面每一项的百分比打分。难度A满分70分,难度B满分90分)一、【实验构思(Conceive)】(10%) 多项式计算器的呈现方式是用控制台程序呈现,;多项式的加减乘以及求导的函数中利用链表保存头结点以及循环结构保存和输出数据;还有利用一个简单的降序排列的函数,在输出时更加明了。 二、【实验设计(Design)】(20%) 在头文件中申明变量,源文件中创建指数和系数的指针的头结点,并为此申请空间。首先考虑指数为0,1和系数为0,1时的特殊情况的表示;然后利用SORT函数对输出时进行降序排列;其次就是加减乘以及求导函数的实现;最后是一个输出界面的设计。 三、【实现描述(Implement)】(30%) //--------函数原型说明-------- typedef struct Node { double xishu; int zhishu;//数据域 //int data; struct Node* pnext;//指针域 }Node,*pNode; pNode phead=(pNode)malloc(sizeof(Node));//创建头节点 pNode creat_list(void);创建链表 void traverse_list(pNode phead);//遍历链表 pNode sort(pNode phead);//对链表进行降序排列 pNode add(pNode phead1,pNode phead2);//两个多项式相加 pNode hebing(pNode phead)//合并同类项 pNode multi(pNode phead1,pNode phead2);//多项式相乘 pNode sub(pNode phead1,pNode phead2);//多项式相减 //多项式求导没有声明和定义函数,而是直接卸载程序里了 2014-2015学年第二学期学号1308210115 《软件工程》 课程设计报告 题目:一元稀疏多项式计算器 专业:计算机科学与技术 班级:计算机科学与技术(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.0 2.2思路分析: ①一般情况下的一元n次多项式可写成 pn(x)=p1xe1+p2xe2+……+pmxem 其中,p1是指数为ei的项的非零系数,且满足0≦e1 院系:计算机科学学院 专业:软件工程 年级: 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为指针域,用链表来表示多项式。适用于不定的多项式,特别是对于项数再运算过程中动态增长的多项式,不存在存储溢出的问题。其次,对于某些零系数项,在执行加法运算后不再是零系数项,这就需要在结果多项式中增添新的项;对于某些非零系数项,在执行加法运算后可能是零系数项,这就需要在结果多项式中删去这些项,利用链表操作,可以简单的修改结点的指针以完成这种插入和删除运算(不像在顺序方式中那样,可能移动大量数据项)运行效率高。 【问题描述】 设计一个一元稀疏多项式简单计算器 【基本要求】 一元多项式简单计算器的基本功能是: 1,输入并建立多项式; 2,输出多项式,输出形式为整数序列:n,c1,e1,c2,c2,...,cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列; 3,多项式a和b相加,建立多项式a+b; 4,多项式a和b相减,建立多项式a-b. 【测试数据】 1,(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7) 【实现提示】 用带表头结点的单链表存储多项式。 #include 一元稀疏多项式计数器预习报告 姓名:刘茂学号2220 一、实验要求 (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^^11)+(7-5x^8+11x^9)=^11+11x^9+2x+7); 2、(6x^-3-x+^^9+^9)-(-6x^-3+^2-x^2+^15 )=^^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 结点的指数项。 ① 若p->expn 实习报告 题目:设计一个一元稀疏多项式计算器 班级: 姓名学号__________完成日期:__ 一、课程题目 一元稀疏多项式计算器 二、需求分析 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); (6)、(x+x^2+x^3)+0=x+x^2+x^3. 三、概要设计 1.有序表的抽象数据类型定义为: ADT List{ 数据对象:D={a i| a i∈R,i=1,2,…,n,n≧0} 实验题目:多项式运算器 实验内容:1、熟悉编程环境 2、用链式存储结构实现稀疏一元多项式运算器 实验目的和要求: 1、通过本实验,掌握VC++6.0的基本使用,包括源程序的输入,编译运行及调 试。调试的目的是找程序的运行错误,通过DEBUG菜单设置断点实现。 2、用链式存储结构实现一元多项式的运算。 熟练掌握指针和链表的基本操作,利用菜单进行功能选择。 功能基本要求:创建、显示、求和、求差、求值、销毁、清空、修改 实验算法: 1、数据结构描述: 输入的稀疏每一个多项式用一个链表存储,链表的每一个节点存储多项式的一个非零项。定义为LNode型结构体,其中保存该项的系数和指数。主 函数中用一个数组存储每一个多项式的第一项的头指针以调用多项式。 2、函数和算法描述: 主函数main定义LNode*数组a[]存储每一个多项式头节点的地址,并构建菜单以选择调用函数进行多项式的操作,对多项式进行操作的函数返回新 改动的多项式头结点地址。 Createpolyn函数用以创建一个多项式,在用户输入结束指令之前,不断的申请空间,构建LNode型结点并加至构建的链表的表尾,输入结束指令之 后,表尾设NULL并返回表头指针。 Printpolyn函数用以在屏幕上打印多项式,接收需要打印的多项式链表的头结点,构造循环体在表尾之前,不断以mx^n格式打印对应结点中的数 据。 Copypolyn函数用以复制多项式,接收需要复制的多项式a和复制位置b 的指针,构造循环体,在a到表尾之前循环,在b对应的链表中构建新的结 点,结点上的数据赋值为a中对应的值,返回b的头结点地址。 Addpolyn函数用以求两个已知多项式a、b的和存入c,先构建循环体,在a、b链表都未进行到表尾时,比较两个结点中的次数值,如果相同,将 系数相加赋于c的当前结点,如果不同,将次数较小多项式y(a或b)的结 点赋值给c当前结点,在将y链表向后推。 Subtract函数用以求两多项式的差,类似求和算法。 Value函数用以求一个多项式的值,接收x的值,构建循环体,在表尾之前循环以遍历多项式链表。内置循环体,以次数n为限循环,求出x^n的 值,乘以系数并将每一项的值叠加得值。 Destroypolyn函数用以销毁已有的多项式,将此多项式链表的空间FREE 掉,返回空指针。 Clearpolyn函数用以清空多项式,构建循环体,将多项式的各项的系数、指数置零。 3、时空分析: L= sizeof(struct LNode) 一个含有N项的多项式占用的储存空间为NL+1 一元稀疏多项式简单计算器 一、设计课题 设计一元稀疏多项式简单计算器。 二、需求分析 2.1 输入的形式和输入值的范围: 输入是从键盘输入的,输入的内容为多项式的系数和指数,数为任意的整数,指数为大于等于0的整数 2.2 输出的形式 从屏幕输出,显示用户输入的多项式,并显示多项式加减以后的多项式的值。 2.3 程序所能达到的功能 a:输入并建立多项式; b:输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,……,cn,en,其中n是多项式的项数,ci和ei 分别是第i项的系数和指数,序列按指数降序排列; c:多项式a和b相加,建立多项式a+b; d:多项式a和b相减,建立多项式a-b; 2.4 测试数据 (1)(2x+5x^8-3.1x^11)+(7-5x^8+11x^9) = (-3.1x^11+11X^9+2X+7) (2)(X+X^3)+(-X-X^3)=0 (3)(X+X^2+X^3)+0= X+X^2+X^3 三、概要设计 3.1 设计思路 A:数据结构的选用 为了实现任意多项式的加法、减法,因此选择单链表的结构体,它有一个系数,指数,下一个指针3个元属;单链表抽象结构类型定义见附录2。 B:多项式的输入 采用头节点插法的方式,输入多项式中一个项的系数和指数,就产生一个新的节点,建立起它的右指针,并用头节点指向它;为了判断一个多项式是否输入结束,定义一个结束标志,当输入非00时就继续,当输入00时,就结束一个多项式的输入; C:2个多项式的加法 它从2个多项式的头部开始,2个多项式的某一项都不为空时,如果指数相等的话,系数就应该相加;相加的和不为0的话,用头插法建立一个新的节点。p的系数小于q的系数的话,就应该复制q接点到多项式中。p的系数大于q的系数的话,就应该复制p接点到多项式中。当第2个多项式空,第1个数不为空时,将第一个数剩下的全用新节点产生。当第1个多项式空,第1个数不为空时,将第2个数剩下的全用新节点产生 D:2个多项式的减法 它从2个多项式的头部开始,2个多项式的某一项都不为空时,如果指数相等的话,系数就应该相减;相加的和不为0的话,用头插法建立一个新的节点。 p的系数小于q的系数的话,就应该复制q接点到多项式中。p的系数大于q的系数的话,就应该复制p接点到多项式中,并且建立的接点的系数为原来的相反数;当第2个多项式空,第1个数不为空时,将第一个数剩下的全用新节点产生。当第1个多项式空,第1个数不为空时,将第2个数剩下的全用新节点产生,并且建立的接点的系数为原来的相反数。 武汉理工大学华夏学院课程设计报告书 课程名称:数据结构 题目:用C语言实现多项式简单计算器的设计 系名:信息工程系 专业班级:软件工程1121班 姓名:邓燕蓉 指导教师:王绪梅 2013 年 6月 28日 课程设计任务书 学生姓名:邓燕蓉专业班级:软件工程1121班 指导教师:王绪梅工作单位:华夏学院计算机教研室设计题目:用C语言实现多项式简单计算器的设计 设计目的 1.巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法; 2.选择合适的数据的逻辑结构和存储结构以及相应操作,实现简单的多项式计算; 3.提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养; 设计任务(在规定的时间内完成下列任务) 〔问题描述〕输入并建立两个多项式并输出多项式 设计一个程序:对两个多项式进行加、减法及乘法运算,建立一个新多项式并输出. 或设计一个程序对其中一个多项式求导。 〔实现提示〕 选择带头结点的单链表或循环链表存储多项式,头结点中存放多项式的参数及单链表的数据具体要完成的任务是: A.编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。 B.写出规范的课程设计报告书; 时间安排:6月24日---28日 具体要求 1. 课程设计报告按统一通用格式书写,具体内容如下: ①设计任务与要求 ②总体方案与说明 ③软件主要模块的流程图 ④源程序清单与注释 ⑤问题分析与解决方案(包括调式记录、调式报告,即在调式过程中遇到的主要问题、解决方法 及改进设想); ⑥小结与体会 附录:①源程序(必须有简单注释)②使用说明③参考资料 2.每位学生应独立完成各自的任务且每天至少在设计室工作半天; 指导教师签名:王绪梅2013 年6月22日 教研室主任(或责任教师)签名:2013年6月24日 武汉工业学院 数学与计算机学院 《数据结构》 课程设计说明书 题目:一元多项式计算器 专业:计算机 班级:计算机类1305班 学号: 1305110053 姓名:杨钦 指导老师:左翠华 2014年12月25日 一、 设计题目 一元稀疏多项式计算器 【问题描述】 设计一个一元稀疏多项式简单计算器。 【基本要求】 一元稀疏多项式简单计算器的基本功能是: (1) 输入并建立多项式 ; (2) 输出多项式,输出形式为整数序列:n ,c l ,e l ,c 2,e 2,…,c n ,e n ,其中n 是多项式的项数,c i 和e i ,分别是第 i 项的系数和指数,序列按指数降序排列; (3) 多项式a 和b 相加,建立多项式a +b ; (4) 多项式a 和b 相减,建立多项式a -b 。 【测试数据】 (1)(2x+5x 8-3.1x 11) + (7-5x 8+11x 9)=(-3.lx 11+11x 9+2x+7) (2)(6x -3-x+4.4x 2-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) 互换上述测试数据中的前后两个多项式 【实现提示】 用带表头结点的单链表存储多项式。 【选作内容】 (1) 计算多项式在x 处的值。 (2) 求多项式 a 的导函数a ' 。 (3) 多项式a 和b 相乘,建立乘积多项式ab 。 (4) 多项式的输出形式为类数学表达式。例如,多项式 -3x8+6x3-18 的输出形式为183683-+-∧∧x x ,x15+(-8)x7-14的输出形式为147815--∧∧x x 。注意,数值为1的非零次项的输出形式中略去系数1,如项1x8的输出形式为x8,项 -1x3的输出形式为-x3。 课程设计说明书 设计题目:数据结构课程设计专业:班级: 设计人: 一、 需求分析 1. 演示程序以用户和计算机的对话方式执行,即在计算机终端上 显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运算命令;相应的输入数据和运算结果显示在其后。 2. 程序执行的命令包括: 1) 创建一元多项式1; 2) 创建一元多项式2; 3) 输出一元多项式 4) 计算多项式1和多项式2的和; 5) 计算多项式1和多项式2的差 注意:输出形式为整数序列n,c1,e1,c2,e2,…,cn,en ,其中n 是多项式的项数,ci 和ei 分别是第I 项的系数和指数,序列指指数降序排列 3.测试数据 1) ) 72111.3()1157()1.352(91198118+++-=+-+-+x x x x x x x x ; 2) )1()()1(25435432+++=--++++++x x x x x x x x x x ; 3) 0)()(33=--++x x x x 4) )(0)(2332x x x x x x ++=+++ 二、 概要设计 为实现上述程序功能,应以带头结点的单链表存储多项式 1. 多项式的抽象数据类型为: ADT Polynmial{ 数据对象:D={a i |ai ∈TermSet ,i=1,2,3,…,m ,TermSet 中的每一个元素包含一个表示系数的实数和表 示指数的整数} 数据关系:R1={a i-1,a i∈D,且a i-1中的指数 实习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≥0Termset中的每个元素包含一个表示系数的实数和表示指数的整数} 数据关系:R1={ 一元稀疏多项式的表示及加法运算 一、需求分析 1.程序的功能 (1).按照指数升序顺序,输入并建立多项式M与N。 (2).计算多项式M与N的和 (3).输出多项式M、N、M+N。 2.输入输出的要求 多项式按指数递增顺序输入;设计的数据结构应有利于表示任意一元稀释多项式;多项式的输出采用数学多项式的表示形式。 3.测试数据 (1)7+3x+9x8+5x17, 8x+22x7-9x8 (2) 0, 8x+22x7-9x8 (3)8x10+22x7-9x8 , -1 二、概要设计 1.通过建立链表来实现多项式的输入 在多项式输入之前,要先定义一个带有头结点的单链表,紧接着以指数递增的顺序输入多项式中系数不为零的项,其中每一项对应一个结点,每项对应的结点依次插入直至遇到结束标志,这样结完成了多项式的输入。 2. 两个多项式相加 两个多项式中如果指数相同则系数相加,构成和多项式的一项;如果指数不同,则直接构成和多项式的一项。 3. 多项式的输出 采用数学多项式的表达方式 三、详细设计 1.定义数据类型: typedef struct pnode { float coef; //系数 int exp; //指数 struct pnode *next; //指针,指向下一个系数不为的子项 }PNode, *PLink; PLink M,N,P; //多项式M、N、P 2.通过建立链表来实现多项式的输入 在多项式输入之前,要先定义一个带有头结点的单链表,先输入多项式项数,紧接着以指数递增的顺序输入多项式中系数不为零的项,其中每一项对应一个结点,每项对应的结点依次插入,当项数达到时结束,这样完成了多项式的输入。 PNode *createList(PNode *p) //建立多项式链表 { float a; int b; int c; int d; p=new PNode; 一元稀疏多项式计算器 C语言编写 悬赏分:120 |提问时间:2008-6-23 20:33 |提问者:骑着单车的熊 一元稀疏多项式计算器: 用C语言编写程序,实现一元稀疏多项式计算器。具体要求如下: (1) 演示程序以用户与计算机对话的形式输入输出数据; (2) 实现两个一元稀疏多项式的加、减、乘运算; (3) 求一个多项式a的导函数a’; (4) 结果以类数学表达式的形式输出。 看清题目的要求我只要C语言的不要其他语言的还有解释一下编程的思路和过程谢谢了大家 请大家传给我能够使用的程序谢谢了 推荐答案 datastruct.h typedef struct list { int c; //多项式的项数 int e; //多项式的指数 struct list *next; //下一结点 }; typedef struct list *LinkList; typedef struct list Node; 下面是线性表的操作相关函数声明,对应文件ListOper.h: //File: ListOper.h #ifndef DATASTRUCT #define DATASTRUCT #include "datastruct.h" #endif //some functions declaretioin bool CreateList(LinkList &L); Node *CreateNode(int e, int c); void FreeList(LinkList &L); void SortList(LinkList &L); void DeleteNextNode(Node *d); void SweepNextNode(Node *s); 数据结构课程设计 系别电子信息系 专业计算机科学与技术 班级学号4090113 姓名王健 指导教师党群 成绩 2011年7 月14 日 目录 一、课程题目 (1) 二、需求分析 (1) 三、测试数据 (2) 四、概要设计 (2) 五、调用关系图 (3) 六、程序代码 (3) 七、心得体会及总结 (12) 数据结构课程设计 一、课程题目 一元稀疏多项式计算器 二、需求分析 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利用链表实现队列的构造。每次输入一项的系数和指数,可以输出构 造的一元多项式 2.4演示程序以用户和计算机的对话方式执行,即在计算机终站上显示 “提示信息”之后,由用户在键盘上输入演示程序中规定的运行命令;最后根据相应的输入数据(滤去输入中的非法字符)建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为:c1x^e1+c2x^e2+… +cnx^en 3、设计思路分析 要解决多项式相加,必须要有多项式,所以必须首先建立两个多项式,在这里采用链表的方式存储链表,所以我将结点结构体定义为 运用尾插法建立两条单链表,以单链表polyn p和polyn h分别表示两个一元多项式a和b,a+b的求和运算等同于单链表的插入问题(将单链表polyn p中的结点插入到单链表polyn h中),因此“和多项式”中的结点无须另生成。 为了实现处理,设p、q分别指向单链表polya和polyb的当前项,比较p、q结点的指数项,由此得到下列运算规则: ① 若p->expn一元稀疏多项式计算器实验(报告+程序)
一元稀疏多项式的加法运算(数据结构实习)
实验报告——2 一元稀疏多项式计算器
多项式的运算(c语言实现)
(整理)一元稀疏多项式计算器
一元稀疏多项式计算器C语言课程设计
一元稀疏多项式计算器(数据结构)
一元稀疏多项式计算器(数据结构)
一元稀疏多项式计算器实验
一元稀疏多项式计算器实习报告
数据结构实验,多项式计算器
一元多项式计算器设计与实现
用C语言实现多项式简单计算器的设计
一元多项式计算器程序设计实验报告
数据结构课程设计——一元稀疏多项式
数据结构课程设计-一元多项式计算器
一元稀疏多项式的表示及加法运算
一元稀疏多项式计算器 C语言编写
数据结构课程设计___一元稀疏多项式计算器(报告+代码)__完整版.