课程设计报告(一元稀疏矩阵计算器)

实习4、稀疏矩阵运算器一、需求分析1. 问题描述稀疏矩阵是指那些多数元素为零的矩阵。

利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。

实现一个能进行稀疏矩阵基本运算的运算器。

2. 基本要求以带“行逻辑连接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵的相加、相减和相乘运算。

稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。

3. 实现提示(1)首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。

可设聚矩阵的行数和列数不超过20。

(2)程序可以对三元组的输入顺序加以限制，例如，按行优先。

注意研究教科书5.3.2节中的算法，以便提高计算效率。

(3)在用三元组表示稀疏矩阵时，相加或者相减所得的结果矩阵应该另生成，乘积矩阵也可以用二维数组存放。

二、概要设计ADT SparseMatrix{数据对象：D={a ij |i=1,2,3……m;j = 1,2,3……n;a i,j ∈intSet,m 和n 分别称为矩阵的行数和列数}数据关系：R ={ Row,col}Row ={<a i,j ,a i,j+1>|1≤i ≤m ，1≤j ≤n-1}Col = {< a i,j ,a i,j+1>|1≤i ≤m-1，1≤j ≤n}基本操作：CreateSMatrix(*T);操作结果：创建稀疏矩阵T 。

AddRLSMatrix(M,N,*Q);初始条件：稀疏矩阵M 和N 的行数列数对应相等。

操作结果：求稀疏矩阵的和Q=M+N 。

SubRLSSMatrix(M,N,*Q);初始条件：稀疏矩阵M 和N 的行数列数对应相等。

操作结果：求稀疏矩阵的差Q=M-N 。

SMatrixrpos(*T)初始条件：稀疏矩阵T 存在。

操作结果：求稀疏矩阵的各行第一个非零元的位置表。

MulTSMatrix(M,N,*Q);初始条件：稀疏矩阵M 的列数与N 的行数对应相等。

数据结构实习报告——一元稀疏多项式运算器的设计一、引言在计算机科学领域中，数据结构是研究数据组织、存储和管理的关键概念之一。

在本次实习中，我设计并实现了一个一元稀疏多项式运算器，旨在使用适当的数据结构和算法来高效地进行多项式的加法、减法和乘法运算。

本报告将详细介绍该运算器的设计思路、算法实现以及性能评估。

二、设计思路1. 多项式的表示在设计多项式运算器时，首先需要确定多项式的表示方法。

为了高效地处理稀疏多项式，我选择使用链表作为基本数据结构。

每个节点包含多项式的系数和指数，并通过指针连接在一起形成链表。

这种表示方法可以有效地处理稀疏多项式，减少了不必要的空间浪费。

2. 多项式的输入和输出为了方便用户输入和输出多项式，我设计了简单的交互界面。

用户可以通过命令行输入多项式的系数和指数，并选择进行的运算操作。

运算结果将直接在命令行中输出。

三、算法实现1. 多项式的加法多项式的加法是指将两个多项式相加得到一个新的多项式。

为了实现这个功能，我设计了一个算法如下：- 创建两个空的链表，分别表示两个多项式。

- 逐个读取用户输入的系数和指数，并将其插入到相应的链表中。

- 对两个链表进行遍历，根据指数的大小关系进行合并操作。

- 将合并后的结果链表输出。

2. 多项式的减法多项式的减法是指将一个多项式减去另一个多项式得到一个新的多项式。

为了实现这个功能，我设计了一个算法如下：- 创建两个空的链表，分别表示两个多项式。

- 逐个读取用户输入的系数和指数，并将其插入到相应的链表中。

- 对第二个链表中的每个节点的系数取相反数。

- 对两个链表进行遍历，根据指数的大小关系进行合并操作。

- 将合并后的结果链表输出。

3. 多项式的乘法多项式的乘法是指将两个多项式相乘得到一个新的多项式。

为了实现这个功能，我设计了一个算法如下：- 创建一个空的链表，表示乘法结果。

- 逐个读取用户输入的系数和指数，并将其插入到链表中。

- 对第一个链表中的每个节点，与第二个链表中的每个节点进行乘法运算，并将结果插入到结果链表中。

课程设计报告1.需求分析【问题描述】设计一个一元稀疏多项式简单计算器.【基本要求】一元稀疏多项式基本功能包括：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；【测试数据】1)(2x+5x8-3.1x11)+(11x9-5x8+7)=(-3.1x11+11x8+2x+7)2)(-1.2x9+6x-3+4.4x2-x)-(7.8x15+4.4x2-6x-3)=(-7.8x15-1.2x9+12x-3-x)3)(x5+x4+x3+x2+x+1)-(-x4-x3)=(x5+x2+x+1)4)(x3+x)-(-x3-x)=05)(x100+x)+(x200+x100)=(x200+2x100+x)6)(x3+x2+x)+0=x3+x2+x7)互换上述测试数据中的前后两个多项式.2.概要设计ADT Polynomial{数据对象: D={a i|a i∈TermSet, i=1,2,…,m,m≥0,TermS et中的每个元素包含一个表示系数的实数和表示指数的整数}数据对象: R1={<a i,a i-1>|a i,a i-1∈D,且a i-1中的指数值小于ai中的指数,i=2,…,m}基本操作：CreatePolyn(void)Result: 指数由大到小输入m项的系数和指数,建立一元多项式pPrintPoly(LNode Head)Result: 输出一元多项式AddPoly(LNode H1,LNode H2)Condition: 一元多项式pa,pb已存在Result: 完成多项式相加运算,即pa=pa+pb,并销毁一元多项式pb.SubtractPoly(LNode H1,LNode H2)Condition: 一元多项式pa,pb已存在Result: 完成多项式相减运算,即pa=pa-pb,并销毁一元多项式pb.}ADT Polynomial3.详细设计【数据类型定义】typedef struct node{int expn,coef;struct node *next;}Nodetype,*LNode; //定义结点类型【函数原型定义】LNode CreatePolyn(void);Void PrintPoly(LNode Head);LNode AddPolyn(LNode H1,LNode H2);LNode SubPolyn(LNode H1,LNode H2);【核心算法描述】CreatePolyn()LNode CreatePolyn(void) //创建表达式{LNode Head,p,pre,pree;int x,z;Head=(LNode)malloc(sizeof(Nodetype));Head->next=NULL;printf("当你输入的系数为0时，输入将结束！\n");printf("请输入第一项系数:");scanf("%d",&x);if(x==0){p=(LNode)malloc(sizeof(LNode));p->coef=0;p->expn=0;Head->next=p;p->next=NULL;}while(x!=0){printf("请输入指数:");scanf("%d",&z);p=(LNode)malloc(sizeof(Nodetype));p->coef=x;p->expn=z;pre=Head;while(pre->next&&pre->next->expn>=z)//原有项指数大于插入项{pree=pre;pre=pre->next;}p->next=pre->next;//插入项pre->next=p;if(pre->expn==p->expn)//原有项指数等于插入项{pre->coef+=p->coef;pre->next=p->next;free(p);}if(pre->coef==0)//系数为0{pree->next=pre->next;free(pre);}printf("请输入系数:");scanf("%d",&x);}if(Head->next==NULL)//多项式空{pre=(LNode)malloc(sizeof(LNode));pre->coef=0;pre->expn=0;pre->next=Head->next;Head->next=pre;}return Head;}PrintPolyn()void PrintPolyn(LNode Head) //输出表达式{LNode pre;pre=Head->next;if(pre->expn==0)//指数为0printf("%d",pre->coef);elseprintf("%d*X(%d)",pre->coef,pre->expn);pre=pre->next;while(pre)//系数不为0{if(pre->expn==0)//指数为0{if(pre->coef>0)printf("+%d",pre->coef);else if(pre->coef<0)printf("%d",pre->coef);}else//指数不为0{if(pre->coef>0)printf("+%d*X(%d)",pre->coef,pre->expn);else if(pre->coef<0)printf("%d*X(%d)",pre->coef,pre->expn);}pre=pre->next;//遍历每一项}printf("\n");}AddPolyn()LNode AddPolyn(LNode H1,LNode H2) //表达式相加{LNode H3,p1,p2,p3,pre;//p1第一个多项式的项，pre p的前一项H3=(LNode)malloc(sizeof(LNode));H3->next=NULL; //建立一个空的多项式p1=H1->next; //第一个多项式的第一项p2=H2->next;pre=H3; //while(p1&&p2){if(p1->expn>p2->expn)//第一个多项式的项的指数大于第二个的{p3=(LNode)malloc(sizeof(LNode));p3->expn=p1->expn;p3->coef=p1->coef;p3->next=pre->next;pre->next=p3;pre=p3;p1=p1->next;}else if(p1->expn<p2->expn)//第一个多项式的项的指数小于第二个的{p3=(LNode)malloc(sizeof(LNode));p3->expn=p2->expn;p3->coef=p2->coef;p3->next=pre->next;pre->next=p3;pre=p3;p2=p2->next;else if(p1->coef+p2->coef!=0)//相加为不0，指数相同系数相加{p3=(LNode)malloc(sizeof(LNode));p3->expn=p1->expn;p3->coef=p1->coef+p2->coef;p3->next=pre->next;pre->next=p3;pre=p3;p1=p1->next;p2=p2->next;}else//相加为0{p1=p1->next;p2=p2->next;}}while(p2){p3=(LNode)malloc(sizeof(LNode));p3->expn=p2->expn;p3->coef=p2->coef;p3->next=pre->next;pre->next=p3;pre=p3;p2=p2->next;}while(p1){p3=(LNode)malloc(sizeof(LNode));p3->expn=p1->expn;p3->coef=p1->coef;p3->next=pre->next;pre->next=p3;pre=p3;p1=p1->next;}return H3;}LNode SubstractPolyn(LNode H1,LNode H2) //表达式相减{//让系数变负，代入加法LNode H3,pre;pre=H2->next;while(pre){pre->coef=-pre->coef;pre=pre->next;}H3=AddPolyn(H1,H2);pre=H2->next;while(pre){pre->coef=-pre->coef;pre=pre->next;}return H3;}【函数调用关系】main()调用CreatePoly()，PrintPoly()，AddPoly()，scanf()函数输入，printf()函数输出。

