数据结构课程设计——一元稀疏多项式
课程设计说明书
设计题目：数据结构课程设计专业：班级：
设计人：
一、 需求分析
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中的指数 i的指数，i=2,3，…，n} 基本操作： CreatePolyn（&P，m） 操作结果：输入m项的系数和指数，建立一元多项式P DestroyPolyn（&P） 初始条件：一元多项式P已存在 操作结果：销毁一元多项式P printPolyn(P) 初始条件：一元多项式P已存在 操作结果：打印输出一元多项式P PolynLength(P) 初始条件：一元多项式P已存在 操作结果：返回一元多项式P的项数 AddPolyn(&Pa,&Pb) 初始条件：一元多项式Pa和Pb已存在 操作结果：完成多项式相加的运算 SubtractPolyn(&Pa,&Pb) 初始条件：一元多项式Pa和Pb已存在 操作结果：完成多项式相减的运算 }ADT Polynmial 2.本程序包含四个模块 1)主程序模块： Void main（）{ 创建多项式a，b； 人机交互界面； 输入命令； 处理命令； 结束程序； } 2)多项式单元模块 3)结点结构单元模块 三、详细设计 1.多项式的存储结构： typedef struct Polynomial { double coef;//系数 int expn;//指数 struct Polynomial *next; }*Polyn,Polynomial; 2.多项式抽象数据类型的基本操作的伪代码 Polyn CreatePolyn(Polyn head,int m) { //建立一个头指针为head、项数为m的一元多项式 p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0; i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立 新结点以接收数据 printf("请输入第%d项的系数与指数:",i+1); scanf("%lf %d",&p->coef,&p->expn); Insert(p,head); //调用Insert函数插入结点 } return head; } void DestroyPolyn(Polyn p) { //销毁多项式p q1=p->next; q2=q1->next; while(q1->next) { free(q1); q1=q2; q2=q2->next; } } void Insert(Polyn p,Polyn h) { if(p->coef==0) free(p);//系数为0的话释放结点 else { q1=h; q2=h->next; while(q2&&p->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; } } } void PrintPolyn(Polyn P) { Polyn q=P->next; int flag=0;//项数计数器 while(q) { flag++; q=q->next; } q=P->next; if(!q) { //若多项式为空，输出0 putchar('0'); printf("\n"); return; } printf("%d ",flag); while(q) { if(q->coef!=1&&q->coef!=-1) { printf("%g %d ",q->coef,q->expn); } else { if(q->coef==1) { printf("%g %d ",q->coef,q->expn); } if(q->coef==-1) { printf("%g %d ",q->coef,q->expn); } } q=q->next; } printf("\n"); } int compare(Polyn a,Polyn b) { if(a&&b) { if(!b||a->expn>b->expn) return 1; else if(!a||a->expn 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; } 3.主函数及其他函数的伪代码算法 Int main() { CreatPolyn(a); CreatPolyn(b); 交互界面菜单； Switch（choose） { Case a： printf(a); Case b: printf(b); Case c: printf(a+b); Case d: printf(a-b); Case e: exit; } } 四、测试结果 1.人机交互界面 2.测试结果显示 )72111.3()1157()1.352(91198118+++-=+-+-+x x x x x x x x )1()()1(25435432+++=--++++++x x x x x x x x x x 0)()(33=--++x x x x )(0)(2332x x x x x x ++=+++ 五、 总结反思 经过这段为期不久的课程设计，使我对于数据结构有了更深层次的理解,对于链表这种数据结构的认识也更加深刻了。 在这个过程中。我曾因为实践经验缺乏，错误过多失落过；也曾经仿真成功而热情高涨。我也感觉用心细心地做好一件事情的重要性，在这次课程设计中，体会到了做设计的严谨，更加加深了我对课程设计的兴趣。在此次课程设计过程中，遇到不懂的问题我会及时向老师，同学请教或者是在网上查询相关的资料，以更好地完成该项课题设计。 在实践结束后，深深地体会到实践对于工科专业的重要性。在学习数据结构的过程中总是觉得有些东西模棱两可，感觉到不能深一步的理解，也因为代码的冗长而缺乏耐心去完成每一个。通过这次课程设计，原本关于链表的模棱两可的东西逐渐变得清晰起来，以后一定加强动手实践的能力，多动手，多思考！ 一元稀疏多项式计数器预习报告 ：刘茂学号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 华北水利水电学院一元稀疏多项式计算器实验报告 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 实习一线性表、栈和队列及其应用 ——一元稀疏多项式的加法运算 【问题描述】 设计一个实现一元稀疏多项式相加运算的演示程序。 【基本要求】 （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.设计思路 云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（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} 一元稀疏多项式简单计算器 一、设计课题 设计一元稀疏多项式简单计算器。 二、需求分析 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个数剩下的全用新节点产生，并且建立的接点的系数为原来的相反数。 武汉工业学院 数学与计算机学院 《数据结构》 课程设计说明书 题目：一元多项式计算器 专业：计算机 班级：计算机类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 一元稀疏多项式简单计数器 题目：编制一个演示一元稀疏多项式简单计数器的程序 完成日期：2015.4.9 一、需求分析 1.1本演示程序中，多项式是以带头结点的单链表存储的，在单链表中有两个数据域，分别存储多项式的一个节点的系数，指数；还有一个指针域，存储指向下一个节点的指针。 1.2演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。 1.3程序执行的命令包括： 1）构造多项式a;2)构造多项式b；3）输出多项式，并且多项式的序列按指数的降序排列；4）求a+b；5）求a-b；6）求a*b；7) 求多项式a的导函数a’;8）求多项式在x处的值。 1.4测试数据 (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)-(-6x^(-3)+5.4x^2-x^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)互换上述测试数据中的前后两个多项式 二、概要设计 为实现上述程序的功能，应以带头结点的单链表表示多项式。为此，需要一个抽象数据类型：单链表。 2.1单链表的抽象数据类型定义 ADT LinkList{ 数据对象：D={ai|ai∈TermSet,i=1,2,…,m,m≥0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数} 数据关系：R1={ 信息学院12级杨征元 PB 稀疏一元多项式运算器 问题描述：完成一元稀疏多项式运算器，完成多项式创建，显示，复制，求和，求差，求值，销毁，清空，修改，n阶微分，不定积分，定积分操作。函数功能描述如下： 稀疏一元多项式运算器 0.退出退出 1.创建多项式创建并打印 2.显示多项式打印 3.复制多项式复制多项式a至空域b，非空报错 4.求和输入abc位置，c=a+b 5.求差输入abc位置，c=a-b 6.求值输入位置，double x，输出double result 7.销毁多项式销毁，使p[i]为NULL 8.清空多项式清空保留头指针，输出为0 9.修改多项式选择插入，删除，修改（删了再插） 阶微分输入微分位置，阶数，结果存放于原位置 11.不定微分输入积分位置，不定积分，常数C取0 12.定微分输入积分位置，上下限值，输出定积分结果 算法描述：通过主菜单调用函数完成各项功能，函数描述见程序结构描述部分。 数据结构描述:多项式每一项结点定义如下： typedef struct lnode{ double coef; int exp; struct lnode* next; }lnode,*linklist; 包含指向下一结点指针linklist next，存储系数的数据单元double coef，存储指数的数据单元int exp；结点名lnode，指向结点指针linklist。 每一个多项式由头指针引出，头指针数组lnode* p[N]。每一个单元存储一多项式头指针。当多项式不存在，p[i]=NULL；多项式为空，p[i]->next=NULL，即只存在头指针。 操作函数见程序结构描述部分。 程序结构描述： 函数包括创建结点函数，有序插入函数，打印函数，创建多项式函数，多项式清空函数，多项式销毁函数，求值函数，求和函数，求差函数，复制函数，删除结点函数，修改函数，n 阶微分函数，不定积分函数。对函数原型，功能，借口逐一描述如下： 1.创建结点函数 函数原型：linklist makenode(double coef, int exp) 输入double型系数项，int型指数项，创建lnode结点，返回指向结点的linklist指针。 功能：创建新结点，在复制函数以及输入系数指数插入结点时（修改多项式） 调用。 2.有序插入函数 函数原型：void insert(linklist phead, linklist head) 输入插入结点指针phead以及多项式头指针head，无返回值 功能：新结点phead有序插入头结点为head的多项式内（按指数项降序排列），在创建， 数据结构课程设计说明书题目：一元稀疏多项式简单计数器 学生姓名： 学号： 院（系）：理学院 数据结构课程设计任务书 题目：一元稀疏多项式简单计数器 课程设计从2011 年12 月19 日起到2011 年12 月23 日 1、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）： 一元稀疏多项式简单计数器 （1）输入并建立多项式 （2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn ，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。 （3）多项式a和b相加，建立多项式a+b，输出相加的多项式。（4）多项式a和b相减，建立多项式a-b，输出相减的多项式。 用带头结点的单链表存储多项式。 2、对课程设计成果的要求〔包括图表、实物等硬件要求〕： 1）根据课程设计题目要求编写所需程序代码 要求可以实现多项式的建立，以及两个多项式的相加、减，并且输出相加、减后所得的结果，同时用手算也可验证实验结果是否符合要求。 2）提交课程设计报告 按照具体要求完成课程设计报告，其中包括问题的描述、算法思想、程序实现结果、数据验证和实验总结等部分。 3、课程设计工作进度计划： 时间设计任务及要求 1-10 搜集学习相关资料，明确实验要求、目的 1-11 分析课题，理清编程思路 1-12 编写程序，修改程序 1-13 代入数据，进行整体调试，运行，再修改 1-14 性能分析，撰写设计说明书 指导教师：日期：2011-11-15 教研室主任：日期： 目录 一、问题描述 (1) 二、算法思想 (2) 三、数据结构 (3) 四、设计模块划分 (4) 五、源程序 (5) 六、算法分析 (10) 七、运行结果 (11) 八、设计总结与体会 (13) 参考文献 (14)一元稀疏多项式计算器实验(报告+程序)
实验报告——2 一元稀疏多项式计算器
一元稀疏多项式的加法运算(数据结构实习)
(整理)一元稀疏多项式计算器
一元稀疏多项式计算器C语言课程设计
一元稀疏多项式计算器(数据结构)
一元稀疏多项式计算器(数据结构)
一元稀疏多项式计算器实验
一元稀疏多项式计算器实习报告
一元多项式计算器设计与实现
一元多项式计算器程序设计实验报告
数据结构课程设计——一元稀疏多项式
数据结构课程设计-一元多项式计算器
一元稀疏多项式的表示及加法运算
一元稀疏多项式计算器 C语言编写
数据结构课程设计___一元稀疏多项式计算器(报告+代码)__完整版.
一元稀疏多项式简单计数器
稀疏一元多项式运算器 实验报告 附源程序
数据结构课程设计-一元稀疏多项式简单计数器
- 一元稀疏多项式计算器C语言课程设计
- 一元稀疏多项式的表示及加法运算
- c一元稀疏多项式计算器-课程设计实验报告
- 实验报告——2一元稀疏多项式计算器
- 一元稀疏多项式计算器实验(报告+程序)
- 设计一个一元稀疏多项式计算器论文(1)
- 一元稀疏多项式计算器实验报告+程序
- 数据结构课程设计___一元稀疏多项式计算器(报告+代码)__完整版.
- 数据结构课程设计报告一元稀疏多项式计算器
- 一元稀疏多项式的计算
- 一元稀疏多项式计算器实验(报告程序)
- 一元稀疏多项式计算器实习报告
- 一元稀疏多项式的计算
- 一元稀疏多项式计算器实习报告[1]
- 数据结构 一元稀疏多项式计算器
- 一元稀疏多项式计算器(数据结构)
- 一元稀疏多项式计算器 C语言编写
- 一个一元稀疏多项式简单计算器课程设计报告
- 一元稀疏多项式计算器数据结构
- (整理)一元稀疏多项式计算器