当前位置：文档之家 › 《程序语言课程设计 - 高次多项式的加法和乘法》

《程序语言课程设计 - 高次多项式的加法和乘法》

  • 格式：doc
  • 大小：321.32 KB
  • 文档页数：26

西安文理学院软件学院课程设计报告设计名称：数据结构课程设计设计题目：两个高次多项式的加法和乘法学生学号：1402120135专业班级：软件工程1班学生姓名：张文东学生成绩：指导教师（职称）：韩利凯（教授）课题工作时间：2014.6.16 至2014.6.27软件学院课程设计任务书指导教师：韩利凯院长：日期：2014年6月16日软件学院课程设计进度安排表学生姓名：张文东学号：1402120135 专业：软件工程班级：1班指导教师签名：2014年6月16日成绩评定表学生姓名：张文东学号：1402120135 专业：软件工程班级：1班摘要摘要：本课程设计主要解决任意两个高次多项式的乘法运算。

所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。

从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。

在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。

这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在本课程设计中尤为重要，这也是本程序好坏的一个评定。

程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。

关键词：高次多项式；加法；乘法；时间复杂度；空间复杂度西安文理学院计算机科学系课程设计报告目录目录 (I)第一章课题背景 (2)1.1 绪论 (2)1.2 主要内容 (2)第二章设计简介及设计方案论述 (3)2.1 系统分析 (3)2.1.1 功能需求 (3)2.1.2 数据需求 (3)2.1.3 系统需求 (3)2.2 总体设计 (3)2.2.1 系统设计方案 (3)2.2.2 功能模块设计 (4)第三章详细设计 (5)3.1 主要流程图 (5)3.2 链表模块 (6)3.3 加法模块 (8)3.4 乘法模块 (10)第四章设计结果及分析 (12)4.1 调试与测试 (12)4.1.1 调试 (12)4.1.2 测试 (12)4.1.3 运行界面 (13)4.2 结果分析 (13)总结 (14)参考文献 (15)附录 (16)第一章课题背景1.1 绪论随着科技的进步，社会的不断发展，计算器已普遍应用于各行各业，为了帮助人们提高工作效率，节约运算时间，设计一个多功能的计算器是很有必要的，在此设计一个高次多项式计算器可以很方便的对多项式相加、相减、相乘，对提高人们的运算效率很有帮助。

这样一个程序需要用到C++多方面的知识，要实现多项式的建立和输入输出等功能，必须要熟练的掌握C++，在此尤其是链表的灵活运用和结点特点。

1.2 主要内容用C++语言实现多项式的输入输出和多项式的加减乘等运算，其中主要用到链表和结点的相关知识,具体功能如下：1）输入并建立多项式；2）输出多项式；3）两个多项式相加，输出和多项式；4）两个多项式相减，输出差多项式。

第二章设计简介及设计方案论述2.1 系统分析2.1.1 功能需求实现任意两个高次多项式的加法和乘法2.1.2 数据需求在输入过程中，首先要给定输入的数据，数据只能是数字，不能是字母或其他，不能连续输入数据，必须要求以空格分开要输入的数据。

2.1.3 系统需求系统必须安全可靠，不会出现无故死机状态，运算速度要快。

2.2 总体设计2.2.1 系统设计方案用户输入高次多项式系数和指数，用单链表储存你输入的数据，输出两个多项式相加和相乘之后的结果。

(1) 数据结构的选择本程序选择的数据结构是单链表，原因如下：当需要插入数据元素时，临时动态地为其申请一个存储空间，而不是将结点放在一个定义的数组中，删除数据元素时，可以释放该数据元素所占用的空间，即可以根据表的实际需要临时动态的分配存储空间以存储表中的数据元素。

单链表是有限个具有相同数据类型的数据元素组成的链表且该链表的每一个结点只有一个指针域。

带头结点的单链表是在单链表的第一个结点之前加一个同类型的结点，目的是为了使链表有一致的描述。

本程序解决的是两多项式相乘的问题，多项式的项数本身就是不确定的，而且相乘后的多项式可能含有指数相同的问题，这时就需要合并，合并后其中的一项就没有用了需要删除，不然就浪费内存空间。