软件学院课程设计报告书课程名称数据结构设计题目一元稀疏多项式计算器专业班级软件工程11级1班学号 1120010107姓名指导教师2013 年 1月目录1设计时间 42设计目的 43设计任务 44设计内容 44.1需求分析 44.1.1.程序所能达到的功能 44.1.2.输入的形式和输入值的范围 44.1.3.输出的形式 44.1.4.测试数据 54.2总体设计 54.2.1.本程序中用到的所有抽象数据类型的定义 54.2.2.主程序的流程 74.2.3.各程序模块之间的层次（调用）关系 74.3详细设计 74.3.1实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法 74.3.2.对主程序和其它主要函数伪码算法 114.3.3.函数的调用关系图 124.4测试与分析 124.4.1测试 124.4.2分析 134.5 附录 135 总结与展望 19参考文献 20 成绩评定 204.1.3.输出的形式本程序要输出的是分别把创建的第一个多项式和第二个多项式按指数升序排序，并且把计算加减后的运算结果按指数升序排列输出。

4.1.4.测试数据(1)正确：图1程序输出(2)错误：图2程序输出4.2总体设计4.2.1.本程序中用到的所有抽象数据类型的定义ADT List{初始条件：多项式L已存在。

操作结果：显示多项式。

AddPoly( L_1,L_2,L_add )初始条件：多项式L_1,L_2,L_add已存在。

操作结果：生成L_1,L_2之和的多项式L_add DiffPoly( L ,L_diff)初始条件：多项式L ,L_diff已存在。

操作结果：生成L的导数多项式L_add。

AlterPoly( L )初始条件：多项式L已存在。

操作结果：将L多项式取相反数。

}ADT Poly4.2.2.主程序的流程图3主程序流程4.2.3.各程序模块之间的层次（调用）关系图4模块层次调用关系4.3详细设计4.3.1实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法Typedef Polynomial //定义结构体类型{float coef; //多项式系数int expn; //多项式指数struct Polynomial *next; //多项式的下一个指针域}*Polyn,Polynomial;void Insert( &p,&h) //定义插入函数{if(p.coef==0) //若p的系数是则释放pfree(p);else{q1=h;q2=h->next;while(q2&&q2.expn<p.expn) //找到链表中第一个指数大于p的指数的项{q1=q2;q2=q2.next;}PrintPolyn(pc);pc=SubtractPolyn(pa,pb);printf("\n输出多项式之差a-b="); PrintPolyn(pc);printf("\n 感谢使用此程序！\n"); DestroyPolyn(pa);DestroyPolyn(pb);4.3.3.函数的调用关系图图5函数调用关系4.4测试与分析4.4.1测试输入：a=2X+3X^2; b=2X^3+7X^4输出：a+b=2X+3X^2+ 2X^3+7X^4a-b=2X+3X^2-2X^3-7X^4图6程序输出。

