- 1设置overflow:hidden； text-overflow: ellipsis； white-space:nowrap；单行文本呢溢出显示省略号失效
- 2OpenCV 3D显示Viz模块
- 3Eclipse中安装Jetty服务器
- 4C语言和数据结构的书单-再次推荐
- 5区块链大解码：深入了解Web3的核心技术
- 6国产API工具爆火，为什么大家都开始用Eolink了？_idea怎么安装eolink
- 7pycharm 中的一个非常好使用的智能提示tabnine(大大提高代码的书写效率)_tabnine for pycharm
- 8八年安卓大佬熬夜亲编《Android 面试题大全（中高级）》，不看必后悔系列！_资深android面试题
- 9Unity3D教程：实现房产项目中的材质动态切换_unity墙壁材质
- 10unity 特效shader下载_Unity3D后期Shader特效-马赛克1-基础（UV马赛克化）
多项式加减（数据结构乱杀+完整实验报告）_用链表实现多项式相加实验可能出现的问题及解决方案
赞
踩
一.实验目的：
理解线性表的基本逻辑结构，完成链表及循环链表的实现
通过实验进一步理解线性表的逻辑结构和存储结构，提高使用理论知识指导解决实际问题的能力，熟练掌握链表的实际应用。
二.实验内容：
题目：一元多项式运算
问题描述：
设计算法实现一元多项式的简单运算。
基本要求：
（1） 输入并建立多项式;
（2） 输出多项式;
（3） 多项式加法
（4） 多项式减法。
测试数据：
（1）(2x+5x8－3.1x11)+(7－5x8+11x9)=(－3.1x11+11x9+2x+7)
（2）(6x－3－x+4.4x2－1.2x9)－(―6x―3+5.4x2－x2+7.8x15) =(―7.8x15―
1.2x9+12x―3―x)
（3）(1+x+x2+x3+x4+x5)+(―x3―x4)=(1+x+x2+x5)
（4）(x+x3)+(―x―x3)=0
（5）(x+x100)+(x100+x200)=(x+2x100+x200)
（6）(x+x2+x3)+0=x+x2+x3
三. 实验方案
（一）算法设计思路：
总体思路：建立两个带头结点的单链表储存多项式，每个结点分别有一个系数、指数、指针。用户输入两个多项式的每一项系数及其对应指数，储存并将其按指数升序排序，并合并指数相同的项。若为加法，则直接将两多项式相加，若为减法，则将两多项式系数相减。输出结果多项式。
关键部分算法思路：
排序函数sort：（根据数据从小到大排列链表结点）
每一个元素与后一个元素比较，若这个元素大于后一个元素，则交换这两个元素的结点位置，加一个tail指向第一个结点的前一个结点，q指向第一个结点，p指向第二个结点。每次交换完p与q后,tail指向下一个结点,并根据tail更新p与q。这样借用tail这个结点，就可以达到跟数组的冒泡排序一样的操作。
合并函数func：（合并相邻结点）
经过sort函数，若有幂指数相同的结点必然会成为相邻结点，把他们的系数相加，然后保存至第一个幂指数相同的结点上，然后free掉后一个结点，加个continue这个循环跳过L=L->next,接着比较这个结点与下一个结点是否幂指数相同(一次只能合并两个结点，不确定是否有多个结点幂相同)。遍历完毕即结束此函数。
（二）使用模块及变量的说明（例如结构体的定义、含义）
1、typedef struct node ：定义多项式结点
2、LinkList Creat_List()：创建带头节点的单链表储存多项式
3、int length1(LinkList L)：有头节点长度
int length2(LinkList L)：无头节点长度
4、void output1(LinkList L)：无头结点输出
void output(LinkList L)：有头节点输出
5、void func(LinkList L)：删除合并相邻结点指数相同的结点
6、void sort(LinkList L)：从小到大排序结点
7、LinkList add(LinkList L1, LinkList L2)：两个多项式相加
8、LinkList sub(LinkList L1, LinkList L2):两个多项式相减
四. 实验步骤或程序（经调试后正确的源程序）
- #include<iostream>
-
- #include<string>
-
- using namespace std;
-
- typedef struct node
-
- {
-
- double mi;
-
- double xishu;
-
- struct node* next;
-
-
-
- }LNode,*LinkList;
-
- LinkList Creat_List()
-
- {
-
- LinkList L = NULL;//有头节点
-
- LNode* s, * r = NULL;
-
- double x;
-
- double y;
-
- char c=NULL;
-
-
-
- cout << "输入系数和幂指数:";
-
- cout << endl;
-
- cin >> x>>y;
-
-
-
- s = (LNode*)malloc(sizeof(LNode));
-
-
-
- if (s == NULL) {
-
- cout << "调用失败";
-
- }
-
- else
-
- L = s;
-
- r = s;
-
-
-
- while (1)
-
- {
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL) {
-
- cout << "调用失败";
-
- }
-
- else
-
- {
-
- s->xishu = x;
-
- s->mi = y;
-
- r->next = s;
-
- }
-
- r = s;
-
-
-
-
-
- cin >> x;
-
- cin >> y;
-
- if (x == 0 && y == 0)
-
- {
-
- break;
-
- }
-
-
-
- }
-
- r->next = NULL;
-
- return L;
-
-
-
- }
-
-
-
- bool Empty_List()
-
- {
-
- return false;
-
- }
-
-
-
- LinkList add(LinkList L1, LinkList L2)
-
- {
-
- LinkList L3=NULL;//无头节点
-
- LNode* s, * r = NULL;
-
- while (L1->next&&L2->next)
-
- {
-
-
-
- if (L1->next->mi == L2->next->mi)
-
- {
-
- L1 = L1->next;
-
- L2 = L2->next;
-
-
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL)
-
- cout << "调用失败";
-
- else
-
- {
-
- s->xishu = L1->xishu + L2->xishu;
-
- s->mi = L1->mi;
-
- }
-
- if (L3 == NULL)
-
- L3 = s;
-
- else
-
- r->next = s;
-
- r = s;
-
-
-
- }
-
- else if(L1->next->mi < L2->next->mi)
-
- {
-
- L1 = L1->next;
-
-
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL)
-
- cout << "调用失败";
-
- else
-
- {
-
- s->xishu = L1->xishu;
-
- s->mi = L1->mi;
-
- }
-
- if (L3 == NULL)
-
- L3 = s;
-
- else
-
- r->next = s;
-
- r = s;
-
-
-
- }
-
- else
-
- {
-
- L2 = L2->next;
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL)
-
- cout << "调用失败";
-
- else
-
- {
-
- s->xishu = L2->xishu;
-
- s->mi = L2->mi;
-
- }
-
- if (L3 == NULL)
-
- L3 = s;
-
- else
-
- r->next = s;
-
- r = s;
-
-
-
- }
-
-
-
-
-
- }
-
- while (L1->next)
-
- {
-
- L1 = L1->next;
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL)
-
- cout << "调用失败";
-
- else
-
- {
-
- s->xishu = L1->xishu;
-
- s->mi = L1->mi;
-
- }
-
- if (L3 == NULL)
-
- L3 = s;
-
- else
-
- r->next = s;
-
- r = s;
-
-
-
-
-
- }
-
- while (L2->next)
-
- {
-
- L2 = L2->next;
-
-
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL)
-
- cout << "调用失败";
-
- else
-
- {
-
- s->xishu = L2->xishu;
-
- s->mi = L2->mi;
-
- }
-
- if (L3 == NULL)
-
- L3 = s;
-
- else
-
- r->next = s;
-
- r = s;
-
-
-
- }
-
-
-
- r->next = NULL;
-
- return L3;
-
- }
-
- LinkList sub(LinkList L1, LinkList L2)
-
- {
-
- LinkList L3 = NULL;
-
- LNode* s, * r = NULL;
-
- while (L1->next && L2->next)
-
- {
-
-
-
- if (L1->next->mi == L2->next->mi)
-
- {
-
- L1 = L1->next;
-
- L2 = L2->next;
-
-
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL)
-
- cout << "调用失败";
-
- else
-
- {
-
- s->xishu = L1->xishu - L2->xishu;
-
- s->mi = L1->mi;
-
- }
-
- if (L3 == NULL)
-
- L3 = s;
-
- else
-
- r->next = s;
-
- r = s;
-
-
-
- }
-
- else if (L1->next->mi < L2->next->mi)
-
- {
-
- L1 = L1->next;
-
-
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL)
-
- cout << "调用失败";
-
- else
-
- {
-
- s->xishu = L1->xishu;
-
- s->mi = L1->mi;
-
- }
-
- if (L3 == NULL)
-
- L3 = s;
-
- else
-
- r->next = s;
-
- r = s;
-
-
-
- }
-
- else
-
- {
-
- L2 = L2->next;
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL)
-
- cout << "调用失败";
-
- else
-
- {
-
- s->xishu = -L2->xishu;
-
- s->mi = L2->mi;
-
- }
-
- if (L3 == NULL)
-
- L3 = s;
-
- else
-
- r->next = s;
-
- r = s;
-
-
-
- }
-
-
-
-
-
- }
-
- while (L1->next)
-
- {
-
- L1 = L1->next;
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL)
-
- cout << "调用失败";
-
- else
-
- {
-
- s->xishu = L1->xishu;
-
- s->mi = L1->mi;
-
- }
-
- if (L3 == NULL)
-
- L3 = s;
-
- else
-
- r->next = s;
-
- r = s;
-
-
-
-
-
- }
-
- while (L2->next)
-
- {
-
- L2 = L2->next;
-
-
-
- s = (LNode*)malloc(sizeof(LNode));
-
- if (s == NULL)
-
- cout << "调用失败";
-
- else
-
- {
-
- s->xishu =-(L2->xishu);
-
- s->mi = L2->mi;
-
- }
-
- if (L3 == NULL)
-
- L3 = s;
-
- else
-
- r->next = s;
-
- r = s;
-
-
-
- }
-
-
-
- r->next = NULL;
-
- return L3;
-
- }
-
- void output(LinkList L)//有头节点输出
-
- {
-
- LNode *p=NULL;
-
- while (L->next!=NULL)
-
- {
-
- L = L->next;
-
- if (L->xishu == 0)
-
- {
-
- p = L;
-
- continue;
-
-
-
- }
-
- else
-
- {
-
- cout << L->xishu << "X^" << L->mi << " ";
-
- if (p != NULL)
-
- {
-
- free(p);
-
- }
-
- }
-
- }
-
- }
-
- void output1(LinkList L)//无头结点输出
-
- {
-
- while(L)
-
- {
-
- if (L->xishu == 0)
-
- {
-
- L = L->next;
-
- continue; //continue直接跳出循环无法到下一个位置导致数据输出不全
-
- }
-
-
-
- else
-
- {
-
- cout << L->xishu << "X^" << L->mi << " ";
-
- }
-
- L = L->next;
-
-
-
- }
-
-
-
- }
-
- int length1(LinkList L)//有头节点
-
- {
-
- int n = 0;
-
- while (L->next)
-
- {
-
- n++;
-
- L = L->next;
-
-
-
- }
-
- return n;
-
- }
-
- int length2(LinkList L)
-
- {
-
- int n = 0;
-
- while (L)
-
- {
-
- n++;
-
- L = L->next;
-
- }
-
- return n;
-
- }
-
- void func(LinkList L)//删除相邻结点mi相同的结点
-
- {
-
- LNode* p;
-
-
-
- while (L->next!=NULL)
-
- {
-
- if (L->mi == L->next->mi)
-
- {
-
- p = L->next;
-
- L->xishu = L->xishu + L->next->xishu;
-
- L->next = L->next->next;
-
- free(p);//删掉相连第二个结点
-
- continue;//查看这个结点和第三个结点
-
- }
-
- L = L->next;
-
- }
-
- }
-
- void sort(LinkList L)
-
- {
-
-
-
- int i, count , num;//count记录链表结点的个数，num进行内层循环，
-
- LNode* p, * q, * tail;//创建三个指针，进行冒泡排序
-
- count = length1(L);
-
- for (i = 0; i < count - 1; i++)//外层循环，跟数组冒泡排序一样
-
- {
-
- num = count - i - 1;//内层循环次数
-
- q = L->next;//第一个结点
-
- p = q->next;//第二个结点
-
- tail = L;//第一个节点的前一个结点方便倒换
-
- while (num!=0)
-
- {
-
- if (q->mi > p->mi)
-
- {
-
- q->next = p->next;
-
- p->next = q;
-
- tail->next = p;
-
-
-
- }
-
-
-
- tail = tail->next;//交换后p在前q在后这时用tail就可以重新调回
-
- q = tail->next;
-
- p = q->next;
-
- num--;
-
- }
-
- }
-
-
-
- }
-
-
-
- int main()
-
- {
-
- int n;
-
- LinkList L1 = NULL, L2 = NULL, L3 = NULL, L4 = NULL;
-
- cout << "请输入链表1(输入0 0结束输入)" << endl;
-
- L1 = Creat_List();
-
- sort(L1);//先排序
-
- cout << endl;
-
- cout << "链表1：";
-
- output(L1);//输出
-
- func(L1);//相邻系数合编
-
- cout << endl;
-
- cout << "请输入链表2(输入0 0结束输入)" << endl;
-
- L2 = Creat_List();
-
- sort(L2);//排序
-
- cout << endl;
-
- cout << "链表2：";
-
- output(L2);
-
- func(L2);//整合相邻系数相同项
-
- cout << endl<<endl;
-
- cout << "***********"<<endl;
-
- cout << "1-多项式加法"<<endl;
-
- cout << "2-多项式减法"<< endl;
-
- cout << "请选择：";
-
- cin >> n;
-
- if (n == 1)
-
- {
-
- L3 = add(L1, L2);
-
- cout << '\n';
-
- func(L3);
-
- cout << endl;
-
- cout << "两多项式相加结果是：";
-
- output1(L3);
-
- cout << endl << endl;
-
- }
-
- else if (n == 2)
-
- {
-
- L4 = sub(L1, L2);
-
- cout << '\n';
-
- func(L4);
-
- cout << endl;
-
- cout << "两多项式相减结果是：";
-
- output1(L4);
-
- cout << endl << endl;
-
- }
-
- else
-
- cout << "功能键错误";
-
- system("pause");
-
- return 0;
-
- }
五．程序运行结果（程序运行结果的一些截图）
六．实验总结（调试过程中遇到哪些问题，怎么解决的）
问题一：在链表排序时用while(p!=null)来控制循环遍历但交换后结点发生混乱p和q在不断交替。
通过查阅资料发现了一种很好的方法，用tail来控制进度tail在第一位（指向头节点），q指向第一个结点，p指向第二个结点，p,q交换并且tail=tail.next，再用tail更新q和p重新指向tail后的第一个结点与第二个结点。
问题二：合并结点时出现如果相邻两个相同指数可以合并，但三个及以上指数相同的的结点就合并出错了，有漏掉的。
仔细调试后发现是每次执行玩之后L=L.next就跳过了合并成功的这个结点与下一个结点的比较，所以我在合并完之后加了一个continue，让他合并后不在执行这个L=L.next，完美解决问题。
问题三：多项式相加时怎样才能挑选正确的结点连接在C后面
刚开始想两条链表一起向后遍历，但是由于还没有排序，无法判断后面与前面的关系，想着人工排序但又显得呆板，不符合时间，就加了sort排序后问题解决。
问题四：在输入数据的时候由于我设置是浮点型数据我用的while循环判定想着输入一个特殊字符后停止输入，但是一输入非浮点型数据就造成非法输入卡住了
我想这设置输入的次数，可是这个对程序员和用户就太繁琐了，所以为此我只能设定极特殊情况，系数和指数都是0后停止输入。
