C/C++数据结构与算法，一元多项式问题
楼主你好，这是我最近写的，把输入的式子当作纯字符串处理，已要求的是一元多项式，我的支持多元多项式，最多可支持5个变元，当然你亦可以修改代码使之更具扩展性，可能算法比较复杂，不懂得随时问我^~^
/*********************************************
*Copyright (c++) 2013 by xihua_university
*All rights reserved
*
*Filename:第二章_常用数据结构_多项式相乘_13.cpp
*Function:计算两个多项式相乘
*Auther:heyanbo
*Final:2013,8,16~18
*********************************************/
#include
#include
#include
#include
using namespace std;
//////////////////////////////////////////////////////////
struct recoder_inf
{ char character;
int number;
};
bool check_number(string s);//检查小项是否只含数字
string link_string(string s_f, string s_s, recoder_inf *temp_recoder);//运算并连接小项
///////////////////////////////////////////////////////////
int main()
{
char c;
int first(0), i(0), j(0), count(0), count1(0), k(0);
recoder_inf *temp_recoder = NULL;
string s_first, s_second, *s_f = NULL, *s_s = NULL, *link = NULL;
system("color 1e");
cout<<setw(46)<<setfill(' ')<<"多项式相乘运算器
";
cout<<"请输入第一个多项式:(如2x^2+3xy+12,其中\"x^2\"表示x的平方)
";
cin>>s_first;
cout<<"请输入第二个多项式:
";
cin>>s_second;
while (((c='-',s_first.find(c,first)!=string::npos) \
&& s_first.find(c,first)<s_first.find('+',first))\
||(c='+',s_first.find(c,first)!=string::npos))//记录多项式1项数
{
count++;
first = s_first.find(c,first)+1;
}
if (s_first[0]=='-')//处理第一个小项带负号
count--;
s_f = new string[count+1];
first = 0;
if (s_first[0]=='-')//擦除负号
{
s_first.erase(0,1);
while (((c='-',s_first.find(c,first)!=string::npos) \
&& s_first.find(c,first)<s_first.find('+',first))\
||(c='+',s_first.find(c,first)!=string::npos))//拆解多项式1至小项
{
if (s_first[first-1]=='-')
s_f[i] = s_first.substr(first-1,s_first.find(c,first)-first+1);//保留负号
else
s_f[i] = s_first.substr(first,s_first.find(c,first)-first);
first = s_first.find(c,first)+1;
i++;
}
if (s_first[first-1]=='-')
s_f[i] = s_first.substr(first-1,s_first.length()-first+1);//处理最后一个小项
else
s_f[i] = s_first.substr(first,s_first.length()-first);
s_f[0].insert(0,'-');//插人负号
}
else
{
while (((c='-',s_first.find(c,first)!=string::npos) \
&& s_first.find(c,first)<s_first.find('+',first))\
||(c='+',s_first.find(c,first)!=string::npos))//拆解多项式1至小项
{
if (s_first[first-1]=='-')
s_f[i] = s_first.substr(first-1,s_first.find(c,first)-first+1);//保留负号
else
s_f[i] = s_first.substr(first,s_first.find(c,first)-first);
first = s_first.find(c,first)+1;
i++;
}
if (s_first[first-1]=='-')
s_f[i] = s_first.substr(first-1,s_first.length()-first+1);//处理最后一个小项
else
s_f[i] = s_first.substr(first,s_first.length()-first);
}
//////////////////////////////////////////////////////////////////////
first = 0;
while (((c='-',s_second.find(c,first)!=string::npos) \
&& s_second.find(c,first)<s_second.find('+',first))\
||(c='+',s_second.find(c,first)!=string::npos))//记录多项式2项数
{
count1++;
first = s_second.find(c,first)+1;
}
if (s_second[0]=='-')//处理第一个小项带负号
count1--;
s_s = new string [count1+1];
first = 0;
i = 0;
if (s_second[0]=='-')
{
s_second.erase(0,1);
while (((c='-',s_second.find(c,first)!=string::npos) \
&& s_second.find(c,first)<s_second.find('+',first))\
||(c='+',s_second.find(c,first)!=string::npos))//拆解多项式2至小项
{
if (s_second[first-1]=='-')
s_s[i] = s_second.substr(first-1,s_second.find(c,first)-first+1);//保留负号
else
s_s[i] = s_second.substr(first,s_second.find(c,first)-first);
first = s_second.find(c,first)+1;
i++;
}
if (s_second[first-1]=='-')
s_s[i] = s_second.substr(first-1,s_second.length()-first+1);//处理最后一个小项
else
s_s[i] = s_second.substr(first,s_second.length()-first);
s_s[0].insert(0,'-');//插入负号
}
else
{
while (((c='-',s_second.find(c,first)!=string::npos) \
&& s_second.find(c,first)<s_second.find('+',first))\
||(c='+',s_second.find(c,first)!=string::npos))//拆解多项式2至小项
{
if (s_second[first-1]=='-')
s_s[i] = s_second.substr(first-1,s_second.find(c,first)-first+1);//保留负号
else
s_s[i] = s_second.substr(first,s_second.find(c,first)-first);
first = s_second.find(c,first)+1;
i++;
}
if (s_second[first-1]=='-')
s_s[i] = s_second.substr(first-1,s_second.length()-first+1);//处理最后一个小项
else
s_s[i] = s_second.substr(first,s_second.length()-first);
}
/////////////////////////////////////////////////////////////////////////
link = new string[(count+1)*(count1+1)];
temp_recoder = new recoder_inf[20];//支持单个大项拥有最多10个不同变量
for (i=0;i<count+1;i++)//连接字符串并处理输出符号问题
for (j=0;j<count1+1;j++)
{
link[k] = link_string(s_f[i], s_s[j],temp_recoder);
if (link[k][0]=='1' && (link[k][1]'9') &&\
!check_number(link[k]))//系数为1就不要系数
link[k].erase(0,1);
if (link[k][0]=='-' && link[k][1]=='1' && \
(link[k][2]'9') && !check_number(link[k]))//系数为-1则只保留负号
link[k].erase(1,1);
if (link[k][0]!='-')
link[k].insert(0,'+');
if (i==0 && j==0 && link[k][0]!='-')
link[k].erase(0,1);
k++;
}
cout<<"计算结果如下:
";
cout<<'(';
for (i=0;i<count+1;i++)
{
if (i!=0 && s_f[i][0]!='-')
{
s_f[i].insert(0,'+');
cout<<s_f[i];
}
else
cout<<s_f[i];
}
cout<<")*(";
for (j=0;j<count1+1;j++)
{
if (j!=0 && s_s[j][0]!='-')
{
s_s[j].insert(0,'+');
cout<<s_s[j];
}
else
cout<<s_s[j];
}
cout<<")=";
for (i=0;i<(count+1)*(count1+1);i++)
cout<<link[i];
cout<<endl;
delete []temp_recoder;
delete []s_f;
delete []s_s;
delete []link;
return 0;
}
/***检查小项是否为纯数字以便直接运算***/
bool check_number(string s)
{
for (int i=0;i<s.length();i++)
{
if (s[i]=='-' || s[i]>='0' && s[i]<='9' || s[i]=='.')
;
else
return false;
}
return true;
}
/***系数相乘并连接小项***/
string link_string(string s_f, string s_s,recoder_inf *temp_recoder)
{
char c_temp;
float s_f_temp(1.0), s_s_temp(1.0);
int t(0), t1, count(0), count1(0), count2(0), i, i1, j, m, n, k, r, r1, r_temp, l, l1;
string s, s1, s_temp;
stringstream f;
/***当第一个与第二个多项式都不全为数字时执行以下操作***/
if (!check_number(s_f) && !check_number(s_s))//检查小项的系数
{
///////////////////////////处理小项系数
for (i=0;i<s_f.length(); ) //对第一个多项式的小项依次做处理
{
if (s_f[i]=='-' || s_f[i]>='0'&&s_f[i]<='9' || s_f[i]=='.')//系数截取位置
i++;
else
break;
}
if (i==1 && s_f[0]=='-')
s_f_temp = -1;
elseif (i>=1)
s_f_temp = atof(s_f.substr(0,i).c_str());
for (i1=0;i1<s_s.length(); ) //对第二个多项式的小项依次做处理
{
if (s_s[i1]=='-' || s_s[i1]>='0'&&s_s[i1]<='9' || s_s[i1]=='.')//系数截取位置
i1++;
else
break;
}
if (i1==1 &&s_s[0]=='-')
s_s_temp = -1;
else if (i1>=1)
s_s_temp = atof(s_s.substr(0,i1).c_str());
f.clear();
f<<s_f_temp*s_s_temp;//类型安全转换
f>>s;
s_temp = s_f.substr(i,s_f.length()-i)+s_s.substr(i1,s_s.length()-i1);
///////////////////////////////////
for (j=0;j<s_temp.length(); )//对连接好的去除了系数的字符串做处理
{
if (((t1=s_temp.substr(0,j).find(s_temp[j],0))>=0?false:true) \
&& s_temp[j]!='^' && (s_temp[j]'9'))//检查变元是否重复
{
temp_recoder[t].character = s_temp[j];
l1 = j;
if (s_temp[j+1]=='^')
{
for (m=j+2;m<s_temp.length();m++)
{
if (s_temp[m]>='0' && s_temp[m]<='9')
count++;
else
break;
}
temp_recoder[t].number = atoi(s_temp.substr(j+2,count).c_str());
j += 2+count;//下一个变元的位置
//////////////////////////////////处理下一变元
for (n=j;n<s_temp.length(); )
{
if (s_temp[n]==s_temp[l1] && s_temp[n+1]!='^')
{
count1++;
n++;
temp_recoder[t].number += count1;
}
if (s_temp[n]==s_temp[l1] && s_temp[n+1]=='^')
{
for (k=n+2;k<s_temp.length();k++)//变元指数截取位数
{
if (s_temp[k]>='0' && s_temp[k]<='9')
count2++;
else
break;
}
temp_recoder[t].number += atoi(s_temp.substr(n+2,count2).c_str());//变元指数
n +=2+count2;
}
if (s_temp[n]!=s_temp[l1])
n++;
}
}
else
{
temp_recoder[t].number = 1;
j++;//下一个变元的位置
count1 = 0;
for (n=j;n<s_temp.length(); )
{
if (s_temp[n]==s_temp[l1] && s_temp[n+1]!='^')
{
count1++;
temp_recoder[t].number += count1;
n++;
}
if (s_temp[n]==s_temp[l1] && s_temp[n+1]=='^')
{
count2 = 0;
for (k=n+2;k<s_temp.length();k++)//变元指数截取位数
{
if (s_temp[k]>='0' && s_temp[k]<='9')
count2++;
else
break;
}
temp_recoder[t].number += atoi(s_temp.substr(n+2,count2).c_str());//变元指数
n +=2+count2;
}
if (s_temp[n]!=s_temp[l1])
n++;
}
}
t++;
}
else
{
j++;
}
}
for (r=0;r<t-1;r++)//选择排序法确保最高指数变元在前面
{
r_temp = r;
for (r1=r+1;r1<t;r1++)
if (temp_recoder[r1].number<temp_recoder[r_temp].number)
r_temp = r1;
if (r_temp!=r)
{
l = temp_recoder[r].number;//指数交换
temp_recoder[r].number = temp_recoder[r_temp].number;
temp_recoder[r_temp].number = l;
c_temp = temp_recoder[r].character;//变元交换
temp_recoder[r].character = temp_recoder[r_temp].character;
temp_recoder[r_temp].character = c_temp;
}
}
for (r=t-1;r>-1;r--)
{
if (temp_recoder[r].number>1)
{
f.clear();//清空缓冲区
f<<temp_recoder[r].character<<'^'<<temp_recoder[r].number;
f>>s1;
s += s1;
}
if (temp_recoder[r].number==1)
{
f.clear();
f<<temp_recoder[r].character;
f>>s1;
s += s1;
}
}
return s;
}
/***当第一个不全为数字而第二个多项式全为数字时执行以下操作***/
if (!check_number(s_f) && check_number(s_s))
{
for (i=0;i<s_f.length(); ) //对第一个多项式的小项依次做处理
{
if (s_f[i]=='-' || s_f[i]>='0'&&s_f[i]<='9' || s_f[i]=='.')//系数截取位置
i++;
else
break;
}
if (i==1 && s_f[0]=='-')
s_f_temp = -1;
else if (i>=1)
s_f_temp = atof(s_f.substr(0,i).c_str());
s_s_temp = atof(s_s.c_str());
f.clear();
f<<s_f_temp*s_s_temp<<s_f.substr(i,s_f.length()-i);
f>>s;
return s;
}
/***当第一个全为数字而第二个多项式不全为数字时执行以下操作***/
if (check_number(s_f) && !check_number(s_s))
{
for (i=0;i<s_s.length(); ) //对第一个多项式的小项依次做处理
{
if (s_s[i]=='-' || s_s[i]>='0'&&s_s[i]<='9' || s_s[i]=='.')//系数截取位置
i++;
else
break;
}
if (i==1 && s_s[0]=='-')
s_s_temp = -1;
else if (i>=1)
s_s_temp = atof(s_s.substr(0,i).c_str());
s_f_temp = atof(s_f.c_str());
f.clear();
f<<s_f_temp*s_s_temp<<s_s.substr(i,s_s.length()-i);
f>>s;
return s;
}
/***当第一个和第二个多项式全为数字时执行以下操作***/
if (check_number(s_f) && check_number(s_s))
{
s_f_temp = atof(s_f.c_str());
s_s_temp = atof(s_s.c_str());
f.clear();
f<<s_f_temp*s_s_temp;
f>>s;
return s;
}
}
注意：输入时，指数按升序输入
如： 1 1 2 2 3 3 0 0
2 2 3 3 0 0
结果：1 1 4 2 6 3
#include
#include
struct poly //设置结构体
{
int xi;
int zhi;
struct poly *next;
};
struct poly *jianli(void) //建立链表
{
struct poly *p1,*head1,*p2;
head1=(struct poly*)malloc(sizeof(poly));
p1=(struct poly*)malloc(sizeof(poly));
scanf("%d %d",&p1->xi,&p1->zhi);
head1->next=p1;
p1->next=NULL;
while(1)
{
p2=(struct poly*)malloc(sizeof(poly));
scanf("%d %d",&p2->xi,&p2->zhi);
if(p2->xi==0) if(p2->zhi==0) {free(p2);break;}
p1->next=p2;
p2->next=NULL;
p1=p2;
}
return(head1);
}
struct poly *jisuan(struct poly *head1,struct poly *head2) //多项式的相加
{
struct poly *p1,*p2,*r1,*r2;
r1=head1;
p1=head1->next;
r2=p2=head2->next;
while(p1&&p2)
{
if(p1->zhi==p2->zhi)
{
p1->xi=(p1->xi)+(p2->xi);
p2=p2->next;
free(r2);
r2=p2;
r1=p1;
p1=p1->next;
}
else if(p1->zhi>p2->zhi)
{
r2->next=p1;
r1->next=r2;
p2=p2->next;
r2=p2;
}
else
if(p1->zhizhi)
{
r1=p1; p1=p1->next;
}
}
if(p1) free(head2);
else {
r1->next=p2;
free(head2);
}
return(head1);
}
void print(poly *head)
{
struct poly *p;
p=head->next;
while(p)
{
printf("%d %d",p->xi,p->zhi);
p=p->next;
}
}
void main()
{
struct poly *head1,*head2,*p;
printf("请输入多项式的每一项的系数与指数并以0 0为结束标志:
");
head1=jianli();
printf("
请输入另一个多项式的每一项的系数与指数并以0 0为结束标志:
");
head2=jianli();
p=jisuan(head1,head2);
printf("
合并后:
");
print(p);
}
1）使用链表，链表的每个节点表示多项式的一个项，结点定义如下：
typedef struct
{
double coeff;
int power;
pItem next;
} item, *pItem;
2) 定义链表头指针
pItem head = null;
3) 打开输入文件
4) 从文件读入，每读入一行，动态生成一个项并加入到链表中
/*申请内存，动态建立一个项*/
pItem p = (pItem)malloc(sizeof(item));
/*假设读入系数为4， 幂为1*/
p->coeff = 4;
p->power = 1;
/*加入到链表中*/
pItem q = head;
while(q!= null)
{
q=q->next;
}
q.next = p;
p.next = null;
5) 输入表达式
pItem r = head;
while(r != null)
{
printf("%fx^%d", r->coeff, r.power);
r = r->next;
}
ps. 上面是伪代码，忽略了诸如读入文件、输出是每个项前的运算符等很多细节。仅供参考
我的回答看下面的链接。
http://zhidao.baidu.com/question/1237696596713441659.html?oldq=1
隐雄清热： 可以做的项目还是挺多的,但是当下的情况是,C++更多做的是底层的工作,而Java、C#等等语言更多的运用在app、网站的项目中.
理县17749874416： C++数据结构与算法什么时候看最好 - ？
隐雄清热： 可以把C++看成“表达方式”,而把算法和数据结构看成“想法”.所以说应该在有一定的语言基础时学习算法和数据结构.C++和数据库是两种不同的概念.建议应该先看C++,知道该怎么应用以后再去看数据库,将数据库运用到其中,功能就很强大了.学习算法的时候还是看C语言描述的比较直观.再者算法学习方面比较权威的有一本《算法导论》,这本书讲的很有深度,所以认真读起来还是很有意思的.另外需要纠正一点,语言本身就是来实现算法的载体,所以学透一门语言也是必须的.
理县17749874416： 学习c++数据结构与算法分析 看那本书比较好啊? - ？
隐雄清热： 如果你对C++不是非常熟悉的话,学习算法的时候还是看C语言描述的比较直观.再者算法学习方面比较权威的有一本《算法导论》,这本书讲的很有深度,所以认真读起来还是很有意思的.另外需要纠正一点,语言本身就是来实现算法的载体,所以学透一门语言也是必须的.维斯【美】编的《数据结构与算法分析》(第三版)C++版,这本书我看了,很不错的,讲得很好,算法导论.维斯【美】编的《数据结构与算法分析》(第三版)C++版这本书,开始讲了一些简单的需要的C++知识,其实这本书用到的C++特性很少,所以即使你对C++的了解不多的话也可以看的.单纯地做算法建议用C.
理县17749874416： 数据结构算法(c++)？
隐雄清热： 比如#includeusing namespace std;#define MAX 10 // MAXIMUM STACK CONTENTclass stack{private:int arr[MAX]; // Contains all the Dataint top; //Contains location of Topmost Data pushed onto Stackpublic:stack() //Constructor{top...
理县17749874416： c++中数据结构是怎么用的 - ？
隐雄清热： 当然是已经写好的啦,写这些库就是为了代码重用,他们封装了数据结构的相关算法和数据,只需拿来用就可以了.怎么使用?去参考下STL文档,或看一本书《The Standard C++ Library》.在这里介绍的话,一天一夜也写不完...
理县17749874416： 数据结构与算法 C++ 双链表的创建 - ？
隐雄清热： #include using namespace std; class node { public:int data; node *head; node *tail; public:node(){} }; class link { public:node * phead;//头指针 node * ptail;//尾指针 node * ptemp;//临时 public:void print(); link(); }; link::link()//构造循环双链表 { ...
理县17749874416： c++数据结构与算法哪本书最好 - ？
隐雄清热： 《算法(第四版)》:给出了程序员应知应会的50个算法.推荐理由:1. 极其优雅的代码实现,对编程水平的提高有极大的帮助.2. 算法深入浅出,尤其是红黑树的讲解,非常精彩.对算法水平的提高有极大帮助.上述是我认为最重要的理由,当然题主要求的代码和重要习题答案官网都有(部分习题). 著作权归作者所有.商业转载请联系作者获得授权,非商业转载请注明出处.
理县17749874416： C、C++、数据结构、算法 - ？
隐雄清热： 我建议还是学数据结构和算法 数据结构和算法只是一种思维方法 是任何语言都必须的 C和C++只是个工具 就好比你买了辆客车用来代步 你接下来是该学开车呢还是再去买一辆轿车呢?你不会开车买再多车也没用 而数据结构算法什么的就是开车的方法 任何程序到后来都归咎到了数据结构和算法
理县17749874416： c++ 线性代数 离散数学 数据结构与算法的学习顺序 - ？
隐雄清热： 线性代数,离散数学是数学理论,你可以先学.然后你先学C语言(C会了,学C++就很简单了),在学数据结构,C和数据结构可以同步学习,最后学算法.我没有看过网上课程,就不推荐了.
理县17749874416： C语言数据结构算法和C++数据结构算法有什么区别吗??进来看看.. - ？
隐雄清热： 没有什么区别哈,只是不同语言来实现的哈,相对来说看c的数据结构还简单一点,你不需要面向对象的思想,如果看c++的写的数据结构的话,你还要封装类,这样多给数据结构加了一层东西,建议直接看c的好点.c++包含了c,一般你看c++的书,如果不是专门讲数据结构的话,一般不会涉及数据结构,因为c++的stl里提供了很多已经封装好了的数据结构,如果你要了解这些封装好了的原理的话,你必须对c写的数据结构有比较好的理解才能看懂.
