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

线性表的应用——实现两多项式的相加

课前准备：
实验学时：2
- 实验目的：
- 实验内容：
- 实验结果：
- 实验报告:（及时撰写实验报告）
- - 实验测试结果：
  - 代码实现：（C/C++）【含注释】

课前准备：

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

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

人物简介：曹操（155年-220年正月庚子），字孟德，一名吉利，小字阿瞒，沛国谯（今安徽亳州）人，是东汉末年杰出的政治家、军事家、文学家、书法家。‌ 他也是曹魏政权的奠基者，其子曹丕称帝后，追尊他为武皇帝，庙号太祖‌。
在这里插入图片描述
注释：
1 龟虽寿：曹操所作乐府组《步出夏门行》中的第四章。
2 神龟：传说中的通灵之龟，能活几千岁。寿，长寿。
3 竟：终结，这里指死亡。
4 腾蛇：传说中龙的一种，能乘云雾升天。
5 骥：良马，千里马。伏：趴，卧。枥：马槽。
6 烈士：操有远大抱负的男子。这里专指为革命事业献身的人。暮年：晚年。

译文：

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

神龟：传说可以活几千岁…
在这里插入图片描述

实验学时：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;elsereturn 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赋NULLrear->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;
}