数据结构课程设计系别电子信息系专业计算机科学与技术班级学号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 建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造。

每次输入一项的系数和指数，可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。

多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en3、设计思路分析要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polyn p中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。

为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：① 若p->expn<q->expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。

课程设计成果学院: 计算机工程学院班级: 计算机科学与技术班学生姓名: 学号:设计地点（单位）：设计题目: 一元稀疏多项式计算器程序完成日期：年月日成绩(五级记分制):_____ _ __________教师签名:__________ _______________荆楚理工学院课程设计任务书设计题目：教研室主任：指导教师：年月日目录1 需求分析 (1)2 设计概要 (2)2.1基本结构 (2)2.2 基本功能模块图 (2)3算法思想 (3)3.1建立多项式 (3)3.2多项式相加 (3)3.3多项式相减 (3)3.4链表的输出 (3)4 详细设计 (4)4.1 函数功能介绍 (4)4.2结构体的定义 (4)4.3产生链表函数 (4)4.4插入结点 (5)4.5多项式的相加函数 (5)4.6多项式相减函数 (7)4.7主函数 (7)5测试结果及运行效果 (10)参考文献 (13)附录全部代码 (14)1 需求分析1、一元多项式简单计算器的基本功能是：1.1输入并建立多项式；1.2输出多项式，输出形式为整数序列n,c1,e1,c2,e2,…,cn,en，其中n是多项式的项数，ci和ei分别是第I项的系数和指数，序列指指数降序排列；1.3多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b。

