【数据结构】宜宾大学-计院-实验三

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using std::cout;
using std::cin;
using std::endl;

//多项式项的两特征
typedef struct
{
	float coef;//系数
	int index;//指数
}polydata;

//单链表节点
typedef struct SLNode
{
	polydata data;//自定义类型（多项式的项）
	struct SLNode* next;
}SLNode, * SLNodePtr;

//比较项的指数来达到合并同类型的目的
int cmp(polydata pa, polydata pb)
{
	if (pa.index > pb.index)
		return 1;
	else if (pa.index < pb.index)
		return -1;
	else
		return 0;
}

//创建一个多项式，n为多项式的项数
void GreatSLNode(SLNodePtr& polyhead, int n)
{
	//动态开辟头节点
	polyhead = (SLNodePtr)malloc(sizeof(SLNode));
	if (polyhead == NULL) return;
	polyhead->next = NULL;

	SLNodePtr rear = polyhead;//尾指针指向头节点

	polydata tmp;
	//创建项数为n的多项式
	for (int i = 1; i <= n; i++)
	{
		SLNodePtr p = (SLNodePtr)malloc(sizeof(SLNode));
		if (p == NULL) return;
		printf("分别输入该多项式第 %d 项的系数与指数\n", i);
		//scanf_s("%f%d", &tmp.coef, &tmp.index);
		cin >> tmp.coef >> tmp.index;
		p->data.coef = tmp.coef;
		p->data.index = tmp.index;

		//更新尾节点并记得给尾的next赋NULL
		rear->next = p;
		rear = p;
		rear->next = NULL;
	}
	rear->next = NULL;//给尾的next赋NULL
}

//两多项式相加并合并同类项
SLNodePtr AddPoly(SLNodePtr pahead, SLNodePtr pbhead)
{
	//动态开辟头节点并创建尾节点指向头节点
	SLNodePtr newhead = (SLNodePtr)malloc(sizeof(SLNode));
	if (newhead == NULL) return NULL;
	SLNodePtr newrear = newhead;

	//分别找到两多项式的第一项数据即第一个有效节点
	SLNodePtr pa = pahead->next;
	SLNodePtr pb = pbhead->next;

	SLNodePtr newnode;//创建新节点待用
	float sum;//相同指数的项系数相加
	while (pa && pb)
	{
		switch (cmp(pa->data, pb->data))
		{
		case 1://指数不相等项
			newnode = (SLNodePtr)malloc(sizeof(SLNode));
			if (newnode == NULL) return NULL;
			newnode->data.coef = pa->data.coef;
			newnode->data.index = pa->data.index;
			//尾插并更新尾
			newrear->next = newnode;
			newrear = newnode;

			pa = pa->next;
			break;
		case -1://指数不相等项
			newnode = (SLNodePtr)malloc(sizeof(SLNode));
			if (newnode == NULL) return NULL;

			newnode->data.coef = pb->data.coef;
			newnode->data.index = pb->data.index;
			//尾插并更新尾
			newrear->next = newnode;
			newrear = newnode;

			pb = pb->next;
			break;
		case 0://指数相等项
			sum = pa->data.coef + pb->data.coef;
			if (sum != 0)
			{
				newnode = (SLNodePtr)malloc(sizeof(SLNode));
				if (newnode == NULL) return NULL;

				newnode->data.coef = sum;
				newnode->data.index = pa->data.index;
				//尾插并更新尾
				newrear->next = newnode;
				newrear = newnode;
			}

			pa = pa->next;
			pb = pb->next;
			break;
		}
	}
	
	//将剩余项接在最后
	if (pa)
		newrear->next = pa;
	if (pb)
		newrear->next = pb;

	return newhead;
}

//打印
void Print(SLNodePtr polynewhead)
{
	SLNodePtr tmp1 = polynewhead->next;//第一个有效节点
	while (tmp1)
	{
		printf("%.2fx^%d", tmp1->data.coef, tmp1->data.index);
		cout << " + ";
		tmp1 = tmp1->next;
	}
}
int main()
{
	//创建两个节点指针
	SLNodePtr polyhead1;
	SLNodePtr polyhead2;

	cout << "前提条件：输入多项式的“指数大小”随着“项数”的“增多而减小”，否则无法完全合并同类项" << endl;
	cout << "请输入第一个多项式" << endl;
	GreatSLNode(polyhead1, 3);
	cout << endl;
	cout << "请输入第二个多项式" << endl;
	GreatSLNode(polyhead2, 2);

	SLNodePtr newhead = AddPoly(polyhead1, polyhead2);
	cout << "输出两多项式相加后的各项系数与指数" << endl;
	Print(newhead);
	return 0;
}