中南民族大学数据结构实验报告

院 系： 计算机科学学院 专 业： 计算机科学与技术 年 级： 2011级 课程名称： 数据结构 学 号： 11061054 姓 名： 甘土有 指导教师： 宋中山

2013年 6月10日

设计题目一：一元稀疏多项式计算器

【问题描述】

一元稀疏多项式计算器 【基本要求】

一元稀疏多项式简单计算器的功能是： （1） 输入并建立多项式；

（2） 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,???cn,en,

其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；

（3）多项式a和b相加，建立多项式a+b； （4） 多项式a和b相减，建立多项式a-b。 一、需求分析

1. 定义线性表的动态分配顺序存储结构； 2. 建立多项式存储结构，定义指针*next

3. 利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式

4. 演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1x^e1+c2x^e2+?+cnx^en 序列按指数降序排列。

5.设计思路分析

要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为: 序数coef指数expn指针域next

运用尾插法建立两条单链表，以单链表LinkList p和LinkList h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题,将单链表LinkList p中的结点插入到单链表LinkList h中即可。

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

p->expn=q->expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数; 若p->expn>q->expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。

6.测试数据

（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）互换上述测试数据中的前后两个多项式

二、概要设计

1、元素类型、结点类型和指针类型：

typedef struct Polynode {

float coef; //系数 int exp; //指数

struct Polynode *next;

}*Poly,Polynode; //Poly为结点指针类型

2、建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 用Insert函数插入结点:

LinkList CreateLinkList(LinkList head,int m){ int i; LinkList p;

p=head=(LinkList)malloc(sizeof(struct LNode)); head->next=NULL; for(i=0;i

p=(LinkList)malloc(sizeof(struct LNode)); printf(\请输入第%d项的系数与指数:\ scanf(\

Insert(p,head); }

return head; }

3、主函数和其他函数：

int main() {

int m,n,flag=0; float x;

Poly pa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULL ·········

}

调 主函数-?建立链表->多项式相加减—>输出多项式

三、详细设计：

#include #include #include typedef struct Polynode {

float coef; //系数 int exp; //指数

struct Polynode *next;

}*Poly,Polynode; //Poly为结点指针类型

void Insert(Poly p,Poly head) {

if(p->coef==0) //系数为0时释放结点 free(p); else {

Poly q1,q2; q1=head;

q2=head->next;

while(q2&&p->expexp) { //后移查找插入位置 q1=q2;

q2=q2->next; }

if(q2&&p->exp==q2->exp) { //将指数相同的相合并 q2->coef+=p->coef; free(p);

if(!q2->coef) //系数为0时释放结点 {

q1->next=q2->next; free(q2); } } else {

p->next=q2; q1->next=p; } }

}//Insert

Poly CreateList(Poly head,int m)

{ //建立一个头指针为head、项数为m的一元多项式 int i; Poly p;

Polynode *q;

p=head=(Poly)malloc(sizeof(struct Polynode)); head->next=NULL; for(i=0;i

p=(Poly)malloc(sizeof(struct Polynode));//建立新结点以接收数据 cout<<\请输入第\项的系数与指数: \cin>>p->coef>>p->exp;

Insert(p,head); //调用Insert函数插入结点 }

q=head->next; while(q!=NULL) {

cout<<\系数：\指数 : \q=q->next; }

return head; }//CreatePoly

void DestroyList(Poly p) { //销毁多项式p Poly q1,q2;

if(p->next!=NULL) {

q1=p->next; q2=q1->next; while(q1->next) {

free(q1);

q1=q2;//指针后移 q2=q2->next; } } }

int OutputList(Poly P) { //输出多项式

本文来源：https://www.bwwdw.com/article/f2kh.html