基于以上几点所以采用了链表。

链表具有动态生成，灵活添加或删除结点的特点，尽可能节省存储空间。

(2) 文件保存方式运用带头节点的单链表储存多项式。

(3) 抽象数据类型定义主要定义多项式的系数和指数，系数项和指数项均用整型定义。

(4) 存储结构采用链式结构，建立链表储存输入的多项式(5) 算法设计先将两个已知的多项式的指数和系数存放在指定链表中在执行乘法运算。

乘法运算的过程是将A式中的第一项与B式的每一项相乘，在将A式的第二项与B式的每一项相乘，依次下去直到A式的所有项与B式乘完为止。

将相乘后所得的指数、系数存在预先建好的C链表中。

C链表中如果有指数相同的项就需要合并，合并时将结果放在前一个项中，将后一项删除。

首先定义3个指针，x、y、z，x、y指向首元素结点z指向第二个结点，用z结点中指数项与x结点的指数项比较，如果不同指针z向后移，若相同则将z结点的系数加到x上去然后将z所在结点空间释放，并且指针z后移。

直到指针z指向空后，将指针x后移一项，并令z指向x的下一项，然后按上述步骤依次执行，直到x指向空结束。

这里指针y是z的前驱结点他的作用是合并后结点空间释放结点空间将此结点的前后两项链接起来。

本程序核心部分全部是运用while 循环语句实现的。

2.2.2 功能模块设计第三章详细设计多项式的建立主要需要建立新链表，并分配给这个新链表一定量的存储空间，分配的存储空间内进行运算；多项式加减乘等运算主要运用了链表的建立，链表存储空间分配，链表的查找，插入与连接进行计算。

