储备知识：
1,储备知识：比如 L 是一个链表的首地址 如果通过 L = L -> next ; 来访问元素，那么，下一次你还能找到它的L原来的地址吗？就不能了是吧 所以，我们新建一个指针，p = L->next, 通过，p = p->next 来访问L,L的地址也不改变，但却可以通过 p 来访问，虽然简单，但是非常重要！！！！！
2,C++ 的用法， cin 等于 scanf() ; cout 等于 printf()
例如： cin >> a; 等于 scanf("%d",&a);
cout << a; 等于 printf("%d",a);
大家不要纠结这些，挺简单的
废话不多说，先看代码
一步一步来
第一步：链表的定义：
typedef struct{
double a;
int e;
}term; //这个结构体是用来储存结构体的指数和系数
typedef struct LNode { //a代表系数，n代表指数
term data;
struct LNode *next;
}*Link,*LinkList;第二步，定义链表的头节点：
bool InitList(LinkList &l){ //初始化一个链表的头节点,
l = new LNode;
l->next = NULL;
return true;
}定义成功后，返回true ，代表定义成功
第三步，链表的有序创建：
怎样实现有序呢？
这样就可了吧，找到第一个次数大于3 的，把x^3插入其前面
具体实现：
void CreatLinklist (LinkList &l, int len,int number){ //创建链表
InitList(l); //初始化一个链表的头节点
for(int i = 1 ;i <= len; i++){ //依次输入n个非0项
LinkList s = new LNode; //生成新节点s
cout<<"---------------------"<<"\n";
cout<<"请输入第"<<number<<"个链表的第"<<i<<"项的系数和指数"<<"\n";
cout<<"---------------------"<<"\n";
cout<<"请输入："<<"\n";
cin >> s->data.a >> s->data.e; //输入系数和指数
LinkList t = l; //生成两个节点，t代表s节点的前驱
LinkList t1 = l->next; //t1代表 s节点的后继，
// 创建这两个的目的就是把s节点插入t和t1中间
while(t1 && t1->data.e < s->data.e){ //通过比较指数，找到第一个大于输入项指数的项
t = t1;
t1 = t1->next;
}
s->next = t1; //把输入的s节点插入到第一个大于等于s节点指数的前面
t->next = s;
}
cout<<"---------------------"<<"\n";
cout<<"第"<<number<<"个链表创建成功"<<"\n";
}这个实现了多项式的有序创建，这个不难，书上有原型，我稍微动了下（47页）
预警！！！！难点(大家啃下来第四步，这个程序就没问题了)
第四步：找元素，增删改查 的查：
试想，如果我们想合并一个多项式的相同元素，怎么办？
是不是要把相同的元素找出来合并，这个函数就是这个功能
int cmp(term a,term b) // 比较两个元素的指数
{
if (a.e==b.e) return 0;
else return (a.e-b.e)/abs(a.e-b.e);
}
/* 这个函数是看老师的，帮了我大忙，大家好好看看
L是我们的链表，e是我们要查找的元素，s, q ，是两个工具人， 是用来记录结果的
*/
bool LocateElem(LinkList L,term e,Link &s,Link &q)
{
Link p; //定义一个链表类型的指针
s = L; //把第一个工具人s用L这个地址赋值
p = s->next; //把第P用s->next这个地址赋值
//发现了吗？目前，s=L ,p =l->next , 接着看;
while (p && cmp(p->data,e) != 0) //当p指针指向的节点的指数，和我们要找的指数不相等时，循环继续，结束时，要么找到了，要么p指向了链表的尾节点//
{
s=p;
p=p->next;
}
if(!p) { //如果指向了我们的尾节点，证明没有找到
s = q = null;
return 0;
}
else { //反面就是找到啦，这时候用到我们的第二个工具人q, 因为p是我们找到的节点，把p 的值赋值给q 才能传回main（）里面哦
q = p;
return 1;
}
}第五步：删除元素：
删除 L 中的 s 后面的那个节点：
void Delnext(LinkList &L,Link s) //删除某一节点
{
Link q = s->next;
s->next = q->next;
delete q;
}第六步：多项式相加功能：
书上有我的代码的原型，在48页。这个不是大头，大头是相乘。
//多项式的相加
void Addlinklist(LinkList la , LinkList lb , LinkList &lc){
//用p1指向la 的首元节点，p2指向lb的首元节点 ，p3指向lc的头节点，相加后的结果放在lc里面
LinkList p1 = la->next , p2 = lb->next , p3 = lc;
while(p1 && p2){ //当两个表不为空的时候
if(p1->data.e == p2->data.e){
//比较 la 和 lb 里的当前元素 的指数，如果相等，把它们加起来
int sum = p1->data.a + p2->data.a; // sum就是它们的和
if(sum != 0) {
LinkList s = new LNode; // 定义一个临时节点 s
s->data.a = sum;
/* 下面的操作是把s的系数变成sum,然后把s这个临时节点，插入到lc，也就是我们的结果里
*/
s->data.e = p1->data.e;
s->next = p3->next; //插入操作
p3->next = s;
p1 = p1->next; //继续向后加，两个指针向后移
p2 = p2->next;
}
}
/* 如果la 和lb 当前位置元素的指数 la < lb ,那么就让la的指针向后移,顺便把当前元素插入到lc里面
*/
else if(p1->data.e < p2->data.e){
LinkList s = new LNode;
s->data.a = p1->data.a;
s->data.e = p1->data.e;
s->next = p3->next;
p3->next = s;
p1 = p1->next;
}
/*
如果lb < la 就让 lb 的指针，就让lb的指针向后移
*/
else {
LinkList s = new LNode;
s->data.a = p2->data.a;
s->data.e = p2->data.e;
s->next = p3->next;
p3->next = s;
p2 = p2->next;
}
/*
迷了吗？ p3 就是 lc 哦
*/
p3 = p3->next; // 因为插入了元素，所以，lc 也向后移一位
}
p3->next=p1?p1:p2;
/* 当p1 为空的时候，说明循环退出，是因为p1 ,所以p2 还没到末尾哦
三目运算符，再给你们复习下相当于
if(p1){
p3->next = p1;
}
else p3->next = p2;
*/
}第七步：一元多项式的相乘：
怎么实现呢：
假如有两个链表
是不是应该 把表1的 1号元素和表二的所有元素相乘，再加上表1的 2号元素和表二的所有元素相乘，再向后一直加....
,怎么用代码实现呢？？ 双重for循环就ok.
因为两个表创建的时候就是有序的，相乘之后，只要按顺序记录，也就是有序的啦
//多项式的相乘
void MultiPList(LinkList la,LinkList lb, LinkList &lc){
LinkList p1 = la->next, p2 = lb->next, p3 = lc;
int numbera = 0, numbere = 0; //代表两个多项式相乘后的系数和指数
for(int i = 1; i <= n; i++){ //n为第一个链表的元素数目，第一行定义过
int t = p1->data.a,t1 = p1->data.e;
//t 代表p1（la）当前元素的系数,t1 代表指数
p1 = p1->next; //咱们已经知道了，p1 的数据，把它们向后移
for(int j= 1 ; j <= m; j++){ //m 在程序第一行定义过了
numbera = t * (p2->data.a); //相乘之后的系数
numbere = t1 + p2->data.e; //相乘之后的指数
LinkList s = new LNode; //用一个新节点s，把这次相乘的结果记下来
s->data.a = numbera;
s->data.e = numbere;
s->next = p3->next;
p3->next = s; // 把s插入到p3后面
p2 = p2->next;
p3 = p3->next;
}
p2 = lb->next; // 表1 的第一个元素，已经和表二的第一个元素相乘了，接下来是不是 表1的第1个元素该和表二的第二个元素想乘了，所以p2 = lb->next;
}
}第八步，多项式的合并：
试想，如果我们输入两项是 2x 3x 那按照我们的程序，输出仍然是 常数C+ 2x + 3x + 更高次幂
明显不是我的的期望，所以要合并同类项
怎样合并呢
比如一个我们的结果是 1 + x + x + x^2 +x^2
那么就应该找 1 后面还有没有常数，找完一遍后，再去找 x 后面还有没有一次项 ，找到了，就合并
变成了 1 + 2x + x^2 + x^2 ,再去找 x^2 后面有没有2次项，找到了，就合并，如下图
看实现过程：
//多项式的合并
void MulMerge(LinkList &la){
LinkList p1 = la -> next ; // p1 指向 la 的首元节点
while(p1){ //当p1 不为空
term t = p1 -> data; // t 就等于当前元素的数据域
LinkList s,q; // 还记得怎么找元素吗
int N = n*m;
while(N--){ //为什么要加这层循环大家想想
if(LocateElem(p1 , t , s, q)){
//如果找到了t,q返回的就是这个元素的地址，q = s->next;
p1->data.a += q->data.a; // 合并过程啊，删除一个相同次幂项，把系数加到另一个相同项上
Delnext(p1, s);
}
}
p1 = p1->next; //一次次找，把指针一次次向后移
}
}
第九步，打印：(你们可以自己写哦)：
代码
void PrintLinkList(LinkList l){
int cnt=0;
while(l){
if(cnt == 1 && l->data.a){
if(l->data.e == 1){
if(l->data.a == 1){
cout<<"x";
}
else cout<<l->data.a<<"x";
}
else if(l->data.e == 0){
if(l->data.a == 1) cout<<"1";
else cout<<l->data.a;
}
else{
if(l->data.a == 1){
cout<<"x^"<<l->data.e;
}
else cout<<l->data.a<<"x^"<<l->data.e;
}
}
else if(cnt > 1 && l->data.a){
if(l->data.e == 1){
if(l->data.a == 1){
cout<<"+"<<"x";
}
else cout<<"+"<<l->data.a<<"x";
}
else if(l->data.e == 0){
if(l->data.a == 1) cout<<"+"<<"1";
else cout<<"+"<<l->data.a;
}
else{
if(l->data.a == 1) cout<<"+"<<"x^"<<l->data.e;
else cout<<"+"<<l->data.a<<"x^"<<l->data.e;
}
}
l = l->next;
cnt++;
}
cout<<"\n";
}
//多项式的合并看到这，说明你已经可以了，加油
最后一步main()：
int main()
{
int number=1;
LinkList la,lb,lc;
cout<<"---------------------"<<"\n";
cout<<"请输入两个多项式的长度"<<"\n";
cout<<"---------------------"<<"\n";
cin>>n>>m;
CreatLinklist(la, n,number++);//最后一个参数，是多项式的序号
MulMerge(la); //多项式的合并
cout<<"创建的多项式为：";
PrintLinkList(la); //打印
CreatLinklist(lb, m,number);
MulMerge(la);
cout<<"创建的多项式为：";
PrintLinkList(lb);
cout<<"---------------------"<<"\n";
InitList(lc); // 这个必须写哦
// 加法
// Addlinklist(la, lb, lc);
// MulMerge(lc);
// cout << "最终的多项式为：";
// PrintLinkList(lc);
MultiPList(la, lb, lc); //乘法
MulMerge(lc); //合并
cout<<"最终的多项式为：";
PrintLinkList(lc);
cout<<"---------------------"<<"\n";
}
完整代码：
//
// main.cpp
// 数据结构2
//
// Created by 宋玉良 on 2020/10/19.
//
/* 储备知识：比如 L 是一个链表的首地址 如果通过
L = L -> next ; 来访问元素，那么，下一次你还能找到它的L原来的地址吗
所以，我们新建一个指针，p = L->next, 通过，p = p->next 来访问L,L的地址也不改变，但却可以通过 p 来访问，虽然简单，但是非常重要！！！！！
*/
#include<bits/stdc++.h>
#define null 0
using namespace std;
int n,m; //代表输入的两个链表的长度，定义在外边，这两个变量全局有效（所有函数都可以直接用）
typedef struct{
float a;
int e;
}term; //这个结构体是用来储存结构体的指数和系数
typedef struct LNode { //a代表系数，n代表指数
term data;
struct LNode *next;
}*Link,*LinkList;
bool InitList(LinkList &l){ //初始化一个链表的头节点
l = new LNode;
l->next = NULL;
return true;
}
int cmp(term a,term b) // 比较两个元素的指数
{
if (a.e==b.e) return 0;
else return (a.e-b.e)/abs(a.e-b.e);
}
/* 这个函数是看老师的，帮了我大忙，大家好好看看
L是我们的链表，e是我们要查找的元素，s, q ，是两个工具人， 是用来记录结果的
*/
bool LocateElem(LinkList L,term e,Link &s,Link &q)
{
Link p; //定义一个链表类型的指针
s = L; //把第一个工具人s用L这个地址赋值
p = s->next; //把第P用s->next这个地址赋值
//发现了吗？目前，s=L ,p =l->next , 接着看;
while (p && cmp(p->data,e) != 0) //当p指针指向的节点的指数，和我们要找的指数不相等时，循环，结束时，要么找到了，要么p指向了链表的尾节点//
{
s=p;
p=p->next;
}
if(!p) { //如果指向了我们的尾节点，证明没有找到
s = q = null;
return 0;
}
else { //反面就是找到啦，这时候用到我们的第二个工具人q, 因为p是我们找到的节点，把p 的值赋值给q 才能传回main（）里面哦
q = p;
return 1;
}
}
void Delnext(LinkList &L,Link s) //删除某一节点
{
Link q = s->next;
s->next = q->next;
delete q;
}
void CreatLinklist (LinkList &l, int len,int number){ //创建链表
InitList(l); //初始化一个链表
for(int i = 1 ;i <= len; i++){ //依次输入n个非0项
LinkList s = new LNode; //生成新节点s
cout<<"---------------------"<<"\n";
cout<<"请输入第"<<number<<"个链表的第"<<i<<"项的系数和指数"<<"\n";
cout<<"---------------------"<<"\n";
cout<<"请输入："<<"\n";
cin >> s->data.a >> s->data.e; //输入系数和指数
LinkList t = l; //生成两个节点，t代表s节点的前驱
LinkList t1 = l->next; //t1代表 s节点的后继，
// 创建这两个的目的就是把s节点插入t和t1中间
while(t1 && t1->data.e < s->data.e){ //通过比较指数，找到第一个大于输入项指数的项
t = t1;
t1 = t1->next;
}
s->next = t1; //插入s节点
t->next = s;
}
cout<<"---------------------"<<"\n";
cout<<"第"<<number<<"个链表创建成功"<<"\n";
}
//多项式的相加
void Addlinklist(LinkList la , LinkList lb , LinkList &lc){
//用p1指向la 的首元节点，p2 只想lb的首元节点 ，p3指向lc的头节点，相加后的结果放在lc里面
LinkList p1 = la->next , p2 = lb->next , p3 = lc;
while(p1 && p2){ //当两个表不为空的时候
if(p1->data.e == p2->data.e){
//比较 la 和 lb 里的当前元素 的指数，如果相等，把它们加起来
float sum = p1->data.a + p2->data.a; // sum就是它们的和
if(sum != 0) {
LinkList s = new LNode; // 定义一个临时节点 s
s->data.a = sum;
/* 下面的操作是把s的系数变成sum,然后把s这个临时节点，插入到lc，也就是我们的结果里
*/
s->data.e = p1->data.e;
s->next = p3->next; //插入操作
p3->next = s;
p1 = p1->next; //继续向后加，两个指针向后移
p2 = p2->next;
}
}
/* 如果la 和lb 当前位置元素的指数 la < lb ,那么就让la的指针向后移,顺便把当前元素插入到lc里面
*/
else if(p1->data.e < p2->data.e){
LinkList s = new LNode;
s->data.a = p1->data.a;
s->data.e = p1->data.e;
s->next = p3->next;
p3->next = s;
p1 = p1->next;
}
/*
如果lb < la 就让 lb 的指针，就让lb的指针向后移
*/
else {
LinkList s = new LNode;
s->data.a = p2->data.a;
s->data.e = p2->data.e;
s->next = p3->next;
p3->next = s;
p2 = p2->next;
}
/*
迷了吗？ p3 就是 lc 哦
*/
p3 = p3->next; // 因为插入了元素，所以，lc 也向后移一位
}
p3->next=p1?p1:p2;
/* 当p1 为空的时候，说明循环退出，是因为p1 ,所以p2 还没到末尾哦
三目运算符，再给你们复习下相当于
if(p1){
p3->next = p1;
}
else p3->next = p2;
*/
}
//多项式的相乘
void MultiPList(LinkList la,LinkList lb, LinkList &lc){
LinkList p1 = la->next, p2 = lb->next, p3 = lc;
float numbera = 0 ;int numbere = 0; //代表两个多项式相乘后的系数和指数
for(int i = 1; i <= n; i++){ //n为第一个链表的元素数目，第一行定义过
float t = p1->data.a,t1 = p1->data.e;
//t 代表p1（la）当前元素的系数,t1 代表指数
p1 = p1->next; //咱们已经知道了，p1 的数据，把它们向后移
for(int j= 1 ; j <= m; j++){ //m 在程序第一行定义过了
numbera = t * (p2->data.a);
numbere = t1 + p2->data.e;
LinkList s = new LNode;
s->data.a = numbera;
s->data.e = numbere;
s->next = p3->next;
p3->next = s;
p2 = p2->next;
p3 = p3->next;
}
p2 = lb->next;
}
}
//多项式的输出
void PrintLinkList(LinkList l){
int cnt=0,flag =1;
while(l){
if(cnt == 1){
if(l->data.a == 0) flag = 0;
else{
if(l->data.e == 1){
if(l->data.a == 1){
cout<<"x";
}
else cout<<l->data.a<<"x";
}
else if(l->data.e == 0){
if(l->data.a == 1) cout<<"1";
else cout<<l->data.a;
}
else{
if(l->data.a == 1){
cout<<"x^"<<l->data.e;
}
else cout<<l->data.a<<"x^"<<l->data.e;
}
}
}
else if(cnt > 1 && l->data.a){
if(l->data.e == 1){
if(l->data.a == 1){
if(flag == 1)cout<<"+"<<"x";
else {
cout << "x";
flag = 1;
}
}
else {
if(flag == 1) cout<<"+"<<l->data.a<<"x";
else {
cout<<l->data.a<<"x"; flag = 1;
}
}
}
else if(l->data.e == 0){
if(l->data.a == 1){
if(flag == 1) cout<<"+"<<"1";
else{
cout << "1";flag = 1;
}
}
else{
if(flag ==1 )cout<<"+"<<l->data.a;
else {
cout<<l->data.a;
flag = 1;
}
}
}
else{
if(l->data.a == 1){
if(flag == 1) cout<<"+"<<"x^"<<l->data.e;
else {
cout<<"x^"<<l->data.e; flag = 1;
}
}
else{
if(flag == 1) cout<<"+"<<l->data.a<<"x^"<<l->data.e;
else {
cout<<l->data.a<<"x^"<<l->data.e; flag = 1;
}
}
}
}
l = l->next;
cnt++;
}
cout<<"\n";
}
//多项式的合并
void MulMerge(LinkList &la,int c){
LinkList p1 = la -> next ;
while(p1){
term t = p1 -> data;
LinkList s,q;
int N = n * m;
while(N--){
if(LocateElem(p1 , t , s, q)){
p1->data.a += q->data.a;
Delnext(p1, s);
if(c == 1) n--;
else if(c == 2) m--;
}
}
p1 = p1->next;
}
}
int main()
{
int number=1;
LinkList la,lb,lc;
cout<<"---------------------"<<"\n";
cout<<"请输入两个多项式的长度（两个数之间用空格分开）"<<"\n";
cout<<"---------------------"<<"\n";
cin>>n>>m;
CreatLinklist(la, n,number++);
MulMerge(la,1);
cout<<"创建的多项式为：";
PrintLinkList(la);
CreatLinklist(lb, m,number);
MulMerge(lb,2);
cout<<"创建的多项式为：";
PrintLinkList(lb);
cout<<"---------------------"<<"\n";
InitList(lc);
// Addlinklist(la, lb, lc);
// MulMerge(lc);
// cout << "最终的多项式为：";
// PrintLinkList(lc);
MultiPList(la, lb, lc);
MulMerge(lc,3);
cout<<"最终的多项式为：";
PrintLinkList(lc);
cout<<"---------------------"<<"\n";
}
为什么要修改？？
大家看这个输入样例：
（1 + 4x + 3x^2）* (2x + 3x^2 + 7x^3)
= 2x + 3x^2 +7x^3 + 8x^2 + 12 x^3 + 28x^4 + 6x^3 + 9x^4 +21 x^5
本来合并结果应该是
2x + 11x^2 + 25x^3 + 37x^4 + 21x^5
但是源代码合并结果是：
2x + 11x^2 + 19x^3 + 37x^4 + 6x^3 + 21x^5
为什么呢，因为结果里有三个三次方的项，而我们的源代码，找到一个，就不找了，所以就加个循环
。。。。。。。。。。。。。。。。。。。。
京公网安备 11010502036488号