实现提示：用带头结点的单链表存储多项式，多项式的项数存在头结点2、设计思路：2.1 定义线性表的动态分配顺序存储结构；2.2 建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造。

每次输入一项的系数和指数，可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。

多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en3、设计思路分析：要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polyn p中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。

一个一元稀疏多项式简单计算器课程设计报告课程课课课告学院,课程名,称课课班课,学生姓名, ,学号目课1 一元稀疏多课式课算器1.1 述概课了课课任意多课式的加法～法～因此课课课课表的课～有一系～指～下减构体它个数数一指课个个元素3使用课言,课言C课课课境,VC++ 6.01.2 课课容内、课课描述1课课一一元稀疏多课式课课课算器。

个基本要求,一元稀疏多课式课课课算器的基本功能是,;,课入建立多课式～并1;,课出多课式～课出形式课整序列,数～其中是多课式2n,c1,e1,c2,e2,…cn,en,n的课～数分课是第课的系和指～序按指降序排序～数数数数c1,e1,i;,多课式和相加～建立多课式3aba+b;;,多课式和相～建立多课式减4aba-b;;,课算多课式在课的课～5x;,课算器的界面;课做,。

仿真6、需求分析2;,课入的形式和课入课的范课,1课入是课课课入的～课入的容课多课式的系和指～课任意的整～指课大于从内数数数数数等于的整数0;,课出的形式2从屏并减幕课出～课示用课课入的多课式～课示多课式加以后的多课式的课。

;,程序所能到的功能达3,课入建立多课式～并a,课出多课式～课出形式课整序列,数其中是多课式的课数～bn,c1,e1,c2,e2,……,cn,en,n和分课是第课的系和指～序列按指降序排列～数数数cieii,多课式和相加～建立多课式～caba+b,多课式和相～建立多课式减～daba-b,多课式的课出形式课课表式～数学达e,系课课数的非零课的课出形式中略去系数～而的课出形式课。

f11-1x-x1.3 要课课概、存课课构1typedef struct Polynomial { float coef; int expn; struct Polynomial *next;}*Polyn,Polynomial;课课用以存放第构体课的系和指和下一指课～以课课课基课。

数数个i、函数2Polyn CreatePolyn(Polyn head,int m)课函用于建立一课指课课数个～课课数的一元多课式headm课函用于课毁多课式数void DestroyPolyn(Polyn p)课函用于课出多课式数void PrintPolyn(Polyn P) aPolyn AddPolyn(Polyn pa,Polyn pb)课函用于求解建立多课式数并～返回其课指课a+bPolyn SubtractPolyn(Polyn pa,Polyn pb)课函用于求解建立多课式数并～返回其课指课a-bfloat ValuePolyn(Polyn head,int x)课函用于课入数课～课算返回多课式的课并x课函用于比课数和的指数int compare(Polyn a,Polyn b) ab、流程课3一元稀疏多课式课算器课入建立多课式并课出多课式课算多课式在x课的课课算a+b课算a-b课束1.4 课课分析1、课课分析2、行课果运1.5 源程序代课#include<stdio.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); else { Polynq1,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){q1->next=q2->next;free(q2);}}else{p->next=q2;q1->next=p; } } } Polyn CreatePolyn(Polyn head,int m) { int i; 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); } return head; } void DestroyPolyn(Polyn p) {Polyn 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) { putchar('0'); printf("\n"); return; } while(q) { if(q->coef>0&&flag!=1) putchar('+'); if(q->coef!=1&&q->coef!=-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; else return1; }Polyn AddPolyn(Polyn pa,Polyn pb) {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); }return headc; }Polyn SubtractPolyn(Polyn pa,Polyn pb) {Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p){ p->coef*=-1; p=p->next; } pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next) p->coef*=-1; return pd;}float ValuePolyn(Polyn head,int x) {Polyn p; int i,t; floatsum=0;for(p=head->next;p;p=p->next){t=1;for(i=p->expn;i!=0;){if(i<0){t/=x;i++;} else{t*=x;i--;} } sum+=p->coef*t; }return sum; }Polyn MultiplyPolyn(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial)); 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); } } return hf; }void main(){ int m,n,a,x,f,k=1; Polyn pa=0,pb=0,pc; while(k!=0){ 课课入的课数printf("a :"); scanf("%d",&m); pa=CreatePolyn(pa,m);课课入的课数printf("b :"); scanf("%d",&n); pb=CreatePolyn(pb,n);课出多课式课出多课式printf(" * 1:a 2:b \n");代入的课课算代入的课课算printf(" * 3:xa 4:xb\n");课出课出printf(" * 5:a+b 6:a-b\n");课出退出printf(" * 7:a*b 0:\n");课课课操作,while(a) { printf("\n "); scanf(" %d",&f); switch(f) { 多课式case 1: { printf("\na="); PrintPolyn(pa); break; }多课式case 2: { printf("\nb="); PrintPolyn(pb); break; }课入的课,case 3: { printf("xx="); scanf("%d",&x);课 printf("\n x=%da=%.3f\n",x,ValuePolyn(pa,x)); break; }课入的课,case 4: {printf("xx="); scanf("%d",&x);课 printf("\n x=%d b=%.3f\n",x,ValuePolyn(pb,x)); break; } case5:{ pc=AddPolyn(pa,pb); printf("\n a+b="); PrintPolyn(pc); break; } case 6:{ pc=SubtractPolyn(pa,pb);printf("\n a-b="); PrintPolyn(pc); break; }case 7:{ pc=MultiplyPolyn(pa,pb);printf("\na*b=");PrintPolyn(pc); break; }case 0:{ DestroyPolyn(pa); DestroyPolyn(pb); a=0; break; }您的课课课课～课重新课default: printf("\n !\n"); } } } }2 哈夫曼课/课课器2.1 述概本课程课课用于建立哈夫曼课～课其课行课课、课课以及打印。

