问题描述

设计算法实现一元多项式的简单运算。

基本要求

（1） 输入并建立多项式;

（2） 输出多项式;

（3） 多项式加法

（4） 多项式减法。

问题分析

（一）算法设计思路：

建立两个带头结点的单链表储存多项式，每个结点分别有一个系数域（浮点型）、指数域（整型）、指针域（指向下一个结点）。用户输入两个多项式的每一项系数及其对应指数，储存并将其按指数升序排序。若为加法，则直接将两多项式相加，若为减法，则将第二个多项式系数依次取反后相加。输出结果多项式。

（二）使用模块及变量的说明

1、typedef  struct xn：定义多项式结点

2、List Creat_List()：建立带头节点的单链表储存多项式

3、List fun(List A)：按指数升序排列单链表

4、List merge(List A)：多项式合并

5、List xnAdd(List A, List B)：两个多项式相加

6、List xnOdd(List B)：多项式系数取反

7、void resPrint(List C)：输出多项式

8、主调函数部分：输入多项式的每一项，创建、排序、合并两个多项式单链表输出多项式，判断加号减号，并进行运算，输出结果多项式

实验代码

C++版

#include<iostream>
using namespace std;

//定义多项式结点
typedef  struct xn
{
	float xi;  //系数部分
	int zhi;  //指数部分
	struct xn* next;  //指向下一项
}xn, * List;

//建立带头结点的单链表储存多项式
List Creat_List()
{
	List L;
	xn* p,  * rear;  //p指针用于插入新的结点，rear为尾指针
	float x=1;
	L = new xn; L->next = NULL;
	rear = L;
	while (x!= 0){   //建立的单链表最后一个结点储存系数为0
		p = new xn;
		cout << "请输入系数：";
		cin >> p->xi;
		x = p->xi;
		cout << "请输入对应指数：";
		cin >> p->zhi;
		rear->next = p;
		rear = p;
	} 
	rear->next = NULL;  //尾指针置空
	return L;
}

//按升序排序多项式
List fun(List A) {
	xn* p, * q; 
	float a;
	int b;
	p = A->next;
	if (p->next != NULL) {
		while (p->next->xi != 0) {  //固定p指针
			q = p->next;    //q指针从p指针后一个结点遍历
			while (q->xi != 0) {
				if (q->zhi < p->zhi) {
					a = q->xi; b = q->zhi;   //a,b用于储存系数和指数
					q->xi = p->xi; q->zhi = p->zhi;    //交换p，q的系数和指数
					p->xi = a; p->zhi = b;
				}
				q = q->next;
			}
			p = p->next;
		}
	}
	return A;
}

//多项式合并
List merge(List A) {
	xn* p;
	p = A->next;
	while (p->xi != 0) {
		if (p->zhi == p->next->zhi) {
			p->xi =p->xi + p->next->xi;
			delete p->next;
			p->next = p->next->next;
			continue;
		}
		p = p->next;
	}
	return A;
}

//多项式加法
List xnAdd(List A, List B)
{
	List C ;
	xn* p, * q, * s, * r;
    C = new xn;
	r = C;
	p = A->next  ; q = B->next  ;   //p,q指向首元结点
	while (p->xi!=0  && q->xi!= 0) {  
		s = new xn;
		if (p->zhi == q->zhi) {
			s->xi = p->xi + q->xi;
			if (s->xi != 0) {   //系数为0，不存入结果多项式
				s->zhi = p->zhi;
				r->next = s;
				r = s;
			}
			p = p->next; q = q->next;
			continue;
		}
		if (p->zhi < q->zhi) {
			s = p;
			r->next = s;
			r = s;
			p = p->next;
			continue;
		}
		if (p->zhi > q->zhi) {
			s = q;
			r->next = s;
			r = s;
			q = q->next;
			continue;
		}
	}
	if (p->xi == 0) r->next = q;
	else r->next = p;
	return C;
}

//多项式系数取反
List xnOdd(List B) {
	xn* p ;
	p = B->next;
	while (p->xi != 0) {  //p指针遍历单链表，并将系数取反
		p->xi = -p->xi;
		p = p->next;
	}
	return B;
}

//输出多项式
void resPrint(List C) {
	xn* q;
	q = C->next;
	if (q->xi == 0) {
		cout << "0";
	}
	else {
		cout << q->xi << "x" << q->zhi;
		while (q->next != NULL) {
			q = q->next;
			if (q->xi > 0) {
				cout << "+" << q->xi << "x" << q->zhi;
			}
			if (q->xi < 0) {
				cout << q->xi << "x" << q->zhi;
			}
		}
	}cout << endl;
}

int main()
{
	char a;
	List A, B, C = NULL;
	cout << "请输入第一个多项式（系数输入0时结束）" << endl;
	A = Creat_List();
	A = fun(A);
	A = merge(A);
	resPrint(A);
	cout << "请输入第二个多项式（系数输入0时结束）" << endl;
	B = Creat_List();
	B = fun(B);
	B = merge(B);
	resPrint(B);
	cout << "请输入“+”或者“-”：";
	cin >> a;
	if (a == '+')  C = xnAdd(A, B);
	if (a == '-') {
		B = xnOdd(B);
		C = xnAdd(A, B);
	}
	resPrint(C);
	xn* d1 = A, * d2 = B, * d3 = C, * d = NULL;
	while (d1->xi != 0) {
		d = d1;
		d1 = d1->next;
		delete d;
	}
	while (d2->xi != 0) {
		d = d2;
		d2 = d2->next;
		delete d;
	}
	if (C != NULL) {
		while (d3->xi != 0) {
			d = d3;
			d3 = d3->next;
			delete d;
		}
	}
	delete d1, d2, d3;
	system("pause");
	return 0;
}

运行截图

 实验总结

1、创建多项式过程中，没有在循环中为新的结点申请空间，导致无法创建链表，调试后问题解决。

2、按升序排序多项式时，未考虑0的情况，导致存在空指针，调试后问题解决。

3、多项式加法部分，p,q指针在if判断后，至少有一个指针会向后移动，移动后出现继续判断下一个if的问题，增加continue后，问题解决。

4、合并同类项部分，指针指向指数相同部分时，增加continue，使指针定在指数相同的第一个位置，直到下一个指数不再相同。