用C语言解决一元多项式运算问题.doc

用C语言解决一元多项式运算问题摘 要 本数据结构课程设计运用一元多项式运算的基本法则，对一元多项式的加法、减法运算进行设计，并有人机交换界面。本课程设计中，系统开发平台为Windows XP；程序设计语言主要采用C语言，其中也掺入了C+部分语句，兼而两者的优势并存；开发环境为Microsoft Visual C+ 6.0,友好的界面、功能更加强大，相比较于C语言的专用开发环境Turbo C，其操作简单却已能完全在其环境中借用C语言开发设计出源程序；程序运行平台为Windows 98/2000/XP，程序兼容特性比较强，具有很好的移植特性。在程序设计中，整个程序层次结构突出，直观性与易理解性优势明显。程序通过调试运行后，完成了一元多项式运算的各种操作的设想，符合题目要求，初步实现了设计目标，达到了预期的效果。关键词：数据结构课程设计； C程序语言；多项式1 引言计算机的快速发展，特别是计算机网络的发展，越来越深刻地改变了人们生活的方方面面。但同时，也要求人们能高效、有效地完成某些运算任务。而“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。本课程设计主要是对所学的数据结构知识进行整合和运用，解决在一元多项式的运算，包括加法、减法及乘法运算，通过该程序，将大大减少运算时间，提高工作效率。2 课程设计目的在我们对一个具体的问题进行分析时，往往要抽象出一个模型，设计一个算法来实现所需要达到的功能。在此程序中，我们主要是综合运用所学过的知识，回顾VC+编程的同时，熟悉并掌握数据结构中的算法分析与设计。同时，要掌握类C语言的算法转换成C程序并上机调试的基础；这次课程设计，要求设计一个C语言程序，该程序能够按照指数的降幂排列，并完成多个一元多项式的相加、相减、相乘，并将结果输出。通过这次课程设计，进一步巩固数据结构等课程所学的知识，特别加强指针、结构体、文件数据类型的应用，熟悉面向过程的结构化、了解面向对象设计方法，通过本次课程设计的实践，加强动手能力的操作，掌握程序设计的流程，以及用C程序语言编写程序，从而解决实际问题的能力，了解掌握Visual C+开发环境，在老师的指导下，独立完成课程设计的全部内容，培养严谨的科学态度和认真学习的工作作风，培养创造性思维方式。3 系统分析3.1 问题描述用C语言编写一段程序，该程序的功能相当于一个一元多项式的计算器，能够实现按照指数降幂建立并输出多项式，并且能够完成多个多项式的相加、相减及相乘运算及结果输出的功能。此程序的数据结构是选择用带表头结点的单链表存储多项式。虽然一元多项式可以用顺序和链表存储结果表示，但顺序结构的最大长度很难确定。比如当多项式的系数较大时，此时就会浪费存储空间，所以应该选用链表结构来存储一元多项式。但链表的结构体可以用来存储多项式的系数、指数、下一个指针3个元素，这样便于实现任意多项式的加法、减法、乘法运算。3.2 设计思路 通过对问题的描述，可设计出如图2-1所示的一元多项式总流程图：开始申请结点空间+num输入多项式的项数指针数组tempi中（i=1num）输入多项式各项的系数 x, 指数 y输出已输入的多项式 进行多项式的加法、减法及乘法运算结束否是是否输入正确图3-1 一元多项式运算总流程图（1）一元多项式的建立输入多项式采用头插法的方式，输入多项式中的一个项的系数和指数，就产生一个新的结点，建立起它的右指针，并用头结点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续；输入为0时，就结束一个多项式的输入。（2）显示一元多项式如果系数是大于0的话就输出的形式；如果系数是小于0的话就输出的形式；如果指数为0的话就直接输出；如果指数是1的话就直接输出；如果指数是-1的话，就直接输出。（3）一元多项式加法运算 从两个多项式的头部开始判断，当两个多项式的某一项度不为空时，假设P、Q分别指向多项式A和多项式B中当前进行比较的结点，然后比较两个结点中的指数项，有三种情况：1、当P所指结点的指数小于Q的话，就应该复制P的结点到多项式链中。2、P所指结点的指数如果大于Q的指数的话，就应该复制Q的结点到多项式链中。3、当P所指结点的指数等于Q所指结点的指数时，则将两个结点中的系数相加，若和不为0，则修改P所指结点的系数值，同时释放Q所指结点；若和为0，从多项式A的链表中删除相应结点，并释放P、Q所指结点。加法流程图如图2-2所示：开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项图3-2 一元多项式加法运算流程图（4）一元多项式的减法 从两个多项式的头部开始判断，当两个多项式的某一项度不为空时，假设P、Q分别指向多项式A和多项式B中当前进行比较的结点，然后比较两个结点中的指数项，有三种情况：1、当P所指结点的指数小于Q的话，就应该复制P的结点到多项式链中。2、P所指结点的指数如果大于Q的指数的话，就应该复制Q的结点到多项式链中，并将建立的结点系数变为相反数。3、当P所指结点的指数等于Q所指结点的指数时，并将Q的结点系数变为相反数，并将两个结点中的系数相加，若和不为0，则修改P所指结点的系数值，同时释放Q所指结点；若和为0，从多项式A的链表中删除相应结点，并释放P、开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项Q所指结点。减法流程图如图2-3所示： 图3-3 一元多项式减法运算流程图4 系统的详细设计4.1 主要算法设计（1）结构式的定义typedef int status; typedef struct NodeType float fCoeff; /系数int iExpon; /指数struct NodeType *next; /下一个指针 NodeType, *LinkType;（2）系统中使用的各函数说明：status MakePolyBuff(PolyPointer *, const int); status MakeNode(polynomial *, const float, const int); void AppNodeToList(polynomial *, polynomial); /* 在链表尾追加结点 */ status CreatePolyn(PolyPointer, int); /输入m项的系数和指数，建立表示一元多项式的有序链表status ProcStrError(const char); /* 检查输入的数据 */ void SortPolyn(PolyPointer, int); /* 根据iExpon域对链表进行升序排序 */ void DestroyBuff(PolyPointer, const int); /销毁一元多项式void DestroyPolyn(polynomial); int PolynLength(const polynomial); /* 求链表的长度 */ void AddProcess(PolyPointer, const int, PolyPointer, const int); /加法运算void SubstractProcess(PolyPointer, const int, PolyPointer); /减法运算void MultiplyProcess(PolyPointer, const int, PolyPointer); /乘法运算void PrintPolyn(const polynomial); /打印输出的一元多项式void MergePolynCoeff(PolyPointer, int); /* 在有序链表中,合并同类项 */（3）主函数：int main(void) int iCounter, iPolyNum; /* 多项式链表缓冲区中链表的个数 */ PolyPointer PolyBuff = NULL; /* 用户输入的多项式链表缓冲区 */ polynomial PolyAddRes = NULL, /* 存放连加结果链表 */ PolySubRes = NULL, /* 存放连减结果链表 */ PolyMulRes = NULL; /* 存放连乘结果链表 */ char strNum10; do printf(请输入需要构造多项式的个数,至少2个: ); gets(strNum); iPolyNum = atoi(strNum); while (iPolyNum 2); MakePolyBuff(&PolyBuff, iPolyNum); /分配内存CreatePolyn(PolyBuff, iPolyNum); /建立多项式的有序链表SortPolyn(PolyBuff, iPolyNum); MergePolynCoeff(PolyBuff, iPolyNum); printf(n打印用户输入并整合后的多项式:n); for (iCounter = 0; iCounter *cpCurr | *cpCurr 9) | (*(cpCurr + 1) = 0 & *cpCurr != ;) printf(输入数据出错,请注意正确的输入方式!n); return FALSE; cpCurr+; 4.3 运行结果分析：对程序进行编译运行，按照窗口的提示，输入多项式个数。首先考虑多项式个数为2，且各指数的系数为正数时。输入数据是，特别注意多项式系数、指数的输入，如图图3-1的所示：图3-1 多项式的输入运行图最终运算结果，如图3-2：图3-2 一元多项式运算运行图1 当多项式个数大于等于2时，且输入各指数的系数均为正数时，对程序进行编译。输入多项式个数为3，具体运行图如图3-3所示：图3-2 一元多项式运算运行图2当输入的多项式系数中存在负数时，对程序进行编译，结果运行图如图3-4所示：5 结束语5.1端正程序设计态度 在这次课程设计中，我遇到了不少困难，但是在我的坚持和虚心请教中都得到顺利解决。在这次课程设计中，我发现理论必须和实践相结合，才能真正学会程序设计，才能完成一个课题。在这次设计中我参考了不少书籍，从中学到了课堂中无法学到的许多东西，对此我感到很兴奋。原来不断的学习，不断的探索是苦中带着甜，虽然经历了不少弯路，经历了不少挫折，但当程序调试成功后，当运行能达到要求后，我感到十二分成就感。面对课题，要展现自信出来，这是成功的一半，在这个设计过程中，不懂的可以虚心向老师请教，与同学交流经验。态度是成功的基石！5.2 程序设计体会 在我这课题中，关键在于对一元多项式的表示及相加的操作。这个实际问题，在学习过的知识中找到一种合适的模型来模拟，数据结构的选择是主要，而对于编写代码，所涉及的并不是很复杂，对于链表数据存储访问方式，在C语言的学习过程中已经有过很多讲解，为了进一步了解，我还阅读了一些数据结构中关于链表的叙述。对于这个课题，运用C语言简单一点的结构化程序设计已足能满足要求而不至于结构过于复杂，为了简便的实现插入操作，我选择了一个带表头结点的链表。在写源代码时要注意指针使用的正确性，为产生的新结点需及时分配存储空间。在设计中将问题抽象化，而完成后在运行时，可以说是用抽象的数据模型来解决实际问题。我的这个课题相比较于其他同学来说，是相对简单的一点的。在现实中，很多功能现在都没法实现，对于文件的写入，我也只是参考了一些书籍，只能写，不能读，还有不少操作需进一步完善，这次程序设计有很多不足处，可能是因为经验不足，对问题预期不够等一些不可预见的原因所致，这些都是我以后要汲取的教训。参考文献1 严蔚敏，吴伟民数据结构（C语言版）. 北京：清华大学出版社，19972李云清，杨庆红数据结构（C语言版）. 北京：人民邮电出版社，20063 美Brian W.Kernighan,Dennis M.Ritchie 。C程序设计语言（第2版新版）. 机械工业出版社 20044 Stephen prata. C.Primer.Plus第五版.北京：北京邮电大学，20045王敬华，林萍，陈静. C语言程序设计. 北京：清华大学出版社，2006太平洋网站，/Info/38/Info15372/：2010-3-5附录1：结构化设计源程序清单/程序名称：v.cpp/程序功能：应用数据结构，采用C语言设计程序，实行一元多项式的加减乘法运算/程序作者： /最后修改日期：#include #include #include #include #define TRUE 1 #define FALSE 0 #define POSITIVE 1 #define NEGATIVE -1 typedef int status; typedef struct NodeType /项的表示，多项式的项作为数据元素float fCoeff; /系数int iExpon; /指数struct NodeType *next; NodeType, *LinkType; typedef LinkType polynomial; /用带表头结点的有序链表表示多项式typedef polynomial *PolyPointer; /基本操作的函数原型说明.status MakePolyBuff(PolyPointer *, const int); status MakeNode(polynomial *, const float, const int); void AppNodeToList(polynomial *, polynomial); /* 在链表尾追加结点 */ status CreatePolyn(PolyPointer, int); /输入m项的系数和指数，建立表示一元多项式的有序链表status ProcStrError(const char); /* 检查输入的数据 */ void SortPolyn(PolyPointer, int); /* 根据iExpon域对链表进行升序排序 */ void DestroyBuff(PolyPointer, const int); /销毁一元多项式void DestroyPolyn(polynomial); int PolynLength(const polynomial); /* 求链表的长度 */ void AddProcess(PolyPointer, const int, PolyPointer, const int); /加法运算void SubstractProcess(PolyPointer, const int, PolyPointer); /减法运算void MultiplyProcess(PolyPointer, const int, PolyPointer); /乘法运算void PrintPolyn(const polynomial); /打印输出的一元多项式void MergePolynCoeff(PolyPointer, int); /* 在有序链表中,合并同类项 */ /主程序int main(void) int iCounter, iPolyNum; /* 多项式链表缓冲区中链表的个数 */ PolyPointer PolyBuff = NULL; /* 用户输入的多项式链表缓冲区 */ polynomial PolyAddRes = NULL, /* 存放连加结果链表 */ PolySubRes = NULL, /* 存放连减结果链表 */ PolyMulRes = NULL; /* 存放连乘结果链表 */ char strNum10; do printf(请输入需要构造多项式的个数,至少2个: ); gets(strNum); iPolyNum = atoi(strNum); while (iPolyNum 2); MakePolyBuff(&PolyBuff, iPolyNum); /分配内存CreatePolyn(PolyBuff, iPolyNum); /建立多项式的有序链表SortPolyn(PolyBuff, iPolyNum); MergePolynCoeff(PolyBuff, iPolyNum); printf(n打印用户输入并整合后的多项式:n); for (iCounter = 0; iCounter iPolyNum; iCounter+) /依次输入非零项printf(第%d个项式:n, iCounter + 1); PrintPolyn(*(PolyBuff + iCounter); /打印输出该多项式 AddProcess(PolyBuff, iPolyNum, &PolyAddRes, POSITIVE); printf(n-连加结果-n); PrintPolyn(PolyAddRes); /打印输出连加结果SubstractProcess(PolyBuff, iPolyNum, &PolySubRes); printf(n-连减结果-n); PrintPolyn(PolySubRes); /打印输出连减结果MultiplyProcess(PolyBuff, iPolyNum, &PolyMulRes); printf(n-连乘结果-n); PrintPolyn(PolyMulRes); /打印输出连乘结果printf(n运行完毕!n); /* 回收资源 */ DestroyBuff(PolyBuff, iPolyNum); /销毁一元多项式DestroyPolyn(PolyAddRes); /销毁连加结果DestroyPolyn(PolySubRes); /销毁连减结果DestroyPolyn(PolyMulRes); /销毁连乘结果getch(); return 0; status MakePolyBuff(PolyPointer *polyBuffHead, const int iPolyNum) int iCounter; /定义多项式个数*polyBuffHead = (PolyPointer) malloc(sizeof(polynomial) * iPolyNum); /分配内存if (!(*polyBuffHead) /内存溢出printf(错误,内存溢出!n); return FALSE; for (iCounter = 0; iCounter iPolyNum; iCounter+) *(*polyBuffHead + iCounter) = NULL; return TRUE; status CreatePolyn(PolyPointer PolyBuff, int iPolyNum) /输入m项的系数和指数，建立表示一元多项式的有序链表int iCounter, iExpon; /分别定义多项式个数，及指数float fCoeff; /系数char strNum100, strTemp64, *cpCurr, *cpCurrNum; polynomial pNewNode = NULL, pInsPos = NULL; /初始化printf(n请输入构造多项式的系数和指数.n); printf(输入一个多项式的方式为: 系数, 指数; . ; 系数, 指数;n例如: 3, 4; 5, 6; 7, 8;n); for (iCounter = 0; iCounter fCoeff = coeff; (*pp)-iExpon = expon; (*pp)-next = NULL; return TRUE; void AppNodeToList(polynomial *pHead, polynomial pNewNode) /多项式加法，利用两个多项式结点构成“和多项式”static polynomial pCurrNode; if (!(*pHead) (*pHead) = pCurrNode = pNewNode; else pCurrNode-next = pNewNode; pCurrNode = pCurrNode-next; void SortPolyn(PolyPointer PolyBuff, int iPolyNum) /建立有序链表int iCounter; polynomial pTemp, pTempCurrNode, /* 临时链表 */ pPrevMinExp, pCurrMinExp,/* 指向最小iExpon结点的指针 */ pCurrNode, pPrevNode; for (iCounter = 0; iCounter next; while (pCurrNode != NULL) if (pCurrMinExp-iExpon pCurrNode-iExpon) pPrevMinExp = pPrevNode; pCurrMinExp = pCurrNode; pPrevNode = pCurrNode; pCurrNode = pCurrNode-next; /* 将系数最小的结点从原链表中取出 */ if (pCurrMinExp = *(PolyBuff + iCounter) *(PolyBuff + iCounter) = pPrevMinExp-next; else pPrevMinExp-next = pCurrMinExp-next; /* 将系数最小的结点插入升序链表 */ pCurrMinExp-next = NULL; if (!pTemp) pTemp = pTempCurrNode = pCurrMinExp; else pTempCurrNode-next = pCurrMinExp; pTempCurrNode = pTempCurrNode-next; *(PolyBuff + iCounter) = pTemp; void MergePolynCoeff(PolyPointer PolyBuff, int iPolyNum) int iCounter; float MergeCoeffRes = 0; polynomial TempList, ResList = NULL, pCurrNode, pPreNode, pNewNode = NULL; for (iCounter = 0; iCounter fCoeff; pCurrNode = (*(PolyBuff + iCounter)-next; while (pCurrNode != NULL) while (pCurrNode != NULL) & (pCurrNode-iExpon = pPreNode-iExpon) MergeCoeffRes += pCurrNode-fCoeff; pPreNode = pCurrNode; pCurrNode = pCurrNode-next; /* 在ResList中加入新结点 */ if (MergeCoeffRes != 0) MakeNode(&pNewNode, MergeCoeffRes, pPreNode-iExpon); AppNodeToList(&ResList, pNewNode); MergeCoeffRes = 0; pPreNode = pCurrNode; DestroyPolyn(TempList); /销毁一元多项式*(PolyBuff + iCounter) = ResList; ResList = NULL; void AddProcess(PolyPointer polyBuff, const int iPolyNum, PolyPointer pResult, const int iSign) /一元多项式的加法运算int iCounter; /定义多项式个数float fCoeffRes; polynomial pNewNode, pCurrNode_1, pCurrNode_2, pDelList = NULL, /* 下次要删除的中间结果链表 */ pResList = NULL; /* 中间结果链表 */ pCurrNode_1 = *(polyBuff); for (iCounter = 1; iCounter iExpon = pCurrNode_2-iExpon) /比较p1和p2指数的大小 /若两指数大小相等fCoeffRes = 0; fCoeffRes = pCurrNode_1-fCoeff + iSign * pCurrNode_2-fCoeff; if (fCoeffRes != 0) MakeNode(&pNewNode, fCoeffRes, pCurrNode_1-iExpon); AppNodeToList(&pResList, pNewNode); pCurrNode_1 = pCurrNode_1-next; pCurrNode_2 = pCurrNode_2-next; else if (pCurrNode_1-iExpon iExpon) /若p1指数比p2小MakeNode(&pNewNode, pCurrNode_1-fCoeff, pCurrNode_1-iExpon); AppNodeToList(&pResList, pNewNode); pCurrNode_1 = pCurrNode_1-next; else /* 当pCurrNode_1-iExpon pCurrNode_2-iExpon时候 */ MakeNode(&pNewNode, iSign * pCurrNode_2-fCoeff, pCurrNode_2-iExpon); AppNodeToList(&pResList, pNewNode); pCurrNode_2 = pCurrNode_2-next; /* 加入余下的多项式 */ while (pCurrNode_1 != NULL) MakeNode(&pNewNode, pCurrNode_1-fCoeff, pCurrNode_1-iExpon); AppNodeToList(&pResList, pNewNode); /增加结点pCurrNode_1 = pCurrNode_1-next; while (pCurrNode_2 != NULL) MakeNode(&pNewNode, iSign * pCurrNode_2-fCoeff, pCurrNode_2-iExpon); AppNodeToList(&pResList, pNewNode); pCurrNode_2 = pCurrNode_2-next; if (pDelList != NULL) DestroyPolyn(pDelList); pCurrNode_1 = pResList; pDelList = pResList; pResList = NULL; *pResult = pCurrNode_1; void SubstractProcess(PolyPointer polyBuff, const int iPolyNum, PolyPointer pResult) /利用多项式相加运算，完成多项式的相减运算AddProcess(polyBuff, iPolyNum, pResult , NEGATIVE); void MultiplyProcess(PolyPointer polyBuff, const int iPolyNum, PolyPointer pResult) /利用多项式相加运算，完成多项式的相乘运算int iCounter = 1, jCounter = 0, iLength; /* 缓冲区的长度 */ PolyPointer pTempBuff = NULL; /* 存放中间结果的缓冲区 */ polynomial pCurrNode_1, pCurrNode_2, pNewNode = NULL; /* 初始化 */ pCurrNode_1 = polyBuff0; iLength = PolynLength(polyBuff0); MakePolyBuff(&pTempBuff, iLength); while (TRUE) while (pCurrNode_1 != NULL) pCurrNode_2 = polyBuffiCounter; while (pCurrNode_2 != NULL) MakeNode(&pNewNode,pCurrNode_1-fCoeff * pCurrNode_2-fCoeff, pCurrNode_1-iExpon + pCurrNode_2-iExpon); AppNodeToList(&pTempBuffjCounter, pNewNode); pCurrNode_2 = pCurrNode_2-next; jCoun