PTA|一元多项式的乘法与加法运算数据结构|链表

文章图片

个人题解：
#include using namespace std; struct Pair { int x; int y; Pair() {} Pair(int x, int y) :x(x), y(y) {} }; struct Node { int x; //系数 int y; //指数 Node* next; Node() {} Node(int& a, int& b) { x = a; y = b; next = NULL; } }; class List { public: Node* headNode; List() { headNode = nullptr; } void push_back(int a, int b) { Node* newNode = new Node(a, b); if (headNode == nullptr) { headNode = newNode; return; //考虑链表无元素的情况 } Node* pMove = headNode; while (pMove->next) { pMove = pMove->next; } pMove->next = newNode; } void printList() { if (headNode == nullptr) { cout << 0 << " " << 0; return; } Node* pmove = headNode; while (pmove->next) { cout << pmove->x << " " << pmove->y << " "; pmove = pmove->next; } cout << pmove->x << " " << pmove->y; //防止多打印空格 } List multiply(List& list, int i, int j) { List newlist; int k = 0; int total = i * j; Pair* pair = new Pair[total]; //1.先将所有乘积和求出来 for (Node* p1 = headNode; p1 != nullptr; p1 = p1->next) { for (Node* p2 = list.headNode; p2 != nullptr; p2 = p2->next) { pair[k++] = Pair(p1->x * p2->x, p1->y + p2->y); } } //2.排序 //遍历出每次剩余数组中最小的元素,进行插入 for (int p = 0; p < total - 1; p++)//->每次挑选total-1次即可 { int max_index = p; for (int z = p; z < total; z++) { if (pair[z].y > pair[max_index].y) { max_index = z; } } if (max_index != p) { Pair temp = pair[p]; pair[p] = pair[max_index]; pair[max_index] = temp; } } //3.放入链表 Node* pmove = newlist.headNode; for (int q = 0; q < total; q++) { if (newlist.headNode) { if (pmove->y == pair[q].y)//有bug多加了！！！ { //newlist.push_back(pair[q].x + pmove->x, pair[q].y); pmove->x = pair[q].x + pmove->x; //注意:这边x可能抵消掉了，所以要进行二次判断 if (!pmove->x) { Node* pt = newlist.headNode; Node* pbeh = newlist.headNode; while (pt != pmove) { pbeh = pt; pt = pt->next; } if (pt != newlist.headNode) { pbeh->next = pt->next; delete pt; pt = nullptr; } else { headNode = pt->next; delete pt; pt = nullptr; pbeh = nullptr; } pmove = pbeh; //pmove回退一个 } continue; } else if (pmove->y > pair[q].y) { newlist.push_back(pair[q].x, pair[q].y); } } else { newlist.push_back(pair[q].x, pair[q].y); pmove = newlist.headNode; continue; } pmove = pmove->next; } return newlist; } List add(List& list) { Node* p1 = headNode, * p2 = list.headNode; List newlist; while (p1 && p2) { if (p1->y > p2->y) { newlist.push_back(p1->x, p1->y); p1 = p1->next; } else if (p1->y < p2->y) { newlist.push_back(p2->x, p2->y); p2 = p2->next; } else//equal { if (p1->x + p2->x != 0) { //为0，不添加！！！！ newlist.push_back(p1->x + p2->x, p2->y); //要注意判断系数不为0 } p1 = p1->next; p2 = p2->next; } } while (p1) { newlist.push_back(p1->x, p1->y); p1 = p1->next; } while (p2) { newlist.push_back(p2->x, p2->y); p2 = p2->next; } return newlist; } }; int main() { int i, j; cin >> i; List y1, y2, y3, y4; //y3是乘积结果,y4是相加结果 for (int k = i; k > 0; k--) { int x, y; cin >> x >> y; y1.push_back(x, y); } cin >> j; for (int k = j; k > 0; k--) { int x, y; cin >> x >> y; y2.push_back(x, y); } y3 = y1.multiply(y2, i, j); y4 = y1.add(y2); y3.printList(); cout << endl; y4.printList(); cout << endl; return 0; }

官方题解与思路：
文章图片

其实可以根据每行第一个读入的数据，然后malloc用数组做是最方便的。

