一元多項式相加問題 一、 問題描述 通過鍵盤輸入兩個形如 P 0 +P 1 X 1 +P 2 X 2 +…+P n X 的多項式，經過程序運后在屏幕上輸出它們的相加和。

　二、數據結構設計 一個一元多項式的每一個子項都由“系數-指數”兩部分組成，因此可將其抽象為包含系數 coef、指數 exp、指針域 next 構成的鏈式線性表。將兩個多項式分別存放在兩個線性表中，然后經過相加后將所得多項式存放在一個新的線性表中，但是不用再開辟新的存儲空間，只依靠結點的移動來構成新的線性表，期間可以將某些不需要的空間回收。基于這樣的分析，可以采用不帶頭結點的單鏈表來表示一個一元多項式。具體數據類型定義為：

　struct node {

　float coef;

　//系數域

　int exp;

　 //指數域

　struct node *next; }; 三、 功能函數設計 1、 輸入多項式的系數和指數初始化多項式的功能模塊 具體函數為 node *in_fun() 此函數的處理較為全面，要求用戶按照指數遞增的順序和一定的輸入格式輸入各個系數不為 0 的子項，輸入一個子項建立一個相關結點，當遇到輸入結束標志時停止輸入。關鍵步驟具體如下：

　⑴控制用戶按照指數遞增的順序輸入

　r=a; while(r!=q->next)

　 {

　if(y<=r->exp)

　{

　 cout<<"請按照指數遞增順序輸入,請重新輸入";

　 cin>>x>>y;

　 break;

　}

　r=r->next;

　 } 從頭開始遍歷，若遇到目前輸入的指數不是最大時，就跳出循環，讓用戶重新輸入。

　⑵當輸入的系數為零時，不為其分配存儲空間存儲 while(x==0) { cin>>x>>y; continue;} 即若系數為 0，不再進行動態分配并新建結點，而是重新提取用戶輸入的下一個子項的系數和指數，利用 continue 進入下一次循環。

　⑶初始化完成后將最后一個結點的指針域置為空，并返回該新建鏈表的首地址。

　if(q!=NULL)

　q->next=NULL;

　return a; ⑷動態分配空間新建結點存儲系數和指數的代碼如下：

　p=new node;

　 p->coef=x;

　p->exp=y;

　 if(a==NULL) a=p;

　 else q->next=p;

　 q=p; 2、 多項式顯示功能函數 由于系數有正有負，故采取如下處理：

　對于正數，輸出時在前面加“+”，頭指針除外；對于負數，直接將系數輸出即可，即：

　p=a;

　while(p)

　{

　 if(p==a)

　cout<<p->coef<<"*x^"<<p->exp;

　 else if(p->coef<0)

　cout<<p->coef<<"*x^"<<p->exp;

　 else if(p->coef>0)

　cout<<"+"<<p->coef<<"*x^"<<p->exp;

　 p=p->next;

　} 輸出的多項式的形式形如：P 1 X^1+P 2 X^2+…+P n X^n 3、 多項式相加的功能函數 函數為：node *plus_fun(node *a,node *b) 此函數根據在 1 中初始化的兩個多項式進行相加運算，并存放在以 c 為頭指針的一個新鏈表中。

　設指針 p,q,r 分別指向描述多項式的鏈表 a,b,c 的頭部，其中將 a 也賦給 c。p,q兩個指針同時移動，并根據 p,q 兩結點對應的指數的大小采取不同的操作。

　⑴當(p->exp)<(q->exp)時，操作如下：

　w=p;

　p=p->next;

　r->next=w;

　r=w; 即定義一個結點 w，將結點 p 賦給它，然后將 p 結點后移，指向 a 中下一個待處理結點，然后將 w 移動到新生成鏈表 c 的尾結點的后面，最后將 w 賦給r,使得 r 仍指向鏈表 c 的尾結點。

　⑵當 p->exp>q->exp 時，采取如下操作：

　 w=q;

　q=q->next;

　r->next=w;

　r=w; 即此時將 q 賦給 w,然后使 q 結點指向鏈表 b 中下一個待處理結點，然后將 w移動到新生成鏈表 c 的尾結點的后面，最后將 w 賦給 r,使得 r 仍指向鏈表 c 的尾結點。

　⑶當 p->exp==q->exp 時，定義一個 float 類型的變量 x，當 x 不為 0 時，采取如下操作：

　p->coef=x;

　 w=p;

　 p=p->next;

　 r->next=w;

　 r=w;

　 w=q;

　q=q->next;

　 delete w;

　即將 x 的值賦給 p 的系數域，之后將結點 p 賦給 w，然后將 p 結點后移，指向 a 中下一個待處理結點，然后將 w 移動到新生成鏈表 c 的尾結點的后面，最后將 w 賦給 r,使得 r 仍指向鏈表 c 的尾結點。同時，將 q 的內存空間釋放，并使得 q 指向 b 中下一個待處理結點。