一个一元稀疏多项式简单计算器课程设计报告课程课课课告学院,课程名,称课课班课,学生姓名, ,学号目课1 一元稀疏多课式课算器1.1 述概课了课课任意多课式的加法～法～因此课课课课表的课～有一系～指～下减构体它个数数一指课个个元素3使用课言,课言C课课课境,VC++ 6.01.2 课课容内、课课描述1课课一一元稀疏多课式课课课算器。

个基本要求,一元稀疏多课式课课课算器的基本功能是,;,课入建立多课式～并1;,课出多课式～课出形式课整序列,数～其中是多课式2n,c1,e1,c2,e2,…cn,en,n的课～数分课是第课的系和指～序按指降序排序～数数数数c1,e1,i;,多课式和相加～建立多课式3aba+b;;,多课式和相～建立多课式减4aba-b;;,课算多课式在课的课～5x;,课算器的界面;课做,。

仿真6、需求分析2;,课入的形式和课入课的范课,1课入是课课课入的～课入的容课多课式的系和指～课任意的整～指课大于从内数数数数数等于的整数0;,课出的形式2从屏并减幕课出～课示用课课入的多课式～课示多课式加以后的多课式的课。

;,程序所能到的功能达3,课入建立多课式～并a,课出多课式～课出形式课整序列,数其中是多课式的课数～bn,c1,e1,c2,e2,……,cn,en,n和分课是第课的系和指～序列按指降序排列～数数数cieii,多课式和相加～建立多课式～caba+b,多课式和相～建立多课式减～daba-b,多课式的课出形式课课表式～数学达e,系课课数的非零课的课出形式中略去系数～而的课出形式课。

f11-1x-x1.3 要课课概、存课课构1typedef struct Polynomial { float coef; int expn; struct Polynomial *next;}*Polyn,Polynomial;课课用以存放第构体课的系和指和下一指课～以课课课基课。