#include using namespace std; typedef struct PolyNode *Polynomial; //结点结构 struct PolyNode { int coef; //系数 int expon; //指数 Polynomial next; }; void Attach(int c, int e, Polynomial *pRear)//在建立链表时，需要不断修改尾指针的值，所以传递指向尾指针的指针，以便修改尾指针的值 { Polynomial p; p = (Polynomial)malloc(sizeof(struct PolyNode)); //给新结点赋值 p->coef = c; p->expon = e; p->next = nullptr; (*pRear)->next = p; (*pRear) = p; } //读入多项式 Polynomial ReadPoly() { Polynomial rear,p,t; p = (Polynomial)malloc(sizeof(struct PolyNode)); //链表的空头结点 p->next = nullptr; rear = p; int termNumber; int c, e; cout << "输入多项式的项数："; cin >> termNumber; cout << "输入多项式的系数与指数："; while (termNumber--) { cin >> c >> e; Attach(c,e,&rear); } t = p; p = p->next; free(t); //删除临时生成的空头结点 return p; } //多项式相乘 Polynomial Mult(Polynomial p1, Polynomial p2) { Polynomial t1, t2, p,rear,t; int c, e; if (!p1 || !p2) { return nullptr; } t1 = p1; t2 = p2; p = (Polynomial)malloc(sizeof(struct PolyNode)); p->next = nullptr; rear = p; //先用p1的第一项乘以p2，得到p while (t2) { Attach(t1->coef*t2->coef, t1->expon + t2->expon, &rear); t2 = t2->next; } t1 = t1->next; while (t1) { t2 = p2; rear = p; //让rear指向空的头结点 while (t2) { c = t1->coef*t2->coef; e = t1->expon + t2->expon; while (rear->next&&rear->next->expon > e) { rear = rear->next; } if (rear->next&&rear->next->expon == e) { if (rear->next->coef + c) rear->next->coef += c; //如果系数相加不为0，则赋值系数的和 //如果系数相加为0，则删除该结点 else { t = rear->next; rear->next = t->next; free(t); } } //插入新的结点 else { t = (Polynomial)malloc(sizeof(struct PolyNode)); t->coef = c; t->expon = e; t->next = rear->next; rear->next = t; rear = rear->next; } t2 = t2->next; } t1 = t1->next; } t2 = p; p = p->next; free(t2); return p; } //多项式相加 Polynomial Add(Polynomial p1, Polynomial p2) { Polynomial front, rear, temp,t1,t2; t1 = p1; t2 = p2; //用t1,t2代替p1,p2,防止修改p1,p2的原有值 rear = (Polynomial)malloc(sizeof(struct PolyNode)); //尾指针 rear->next = nullptr; front = rear; //空的头结点 while (t1&&t2) { if (t1->expon == t2->expon) { int sum = t1->coef + t2->coef; if (sum) { Attach(sum, t1->expon, &rear); } t1 = t1->next; t2 = t2->next; } else if (t1->expon > t2->expon) { Attach(t1->coef, t1->expon, &rear); t1 = t1->next; } else { Attach(t2->coef, t2->expon, &rear); t2 = t2->next; } } while (t1) { Attach(t1->coef, t1->expon, &rear); t1 = t1->next; } while (t2) { Attach(t2->coef, t2->expon, &rear); t2 = t2->next; } temp = front; front = front->next; free(temp); return front; } //打印多项式 void PrintPoly(Polynomial p) { int flag = 0; //辅助调整格式输出 if (!p) { cout << 0 << " " << 0 << endl; return; } while (p) { if (!flag) flag = 1; else cout << ""; cout << p->coef << ' ' << p->expon; p = p->next; } cout << endl; } int main() { Polynomial p1,p2,ps,pp; p1 = ReadPoly(); p2 = ReadPoly(); ps = Add(p1, p2); pp = Mult(p1, p2); PrintPoly(p1); PrintPoly(p2); PrintPoly(ps); PrintPoly(pp); return 0; }

折磨良久的bug

①一个逗号后面不能让后面的变量也成为指针

文章图片

老问题了，一个逗号后面不能让后面的变量也成为指针，改动后

文章图片

②临时变量就不要返回引用了！！
文章图片

③输入细节：每次输入一组，所以不要乘2
文章图片

④一开始pmove赋值为NULL，且并不会随着headNode插入节点之后，而改变pmove的值！！！！！！—>导致访问越界问题。

文章图片

⑤细心：
文章图片

⑥多项式在合并之后，要记得判断，系数是否为0，合并系数为0若要删节点，记得回退。
文章图片

文章图片