实习一线性表及其应用
题目：一元稀疏多项式加法实习时间：2011.3.25
一．需求分析：
设计一个实现一元稀疏多项式相加运算的演示程序。
基本要求：（1）输入并建立两个多项式；（2）多项式a与b相加，建立和多项式c；（3）输出多项式a,b,c。输出格式：比如多项式a为：A(x)=c1xe1+ c2xe2+…+ c m xe m，其中，c i和e i分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e2＜…＜e m。多项式b,c类似输出。
二．设计：
? 1.设计思想
（1）用带头结点的单链表存储多项式。
（2）三个多项式链表中都只存储非零系数项。若多项式a与b中指数相等的两项相加后，系数为零，则在和多项式c中不存储该指数项。
? 2.设计表示
（1）函数调用关系图：
main→ListCreate→ListInsertSort→ListAdd→Printf （2）函数接口规则说明：
int ListCreate(SLNode **head,int t)/*建立以head为头指针的有t个结点的单向链表
void ListInsertSort(SLNode *head,int n)/*对以head为头指针有n个结点的单向链表按其存储的多项式各项的指数用冒泡法排序法由小到大排序*/ int ListAdd(SLNode *f1,SLNode *f2,SLNode **head,int n1,int n2)/*将有n1项的多项式f1和有n2项的多项式f2相加，存储在新建的以head为头指针的单向链表中*/
void Printf(SLNode *la)/*按题目要求输出多项式la*/
? 3.实现注释
（1）根据多项式的项数n、系数以及指数建立单向链表；
（2）多项式的项数、系数和指数均可自由输入；
（3）多项式按A(x)=c1xe1+ c2xe2+…+ c m xe m的形式输出
? 4.详细设计
创建函数
int ListCreate(SLNode **head,int t)
{
SLNode *p,*q;
int i;
if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL) {
printf("内存空间不足！\n");
return 0;
}
(*head)->next=NULL;q=*head;
for(i=0;i { if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) { printf("内存空间不足！\n"); return 0; } printf("请输入x的系数data和指数n:"); scanf("%d%d",&p->data,&p->n); p->next=NULL;q->next=p;q=p; } return 1; } 插入函数 void ListInsertSort(SLNode *head,int n) { SLNode *p,*q,*s; int i,j,k; j=n;k=1; while(k { i=1; p=head; q=p->next; s=q->next; while(i { if(q->n>s->n) { p->next=s; q->next=s->next; s->next=q; p=s; s=q->next; } else { p=p->next; q=q->next; s=s->next; }i++; }j--;k++; } } 求和函数 int ListAdd(SLNode *f1,SLNode *f2,SLNode **head,int n1,int n2) { SLNode *p,*q,*M,*N; int i=0,j=0; M=f1->next,N=f2->next; if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL) printf("内存空间不足！\n"); return 0; } (*head)->next=NULL;q=*head; while(i { if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) { printf("内存空间不足！\n"); return 0; } if(M->n { p->data=M->data; p->n=M->n; M=M->next; i++; } else if(M->n>N->n) { p->data=N->data; p->n=N->n; N=N->next; j++; } else { p->data=M->data+N->data; p->n=M->n; M=M->next; N=N->next; i++; j++; } if(p->data==0) free(p); else { q->next=p; p->next=NULL; q=p; } if(i>=n1) { while(j { if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) { printf("内存空间不足！\n"); return 0; } p->data=N->data; p->n=N->n; N=N->next; q->next=p; p->next=NULL; q=p; j++; } } if(j>=n2) { while(i { if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) { printf("内存空间不足！\n"); return 0; } p->data=M->data; p->n=M->n; M=M->next; q->next=p; p->next=NULL; q=p; i++; } } return 1; } 输出函数 void Printf(SLNode *la) { SLNode *p; p=la->next; if(la->next==NULL) { free(p); printf("0"); return; } if(p->n==0) printf("%d",p->data); else if(p->data==1) printf("X%d",p->n); else if(p->data==-1) printf("-X%d",p->n); else printf("%dX%d",p->data,p->n); p=p->next; while(p->next!=NULL) { if(p->data==1) printf("+X%d",p->n); else if(p->data==-1) printf("-X%d",p->n); else if((p->data<0)&&(p->data!=-1)) printf("%dX%d",p->data,p->n); else printf("+%dX%d",p->data,p->n); p=p->next; } if(p->next==NULL) { if(p->data==1) printf("+X%d",p->n); else if(p->data==-1) printf("-X%d",p->n); else if((p->data<0)&&(p->data!=-1)) printf("%dX%d",p->data,p->n); else printf("+%dX%d",p->data,p->n); } } 三.调试分析 四、用户手册 五、运行结果 六、源程序清单 #include #include typedef struct Node { int data; int n; struct Node *next; }SLNode; int ListCreate(SLNode **head,int t) { SLNode *p,*q; int i; if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL) { printf("内存空间不足！\n"); return 0; } (*head)->next=NULL;q=*head; for(i=0;i { if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) { printf("内存空间不足！\n"); return 0; } printf("请输入x的系数data和指数n:"); scanf("%d%d",&p->data,&p->n); p->next=NULL;q->next=p;q=p; } return 1; } void ListInsertSort(SLNode *head,int n) { SLNode *p,*q,*s; int i,j,k; j=n;k=1; while(k { i=1; p=head; q=p->next; s=q->next; while(i { if(q->n>s->n) { p->next=s; q->next=s->next; s->next=q; p=s; s=q->next; } else { p=p->next; q=q->next; s=s->next; }i++; }j--;k++; } } int ListAdd(SLNode *f1,SLNode *f2,SLNode **head,int n1,int n2) { SLNode *p,*q,*M,*N; int i=0,j=0; M=f1->next,N=f2->next; if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL) { printf("内存空间不足！\n"); return 0; } (*head)->next=NULL;q=*head; while(i { if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) { printf("内存空间不足！\n"); return 0; } if(M->n { p->data=M->data; p->n=M->n; M=M->next; i++; } else if(M->n>N->n) { p->data=N->data; p->n=N->n; N=N->next; j++; } else { p->data=M->data+N->data; p->n=M->n; M=M->next; N=N->next; i++; j++; } if(p->data==0) free(p); else { q->next=p; p->next=NULL; q=p; } } if(i>=n1) { while(j { if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) { printf("内存空间不足！\n"); return 0; } p->data=N->data; p->n=N->n; N=N->next; q->next=p; p->next=NULL; q=p; j++; } } if(j>=n2) { while(i { if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) { printf("内存空间不足！\n"); return 0; } p->data=M->data; p->n=M->n; M=M->next; q->next=p; p->next=NULL; q=p; i++; } } return 1; } void Printf(SLNode *la) { SLNode *p; p=la->next; if(la->next==NULL) { free(p); printf("0"); return; } if(p->n==0) printf("%d",p->data); else if(p->data==1) printf("X%d",p->n); else if(p->data==-1) printf("-X%d",p->n); else printf("%dX%d",p->data,p->n); p=p->next; while(p->next!=NULL) { if(p->data==1) printf("+X%d",p->n); else if(p->data==-1) printf("-X%d",p->n); else if((p->data<0)&&(p->data!=-1)) printf("%dX%d",p->data,p->n); else printf("+%dX%d",p->data,p->n); p=p->next; } if(p->next==NULL) { if(p->data==1) printf("+X%d",p->n); else if(p->data==-1) printf("-X%d",p->n); else if((p->data<0)&&(p->data!=-1)) printf("%dX%d",p->data,p->n); else printf("+%dX%d",p->data,p->n); } } void main() { SLNode *f1,*f2,*f3; int t1,t2; printf("请输入两个多项式非零项个数t1,t2\n"); scanf("%d%d",&t1,&t2); if(t1<=0||t2<=0) { printf("输入参数错误！\n"); return; } printf("创建多项式f1\n"); ListCreate(&f1,t1); printf("创建多项式f2\n"); ListCreate(&f2,t2); ListInsertSort(f1,t1); ListInsertSort(f2,t2); ListAdd(f1,f2,&f3,t1,t2); printf("f1(X)="); Printf(f1); printf("\nf2(X)="); Printf(f2); printf("\nf3(X)="); Printf(f3); printf("\n"); } 实验一一元多项式的表示和相减、相乘 一、实验目的 1.掌握链表的存储方式 2.掌握一元多项式的存储及运算。 二、实验内容 已知一元多项式P(x)和Q(x)已存在，求P(x)-Q(x)和P(x)* Q(x)并输出。 要求： 1.通过键盘随机输入两多项式P(x)和Q(x)的内容。 2.输出结果要有P(x)和Q(x)的以及它们的差P(x)-Q(x)和乘积P(x)* Q(x)。 三、实验步骤： 1.创建一元多项P(x)和Q(x)。 2.求P(x)-Q(x)，P(x)* Q(x)。 3.输出P(x)、Q(x)、P(x)-Q(x)，P(x)* Q(x)。 四、算法说明 首先，定义一元多项式的存储方式，然后从键盘输入P(x)和Q(x)对应多项式的各对系数和指数，建立相应的一元多项式 五、测试结果参考下图 多项式相减 多项式相乘 六、源代码 1.多项式的相减 # include void InsAfter(LinkList p,LinkList s){ //插入结点 s->next=p->next; p->next=s; } int compare(ElemType e1,ElemType e2){ //比较 if(e1.expn>e2.expn) return 1; else if(e1.expn 一元稀疏多项式计数器预习报告 ：刘茂学号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 目录 一、需求分析 (4) 1、程序的功能 (4) 2、输入输出的要求 (4) 二、概要设计 (4) 三、详细设计 (4) 1、数据类型 (4) 2、模块的类C码算法 (5) 3、函数调用关系 (12) 四、调试分析以及设计体会 (14) 1、调试分析 (14) 2、调试分析中遇到的问题及解决方法 (16) 3、心得体会 (17) 五、使用说明 (18) 六、附录 (19) 1、参考书目 (19) 2、源程序代码（带注释） (19) 七、计算机科学与技术课程设计评分表 (28) 1)需求分析 A.程序的功能。 a.输入并建立多项式； b.输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,…,cn,en，其中n 是多项式的项数，ci,ei，分别是第i项的系数和指数，序列按指数降序排 列； c.多项式a和b相加，建立多项式a+b； d.多项式a和b相减，建立多项式a-b； e.计算多项式在x处的值； B.输入输出的要求。 每输入一个系数和指数确定一个一元多项式 2)概要设计 a.程序模块组成以及每个模块的功能。 主程序中通过调用void create(polynmial &L) 创建存储在单链表中的多项式，调用void display(polynmial L);输出显示多项式，调用void sort(polynomial &L);和void reverse(polynomial &L)对多项式进行排序，使其按降序排列，调用void add(polynomial La, polynomial Lb, polynomial&Lc)和void subtract(polynomial La, polynomial Lb, polynomial &Ld)对两个多项式进行加减操作 b．数据结构和数据库结构 多项式的系数为浮点型，多项式的指数为整型；用带表头结点的单链表存储多项式，多项式的项数存放在头结点中；多项式之间进行加减运算。 3)详细设计 A.采用C语言定义相关的数据类型。 元素类型，结点类型和指针类型 typedef struct node { float coef; // int exp; struct node *next; }Lnode, *polynmial; 实习一线性表、栈和队列及其应用 ——一元稀疏多项式的加法运算 【问题描述】 设计一个实现一元稀疏多项式相加运算的演示程序。 【基本要求】 （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 一、设计题目 一元多项式的加法、减法、乘法的实现。 二、主要内容 设有一元多项式A m(x)和B n(x). A m(x)=A0+A1x1+A2x2+A3x3+… +A m x m B n(x)=B0+B1x1+B2x2+B3x3+… +B n x n 请实现求M(x)= A m(x)+B n(x)、M(x)= A m(x)-B n(x)和M(x)= A m(x)×B n(x)。要求： 1) 首先判定多项式是否稀疏 2) 采用动态存储结构实现； 3) 结果M(x)中无重复阶项和无零系数项； 4) 要求输出结果的升幂和降幂两种排列情况 三、具体要求及应提交的材料 1．每个同学以自己的学号和姓名建一个文件夹，如：“312009*********张三”。里面应包括：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）、任务书和课程设计说明书的电子文档。 2．打印的课程设计说明书（注意：在封面后夹入打印的“任务书”以后再装订）。 四、主要技术路线提示 为把多个小功能结合成一个完整的小软件，需使用“菜单设计”技术（可以是控制台方式下的命令行形式，若能做成图形方式则更好）。 五、进度安排 共计两周时间，建议进度安排如下： 选题，应该在上机实验之前完成 需求分析、概要设计可分配4学时完成 详细设计可分配4学时 调试和分析可分配10学时。 2学时的机动，可用于答辩及按教师要求修改课程设计说明书。 注：只用课内上机时间一般不能完成设计任务，所以需要学生自行安排时间做补充。 六、推荐参考资料(不少于3篇) ［1］苏仕华等编著，数据结构课程设计，机械工业出版社，2007 ［2］严蔚敏等编著，数据结构（C语言版），清华大学出版社，2003 ［3］严蔚敏等编著，数据结构题集（C语言版），清华大学出版社，2003 指导教师签名日期年月日 系主任审核日期年月日 摘要 分析了matlab，mathmatic，maple等数学软件对一元多项式的计算过程，步骤后。由于这些软件比较大功能齐全，但是实用性不强。因此，利用microsoft visual studio 6.0开发工具，编程实现了一元多项式的加法、减法、乘法的计算器系统，该系统具有一元多项式的加法、减法、乘法等功能。 关键词：一元多项式; 软件; 计算 云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（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 实验一一元稀疏多项式的表示及加法运算 一、需求分析 1.程序的功能: ●多项式以指数递增的顺序输入。 ●设计的数据结构应有利于表示任意一元稀释多项式。 ●输出原始多项式及运算结果。 ●附加功能：乱序输入计算表达式结果 2.输入输出要求： ●多项式以指数递增的方式输入 ●输出原始多项式及其结果 3.测试数据 (1> , (2>0 , (3> , -1 附加功能测试数据： (4>, 二、概要设计 ●所用数据结构定义： struct Term{ //多项式结点的定义 float coef。//系数 int exp。//指数 Term * link。 Term(float c,int e,Term * next=NULL>{coef=c。exp=e。link=next。} Term *InsertAfter(float c,int e>。 Term & operator -=(Term & t>{ if(t.exp==exp> coef-=t.coef。return *this。} Term & operator +=(Term & t>{ if(t.exp==exp> coef+=t.coef。return *this。} friend ostream & operator<<(ostream &,const Term&>。 }。 class Polynomal{ //多项式的类定义public: Polynomal(>{ //构造函数，建立空链表first=new Term(0,-1>。 first->link=first。//必须链成环 } ~Polynomal(>{makeEmpty(>。} Polynomal(Polynomal & R>。//复制构造函数 Polynomal & operator=(const Polynomal & R>。//重载复制赋值操作符void insert(float c,int e,Polynomal& R>。//对于二项式进行插入排序 Polynomal sort(>。//对于多项式进行排序 Term * getHead(> const{return first。} void makeEmpty(>。 private: Term * first。 friend ostream & operator<<(ostream &,const Polynomal&>。 friend istream & operator>>(istream &,Polynomal&>。 friend Polynomal operator+(Polynomal&,Polynomal&>。 }。 主程序的流程及各模块之间的层次关系： 1)主程序流程 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.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所示，图中的长方框表示已被释放的结点。 院系：计算机科学学院 专业：软件工程 年级： 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为指针域，用链表来表示多项式。适用于不定的多项式，特别是对于项数再运算过程中动态增长的多项式，不存在存储溢出的问题。其次，对于某些零系数项，在执行加法运算后不再是零系数项，这就需要在结果多项式中增添新的项；对于某些非零系数项，在执行加法运算后可能是零系数项，这就需要在结果多项式中删去这些项，利用链表操作，可以简单的修改结点的指针以完成这种插入和删除运算（不像在顺序方式中那样，可能移动大量数据项）运行效率高。 福建农林大学计算机与信息学院 课程设计报告 课程名称：数据结构 课程设计题目：一元多项式的加法减法乘法的实现姓名： 系：软件工程系 专业：软件工程专业 年级：2014 学号： 指导教师：黄思先 职称：副教授 完成起止日期：2016.6.5 - 2016.7.1 2016年07月1日 福建农林大学计算机与信息学院课程设计结果评定 目录 一、问题分析和任务定义 (1) 二、程序设计内容 (1) 三、程序调试与测试 (7) 四、实验心得 (9) 五、程序编码 (9) 一、问题分析及任务定义 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。 【问题描述和基本要求】设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn 请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。 要求： 1) 首先判定多项式是否稀疏 2) 分别采用顺序和动态存储结构实现； 3) 结果M(x)中无重复阶项和无零系数项； 4) 要求输出结果的升幂和降幂两种排列情况 二、课程设计的内容 2.1函数 多项式创建函数PolyNode *Creatpoly() 多项式输出函数void Prin_poly(PolyNode *h) 多项式升序排列函数void Insortup(PolyNode *h) 多项式降序排列函数void Insortdown(PolyNode *h) 多项式合并函数void UnitePoly(PolyNode *h) 多项式相乘函数PolyNode *polymuti(PolyNode *h1,PolyNode *h2) 多项式相加函数PolyNode *addition(PolyNode *ha, PolyNode *hb) 多项式相减函数PolyNode *subduction (PolyNode *ha, PolyNode *hb) 2.2设计各个模块的流程图 （1）main() 学号： 课程设计 题目稀疏多项式的乘法实现 学院计算机科学与技术学院 专业软件工程专业 班级 姓名 指导教师夏红霞 2010年7月9日 课程设计任务书 学生专业班级： 指导教师：夏红霞工作单位：计算机科学与技术学院 题目: 稀疏多项式的乘法实现 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写 等具体要求） 1、系统应具备的功能： （1）设计稀疏多项式的存储结构 （2）实现稀疏多项式的乘法 （3）输出运算结果 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等； （4）结束语； （5）参考文献。 时间安排：2010年7月5日－9日（第19周） 7月5日查阅资料 7月6日系统设计，数据结构设计，算法设计 7月7日 -8日编程并上机调试 7月9日撰写报告 7月10日验收程序，提交设计报告书。 指导教师签名：2010年7月4日系主任（或责任教师）签名：2010年7月4日 稀疏多项式的乘法实现 摘要：该程序主要部分有：①首先定义多项式再用链表表示稀疏多项式的存 储结构；②多项式的输入并对其各项按照幂从大到小排列；③实现稀疏多项式的 加法运算；④再加法运算的基础上对多项式进行乘法运算。 关键字：稀疏多项式，链表，排列，乘法运算 0.引言 在科学技术日新月异的今天，计算机技术广泛的应用于人们的日常生活中。其中数据结构就是比较突出的一种，数据结构是计算机科学的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。而多项式的乘法在日常生活和学习中具有什么重要的作用，本程序就是用数据结构里的算法思想加上c++语言写的，用于处理稀疏多项式的乘法问题。 1.需求分析 系统应具备的功能，具体如下： （1）设计稀疏多项式的存储结构 （2）实现稀疏多项式的乘法 （3）输出运算结果 2.数据结构设计 struct poly{ int c; int e; poly * next;} 3.算法设计 实验一一元多项式的表示与相加 实验目的： 1.复习并熟练掌握数据结构所使用的程序设计语言——C语言； 2.学会单步跟踪、调试自己的程序； 3.加深对线性表特别是链表知识的理解和掌握，并能够运用相关知识来解决相关的具体问题，如一元多项式相加等； 程序流程： 1.定义一元多项式链表结构体类型； 2.输入多项式项数以分配存储空间； 3.输入多项式每项的系数和指数，将其插入当前多项式链表。同时判断是否有与当前节点指数相同的项，若存在，则将两项系数相加合并。此外，若存在系数为0的项，将其存储空间释放； 4.进行多项数加法时，新建一个存储结果的链表，分别将两多项式各项依次插入结果多项式即完成多项式相加运算； 5.进行多项数加法时，将减项多项式各项系数化为相反数后进行加法操作，即完成多项式相减运算； 6.对x赋值后，将x值代入多项式进行运算得到多项式的值； 7.输出多项式。 注意：进行完一次运算以后，应该及时销毁无用多项式以释放空间以便再次应用。 算法及注释： 1）定义一元多项式链表结构体类型 typedef struct Lnode{ float cof; //定义系数 int exp; //定义指数 struct Lnode *next; //定义指针变量指向下一个节点 }Lnode ,*Linklist; //定义新的变量类型 2）建立多项式存储线性链表头结点 void makehead(Linklist &head){ head=(Linklist)malloc(sizeof(Lnode)); //建立新的节点 head->exp=-1; head->next=NULL; //指针赋空 head->cof=1; } 数据结构实验报告实验一：一元多项式相加 姓名：周成 学号： 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 一元稀疏多项式计数器预习报告 姓名：刘茂学号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一元多项式的相加减复习过程
一元稀疏多项式计算器实验(报告+程序)
一元稀疏多项式设计报告.doc
一元稀疏多项式的加法运算(数据结构实习)
实验报告——2 一元稀疏多项式计算器
数据结构课程设计-一元多项式的加法、减法、乘法的实现
(整理)一元稀疏多项式计算器
一元稀疏多项式计算器C语言课程设计
实验一一元稀疏多项式表示及加法运算
一元多项式相加完整实验报告
数据结构 一元多项式的计算
一元稀疏多项式计算器(数据结构)
一元多项式的加法减法乘法的实现
稀疏多项式的乘法实现
数据结构：一元多项式的表示与相加
数据结构-实验一-一元多项式相加
一元稀疏多项式计算器实验
相关主题
文本预览