[数据结构与算法]一元多项式输入、输出、运算（基于链表）

题目描述

测试程序

#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; 
}

题目思路

思路其实并不难，但是实现起来非常难，其中有很多很多细节要去分析和注意。

题目的坑

1.char **s; 则*s[1]与（*s）[1] 是不一样的
2.输入为0时用依次取位的方法要加以特判（测试点里面说”输入多项式5“ 无语0.0~）
3.输入为空行时要认为是0
4.当处理指数时，对于无x的项应当直接跳过，否则会有被吞掉的位。
5.特别留心指针为空的情况，比如p=NULL 当调用p->next时程序崩溃

AC代码

void print(int coef){//打印系数
	if(coef == 1) return ;
	else if(coef == -1) printf("-");
	else printf("%d", coef);
}
void PrintMonomial(int coef, int expo){//打印单项式
	if(expo == 0) printf("%d", coef);
	else if(expo == 1){
		print(coef);
		printf("x");
	}
	else{
		print(coef);
		printf("x^%d", expo);
	}		
	return ;
} 
#include<ctype.h>
Monomial*  ParseMonomial(char **s){//输入单项式
	*s = SkipSpaceChars(*s);
	if(IsEndingChar(**s)) return NULL;
	Polynomial p = (Polynomial)malloc(sizeof(Monomial));
	p->coef = 1, p->expo = 0;
	int t = 0;
	if((*s)[0] == 'x' || (*s)[0] == 'X'){
		t = 1;
		if((*s)[1] == '^') *s += 2;
		else{
			p->expo = 1;
			*s += 1;
			return p;
		}
	}
	else{//处理系数 
		if(!isdigit(**s)){
			if(**s == '-') p->coef *= -1;
			*s += 1;
		}
		int sum = 0;
		if(**s == '0') p->coef = 0; 
		while(isdigit(**s)){
			sum = **s - '0' + sum * 10;
			*s += 1;
		}
		if(sum != 0) p->coef *= sum;
		if((*s)[0] == 'x' || (*s)[0] == 'X'){
			t = 1;
			if((*s)[1] == '^') *s += 2;
			else{
				p->expo = 1;
				*s += 1;
				return p;
			}
		}
	}
	//处理指数 
	if(t == 0) return p;
	int sign = 1; 
	if(!isdigit(**s)){
		if(**s == '-') sign *= -1, *s += 1;
	}
	int Sum = 0;
	while(isdigit(**s)){
		Sum = **s - '0' + Sum * 10;
		*s += 1;
	}
	if(Sum != 0) p->expo = sign * Sum;
	return p;
}
Polynomial InsertAfterTail(Polynomial head, Monomial* pNewNode){//插入单项式
	if(head == NULL){
		head = pNewNode;
		head->next = NULL;
		return head;
	}
	else{
		Polynomial tmp = head;
		while(tmp->next){
			tmp = tmp->next;
		}
		tmp->next = pNewNode;
		tmp->next->next = NULL;
		return head;
	}
}
Polynomial TrimZeroTerms(Polynomial head){//去掉零多项式
	Polynomial H = NULL;
	while(head){
		if(head->coef != 0)
			H = InsertAfterTail(H, CreateMonomial(head->coef, head->expo));
		head = head->next;
	}
	return H;
}
Polynomial SortPolynomial(Polynomial head){//排序函数（选择排序）
	if(head == NULL || head->next == NULL) return head;
	Polynomial p, q, temp;
	for(p = head; p ; p = p->next){
		temp = p;
		for(q = p->next; q ; q = q->next)
			if(q->expo < temp->expo){
				temp = q;
			}
		int tmp;
		SWAP(p->coef, temp->coef, tmp);
		SWAP(p->expo, temp->expo, tmp);		
	}
	return head;
}
Polynomial MinusMonomial(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;
}
Polynomial Minus(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 = MinusMonomial(h, p2->coef, p2->expo);
    return h;
}
Polynomial Multiply(Polynomial p1, Polynomial p2){//乘法函数
    Polynomial h = NULL;
    Polynomial k;
    for( ; p1; p1 = p1->next)
    	for(k = p2 ; k; k = k->next)
    		h = AddMonomial(h, p1->coef * k->coef, p1->expo + k->expo);
    return h;
}