Trending News
請教各位高手，C++程式一問
想跪求C++高手設計「一個鏈結串列結合程式，可對兩個具有多項式的連結串列(例如: 串列A與串列B)做一加法、減法、乘法與除法等四則運算」。
能夠附上程式碼讓小弟研究感激不盡
5 Answers
- spongeLv 610 years agoFavorite Answer
抱歉，知識+有規定貼字上限，所以以下為虛擬碼：
typedef struct PnNode{ // 定義多項式型別
double coef;
int expo;
PnNode* link;
} *Pn;
Pn add(Pn a, Pn b){
if(a==NULL) return copyPn(b);
else if(b==NULL) return copyPn(a);
PnNode *p, *q;
Pn r; // 相加結果
p=a;q=b;
for(;p->link!=NULL&&q->link!=NULL;){
if(p->expo>q->expo){append(&r, p);p=p->link;}
else if(p->expo<q->expo){append(&r, q);q=q->link;}
else if(p->coef+q->coef!=0){
PnNode t={p->coef+q->coef, p->expo};
append(&r, &t);
p=p->link;q=q->link;
}
}
for(;p->link!=NULL;p=p->link) append(&r, p);
for(;q->link!=NULL;q=q->link) append(&r, q);
return r;
}
Pn sub(Pn a, Pn b){
if(b==NULL) return copyPn(a);
else if(a==NULL) return minusPn(b);
else return add(a, minusPn(b));
}
Pn mul(Pn a, Pn b){
if(a==NULL||b==NULL) return NULL;
Pn r; // 相乘結果
copyPn(&r, b);
if(a->link==NULL){
for(PnNode* p=r;p->link!=NULL;p=p->link)
{p->coef*=a->coef;p->expo+=a->expo;}
return r;
}
else{
PnNode t, *p=a, *q;
for(;p->link!=NULL;p=p->link){
t=*p;
t.link=NULL;
q=mul(r, &t);
destroy(r);
r=q;
}
return r;
}
int div(Pn a, Pn b, Pn* quot, Pn* rem){
if(b==NULL) return 1;
else if(a==NULL) *quot=*rem=NULL;
else if(a->expo<b->expo){*quot=NULL;*rem=copyPn(a);}
else{
Pn p1=copyPn(a), p2, p3;
PnNode t;
for(*quot=NULL;p1->expo>=b->expo;p1=p3){
t.coef=p1->coef/b->coef;
t.expo=p1->expo-b->expo;
t.link=NULL;
append(quot, &t);
p2=mul(&t, b);
p3=sub(p1, p2);
destroy(p1);
destroy(p2);
}
*rem=p1;
}
return 0;
}
以上有幾個沒寫出來的函式：
Pn copyPn(Pn) 複製一個相同的串列
void append(Pn, PnNode*) 將新的項目增加到多項式後面
因為以上假設傳入的參數都已經做過排序(升/降冪)
void destroy(Pn) 將動態配置的串列記憶體釋放
程式中有些多項式只是暫時運算結果
因此必須在用過之後立即釋放
另外div其實cstdlib(stdlib.h)定義過，但C++允許負載
意見中有大大提到用STL, 是OK的
operator=或拷貝建構員就是copyPn
push_back就是append, ~list就是destroy
STL有提供sort函式解決排序問題
希望以上回答對您有幫助！
2011-08-01 14:25:53 補充：
code中還有一個minus函式
Pn minus(Pn) 產生一個冪次相同係數異號的多項式
- How do you think about the answers? You can sign in to vote the answer.