3.1 主要流程图此阶段是程序构建的思路，是本程序的结构图，同时也体现出本程序将要达到的功能，如图3-1所示：图 3-1 主流程图3.2 链表模块此阶段是程序中链表的主要流程，如图3-2所示：图 3-2 链表结构图主要代码如下：list<term> Poly_add(list<term>&poly_list_first,list<term>&poly_list_second) {list<term> poly_list_result; //用以存储运算结果list<term>::iterator iter_first = poly_list_first.begin();list<term>::iterator iter_second = poly_list_second.begin();/*该while循环针对两个链表迭代器都没有指到结尾的情形*/while (iter_first != poly_list_first.end() && iter_second != poly_list_second.end()){term t_temp;term t_first = (term)*iter_first;term t_second = (term)*iter_second;if (t_first.exp>t_second.exp){poly_list_result.push_back(t_first);iter_first++;}else if (t_second.exp>t_first.exp) {poly_list_result.push_back(t_second);iter_second++;}else{t_temp.coef = t_first.coef + t_second.coef;t_temp.exp = t_first.coef;poly_list_result.push_back(t_temp);iter_first++;iter_second++;}}//该for循环针对第一个多项式的迭代器没有指到结尾for (;iter_first != poly_list_first.end();iter_first++){poly_list_result.push_back(*iter_first);}//该for循环针对第二个多项式的迭代器没有指到结尾for (; iter_second != poly_list_second.end(); iter_second++){poly_list_result.push_back(*iter_second);}return poly_list_result;}3.3 加法模块此阶段是程序中加法模块的主要流程，如图3-3所示：图 3-3 加法模块结构主要代码如下：void Poly_add(){list<term>::iterator iter_first = m_poly_list_first.begin();list<term>::iterator iter_second = m_poly_list_second.begin();while (iter_first != m_poly_list_first.end() && iter_second != m_poly_list_second.end()){term t_temp;term t_first = (term)*iter_first;term t_second = (term)*iter_second;if(t_first.exp>t_second.exp){m_poly_list_result.push_back(t_first);iter_first++;}else if(t_second.exp>t_first.exp){m_poly_list_result.push_back(t_second);iter_second++;}else{t_temp.coef = t_first.coef + t_second.coef;t_temp.exp = t_first.exp;m_poly_list_result.push_back(t_temp);iter_first++;iter_second++;}}for(;iter_first != m_poly_list_first.end(); iter_first++){m_poly_list_result.push_back(*iter_first);}for (;iter_second != m_poly_list_second.end(); iter_second++){m_poly_list_result.push_back(*iter_second);}}3.4 乘法模块此阶段是程序中乘法模块的主要流程，如图3-4所示：图3-4 乘法模块结构主要代码如下：void Poly_multi(){list<term> poly_list_result;list<term>::iterator iter_first = m_poly_list_first.begin();for (; iter_first != m_poly_list_first.end(); iter_first++){list<term> poly_list_temp; //用以存储多项式的中间运算结果list<term>::iterator iter_second=m_poly_list_second.begin();for (;iter_second != m_poly_list_second.end();iter_second++){term t_temp; //用以存储项的中间运算结果term t_first = (term)*iter_first;term t_second = (term)*iter_second;//此处实现多项式项的相乘t_temp.coef = t_first.coef*t_second.coef; //系数相乘t_temp.exp = t_first.exp + t_second.exp; //指数相加poly_list_temp.push_back(t_temp);}//此处调用私有成员函数Poly_add()poly_list_result = Poly_add(poly_list_temp, poly_list_result);}//将运算结果赋值给私有数据成员,用以输出m_poly_list_result = poly_list_result;}第四章设计结果及分析4.1 调试与测试4.1.1 调试调试过程主要是运行编制好的程序，然后遇到错误后根据系统的提示，找到相关的问题所在。

合集下载

多项式的加法与乘法

多项式的加法与乘法

多项式的加法与乘法一、课题内容和要求给定两个多项式，用程序实现这两个多项式的相加和相乘。

（可以利用单链表法实现）例如给定多项式X+3X 2-4X 3+5X 4和多项式X 2+3X 3-4X 4。

二、需求分析整个程序中有两个大类，项结点的TERM 类和多项式的POL YNOMINAL 的类。

TERM 类用以存放项结点，POL YNOMINAL 类用以构建多项式的每一项。

而在进行多项式的加法和乘法时要进行多次的插入和删除操作，因此采用线性表的链接存储。

主要的实现函数有多项式类的输入输出函数，多项式的相加函数，多项式的相乘函数，几个友元函数。

而多项式类的构造函数和析构函数也是必不可少的。

最后加上主函数即能完成课题内容和要求。

三、概要设计先定义链表类型结点和一元多项式，然后申明各个功能函数，并编写功能函数的算法，然后定义一个主函数，用于调用各个功能函数。

其中输入输出函数由链表进行存储。

其系统结构如图所示：一元多项式的加法乘法运算一元多项式的创建 一元多项式的乘法 一元多项式的加法 一元多项式的消除一元多项式的创建流程图如下：NY（1）一元多项式的创建流程图开 始 创建一个含有n 个链表类型结点的项按降幂分别输入各项系数和指数 系数指数均小0？ 一元多项式创建成功（2）多项式相加流程图开始判断输入的p多项式系数>=0?P q指数相等时系数相加当q的系数大于p，则跳过q->exp大的项当q的系数小于p，则p的系数和指数生成新的节点插入p 进行运算开始给出两个多项式将系数相乘，指数相加将运算结果相加，并输出（3）多项式的相乘流程图四、详细设计在定义多项式类polynominal之前，首先构建一个项结点的c++类Term，用以存放系数coef和指数exp。

具体实现代码如下：class Term{ public:Term(int c,int e);Term(int c,int e,Term* nxt);Term* InsertAfter(int c,int e); //在this指针指示的结点后插入新结点private:int coef;int exp;Term *link;friend ostream &operator<<(ostream &,const Term &); //重载"<<"，输出多项式的一项friend class Polynominal;};Term::Term(int c,int e):coef(c),exp(e){ link=0;}Term::Term(int c,int e,Term *nxt):coef(c),exp(e){ link=nxt;}Term* Term::InsertAfter(int c,int e){ link=new Term(c,e,link); //为新项申请结点的存储单元，并用Term函数将return link; //c,e和this->link的值填入新结点的相应域}其中公有成员函数InsertAfter的功能是建立一个新的项结点，系数为c,指数为e，并将新结点插入调用该函数项结点及其后继结点之间。

《C语言程序设计课程设计》题目

《C语言程序设计课程设计》题目

1 一元稀疏多项式的运算问题描述：设有两个带头指针的单链表表示两个一元稀疏多项式A、B，实现两个一元稀疏多项式的处理。

实现要求：⑴输入并建立多项式；⑵输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……c n，e n，其中n是多项式的项数，c i，e i分别为第i项的系数和指数。

序列按指数降序排列；⑶多项式A和B相加，建立多项式A+B，输出相加的多项式；⑷多项式A和B相减，建立多项式A-B，输出相减的多项式；⑸多项式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)(x+x2+x3)+0(4)(x+x3)-(-x-x-3)2 成绩排序假设某年级有4个班，每班有45名同学。

本学期有5门课程考试，每门课程成绩是百分制。

假定每个同学的成绩记录包含：学号、姓名各门课程的成绩共7项，其中学号是一个10位的字符串，每个学生都有唯一的学号，并且这4个班的成绩分别放在4个数组中，完成以下操作要求：⑴编写一个成绩生成函数，使用随机数方法，利用随机函数生成学生的各门课程的成绩（每门课程的成绩都是0∽100之间的整数），通过调用该函数生成全部学生的成绩；⑵编写一个平均成绩计算函数，计算每个同学的平均成绩并保存在成绩数组中；⑶用冒泡排序法对4个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序；⑷ 用选择排序法对4个班的成绩按每个同学的平均成绩的以非递增方式进行班内排序；⑸ 对已按平均成绩排好序的4个班的同学的构造一个所有按平均成绩的以非递增方式排列的新的单链表；⑹ 设计一个菜单，至少具有上述操作要求的基本功能。

3 栈及其操作问题描述：栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。

多项式相加c语言

多项式相加c语言

Print(&sum);
reset(&p);
reset(&q);
reset(&sum);
return 0;
}
```
在上述代码中，首先定义了一个`Node`结构体，包含多项式的系数和指数，并通过链表的方式存储多项式的每一项。然后，实现了一系列函数，包括多项式的增加、输出、相加和消除。在`main`函数中，调用这些函数来完成多项式的输入、相加和输出。
请注意，这只是一个简单的示例，实际应用中可能需要考虑更多的边界情况和错误处理。
以下是一个简单的 C 语言示例，展示了如何实现多项式相加：
```c
#include <stdio.h>
#include <stdlib.h>
// 定义结构的数据部分
struct poly {it zhishu;float xishu;
};
// 定义一个多项式结构
typedef struct node {
s->date.xishu = s->date.xishu + s->next->date.xishu;
s->next = s->next->next;
} else {
s = s->next;
}
}
d = d->next;
}
}
// 链表的消除函数
void reset(Node *pList) {
Node *p = pList;
while (p->next) {
if (flog == 1)
printf(" + ");
else {
多项式的加法和乘法

多项式的加法和乘法

while(L->next){
e.coef=L->next->data.coef*p->data.coef;
e.expn=L->next->data.expn+p->data.expn;
if(!LocateNode(pa,e))
InsertNode(pa,e);
L=L->next;
p=p->next;
}
printf("tNode *AddPolyn(LinkList La,LinkList Lb){
ListNode *pa,*pb,*pc,*s;
LinkList Lc;
float sum;
pa=La->next;
pb=Lb->next;
s=(ListNode *)malloc(sizeof(ListNode));
s->data.coef=e.coef;
s->data.expn=e.expn;
s->next=p->next;
p->next=s;
}
ListNode *CreatPolyn(LinkList L,int n){
free(Lb);
return Lc;
}
ListNode *CreatPolyn1(LinkList L,LinkList p){
LinkList pa;
DataType e;
pa=(ListNode *)malloc(sizeof(ListNode));
pa->next=NULL;
pc->next=NULL;