大家如果發(fā)現(xiàn)代碼有錯(cuò)誤，麻煩評(píng)論告知一下!!!

下面的代碼多項(xiàng)式相乘的算法實(shí)現(xiàn)并不是書上那種，書上那種我實(shí)在是看不懂，所以用了自己的方法寫了相乘的算法，就是模擬手算過(guò)程，一個(gè)一個(gè)相乘。

代碼如下:

#include <iostream> using namespace std;typedef struct {double coef;int expn; }term,ElemType;typedef struct LNode {ElemType data;LNode *next; }*Link,*Position;typedef struct {Link head, tail;int len; }LinkList;typedef LinkList Polynomial;bool makeNode(Link &p, ElemType e) {p = new LNode;if (!p) return false;p->data = e;p->next = nullptr;return true; }void freeNode(Link &p) {delete p;p = nullptr; }bool initList(LinkList &L) {L.head = new LNode;if (!L.head) return false;L.tail = L.head;L.head->next = nullptr;L.len = 0;return true; }bool insFirst(Link h, Link s) {s->next = h->next;h->next = s;return true; }bool delFirst(Link h, Link &q) {q = h->next;h->next = h->next->next;q->next = nullptr;return true; }bool append(LinkList &L, Link s) {L.tail->next = s;while (L.tail->next){L.tail = L.tail->next;L.len++;}return true; }bool remove(LinkList &L, Link &q) {LNode *s = L.head;while (s->next != L.tail){s = s->next;}q = L.tail;L.tail = s;s->next = nullptr;L.len--;return true; }bool insBefore(LinkList &L, Link &p, Link s) {LNode *q = L.head;while (q->next != p){q = q->next;}s->next = p;q->next = s;L.len++;return true; }bool insAfter(LinkList &L, Link &p, Link s) {s->next = p->next;p->next = s;p = s;L.len++;return true; }bool setCurElem(Link &p, ElemType e) {p->data = e;return true; }ElemType getCurElem(Link p) {return p->data; }int polynLength(Polynomial &p) {int j = 0;LNode *s = p.head->next;while (s){j++;s = s->next;}p.len = j;return p.len; }bool listEmpty(LinkList &L) {polynLength(L);if (L.len == 0) return true;else return false; }Position getHead(LinkList L) {return L.head; }Position getLast(LinkList L) {return L.tail; }Position priorPos(LinkList L, Link p) {LNode *s = L.head;while (s->next != p){s = s->next;}if (s == L.head){return nullptr;}return s; }Position nextPos(LinkList L, Link p) {return p->next; }bool locatePos(LinkList L, int i, Link &p) {int j = 1;LNode *s = L.head->next;if (i < 1 || i > L.len) return false;while (s && j < i){s = s->next;j++;}if (!s || j > i){return false;}p = s;return true; }bool locateElem(LinkList L, ElemType e, Position &q,int(*compare)(ElemType, ElemType)) {LNode *s = L.head->next;while (s){if (compare(s->data, e) == 0){q = s;return true;}s = s->next;}s = L.head;while (s->next){if (compare(s->next->data, e) > 0){q = s;return false;}s = s->next;}q = s;return false; }int cmp(term a, term b) {if (a.expn < b.expn) return -1;else if (a.expn == b.expn) return 0;else if (a.expn > b.expn) return 1; }void destroyPolyn(Polynomial &L) {LNode *p = L.head;while (p){LNode *q = p;p = p->next;delete q;}L.tail = L.head = nullptr; }void printPolyn(Polynomial p) {LNode *s = p.head->next;int j = 1;int len = polynLength(p);while (s){if (s->data.expn == 0){cout << s->data.coef;}else{cout << s->data.coef << "x^" << s->data.expn;}if (j < len)cout << " + ";s = s->next;j++;}cout << endl; }void createPolyn(Polynomial &p, int n) {initList(p);LNode *s = nullptr;LNode *h = nullptr;LNode *q = nullptr;h = getHead(p);ElemType e;e.coef = 0.0;e.expn = -1;setCurElem(h, e);for (int i = 0; i < n; i++){cin >> e.coef >> e.expn;if (e.coef == 0.0)continue;if (!locateElem(p, e, q, cmp)){if (makeNode(s, e)){insFirst(q, s);}}}LNode *p1 = p.head;while (p1->next){p1 = p1->next;}p.tail = p1; }void addPolyn(Polynomial &pa, Polynomial &pb) {LNode *ha = getHead(pa);LNode *hb = getHead(pb);LNode *qa = nextPos(pa, ha);LNode *qb = nextPos(pb, hb);while (qa && qb){ElemType a = getCurElem(qa);ElemType b = getCurElem(qb);switch (cmp(a, b)){case -1:ha = qa;qa = nextPos(pa, qa);break;case 0:ElemType sum;sum.coef = a.coef + b.coef;sum.expn = a.expn;if (sum.coef != 0.0){setCurElem(qa, sum);ha = qa;}else{delFirst(ha, qa);freeNode(qa);}delFirst(hb, qb);freeNode(qb);qb = nextPos(pb, hb);qa = nextPos(pa, ha);break;case 1:delFirst(hb, qb);insFirst(ha, qb);qb = nextPos(pb, hb);ha = nextPos(pa, ha);break;}}if (!listEmpty(pb)) append(pa, qb);freeNode(hb); }void subtractPolyn(Polynomial &pa, Polynomial &pb) {LNode *ha = getHead(pa);LNode *hb = getHead(pb);LNode *qa = nextPos(pa, ha);LNode *qb = nextPos(pb, hb);while (qa && qb){ElemType a = getCurElem(qa);ElemType b = getCurElem(qb);switch (cmp(a, b)){case -1:ha = qa;qa = nextPos(pa, qa);break;case 0:ElemType sum;sum.coef = a.coef - b.coef;sum.expn = a.expn;if (sum.coef != 0.0){setCurElem(qa, sum);ha = qa;}else{delFirst(ha, qa);freeNode(qa);}delFirst(hb, qb);freeNode(qb);qb = nextPos(pb, hb);qa = nextPos(pa, ha);break;case 1:delFirst(hb, qb);insFirst(ha, qb);qb = nextPos(pb, hb);ha = nextPos(pa, ha);break;}}if (!listEmpty(pb)) append(pa, qb);freeNode(hb); }void multiplyPolyn(Polynomial &pa, Polynomial &pb) {Polynomial pc;initList(pc);LNode *ha = getHead(pa);LNode *hb = getHead(pb);LNode *qa = nextPos(pa, ha);LNode *qb = nextPos(pb, hb);LNode *s = nullptr;LNode *q = nullptr;ElemType e;while (qa){while (qb){e.coef = qa->data.coef*qb->data.coef;if (qa->data.expn!= 0 && qb->data.expn!=0)e.expn = qa->data.expn+qb->data.expn;if (qa->data.expn == 0){e.expn = qb->data.expn;}else if (qb->data.expn == 0){e.expn = qa->data.expn;}if (!locateElem(pc, e, q, cmp)){if (makeNode(s, e)){insFirst(q, s);}}else{q->data.coef += e.coef;}qb = nextPos(pb, qb);}qb = nextPos(pb, hb);qa = nextPos(pa, qa);}destroyPolyn(pa);destroyPolyn(pb);pa = pc; }int main() {Polynomial L,L1;int n;cin >> n;createPolyn(L, n);printPolyn(L);cin >> n;createPolyn(L1, n);printPolyn(L1);cout << polynLength(L) << endl;cout << polynLength(L1) << endl;multiplyPolyn(L, L1);printPolyn(L);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[数据结构-严蔚敏版]P42多项式Polynomial的实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。