一元多项式输入、输出、运算（基于链表）
读入2个多项式和一个运算符（加号+,减号-,乘号*），计算多项式运算结果，并按照要求输出运算结果。
输入样例：
x+5x^2
*
-x+5x^2输出样例：
运算结果是:
x + 5x^2
*
-x + 5x^2
= -x^2 + 25x^4多项式的定义
由若干个单项式，通过 '+' 或 '-' 连接起来的式子。 例如：-x^2+3-5x^6 + x + 9 + x单项式的基本格式为：
系数x^幂指数例如：
5x^2 表示5倍的 x 平方
3x^-4 表示3倍的 x 的 -4 次方
一个单项式内部【不允许】有空白字符（空格或\t)。例如不允许：2 x^ 3 输入要求
1）当省略系数，则表示系数为 1。例如：x^3
2）当系数省略为减号时，则表示系数为 -1。例如：-x^3
3）当省略幂指数时，则表示幂指数为1。例如：-5x。
4）对于常数项，可以省略x^0，例如：-2 （表示 -2x^0） 单项输出要求
1）如果幂指数为 0，须简化为常数项。例如：3x^0 应该输出为 3
2）如果幂指数为 1，须省略它。例如：3x^1 应该输出为3x
3）如果系数为1或-1，须省略1。例如：-x^6，x^2
4）单项式内部不能有空白字符（空格或\t)多项式输出要求
1）在项与项之间的+号、-号左右两侧须各留一个空格
2）按照幂指数升高的顺序输出，例如：-2 + 3x^5 -x^9
3）不输出系数为零的项
4）零多项式，输出 0 按照接口要求，编写以下 7 个函数代码
void PrintMonomial(int coef, int expo);
Monomial* ParseMonomial(char **s);
Polynomial InsertAfterTail(Polynomial head, Monomial* pNewNode);
Polynomial TrimZeroTerms(Polynomial head);
Polynomial SortPolynomial(Polynomial head);
Polynomial Minus(Polynomial p1, Polynomial p2);
Polynomial Multiply(Polynomial p1, Polynomial p2);函数接口定义：
------------------------------------------------------------------------------
函数 PrintMonomial - 输出单项式
void PrintMonomial(int coef, int expo);
1）如果幂指数为 0，则简化为常数项。例如：x^0 应该输出为 1
2）如果幂指数为 1，则须省略它。例如：-3x^1 应该输出为-3x
3）如果系数为1或-1，则输出时须省略1。例如：-x^6，x^2
4）输出时，单项式内部不能有空白字符（空格或\t)
5）零单项式不输出
参数
coef - 单项式系数
expo - 单项式幂指数
返回值
无
------------------------------------------------------------------------------
函数 ParseMonomial - 读入字符串中的第一个单项式
Monomial* ParseMonomial(char **s)
参数
s - *s是字符串指针，指定数据读取源
函数执行成功后，*s会单项式后面的第一个字符
返回值
成功 - 所读入的单项式指针
失败 - NULL
------------------------------------------------------------------------------
函数 InsertAfterTail - 插入新节点到多项式链表末尾
Polynomial InsertAfterTail(Polynomial head, Monomial* pNewNode);
参数
head - 多项式的头节点指针
pNewNode - 新插入节点的指针
返回值
插入节点后，新多项式的头节点指针
------------------------------------------------------------------------------
函数 DeleteZeroTerms - 删除多项式中的零系数节点
Polynomial DeleteZeroTerms(Polynomial head);
参数
head - 被简化的多项式的头节点指针
返回值：简化后的多项式链表的节点指针
------------------------------------------------------------------------------
函数 SortPolynomial - 对多项式按照幂指数进行升序排序
Polynomial SortPolynomial(Polynomial head);
参数
head - 被排序的多项式的头节点指针
返回值：排序后的多项式头节点指针
------------------------------------------------------------------------------
函数 Minus - 多项式求差： p1 - p2
链表 p1和p2保持不变
Polynomial Minus(Polynomial p1, Polynomial p2);
返回值：
多项式 "差" 的表头指针
------------------------------------------------------------------------------
函数 Multiply - 多项式乘积： p1 * p2
链表 p1和p2保持不变
Polynomial Multiply(Polynomial p1, Polynomial p2);
返回值：
多项式 "积" 的表头指针
------------------------------------------------------------------------------
测试程序
#include <stdlib.h>
#include <stdio.h>
#define MAXLINE 1024
// 交换 a, b，以t为中间变量
#define SWAP(a,b,t) (t)=(a),(a)=(b),(b)=(t)
// 单项式结构
typedef struct MonomialStruct{
int coef; // 系数
int expo; // 幂次
struct MonomialStruct * next;
} Monomial;
// 多项式类型定义
typedef Monomial *Polynomial;
void PrintMonomial(int coef, int expo);
Monomial* ParseMonomial(char **s);
Polynomial InsertAfterTail(Polynomial head, Monomial* pNewNode);
Polynomial TrimZeroTerms(Polynomial head);
Polynomial SortPolynomial(Polynomial head);
Polynomial Minus(Polynomial p1, Polynomial p2);
Polynomial Multiply(Polynomial p1, Polynomial p2);
/*******************************************************************************
函数 CreateMonomial - 创建一个单项式项式节点
Monomial * CreateMonomial(int coef, int expo);
参数
coef - 系数
expo - 幂指数
返回值
成功 - 所创建的节点指针
失败 - NULL
*******************************************************************************/
Monomial * CreateMonomial(int coef, int expo)
{
Monomial * p = (Monomial*)malloc(sizeof(Monomial));
if( !p )
return NULL;
p->coef = coef;
p->expo = expo;
p->next = NULL;
return p;
}
/*******************************************************************************
函数 DeletePolynomial - 删除一个多项式，并释放所有的节点内存
Polynomial DeletePolynomial(Polynomial p)
参数
head - 被删除的多项式的头节点指针
返回值
空指针 NULL
*******************************************************************************/
Polynomial DeletePolynomial(Polynomial head)
{
while(head) {
Monomial * d = head;
head = head->next;
free(d);
}
return NULL;
}
/*****************************************************
函数 AddMonomial - 在多项式中添加一个单项式
如果链表中已经存在同次项，则不会创建新节点，而是对系数进行累加。
Polynomial AddMonomial(Polynomial head, int coef, int expo);
参数
head - 多项式的头节点指针
coef - 单项式的系数
expo - 单项式的幂指数
返回值
新的多项式链表的表头指针
*****************************************************/
Polynomial AddMonomial(Polynomial head, int coef, int expo)
{
Monomial * p;
if( coef==0 )
return head;
for( p = head; p && p->expo!=expo; p = p->next )
; // 寻找同次项
if( p )
// 找到同次项
p->coef += coef;
else {
p = CreateMonomial(coef, expo);
head = InsertAfterTail(head, p);
}
return head;
}
/*****************************************************
函数 Add - 多项式求和： p1 + p2
链表 p1 和 p2保持不变
返回值：
多项式 "和" 的表头指针
*****************************************************/
Polynomial Add(Polynomial p1, Polynomial p2)
{
Polynomial h = NULL;
for( ; p1; p1=p1->next )
h = AddMonomial(h, p1->coef, p1->expo);
for( ; p2; p2=p2->next )
h = AddMonomial(h, p2->coef, p2->expo);
return h;
}
// 判断字符串 s 的起始字符是否为：x^ 或 X^
int IsEXPO(char *s)
{
return ( (s[0]=='x' || s[0]=='X') && s[1]=='^');
}
// 字符是否为\n或\0
int IsEndingChar(char ch)
{
return (ch==0 || ch=='\n');
}
// 跳过字符串起始部分的空格和制表符
// 返回值：一个指针
// 指向字符串前面的第一个非空白字符
char * SkipSpaceChars(char *s)
{
while( *s==' ' || *s=='\t' )
s++;
return s;
}
/*****************************************************
函数 GetSignChar - 字符串*s中第一个单项式的符号字符
int GetSignChar(char **s);
参数
s - *s是字符串指针
返回值
成功 -返回符号字符，将*s指向符号之后的字符
不成功 -返回 0
*****************************************************/
int GetSignChar(char **s)
{
char *p = SkipSpaceChars(*s); // 忽略空白字符
if( *p=='+' || *p=='-' ) {
*s = p + 1;
return (*p);
}
return 0;
}
/*****************************************************
从一行标准输入，读取一个一元多项式
返回值：
所读取的多项式链表的表头指针
*****************************************************/
Polynomial ParsePolynomial()
{
char linebuffer[1024], *s = linebuffer;
Polynomial hResult = NULL;
if( !fgets(linebuffer, sizeof(linebuffer), stdin) )
return NULL;
while( 1 ) {
Monomial *pNewNode;
int signChar = GetSignChar(&s);
pNewNode = ParseMonomial(&s);
if( !pNewNode )
break;
if( signChar == '-' )
pNewNode->coef = -pNewNode->coef;
hResult = InsertAfterTail(hResult, pNewNode);
}
return hResult;
}
/*****************************************************
函数 PrintPolynomial - 输出多项式
Polynomial PrintPolynomial(Polynomial pHead);
两个单项式之间的+/-左右各留出一个空格
返回值
被输出的多项式
*****************************************************/
Polynomial PrintPolynomial(Polynomial pHead)
{
Polynomial p = pHead;
int firstTerm = 1, nothingOutputYet = 1;
for( ; p; p = p->next )
{
int c = p->coef;
int k = p->expo;
if( c==0 ) // 忽略系数为0的项
continue;
if( firstTerm ) {
PrintMonomial(c,k);
firstTerm = 0;
} else {
printf(" %c ", c>0 ? '+' : '-');
PrintMonomial(c>0?c:-c, k);
}
nothingOutputYet = 0;
}
if( nothingOutputYet )
putchar('0');
putchar('\n');
return pHead;
}
/*------------------------------------------------------------------
1. 如果测试多项式输入输出，那么：
输入多项式1，回车
回车
2. 如果测试两个多项式的 "加"、"减"、"乘"运算，那么：
输入第一个多项式，回车
输入运算符（+、-、*)，回车
输入第二个多项式，回车
------------------------------------------------------------------*/
int main()
{
Polynomial p1, p2, pResult;
char cmdString[MAXLINE], cmd;
p1 = ParsePolynomial(); //读入多项式 1
if( !fgets(cmdString, sizeof(cmdString), stdin) )
return 0;
cmd = cmdString[0];
if( cmd!='+' && cmd!='-' && cmd!='*' ) {
//测试多项式的输入和输出
printf("input=");
PrintPolynomial( p1 );
return 0;
}
p2 = ParsePolynomial(); //读入多项式 1
// printf("\n运算结果是:\n\n");
PrintPolynomial( p1 );
printf("%c\n", cmd);
PrintPolynomial( p2 );
printf("=\n");
if( cmd=='+' )
pResult = PrintPolynomial( SortPolynomial( TrimZeroTerms( Add(p1,p2) ) ) );
else if( cmd=='-' )
pResult = PrintPolynomial( SortPolynomial( TrimZeroTerms( Minus(p1, p2) ) ) );
else //if( cmd=='*' )
pResult = PrintPolynomial( SortPolynomial( TrimZeroTerms( Multiply(p1, p2) ) ) );
// printf("\n");
DeletePolynomial(p1);
DeletePolynomial(p2);
DeletePolynomial(pResult);
return 0;
}仅供参考：
//链表实现一元多项式的加法减法乘法
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
float coef; //系数
int expn; //指数
struct node *next;
} PolyNode;
typedef PolyNode* Polynomial;
Polynomial createPolynomial() { //创建多项式
PolyNode *p, *q, *head = (PolyNode *)malloc(sizeof(PolyNode));
head->next = NULL;
float coef;
int expn;
printf("输入该多项式每一项的系数和指数，每项一行，输入0 0结束！\n");
while (1) {
scanf("%f %d", &coef, &expn);
if (0.0==coef && 0==expn) break;
if (head->next) {
p = head;
while (p->next && expn < p->next->expn) p = p->next;
if (p->next) {
if (expn == p->next->expn) { //有相同指数的直接把系数加到原多项式
p->next->coef += coef;
if (-0.00001f < p->next->coef && p->next->coef < 0.00001f) { //若是相加后系数为0，则舍弃该节点
q = p->next;
p->next = q->next;
free(q);
}
} else {
q = (PolyNode*)malloc(sizeof(PolyNode));
q->coef = coef;
q->expn = expn;
q->next = p->next;
p->next = q;
}
} else {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = coef;
p->expn = expn;
p->next = NULL;
}
} else {
head->next = (PolyNode*)malloc(sizeof(PolyNode));
head->next->coef = coef;
head->next->expn = expn;
head->next->next = NULL;
}
}
return head;
}
Polynomial polyAdd(Polynomial poly1, Polynomial poly2) { //多项式相加 poly1+poly2形成一个新的多项式
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //和多项式的头节点
poly->next = NULL;
PolyNode *p, *q, *r;
r = poly;
p = poly1->next;
q = poly2->next;
while (p&&q) {
if (p->expn > q->expn) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = p->coef;
r->expn = p->expn;
p = p->next;
} else if (p->expn < q->expn) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = q->coef;
r->expn = q->expn;
q = q->next;
} else {
float m = p->coef + q->coef;
if (!(-0.00001f <m && m < 0.00001f)) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = m;
r->expn = p->expn;
}
q = q->next;
p = p->next;
}
}
while (p) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = p->coef;
r->expn = p->expn;
p = p->next;
}
while (q) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = q->coef;
r->expn = q->expn;
q = q->next;
}
r->next = NULL;
return poly;
}
Polynomial polySubtract(Polynomial poly1, Polynomial poly2) { //多项式减法 poly1-poly2形成一个新的多项式
//把poly2的系数取相反数，形成一个新的多项式
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //构造头节点
PolyNode *p, *q;
p = poly;
q = poly2->next;
while (q) {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = -(q->coef); //系数取反
p->expn = q->expn;
q = q->next;
}
p->next = NULL;
Polynomial poly3 = polyAdd(poly1, poly); //利用加法
return poly3;
}
void add(Polynomial poly1, Polynomial poly2) { //把 poly2 加到 poly1 上
PolyNode *p, *q, *r;
r = poly1;
p = poly1->next; //指向第一个节点
q = poly2->next;
poly2->next = NULL;
while (p && q) {
if (p->expn > q->expn) {
r->next = p;
p = p->next;
r = r->next;
} else if (p->expn < q->expn) {
r->next = q;
q = q->next;
r = r->next;
} else {
PolyNode *t;
p->coef += q->coef;
if (!(-0.00001f < p->coef && p->coef < 0.00001f)) { //系数不为0
r->next = p;
r = r->next;
p = p->next;
} else {
t = p;
p = p->next;
free(t);
}
t = q;
q = q->next;
free(t);
}
}
if (p) r->next = p;
if (q) r->next = q;
}
void printPoly(Polynomial poly) { //打印多项式
if (poly && poly->next) {
PolyNode *p = poly->next; //p指向第一个节点
while (p->next) {
if (1!=p->expn) printf("%g X^%d", p->coef, p->expn);
else printf("%g X" , p->coef );
p = p->next;
if (p) {
if (p->coef > 0) printf(" +");
else printf(" ");
}
}
if (p->expn == 0)
printf("%g", p->coef); //打印常数项
else {
if (1!=p->expn) printf("%g X^%d", p->coef, p->expn);
else printf("%g X" , p->coef );
}
printf("\n");
} else {
printf("0\n");
}
}
Polynomial multiply(Polynomial poly, float coef, int expn) { //多项式与指定单项式相乘，该单项式为 coefx^expn
PolyNode *p, *q, *Poly = (PolyNode*)malloc(sizeof(PolyNode));
p = Poly;
q = poly->next;
while (q) {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = (q->coef * coef);
p->expn = (q->expn + expn);
q = q->next;
}
p->next = NULL;
// printf("多项式");printPoly(poly);
// printf("乘");printf("%g X^%d\n",coef,expn);
// printPoly(Poly);
return Poly;
}
Polynomial polyMultiply(Polynomial poly1, Polynomial poly2) { //多项式相乘
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //创建多项式和的头节点
poly->next = NULL;
PolyNode *p;
p = poly2->next;
while (p) {
add(poly, multiply(poly1, p->coef, p->expn));
// printf("子多项式");printPoly(poly);
p = p->next;
}
// printf("结果多项式");printPoly(poly);
return poly;
}
void freePoly(Polynomial poly) { //释放内存
if (poly && poly->next) {
PolyNode *p, *q;
p = poly;
while (p) {
q = p->next;
free(p);
p = q;
}
}
poly = NULL;
}
int main() {
printf("用链表实现多项式的加减乘法\n");
Polynomial poly1, poly2, poly3;
printf("创建多项式一\n");
poly1 = createPolynomial();
printf("创建多项式二\n");
poly2 = createPolynomial();
printf(" 多项式一：");printPoly(poly1);
printf(" 多项式二：");printPoly(poly2);
poly3 = polyAdd(poly1, poly2);
printf("两多项式相加，和为：");printPoly(poly3);
freePoly(poly3);
poly3 = polySubtract(poly1, poly2);
printf("两多项式相减，差为：");printPoly(poly3);
freePoly(poly3);
// printf(" 多项式一：");printPoly(poly1);
// printf(" 多项式二：");printPoly(poly2);
poly3 = polyMultiply(poly1, poly2);
printf("两多项式相乘，积为：");printPoly(poly3);
freePoly(poly3);
freePoly(poly2);
freePoly(poly1);
system("pause");
return 0;
}
//用链表实现多项式的加减乘法
//创建多项式一
//输入该多项式每一项的系数和指数，每项一行，输入0 0结束！
//4 9
//3 6
//2 5
//0 0
//创建多项式二
//输入该多项式每一项的系数和指数，每项一行，输入0 0结束！
//4 9
//3 6
//2 5
//0 0
// 多项式一：4 X^9 +3 X^6 +2 X^5
// 多项式二：4 X^9 +3 X^6 +2 X^5
//两多项式相加，和为：8 X^9 +6 X^6 +4 X^5
//两多项式相减，差为：0
//两多项式相乘，积为：16 X^18 +24 X^15 +16 X^14 +9 X^12 +12 X^11 +4 X^10
//请按任意键继续. . .
你好，我是有问必答小助手。为了技术专家团更好地为您解答问题，烦请您补充下（1）问题背景详情，（2）您想解决的具体问题，（3）问题相关代码图片或者报错信息。便于技术专家团更好地理解问题，并给出解决方案。
您可以点击问题下方的【编辑】，进行补充修改问题。