連結串列實現多項式相乘-資料結構學習
連結串列實現多項式相乘<線性表>
初學資料結構,我這個菜鳥 沒看教程完全自己想. 這個題做好了好久. 不過還好總於做出來了.
先上程式碼,程式碼裡有註釋. 可以把註釋變為cout<<註釋 看一下向乘的過程.
後面再做詳細的補充說明
問題描述 :
輸入兩個多項式,多項式的第一個數是項數.後續是兩兩一對,一個係數,一個指數. 多項式有序,按照係數的降序. 通過單鏈表實現兩個多項式相乘. 輸出結果多項式.同樣第一項為項的個數, 後續安裝指數降序排列.
要通過連結串列實現.
解決思路:
初始時把兩個多項式的第一項存下來,這就是結果多項式的第一項.因為有序的原因,後面的都沒有這一項的指數大,因此不用考慮這一項的本位相加和向前插入.之後遍歷連結串列每一項,三個基本過程,本位相加,向前插入,向後插入.就實現了,兩個多項式相乘,這個新構建的連結串列就是結果多項式.
上程式碼:
1 #include<iostream> 2 #define ends " ";//linux ends不輸出 3 using namespace std; 4 5 typedef struct polynomial 6 { 7int coef; //項的係數 8int index; //指數 9polynomial * next; 10 }term,*pTerm; 11 12 pTerm creatterm(); 13 void showterm(pTerm); 14 pTerm mult(pTerm,pTerm); 15 16 int main(){ 17pTerm term1,term2,termAns; 18term1=creatterm(); 19term2=creatterm(); 20cout<<"輸入的兩個多項式分別是:"<<endl; 21showterm(term1); 22showterm(term2); 23cout<<"結果是:"<<endl; 24termAns=mult(term1,term2); 25showterm(termAns); 26return 0; 27 } 28 //建立多項式 29 pTerm creatterm(){ 30int val,m,c,f; 31pTerm phead, ptail; 32phead = (pTerm)malloc(sizeof(term)); 33ptail=phead; 34ptail->next=NULL; 35cout<<"輸入多項式的項數:"; 36cin>>m; 37for(int i=0;i<m;i++){ 38cin>>c>>f; 39pTerm pnew=(pTerm)malloc(sizeof(term)); 40pnew->coef=c; 41pnew->index=f; 42ptail->next=pnew; 43pnew->next=NULL; 44ptail=pnew; 45} 46phead->coef=m; 47return phead; 48 } 49 //顯示多項式的值 50 void showterm(pTerm phead){ 51pTerm p; 52p=phead->next; 53while(p!=NULL){ 54cout<<p->coef <<" "<< p->index<<" "; 55p=p->next; 56} 57cout<<endl; 58 } 59 //多項式相乘 60 pTerm mult(pTerm t1,pTerm t2){ 61pTerm p1,p2,p,pre,phead;//第一個多項式 第二個多項式 工作節點指向當前的比較項 p的前一項 頭節點 62int n=1;//項數 63//分配空間 64p=(pTerm)malloc(sizeof(term)); 65pre=(pTerm)malloc(sizeof(term)); 66phead=(pTerm)malloc(sizeof(term)); 67p1=t1->next;//第一個多項式的第一項 68p2=t2->next;//第二個多項式的第一項 69//p初始化為第一項 70p->coef=p1->coef*p2->coef; 71p->index=p1->index+p2->index; 72p->next=NULL; 73pre->next=p; 74phead->next=p; 75//迴圈遍歷處理每一項 76while(p1!=NULL){ 77p2=t2->next; 78while(p2!=NULL){ 79p=phead->next; 80pTerm pnew=(pTerm)malloc(sizeof(term)); 81pnew->coef=p1->coef*p2->coef; 82pnew->index=p1->index+p2->index; 83pnew->next=NULL; 84for(int i=0;i<t1->coef*t2->coef;i++) 85{ 86if(p->index==pnew->index){ //本位相加 87if(n==1) break;//第一項已有直接退出迴圈 88else{p->coef+=pnew->coef; 89n++; 90break;} 91}else if(p->index>pnew->index){ 92pre=p; 93if(p->next==NULL) {//向後插入 94p->next=pnew; 95n++; 96break; 97} 98else p=p->next; 99}else if(p->index<pnew->index) { //向前插入 100pre->next=pnew; 101pnew->next=p; 102pre=pnew; 103n++; 104break; 105} 106} 107p2=p2->next;//p2移動 108} 109p1=p1->next;//p1移動 110} 111cout<<n<<" ";//輸出項數 112return phead; 113 }