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

课前准备：

大家跟着我一起读，少壮不努力，没钱打游戏…

———龟虽寿
——东汉末年·曹操
神龟虽寿，犹有竟时；
腾蛇乘雾，终为土灰。
老骥伏枥，志在千里；
烈士暮年，壮心不已。
盈缩之期，不但在天；
养怡之福，可得永年。
幸甚至哉，歌以咏志。

人物简介：曹操（155年-220年正月庚子），字孟德，一名吉利，小字阿瞒，沛国谯（今安徽亳州）人，是东汉末年杰出的政治家、军事家、文学家、书法家。‌ 他也是曹魏政权的奠基者，其子曹丕称帝后，追尊他为武皇帝，庙号太祖‌。

注释：
1 龟虽寿： 曹操所作乐府组《步出夏门行》中的第四章。
2 神龟： 传说中的通灵之龟，能活几千岁。寿，长寿。
3 竟： 终结，这里指死亡。
4 腾蛇： 传说中龙的一种，能乘云雾升天。
5 骥： 良马，千里马。伏：趴，卧。枥：马槽。
6 烈士： 操有远大抱负的男子。这里专指为革命事业献身的人。暮年：晚年。

译文：

1. 神龟虽寿，犹有竟时；腾蛇乘雾，终为土灰。
   译：
   神龟虽然十分长寿，但生命终究会有结束的一天；腾蛇尽管能腾云乘雾飞行，但终究也会死亡化为土灰。
2. 老骥伏枥，志在千里；烈士暮年，壮心不已。
   译：
   年老的千里马虽然伏在马槽旁，雄心壮志仍是驰骋千里；壮志凌云的人士即便到了晚年，奋发思进的心也永不止息。
3. 盈缩之期，不但在天；养怡之福，可得永年。
   译：
   人寿命长短，不只是由上天决定；调养好身心，就定可以益寿延年。
4. 幸甚至哉，歌以咏志。
   译：
   真是幸运极了，用歌唱来表达自己的思想感情吧。

神龟：传说可以活几千岁…

实验学时：2

实验目的：

1．掌握线性表的链式存储结构
2．能实现链表的基本操作，包括链表的建立、释放、查找、求长度、查找后继、插入、删除、输出等函数

实验内容：

实验结果：

每个同学都要记录实验结果（无论对与错），如果程序调试中有什么错误，记录并分析原因，必须另寻时间调试成功。

实验报告:（及时撰写实验报告）

实验测试结果：

代码实现：（C/C++）【含注释】

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

传送门：