一元多项式的计算数据结构课程设计.doc

一元多项式的计算加，减摘要题目一元多项式计算任务能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；目录1引言2需求分析3概要设计4详细设计5测试结果6调试分析7设计体会8结束语一引言通过C语言使用链式存储结构实现一元多项式加法、减法和乘法的运算。按指数降序排列。二需求分析建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果三概要设计存储结构一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。1．单连表的抽象数据类型定义ADTLIST{数据对象D{AI|AI∈ELEMSET,I1,2,,N,N≥0}数据关系R1{|AI1,AI∈D,I2,,N}基本操作INITLIST(＆L)//操作结果构造一个空的线性表CREATPOLYNVOIDINITLISTLINKLISTINTEXPNSTRUCTPOLYNOMIALNEXT}POLYN,POLYNOMIAL//POLYN为结点指针类型VOIDINSERTPOLYNP,POLYNH{IFPCOEF0FREEP//系数为0的话释放结点ELSE{POLYNQ1,Q2Q1HQ2HNEXTWHILEQ2Q2Q2NEXT}IFQ2FREEPIFQ2COEF{//系数为0的话释放结点Q1NEXTQ2NEXTFREEQ2}}ELSE{//指数为新时将结点插入PNEXTQ2Q1NEXTP}}}//INSERTPOLYNCREATEPOLYNPOLYNHEAD,INTM{//建立一个头指针为HEAD、项数为M的一元多项式INTIPOLYNPPHEADPOLYNMALLOCSIZEOFSTRUCTPOLYNOMIALHEADNEXTNULLFORI0ICOEF,INSERTP,HEAD//调用INSERT函数插入结点}RETURNHEAD}//CREATEPOLYNVOIDDESTROYPOLYNPOLYNP{//销毁多项式PPOLYNQ1,Q2Q1PNEXTQ2Q1NEXTWHILEQ1NEXT{FREEQ1Q1Q2//指针后移Q2Q2NEXT}}VOIDPRINTPOLYNPOLYNP{POLYNQPNEXTINTFLAG1//项数计数器IFQ{//若多项式为空，输出0PUTCHAR 0 PRINTF“\N“RETURN}WHILEQ{IFQCOEF0//系数大于0且不是第一项IFQCOEF1IFQEXPN1PUTCHAR X ELSEIFQEXPNPRINTF“XD“,QEXPN}ELSE{IFQCOEF1{IFQEXPNPUTCHAR 1 ELSEIFQEXPN1PUTCHAR X ELSEPRINTF“XD“,QEXPN}IFQCOEF1{IFQEXPNPRINTF“1“ELSEIFQEXPN1PRINTF“X“ELSEPRINTF“XD“,QEXPN}}QQNEXTFLAG}//WHILEPRINTF“\N“}//PRINTPOLYNINTCOMPAREPOLYNA,POLYNB{IFAELSEIFA||AEXPNEXPNRETURN1ELSERETURN0}ELSEIFA//A多项式已空，但B多项式非空ELSERETURN1//B多项式已空，但A多项式非空}//COMPAREPOLYNADDPOLYNPOLYNPA,POLYNPB{//求解并建立多项式AB，返回其头指针POLYNQAPANEXTPOLYNQBPBNEXTPOLYNHEADC,HC,QCHCPOLYNMALLOCSIZEOFSTRUCTPOLYNOMIAL//建立头结点HCNEXTNULLHEADCHCWHILEQA||QB{QCPOLYNMALLOCSIZEOFSTRUCTPOLYNOMIALSWITCHCOMPAREQA,QB{CASE1{QCCOEFQACOEFQCEXPNQAEXPNQAQANEXTBREAK}CASE0{QCCOEFQACOEFQBCOEFQCEXPNQAEXPNQAQANEXTQBQBNEXTBREAK}CASE1{QCCOEFQBCOEFQCEXPNQBEXPNQBQBNEXTBREAK}}//SWITCHIFQCCOEF0{QCNEXTHCNEXTHCNEXTQCHCQC}ELSEFREEQC//当相加系数为0时，释放该结点}//WHILERETURNHEADC}//ADDPOLYNPOLYNSUBTRACTPOLYNPOLYNPA,POLYNPB{//求解并建立多项式AB，返回其头指针POLYNHPBPOLYNPPBNEXTPOLYNPDWHILEP{//将PB的系数取反PCOEF1PPNEXT}PDADDPOLYNPA,HFORPHNEXTPPPNEXT//恢复PB的系数PCOEF1RETURNPD}//SUBTRACTPOLYNINTMAIN{INTM,N,FLAG0FLOATXPOLYNPA0,PB0,PC,PD,PE,PF//定义各式的头指针，PA与PB在使用前付初值NULLPRINTF“请输入A的项数“SCANF“D“,PACREATEPOLYNPA,M//建立多项式APRINTF“请输入B的项数“SCANF“D“,PBCREATEPOLYNPB,N//建立多项式A//输出菜单PRINTF“\N“PRINTF“操作提示\N\T1输出多项式A和B\N\T2建立多项式AB\N\T3建立多项式AB\N“PRINTF“\T4退出\N\N“FORFLAG0{PRINTF“执行操作“SCANF“D“,IFFLAG1{PRINTF“多项式A“PRINTPOLYNPAPRINTF“多项式B“PRINTPOLYNPBCONTINUE}IFFLAG2{PCADDPOLYNPA,PBPRINTF“多项式AB“PRINTPOLYNPCDESTROYPOLYNPCCONTINUE}IFFLAG3{PDSUBTRACTPOLYNPA,PBPRINTF“多项式AB“PRINTPOLYNPDDESTROYPOLYNPDCONTINUE}IFFLAG4BREAKIFFLAG4PRINTF“ERROR\N“CONTINUE}//FORDESTROYPOLYNPADESTROYPOLYNPBRETURN0}