数数个i、函数2Polyn CreatePolyn(Polyn head,int m)课函用于建立一课指课课数个～课课数的一元多课式headm课函用于课毁多课式数void DestroyPolyn(Polyn p)课函用于课出多课式数void PrintPolyn(Polyn P) aPolyn AddPolyn(Polyn pa,Polyn pb)课函用于求解建立多课式数并～返回其课指课a+bPolyn SubtractPolyn(Polyn pa,Polyn pb)课函用于求解建立多课式数并～返回其课指课a-bfloat ValuePolyn(Polyn head,int x)课函用于课入数课～课算返回多课式的课并x课函用于比课数和的指数int compare(Polyn a,Polyn b) ab、流程课3一元稀疏多课式课算器课入建立多课式并课出多课式课算多课式在x课的课课算a+b课算a-b课束1.4 课课分析1、课课分析2、行课果运1.5 源程序代课#include<stdio.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); else { Polynq1,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){q1->next=q2->next;free(q2);}}else{p->next=q2;q1->next=p; } } } Polyn CreatePolyn(Polyn head,int m) { int i; 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); } return head; } void DestroyPolyn(Polyn p) {Polyn 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) { putchar('0'); printf("\n"); return; } while(q) { if(q->coef>0&&flag!=1) putchar('+'); if(q->coef!=1&&q->coef!=-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; else return1; }Polyn AddPolyn(Polyn pa,Polyn pb) {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); }return headc; }Polyn SubtractPolyn(Polyn pa,Polyn pb) {Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p){ p->coef*=-1; p=p->next; } pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next) p->coef*=-1; return pd;}float ValuePolyn(Polyn head,int x) {Polyn p; int i,t; floatsum=0;for(p=head->next;p;p=p->next){t=1;for(i=p->expn;i!=0;){if(i<0){t/=x;i++;} else{t*=x;i--;} } sum+=p->coef*t; }return sum; }Polyn MultiplyPolyn(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial)); 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); } } return hf; }void main(){ int m,n,a,x,f,k=1; Polyn pa=0,pb=0,pc; while(k!=0){ 课课入的课数printf("a :"); scanf("%d",&m); pa=CreatePolyn(pa,m);课课入的课数printf("b :"); scanf("%d",&n); pb=CreatePolyn(pb,n);课出多课式课出多课式printf(" * 1:a 2:b \n");代入的课课算代入的课课算printf(" * 3:xa 4:xb\n");课出课出printf(" * 5:a+b 6:a-b\n");课出退出printf(" * 7:a*b 0:\n");课课课操作,while(a) { printf("\n "); scanf(" %d",&f); switch(f) { 多课式case 1: { printf("\na="); PrintPolyn(pa); break; }多课式case 2: { printf("\nb="); PrintPolyn(pb); break; }课入的课,case 3: { printf("xx="); scanf("%d",&x);课 printf("\n x=%da=%.3f\n",x,ValuePolyn(pa,x)); break; }课入的课,case 4: {printf("xx="); scanf("%d",&x);课 printf("\n x=%d b=%.3f\n",x,ValuePolyn(pb,x)); break; } case5:{ pc=AddPolyn(pa,pb); printf("\n a+b="); PrintPolyn(pc); break; } case 6:{ pc=SubtractPolyn(pa,pb);printf("\n a-b="); PrintPolyn(pc); break; }case 7:{ pc=MultiplyPolyn(pa,pb);printf("\na*b=");PrintPolyn(pc); break; }case 0:{ DestroyPolyn(pa); DestroyPolyn(pb); a=0; break; }您的课课课课～课重新课default: printf("\n !\n"); } } } }2 哈夫曼课/课课器2.1 述概本课程课课用于建立哈夫曼课～课其课行课课、课课以及打印。

云南大学软件学院实验报告指导教师：朱艳萍 2009秋季学期学号：20081120064 姓名：李雪寒【实验题目】实验2. 一元稀疏多项式简单计算器【问题描述】设计并实现一个一元稀疏多项式的简单计算器。

【基本要求】一元稀疏多项式简单计算器的基本功能是：1.输入并建立多项式；2.输出多项式，序列按指数降序排列；3.多项式a和b相加，并建立多项式a+b；4.多项式a和b相减，并建立多项式a-b；【实现提示】1.用带头节点的单链表作为多项式的存储结构；一、【概要设计】链式存储结构，由于不要求逻辑上相邻的元素在物理上也相邻，因此，能够迅速进行插入或删除操作，而且不像顺序存储结构那样需要移动大量元素，但也没有顺序表那样随机存取的优点。

主程序中通过调用void create(polynmial &L) 创建存储在单链表中的多项式，调用void display(polynmial L); 输出显示多项式，调用void sort(polynmial &L)和void reverse(polynmial &L)对多项式进行排序，使其按降序排列，调用void add(polynmial La,polynmial Lb, polynmial &Lc) 和void subtract(polynmial La, polynmial Lb, polynmial &Ld) 对两个多项式进行加减操作。

