实训C++语言设计——多项式Polynomial运算

平台：VC++ 2005 测试通过！
.vcproj
这是使用应用程序向导生成的 VC++ 项目的主项目文件。
它包含生成该文件的 Visual C++ 的版本信息，以及有关使用应用程序向导选择的平台、配置和项目功能的信息。
StdAfx.h, StdAfx.cpp
这些文件用于生成名为 twod.pch 的预编译头 (PCH) 文件和名为 StdAfx.obj 的预编译类型文件。
这些都是使用应用程序向导生成的 VC++ 文件故不列出
我只列出程序主要部分！

/*给予标准库中的vector, lists等实现
一元稀疏多项式*/
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
using namespace std;

typedef struct {
float _coef;
int _expn;
} LNode;//定义多项式链表的'节点'类型

typedef list<LNode> Polynomial;

/*一元多项式类型接口函数的定义部分,
此部分对Polynomial类型的使用者公开*/
void CreatPolyn(Polynomial& p, vector<double>& coef, vector<int>& expon);
void PrintPolyn(const Polynomial& p);
bool comp (const LNode& a, const LNode& b);
void AddPolyn(const Polynomial& Pa,const Polynomial& Pb,Polynomial& PSum);

/*一元多项式类型接口函数的实现部分,
此部分不对Polynomial类型的使用者公开*/
void CreatPolyn(Polynomial& p, vector<double>& coef, vector<int>& expon)
{
for (int i = 0; i < expon.size(); ++i) {
LNode tempnode;
tempnode._coef = coef[i]; tempnode._expn = expon[i];
/*不断将新节点从链表头部插入*/
p.push_back(tempnode);
}
/*将新生成的list按照指数进行排序*/
p.sort(comp); //comp是节点排序的标准
}

//LNode的排序标准,此函数将作为sort函数的
//参数来使用
bool comp (const LNode& a, const LNode& b){
if (a._expn < b._expn) return true;
else return false;
}

//输出多项式链表内容
void PrintPolyn(const Polynomial& p){
if( p.empty() )
cout<<"链表是空链表!";
else{
/*定义遍历链表的迭代子*/
list<LNode>::const_iterator iter = p.begin();
for(int i = 0; i<p.size(); i++ ){
cout<<(*iter)._coef << "x^" <<(*iter)._expn;
if ( i != (p.size()-1) ) cout<<"+";
iter++;
}
cout << endl;
}
}

void AddPolyn(const Polynomial& Pa, const Polynomial& Pb,Polynomial& PSum)
{
/*定义遍历链表的迭代子*/
list<LNode>::const_iterator iter_a = Pa.begin();
list<LNode>::const_iterator iter_b = Pb.begin();

while( (iter_a!=Pa.end()) && (iter_b!=Pb.end()) ){
if ( (*iter_a)._expn > (*iter_b)._expn ) { //if 1
LNode newnode;
newnode._coef = (*iter_b)._coef;
newnode._expn = (*iter_b)._expn;
PSum.push_back(newnode);
iter_b++;
}//endif 1
else if ((*iter_a)._expn < (*iter_b)._expn ){ //if 2
LNode newnode;
newnode._coef = (*iter_a)._coef;
newnode._expn = (*iter_a)._expn;
PSum.push_back(newnode);
iter_a++;
}//end if 2
else {
LNode newnode;
newnode._coef = (*iter_a)._coef + (*iter_a)._coef;
newnode._expn = (*iter_a)._expn;
PSum.push_back(newnode);
iter_a++; iter_b++;
}

}
//Pa链表中还有剩余节点
while(iter_a!=Pa.end()){
LNode newnode;
newnode._coef = (*iter_a)._coef;
newnode._expn = (*iter_a)._expn;
PSum.push_back(newnode);
iter_a++;
}
//Pb链表中还有剩余节点
while(iter_b!=Pb.end()){
LNode newnode;
newnode._coef = (*iter_b)._coef;
newnode._expn = (*iter_b)._expn;
PSum.push_back(newnode);
iter_b++;
}

}

// Polynomial_SL.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "Polynomial_SL.h"

int _tmain(int argc, _TCHAR* argv[])
{
string s;
do{
double dval = 0.0;
int ival = 0;
int A_Num_items;//A多项式包含的项数,程序中由用户指定
int B_Num_items;//B多项式包含的项数,程序中由用户指定
vector<double> A_coefficients;//A多项式系数数组
vector<int> A_exponents;//A多项式指数数组
vector<double> B_coefficients;//B多项式系数数组
vector<int> B_exponents;//B多项式指数数组

cout<<"请输入多项式A(x)的项数: ";
cin>>A_Num_items;
cout<<"请输入多项式A(x)的系数: ";
for(int i = 0; i < A_Num_items; i++){
cin>>dval;
A_coefficients.push_back(dval);
}
cout<<"请输入多项式A(x)的指数: ";
for(int i = 0; i < A_Num_items; i++){
cin>>ival;
A_exponents.push_back(ival);
}

cout<<"请输入多项式B(x)的项数: ";
cin>>B_Num_items;
cout<<"请输入多项式B(x)的系数: ";
for(int i = 0; i < B_Num_items; i++){
cin>>dval;
B_coefficients.push_back(dval);
}
cout<<"请输入多项式B(x)的指数: ";
for(int i = 0; i < B_Num_items; i++){
cin>>ival;
B_exponents.push_back(ival);
}

Polynomial Pa,Pb,PSum;

CreatPolyn(Pa,A_coefficients,A_exponents);
CreatPolyn(Pb,B_coefficients,B_exponents);
cout<<"A(x) = ";
PrintPolyn(Pa);
cout<<"B(x) = ";
PrintPolyn(Pb);

cout << "A(x) + B(x) = ";
AddPolyn(Pa,Pb,PSum);
PrintPolyn(PSum);

}while(!(s == "exit"));

return 0;
}