　當 x 為 0 時，采取如下操作：

　w=p;

　 p=p->next;

　 delete w;

　 w=q;

　 q=q->next;

　 delete w; 即將 pq 的空間釋放，并分別使其指向各自鏈表中下一個待處理結點。

　⑷當上面的循環進行完后，至少有一個鏈表已被遍歷完，然后只需將另一個鏈表剩余的所有結點都移動到 c 中即可。

　if(p!=NULL)

　{

　 while(p)

　 {

　w=p;

　p=p->next;

　r->next=w;

　r=w;

　}

　}

　if(q!=NULL)

　{

　 while(q)

　 {

　w=q;

　q=q->next;

　r->next=w;

　r=w;

　 }

　} ⑸最后將 c 中的最后一個結點的指針域置為空,并返回 c 的地址。

　r->next=NULL;

　return c; 4、 主函數功能設計 采用循環的形式可以多次進行兩個多項式的初始化和求和。

　四、 界面設計 提示用戶進行每一步操作以及每一步輸出的內容，界面簡明清晰。

　五、 運行與調試

　 六、 源代碼 #include<iostream.h> struct node {

　float coef;

　//系數域

　int exp;

　 //指數域

　 struct node *next; }; node *in_fun() {

　node *p,*a,*q,*r;

　a=q=NULL;

　float x;

　int y;

　cin>>x>>y;

　while(x!=0||y!=0)

　{

　 while(x==0)

　{

　 cin>>x>>y;

　if(x==0&&y==0)

　break;

　else

　{continue;}

　 }

　 if(x==0&&y==0)

　break;

　 p=new node;

　 p->coef=x;

　 p->exp=y;

　 if(a==NULL) a=p;

　 else q->next=p;

　 q=p;

　 cin>>x>>y;

　 if(x==0&&y==0)

　break;

　 r=a;

　 while(r!=q->next)

　 {

　if(y<=r->exp)

　{

　 cout<<"請按照指數遞增順序輸入,請重新輸入";

　 cin>>x>>y;

　break;

　}

　r=r->next;

　 }

　 if(x==0&&y==0) break;

　}

　 if(q!=NULL)

　q->next=NULL;

　return a; } void out_fun(node *a) {

　node *p;

　p=a;

　while(p)

　{

　 if(p==a)

　cout<<p->coef<<"*x^"<<p->exp;

　 else if(p->coef<0)

　cout<<p->coef<<"*x^"<<p->exp;

　 else if(p->coef>0)

　cout<<"+"<<p->coef<<"*x^"<<p->exp;

　 p=p->next;

　}

　cout<<endl; } node *plus_fun(node *a,node *b) {

　node *c,*p,*q,*r,*w;

　float x;

　p=a;

　q=b;

　c=a;

　r=c;

　while(p&&q)

　{

　 if((p->exp)<(q->exp))

　 {

　w=p;

　p=p->next;

　 r->next=w;

　r=w;

　 }

　 else if(p->exp==q->exp)

　 {

　x=p->coef+q->coef;

　if(x!=0)

　{

　 p->coef=x;

　 w=p;

　 p=p->next;

　 r->next=w;

　 r=w;

　 w=q;

　 q=q->next;

　 delete w;

　}

　else if(x==0)

　{

　 w=p;

　 p=p->next;

　 delete w;

　 w=q;

　 q=q->next;

　 delete w;

　}

　 }

　 else if(p->exp>q->exp)

　 {

　w=q;

　q=q->next;

　r->next=w;

　r=w;

　 }

　}

　if(p!=NULL)

　{

　 while(p)

　 {

　w=p;

　p=p->next;

　r->next=w;

　r=w;

　 }

　}

　if(q!=NULL)

　{

　 while(q)

　{

　w=q;

　q=q->next;

　r->next=w;

　r=w;

　 }

　}

　r->next=NULL;

　return c; } int main() {

　node *a,*b,*c;

　int n=1;

　while(n)

　{

　cout<<endl<<"--------一元多項式相加問題----------"<<endl;

　cout<<endl<<"請輸入第一個多項式的系數和指數"<<endl;

　a=in_fun();

　cout<<endl<<"您所輸入的多項式為"<<endl;

　out_fun(a);

　cout<<endl<<"請輸入第二個多項式的系數和指數"<<endl;

　b=in_fun();

　cout<<endl<<"您所輸入的多項式為"<<endl;

　out_fun(b);

　cout<<endl<<"初始化完畢，兩多項式相加得"<<endl;

　c=plus_fun(a,b);

　out_fun(c);

　cout<<"繼續初始化多項式請輸入 1，停止請輸入 0

　";

　cin>>n;

　cout<<endl;

　while(n!=1&&n!=0)

　{

　 cout<<"輸入錯誤，請重新輸入:";

　 cin>>n;

　}

　cout<<endl;

　}

　return 0; }

推薦訪問： 多項式 相加 實驗