二、【详细设计】在此次试验中，主要通过以下7个子函数对存储在单链表中的多项式进行操作：void create(polynmial &L) //输入并建立多项式L{int i, n;static struct node *p;printf("输入多项式项数：\n");scanf("%d", &n);//输入多项式的项数L = (struct node *)malloc (sizeof(struct node));L->next = NULL;for(i = 0; i < n; i++){p = (struct node *)malloc(sizeof(struct node));printf("输入一个项的系数和指数，用空格隔开：\n");scanf("%f %d", &p->c, &p->e);p->next = L->next;L->next = p;}//利用for循环输入多项式中每一项的系数和指数}void display(polynmial L)//显示，输出多项式L{struct node *p, *q;//建立两个结点int flag = 0;int k = 0;q = L->next;while(q){if(q->c!= 0)k++;//计算多项式的项数q = q->next;}printf("共%d项\n", k);//输出多项式的项数p = L->next;if(p->c != 0){printf("+%.1fx^%d", p->c, p->e);flag++;}//判断该项是否为零，不为零则输出for(p = p->next; p; p = p->next){if(p->c != 0){printf("+%.1fx^%d", p->c, p->e);flag++;}}//输出多项式if(flag == 0)printf("%d\n", flag);elseprintf("\n");}void sort(polynmial &L)//多项式L按指数排序{polynmial p, q, r, s;p = L->next;L->next = NULL;while(p != NULL){r = L;q = L->next;while((q != NULL) && (q->e <= p->e)){r = q;q = q->next;}s = p->next;r->next = p;p->next = q;p = s;}}void reverse(polynmial &L)//逆置{polynmial H;static struct node *p, *q, *s;H = (struct node*)malloc(sizeof(struct node));H->next = NULL;p = (struct node*)malloc(sizeof(struct node));s = L->next;p->c = s->c;p->e = s->e;p->next = s->next;while(s){p->c = s->c;p->e = s->e;p->next = s->next;q = H->next;H->next = p;p->next = q;p = (struct node*)malloc(sizeof(struct node));s = s->next;}p = H->next;q = L->next;while(p){q->c = p->c;q->e = p->e;q = q->next;p = p->next;}}void select() //用户选择加减操作{printf("请选择加减操作\n");printf("1.两个一元多项式相加\n");printf("2.两个一元多项式相减\n");}void add(polynmial La, polynmial Lb, polynmial &Lc)//多项式La,Lb相加，并付给Lc {struct node *pa, *pb;static struct node *pc;Lc = (struct node*)malloc(sizeof(struct node));pa = La->next;pb = Lb->next;Lc->next = NULL;while(pa && pb){pc = (struct node*)malloc(sizeof(struct node));if(pa->e < pb->e){pc->next = Lc->next;Lc->next = pc;pc->c = pa->c;pc->e = pa->e;pa = pa->next;}elseif(pa->e == pb->e){pc->next = Lc->next;Lc->next = pc;pc->e = pa->e;pc->c = pa->c + pb->c;pa = pa->next;pb = pb->next;}else{pc->next = Lc->next;Lc->next = pc;pc->c= pb->c;pc->e = pb->e;pb = pb->next;}}while(pa){pc = (struct node*)malloc(sizeof(struct node));pc->next = Lc->next;Lc->next = pc;pc->c = pa->c;pc->e = pa->e;pa = pa->next;}while(pb){pc = (struct node*)malloc(sizeof(struct node));pc->next = Lc->next;Lc->next = pc;pc->c = pb->c;pc->e = pb->e;pb = pb->next;}}void subtract(polynmial La, polynmial Lb, polynmial &Ld)//多项式La减去Lb，结果赋给Ld{struct node *pa, *pb;static struct node *pd;Ld = (struct node*)malloc(sizeof(struct node));pa = La->next;pb = Lb->next;Ld->next = NULL;while(pa && pb){pd = (struct node*)malloc(sizeof(struct node));if(pa->e< pb->e){pd->next = Ld->next;Ld->next = pd;pd->c= pa->c;pd->e = pa->e;pa = pa->next;}elseif(pa->e == pb->e){pd->next = Ld->next;Ld->next = pd;pd->e= pa->e;pd->c = pa->c - pb->c;pa = pa->next;pb = pb->next;}else{pd->next = Ld->next;Ld->next = pd;pd->c = pb->c;pd->e = pb->e;pb = pb->next;}}while(pa){pd = (struct node*)malloc(sizeof(struct node));pd->next = Ld->next;Ld->next = pd;pd->c = pa->c;pd->e = pa->e;pa = pa->next;}while(pb){pd = (struct node*)malloc(sizeof(struct node));pd->next = Ld->next;Ld->next = pd;pd->c = -pb->c;pd->e = pb->e;pb = pb->next;}}三、【测试结果】四、【实验总结】此次实验较实验一来说要难得多，算法也复杂得多，原因主要有：1、C语言的应用很生疏，有待加强；2、对于单链表的插入和删除操作不熟练，需要借助课本和资料进行参考；3、程序比较复杂，算法思想也很难理清，需要多加锻炼。

一元稀疏多项式计算器实验报告级班年月日姓名学号_1 •实验题目设计一个一元稀疏多项式简单计算器。

2 •需求分析本程序用VC编写，实现一元浮点系数，整数指数稀疏多项式的创建、两个一元多项式相加、两个一元多项式相减、输出一元多项式。

①输入的形式和输入值的范围：A. 输入指定的数字，以此选择两个多项式的运算方式，运算方式有两个一元多项式相加、两个一元多项式相减。

B. 创建多项式时，需要输入此多项式，每一项的系数和指数。

②输出的形式：每次输入一个完整的多项式后、每次得出多项式运算结果时，会以指定的方式输出多项式。

③程序所能达到的功能：实现一元稀疏多项式的创建、两个一元多项式相加、两个一元多项式相减、输出一元多项式。

④测试数据：输入数据：A. 出现选择两个多项式的运算方式菜单时，输入 1 （即使两个多项式相加）；B. 首先输入多项式p的每一项系数和指数，当输入的指数为-5000时，表示该多项式输入完毕，输入的数据依次为：3, 3, 0, -5000 ;C•其次输入多项式q的每一项系数和指数，输入数据依次为：2, 2, 0, -5000。

