《数据结构》课程设计报告
课程设计题目：姓名： 院系： 专业： 年级： 学号： 指导教师：
一元稀疏多项式计算器
张程浩 通信工程 信息安全 2011 11225104 任雪萍
2012年10月30日 (任雪萍编写)
11225104 张程浩 一元稀疏多项式计算器 数据结构
目录
一、课程设计目的 ....................................................... 3 二、任务分析 ............................................................... 3 三、分析设计 ............................................................... 3 四、调试分析 ............................................................... 5 五、测试结果 ............................................................... 6 六、小结 ........................................................................ 7 七、用户手册 ............................................................... 7 八、附录 ........................................................................ 8 九、参考文献 ............................................................... 9
2
11225104 张程浩 一元稀疏多项式计算器 数据结构
一、课程设计目的
(1) 熟练使用C语言编写程序，强化模块设计理念； (2) 解决一元稀疏多项式的基本运算。
(3) 熟练掌握线性表的基本操作，以及用线性链表表示线性表的存储结构和操作的实现。 (4) 提高分析和解决问题的能力。
(5) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
二、任务分析
一元稀疏多项式计算器实现的功能 （1）输入并建立多项式；
（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，„„，cn，en，其中n是多项式的项数，
ci和ei分别是第i项的系数和指数，序列按指数降序排列； （3）多项式a和b相加，建立多项式a＋b； （4）多项式a和b相减，建立多项式a—b； （5）多项式a和b相乘，建立多项式a×b； （6）计算多项式在x处的值； （7）求多项式P的导函数P'；
测试数据：
（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
三、分析设计
需要处理的数据的逻辑结构：线性结构 合适的存储结构：链式储存 设计好的数据类型：
typedef struct{ //项的表示，多项式的项作为Linklist的数据元素 float coef; //系数 int expn; //指数
} term, ElemType;//两个类名：term用于本ADT，ElemType为Linklist的数据对象名
typedef struct LNode {//结点类型 ElemType data; struct LNode *next; } *Link, *Position;
typedef struct{//链表类型 Link head,tail; //分别指向线性链表中的头结点和最后一个结点 int len; //指示线性链表中数据个数 } LinkList;
typedef LinkList polynomial;//基于带头结点的线性链表定义的多项式数据类型
与功能对应的模块划分定义：
// 分配由p指向值为e的结点,并返回OK,若分配失败,则返回ERROR。 Status MakeNode(Link &p, ElemType e);//释放p所指结点 void FreeNode(Link &p);
3
11225104 张程浩 一元稀疏多项式计算器 数据结构
//构造一个空的线性链表L Status InitList(LinkList &L);
// 返回线性表L中头结点的位置。 Position GetHead(LinkList &L);
//已知p指向线性链表L中的一个结点，返回p所指结点的直接后驱的位置 //若无后继，返回NULL
Position Nextpos(LinkList &L,Link p);
//已知p指向线性表L中的一个结点,返回p所指结点中数据元素的值。 ElemType GetCurElem(Link p);
//已知p指向线性链表L中的一个结点,用e更新p所指结点中数据元素的值。 Status SetCurElem(Link &p,float e);
//已知h指向线性链表的头结点,删除线性链表第一个指结点并以q返回 Status DelFirst(Link h,Link &q);
//已知h指向线性链表的某个结点,将q所指的结点插入在h之后。 Status InsFirst(Link h,Link q);
//若线性链表L为空,则返回TRUE,否则返回FALSE。 Status ListEmpty(LinkList L);
//将指针s所指的一连串结点连接在线性表L的最后一个结点之后,并改变链表L的尾指针指向新的尾结点。
Status Append(polynomial &L,Link s);
//判断已知链表中，是否存在相同的元素e，若存在返回TURE，且q指示L中第一个与e相同的结点元素；
//否则返回FALSE,并q指示L中第一个稍大于e的元素的直接前驱的位置 Status LocateElem(LinkList L,ElemType e,Position &q);
void ClearList(LinkList &L);
//依a的指数值<（或=）(或>）b的指数数值，分别返回-1，0，+1 int cmp(term a, term b) ;
//输入m项的系数和指数，建立表示一元多项式的有序链表P void CreatPolyn(polynomial &P,int m);
//打印输出一元多项式P
void PrintPolyn(polynomial P);
//返回一元多项式P中系数 void PolynLength(polynomial P);
//完成多项式的相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb void AddPolyn(polynomial &Pa ,polynomial &Pb);
//完成多项式的相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb void SubtractPolyn(polynomial &Pa ,polynomial &Pb);
//完成多项式的相减运算，即：Pa=Pa×Pb，并销毁一元多项式Pb void MultiplyPolyn(polynomial &Pa ,polynomial &Pb);
4
11225104 张程浩 一元稀疏多项式计算器 数据结构
//计算多项式在x处的值
double Evaluation(double x, polynomial P);
//计算多项式P的导函数P'
void Derivative( polynomial &P );
模块调用关系：
四、调试分析
1、调试中的问题
（1）
调试问题：在x的指数为1时，输出仍显示为x^1 解决方案：
if(p->data.coef!=0) { a=p->data.coef; b=p->data.expn; if(b!=0) { if(1.0 !=a) { if (1==b)
5
11225104 张程浩 一元稀疏多项式计算器 数据结构
}
printf(\" %.2fx \ else printf(\" %.2fx^%d \ } else { if (1==b) printf(\" x \"); else printf(\" x^%d \ } } else printf(\" %.2f \ if(p->next!=NULL) if(p->next->data.coef>=0) printf(\"+\");
（2）
调试问题：在多项式中出现相同系数重复输入时，无法自动累加系数，使得程序错误 解决方案： if(!LocateElem(P,e,q)) //当前链表中不存在该指数项 { if(MakeNode(s,e)) //将数据信息存为一个新结点s InsFirst(q,s); } else q->data.coef += e.coef;
2、时间复杂度和空间复杂度
本实验所涉及算法基本采用顺序遍历方式，因而时间复杂度为o(m+n)，空间复杂度为o(m+n)。
五、测试结果
6
11225104 张程浩 一元稀疏多项式计算器 数据结构
结论：合法数据输入输出均能正常输出，但是非法字符座位指数和稀疏时，程序出现错误。
六、小结
这个程序涉及的函数特别多。在线性链表的基础上，改进设计成一元多项式的储存结构。 对一元稀疏多项式，若采用顺序存储结构，需n+1个元素单元存放系数。当n很大且为零的系数较多时，既浪费存储空间，又浪费运算时间。如：s(x)=1+3x采用链式存储结构是必然的选择。
对于乘法算法，可以改进提高算法的效率。
10000
20000
+2x采用顺序存储分配需20001个元素
空间，但只有3个元素有意义。若参与同数量级的加法运算，要运行2000次以上。因此，对一元多项式
七、用户手册
本程序在DOS环境下运行，根据提示输入要选择的功能序号即可运行。
7
11225104 张程浩 一元稀疏多项式计算器 数据结构
八、附录
程序清单如下：
void AddPolyn(polynomial &Pa ,polynomial &Pb){ //完成多项式的相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb Link ha=GetHead(Pa); Link hb=GetHead(Pb); //ha,hb分别指向Pa,Pb的头结点 Link qa=Nextpos(Pa,ha); Link qb=Nextpos(Pb,hb);//qa,qb分别指向Pa,Pb的当前(首元)结点 ElemType a,b; float sum; while (qa && qb)//qa qb均非空 { a=GetCurElem(qa); b=GetCurElem(qb); //a,b为两表中当前比较元素 switch (cmp(a,b)) { case 1://多项式PA中的当前结点的指数值小 ha=qa; qa=Nextpos(Pa,ha);//当前结点后移 break; case 0: sum= a.coef+b.coef; if (sum!=0.0)//修改多项式PA中当前结点的系数 { SetCurElem(qa,sum); ha=qa;//当前结点后移 } else//删除多项式PA中当前结点 { DelFirst(ha,qa); FreeNode(qa); } DelFirst(hb,qb); //当前结点后移，并删除当前结点 FreeNode(qb); qb=Nextpos(Pb,hb); qa=Nextpos(Pa,ha);//当前结点后移 break; case -1://多项式PB中的当前结点指数值小。 DelFirst(hb,qb); InsFirst(ha,qb); //将较小的指数插入Pa当前元素之前，即“首结点”之后 qb=Nextpos(Pb,hb); //Pb当前结点后移 break; }//switch
}//while
if (!ListEmpty(Pb)) Append(Pa,qb); FreeNode(hb); }
void MultiplyPolyn(polynomial &Pa ,polynomial &Pb){
//完成多项式的相减运算，即：Pa=Pa×Pb，并销毁一元多项式Pb Link ha=GetHead(Pa); Link hb=GetHead(Pb); //ha,hb分别指向Pa,Pb的头结点 polynomial R,N;//R为乘积结果项结点,N为运算过程中生成的只含一个项的结点中间变量 InitList(R); Link hr=GetHead(R),hn; Link qa=Nextpos(Pa,ha),qb,qn; //qa,qb分别指向Pa,Pb的当前相乘的两结点 ElemType a,b,n; //a被乘项,b乘项，n新的结果项 while (qa) { a=GetCurElem(qa); qb=Nextpos(Pb,hb); while (qb) { InitList(N); hn=GetHead(N); b=GetCurElem(qb); n.coef= a.coef * b.coef; n.expn= a.expn + b.expn; MakeNode(qn,n); //将数据元素转为一个结点 InsFirst(hn,qn); //将新的乘积结果元素存到结点N中。 AddPolyn(R,N); //累加项 qb=qb->next; //移动Pb多项式到下一个项 } qa=qa->next; //移动Pa多项式到下一个项 } ClearList(Pa); Pa.head=R.head; Pa.tail=R.tail; Pa.len=R.len; hb=GetHead(Pb);
8
11225104 张程浩 一元稀疏多项式计算器 数据结构
FreeNode(hb); }
void main() { polynomial Pa,Pb; int m,k; double x,y; printf(\"*******欢迎使用一元稀疏多项式计算器*******\\n************************By 张程浩*********\\n** 1 **计算多项式在x处的值****************\\n** 2 **求多项式P的导函数P'****************\\n** 3 **多项式Pa和Pb相加，建立多项式Pa＋Pb\\n** 4 **多项式Pa和Pb相减，建立多项式Pa—Pb\\n** 5 **多项式Pa和Pb相乘，建立多项式Pa×Pb\\n请选择功能的序号：\"); scanf(\"%d\ switch (k) { case 1: printf(\"x=\"); scanf(\"%lf\ printf(\"多项式项数m=\"); scanf(\"%d\ CreatPolyn(Pa,m); printf(\"y=\"); PrintPolyn(Pa); y=Evaluation(x,Pa); printf(\"y(%f)=%f\\n\ break; case 2: printf(\"多项式项数m=\"); scanf(\"%d\ CreatPolyn(Pa,m); printf(\"* y=\"); PrintPolyn(Pa); Derivative(Pa); printf(\"* y'=\"); PrintPolyn(Pa); break; case 3: printf(\"多项式Pa 项数m=\");
}
scanf(\"%d\ CreatPolyn(Pa,m); printf(\"多项式Pb 项数m=\"); scanf(\"%d\ CreatPolyn(Pb,m); printf(\"Pa=\"); PrintPolyn(Pa); printf(\"Pb=\"); PrintPolyn(Pb); AddPolyn(Pa,Pb); printf(\"* Pa＋Pb =\"); PrintPolyn(Pa); break; case 4: printf(\"多项式Pa 项数m=\"); scanf(\"%d\ CreatPolyn(Pa,m); printf(\"多项式Pb 项数m=\"); scanf(\"%d\ CreatPolyn(Pb,m); printf(\"Pa=\"); PrintPolyn(Pa); printf(\"Pb=\"); PrintPolyn(Pb); SubtractPolyn(Pa,Pb); printf(\"* Pa—Pb =\"); PrintPolyn(Pa); break; case 5: printf(\"多项式Pa 项数m=\"); scanf(\"%d\ CreatPolyn(Pa,m); printf(\"多项式Pb 项数m=\"); scanf(\"%d\ CreatPolyn(Pb,m); printf(\"Pa=\"); PrintPolyn(Pa); printf(\"Pb=\"); PrintPolyn(Pb); MultiplyPolyn(Pa,Pb); printf(\"* Pa×Pb =\"); PrintPolyn(Pa); }
九、参考文献
陆 蓓. C语言程序设计（第二版）[M]. 北京：科学出版社，2009
严蔚敏. 数据结构：C语言版[M]. 北京：清华大学出版社，2007.
9
