題目要求

從字符文件輸入兩個(gè)多項(xiàng)式的非零系數(shù)及對(duì)應(yīng)的指數(shù)，建立多項(xiàng)式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，計(jì)算這兩個(gè)多項(xiàng)式的乘積，輸出乘積多項(xiàng)式的全部非零系數(shù)及對(duì)應(yīng)的指數(shù)到另一字符文件中。

算法原理

兩個(gè)多項(xiàng)式的乘法，可以借助兩個(gè)多項(xiàng)式的加法的算法來實(shí)現(xiàn)。

設(shè)：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

則：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

例如：? ??,? ? ??,

則：

? ? ? ? ? ? ? ? ? ? ? ? ? ?

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

采用帶附加頭結(jié)點(diǎn)單向鏈表；每個(gè)結(jié)點(diǎn)包括雙精度類型的系數(shù)域、整型類型的指數(shù)域和一個(gè)指針域。

typedef struct polynode {double c; //系數(shù)int e; //指數(shù)struct polynode *next; //指針域，要求結(jié)點(diǎn)按指數(shù)e升序連接 }PNode,*Polyn; //PNode為結(jié)點(diǎn)類型，Polyn為結(jié)點(diǎn)指針類型

程序代碼

#include <iostream> #include <fstream> #include <string.h> using namespace std; //定義結(jié)點(diǎn)及結(jié)點(diǎn)指針數(shù)據(jù)類型 typedef struct polynode {double c; //系數(shù)int e; //指數(shù)struct polynode *next; //要求結(jié)點(diǎn)按指數(shù)e升序連接 }PNode,*Polyn; //PNode為結(jié)點(diǎn)類型，Polyn為結(jié)點(diǎn)指針類型 Polyn h1, h2; //兩個(gè)多項(xiàng)式P(x),Q(x)的頭結(jié)點(diǎn) double a[20]; //數(shù)組a保存系數(shù) int b[20]; //數(shù)組b保存指數(shù) void Read(char *s) //讀取數(shù)據(jù)，s代入不同的文件名 {double c;int i = 0, e;ifstream infile(s);if (!infile) //打開文件失敗輸出提示信息{cout << "file open error!" << endl;exit(0);}while (1) //打開成功，將系數(shù)和指數(shù)保存在兩個(gè)數(shù)組中{infile >> c >> e;if (infile.eof())break;a[i] = c;b[i] = e;i++;}infile.close(); } void Write(Polyn h) //輸出函數(shù)，將結(jié)果輸出到文件中，h為鏈表頭結(jié)點(diǎn) {ofstream outfile("multiply.txt"); //輸出文件名為multiply.txtPolyn p = h->next; //去掉附加頭結(jié)點(diǎn)if (!outfile) //打開文件失敗輸出提示信息{cout << "file open error!" << endl;exit(0);}if (!p) //第一個(gè)結(jié)點(diǎn)為空，表示運(yùn)算結(jié)果為0outfile << "0" << endl;while (p) //p不為空，依次輸出系數(shù)和指數(shù){outfile << p->c << " " << p->e << endl;p = p->next;}outfile.close(); }void clearArray() { //清空數(shù)組memset(a, 0, sizeof(a));memset(b, 0, sizeof(b)); }Polyn Create(char *s) //先入先出建立鏈表，s代入不同的文件名 {int i = 0; //i用于記錄數(shù)組下標(biāo)Polyn h, last, p;h = new PNode;h->next = NULL; //h為附加頭結(jié)點(diǎn)last = h;clearArray();Read(s); //從文件中讀取系數(shù)和指數(shù)while (a[i]!=0){p = new PNode;p->c = a[i];p->e = b[i];p->next = NULL; //建新結(jié)點(diǎn)last->next = p;last = p; //新結(jié)點(diǎn)插入到鏈表尾i++;}return h; }void PrintPoly(Polyn h) //按多項(xiàng)式的形式將結(jié)果打印到控制臺(tái)界面中 {Polyn p = h->next;if (!p) //所得結(jié)果為空，則輸出0cout << "0" << endl;while (p){if (p->next) //p不是尾結(jié)點(diǎn){if (p->next->c < 0) //p的后繼結(jié)點(diǎn)的系數(shù)小于0，不輸出符號(hào) + {if (p->c == -1) //p的后繼結(jié)點(diǎn)的系數(shù)等于-1{cout << "-x^" << p->e;p = p->next;}else if (p->c == 1) //p的后繼結(jié)點(diǎn)的系數(shù)等于1{cout << "x^" << p->e;p = p->next;}else{cout << p->c << "x^" << p->e;p = p->next;}}else if (p->next->c > 0) //p的后繼結(jié)點(diǎn)的系數(shù)大于0，需輸出符號(hào)+{if (p->c == 1) //p的后繼結(jié)點(diǎn)的系數(shù)等于1{cout << "x^" << p->e << "+";p = p->next;}else if (p->c == -1) //p的后繼結(jié)點(diǎn)的系數(shù)等于-1{cout << "-x^" << p->e << "+";p = p->next;}else{cout << p->c << "x^" << p->e << "+";p = p->next;}}}else //p是尾結(jié)點(diǎn)，需在結(jié)尾輸出換行{if (p->c < 0) //p的指數(shù)小于0{if (p->c == -1){cout << "-x^" << p->e << endl;p = p->next;}else{cout << p->c << "x^" << p->e << endl;p = p->next;}}else if (p->c > 0) //p的指數(shù)大于0{if (p->c == 1){cout << "x^" << p->e << endl;p = p->next;}else{cout << p->c << "x^" << p->e << endl;p = p->next;} } }} } void CreateNode(Polyn &p) //創(chuàng)建新結(jié)點(diǎn) {p = new PNode; } void DeleteNode(Polyn &p) //刪除結(jié)點(diǎn) {delete p; } Polyn add(Polyn h1, Polyn h2) //實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相加，返回和式頭指針 {Polyn p1, p2, p3, h, p; //h為和式R(x)的附加頭結(jié)點(diǎn)指針p1 = h1->next;p2 = h2->next;CreateNode(h);p3 = h;while (p1&&p2){if (p1->e < p2->e) //p1的指數(shù)大于p2,先保存p1結(jié)點(diǎn){p = p1;p1 = p1->next;}else if (p2->e < p1->e) //p2的指數(shù)大于p1,先保存p2結(jié)點(diǎn){p = p2;p2 = p2->next;}else //p1與p2指數(shù)相等時(shí){p1->c += p2->c; //系數(shù)相加，結(jié)果保存在p1中if (p1->c == 0) //系數(shù)之和為0,則刪除該結(jié)點(diǎn){p = p1;p1 = p1->next;DeleteNode(p); //刪除結(jié)點(diǎn)p = p2;p2 = p2->next;DeleteNode(p);continue;}p = p2; //系數(shù)之和不為0時(shí)，先刪除p2結(jié)點(diǎn)p2 = p2->next;DeleteNode(p);p = p1; //將p1連接到p中p1 = p1->next;}p3->next = p; //插入p結(jié)點(diǎn)至和式末尾p3 = p;}if (p1) //p1沒有結(jié)束，將p1后面所有的結(jié)點(diǎn)連接到和式p3->next = p1;else if (p2) //p2沒有結(jié)束，將p2后面所有的結(jié)點(diǎn)連接到和式p3->next = p2;elsep3->next = NULL;h1->next = h2->next = NULL; //清空h1和h2鏈表return h; } Polyn mul(Polyn hp, Polyn hq) //實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相乘 {Polyn hr, ht, q, p, pt;CreateNode(hr);hr->next = NULL; //R(x) = 0CreateNode(ht);ht->next = NULL; //T(x) = 0q = hq->next;while (q){pt = ht;p = hp->next;while (p){CreateNode(pt->next); //創(chuàng)建新的尾結(jié)點(diǎn)pt = pt->next;pt->c = p->c*q->c; //系數(shù)相乘pt->e = p->e + q->e; //指數(shù)相加p = p->next;}pt->next = NULL;q = q->next;p = add(hr, ht); //實(shí)現(xiàn)R(x) = R(x) + T(x)DeleteNode(hr);hr = p;}DeleteNode(ht);return hr; } int main() {Polyn h1, h2, h3; //定義單向鏈表附加頭結(jié)點(diǎn)指針cout << "讀取文件，直到讀入0時(shí)停止，建立單向鏈表" << endl;h1 = Create("polynode1.txt");h2 = Create("polynode2.txt");cout << "P(x) = ";PrintPoly(h1);cout << "Q(x) = ";PrintPoly(h2);h3 = mul(h1, h2);cout << "R(x) = P(x) * Q(x) = ";PrintPoly(h3);Write(h3); //寫入文件return 0; }

示例

?(1)? P(x)? ?1 ??2 ???2 ??3 ????0

? ? ? ?Q(x)??1 ?-2 ???2 ?-3 ????0

輸出結(jié)果為：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

（2）P(x)? ? ?1 ?1? ? ? 2 ?2 ?????3 ?3 ?????0

? ? ? ? ?Q(x)? ? -1 ?1 ???-2 ?2 ????-3 ?3 ?????0

輸出結(jié)果為：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

總結(jié)

以上是生活随笔為你收集整理的【数据结构】——多项式乘法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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