输出结果：多项式q+p的结果为：多项式为：3 23x +2x3 •概要设计1）为了实现上述程序功能，需要定义多项式结点的抽象数据类型：class Term{数据对象：floatcoef;该数据对象为多项式一项中的系数。

intexp;该数据对象为多项式一项中的指数。

Term*link;该数据对象为指向下一个多项式结点的指针。

基本操作：A. Term（float c, int e）初始条件：无操作结果：初始化多项式结点对象，将c赋值给该结点的数据成员coef （表示系数），将e赋值给该结点的数据成员exp （表示指数），将该结点的数据成员link赋值为0。

B. Term（float c, int e,Term*next）初始条件：无操作结果：初始化多项式结点对象，将c赋值给该结点的数据成员coef （表示系数），将e赋值给该结点的数据成员exp (表示指数)，将next赋值给该结点的数据成员link (link表示指向下一个多项式结点的指针)。

目录一、课程题目 (3)二、设计目的 (3)三、需求分析 (3)四、总体设计 (3)五、详细设计 (2)六、实现部分 (3)七、程序测试 (3)八、设计总结 (12)一、课程题目一元稀疏多项式计算器二、设计目的掌握稀疏矩阵的相关运算。

掌握广义表的操作。

三、需求分析一元稀疏多项式简单计算器的基本功能是：输入并建立多项式；输出多项式,输出形式为整数序列：n,c1,e1,,c2,e2 ……cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列。

多项式a和b相加,建立多项式a+b多项式a和b相减,建立多项式a-b四、总体设计创建两个类，把一个作为另一个的友元类！两个类分别是listnode和polynomial！创建一个链表，包括指数，次数以及下一个结点信息，然后利用冒泡排序法进行排序，排完之后输出多项式！最后一个环节就是进行多项式的最原始运算，即加减运算！其中运用的内容包括链表知识，冒泡排序的知识！五、详细设计类listnode中包含friend class polynomial、double coef、int exp、listnode *next！类polynomial包含poly(); void printpoly();void bubblesort();polynomial operator+(polynomial &p1); polynomial operator-(polynomial &p1);在这个程序设计中，为了实现多项式的运算必须首先创建两个多项式，存储多项式的存储结构是链表，其结构如下：else if(p->exp<q->exp){double m;int n;m=p->coef;p->coef=q->coef;q->coef=m;n=p->exp;p->exp=q->exp;q->exp=n;s=q;q=q->next;｝再就是实现多项式的加减法运算，在加减法运算中为了实现处理，设p、q分别指向单链表的两个多项式，比较p、q结点的指数项，由此得到下列运算规则：①若p->exp<q->exp，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。

*****大学数据结构课程设计说明书题目：稀疏矩阵运算器学生姓名：学号：专业：班级：指导教师：2013 年 7 月 24日稀疏矩阵运算器摘要摘要：设计一稀疏矩阵运算器。

实现两个矩阵的相加、相减和相乘的功能。

用“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算，采用分级的设计方法，分别设计出加、减、乘运算器的子程序，相加运算时只要依次存储、扫描两矩阵的行、列数，若行、列数相等，再取行、列下标相等的元素，相加后存入结果矩阵。

相减运算与相加运算相同，同样取行、列下标相等的元素，相减后存入结果矩阵。

相乘运算要先判断两矩阵能否相乘。

若能相乘，则取行、列号相对应的元素进行相乘及相加，最后将对应元素存入结果矩阵中。

通过实验表明本程序能够进行稀疏矩阵的相加，相减，相乘运算。

具备矩阵的加、减、乘功能。

关键词：相加运算器；相减运算器；相乘运算器数据结构课程设计任务书针对本课程设计，完成以下课程设计任务：1、熟悉系统实现工具和上级环境。

2、根据课程设计任务，查阅相关资料。

3、针对所选课题完成以下工作：（1）、需求分析（2）、概要设计（3）、详细设计（4）、编写源程序（5）、静态走查程序和上机调试程序4、书写上述文档和撰写课程设计报告。

目录稀疏矩阵运算器 (I)摘要 (II)课程设计任务书 (III)课程设计正文 (Ⅳ)第一章问题描述 (5)第二章需求分析 (6)第三章概要设计 (9)第四章详细设计 (19)4.1 函数说明 (10)4.2 算法分析 (19)第五章调试分析 (21)第六章测试结果 (23)第七章课程设计总结 (24)参考文献 (24)附录（程序清单） (33)第一章问题描述一、问题描述：稀疏矩阵是指那些多数元素为零的矩阵，利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率，实现一个能进行稀疏矩阵基本运算的运算器。

二、基本要求：以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。