本学期最后一个技术贴，多项式加、乘法

zkkpkk

1. /*
   
2. [全民编程]76道C++高难度自虐题之43：对于次数很高，但项目很少的多项式，可用链表来表示。
   
3.   例如：X^1000－76*X^76＋3*X^3－7可表示为
   
4.   ┌─┬──┬─┐  ┌──┬─┬─┐   ┌─┬─┬─┐  ┌─┬─┬──┐
   
5.   │1 │1000│  ┼→│-76 │78│  ┼→ │3 │3 │  ┼→│-7│0 │ NIL│
   
6.   └─┴──┴─┘  └──┴─┴─┘   └─┴─┴─┘  └─┴─┴──┘
   
7. 在此方式下，编程完成两个多项式的加法与乘法。
   
8. */
   
9. #include <iostream.h>
   
10. class Node
    
11. {
    
12. private:
    
13. int cof;
    
14. int exp;
    
15. Node* next;
    
16. public:
    
17. //用默认值初始化
    
18. Node()
    
19. {
    
20.   cof=0;
    
21.   exp=0;
    
22.   next=NULL;
    
23. }
    
24. //用给定值初始化
    
25. Node(int cof,int exp)
    
26. {
    
27.   this->cof=cof;
    
28.   this->exp=exp;
    
29.   next=NULL;
    
30. }
    
31. //建立多项式
    
32. Node* CreateLink(Node* head,int m);
    
33. //取头节点
    
34. Node* GetHead(Node* head);
    
35. //多项式加法
    
36. Node* AddNode(Node* head1,Node* head2);
    
37. //乘法
    
38. Node* MultiNode(Node* head1,Node* head2,Node* head3);
    
39. //输出
    
40. void Display(Node* head);
    
41. };
    
42. /*取头节点*/
    
43. Node* Node::GetHead(Node* head)
    
44. {
    
45. return head;
    
46. }
    
47. /*输出多项式*/
    
48. void Node::Display(Node* head)
    
49. {
    
50. Node* temp=head;
    
51. while(temp!=NULL)
    
52. {
    
53.   temp=temp->next;
    
54.   if(temp->exp==0)  //处理指数为0的情况
    
55.    cout<<temp->cof<<"  ";
    
56.   else
    
57.    cout<<temp->cof<<"*X^"<<temp->exp<<"  ";
    
58. }
    
59. cout<<endl;
    
60. }
    
61. /*建立链表，m为节点数*/
    
62. Node* Node::CreateLink(Node* head,int m)
    
63. {
    
64. Node *p=head;
    
65. cout<<"Input cof and exp"<<endl;
    
66. for(int i=1;i<=m;i++)
    
67. {
    
68.   int cof,exp;
    
69.   cout<<"cof:";
    
70.   cin>>cof;
    
71.   cout<<"exp";
    
72.   cin>>exp;
    
73.   Node* newnode=new Node;
    
74.   newnode->cof=cof;
    
75.   newnode->exp=exp;
    
76.   newnode->next=p->next;
    
77.   p->next=newnode;
    
78.   p=newnode;
    
79. }
    
80. return head;
    
81. }
    
82. /*多项式加法*/
    
83. Node* Node::AddNode(Node* head1,Node* head2)
    
84. {
    
85. Node* ha=GetHead(head1);
    
86. Node* hb=GetHead(head2);
    
87. Node *la=ha,*lb=hb;
    
88. Node *qa=la->next;
    
89. Node *qb=lb->next;
    
90. while(qa!=NULL && qb!=NULL)  //pa,pb不为空指数比较
    
91. {
    
92.   if(qa->exp > qb->exp)  //如果qa指数大
    
93.   {
    
94.    la=qa;
    
95.    qa=qa->next;
    
96.   }
    
97.   if(qa->exp == qb->exp)  //如果指数相等
    
98.   {
    
99.    int sum=qa->cof+qb->cof;
    
100.    if(sum!=0)  //系数不为0
     
101.    {
     
102.     /*修改系数值*/
     
103.     qa->cof=sum;
     
104.     la=qa;
     
105.     qa=qa->next;
     
106.     lb->next=qb->next;
     
107.     delete qb;
     
108.     qb=lb->next;
     
109.    }
     
110.    else  //系数为0
     
111.    {
     
112.     /*删除多项式pa中的当前节点*/
     
113.     la->next=qa->next;
     
114.     delete qa;
     
115.     qa=la->next;
     
116.     lb->next=qb->next;
     
117.     delete qb;
     
118.     qb=lb->next;
     
119.    }
     
120.   }
     
121.   if(qa->exp < qb->exp)  //如果pb指数大
     
122.   {
     
123.    /*qb在前*/
     
124.    lb->next=qb->next;
     
125.    la->next=qb;
     
126.    qb->next=qa;
     
127.    la=qb;
     
128.    qb=lb->next;
     
129.   }
     
130. }
     
131. if(qb!=NULL)
     
132.   la->next=qb;
     
133. delete lb;
     
134. return ha;
     
135. }
     
136. /*乘法*/
     
137. Node* Node::MultiNode(Node* head1,Node* head2,Node* head3)
     
138. {
     
139. Node* ha=GetHead(head1);
     
140. Node* hb=GetHead(head2);
     
141. Node* hc=GetHead(head3);
     
142. Node *la=ha,*lb=hb,*tmp=hc;
     
143. Node* qa=la->next;
     
144. Node* qb=lb->next;
     
145. 
     
146. while(qa!=NULL)
     
147. {
     
148.   while(qb!=NULL)
     
149.   {
     
150.    /*系数相乘指数相加*/
     
151.    int sumc=qa->cof*qb->cof;
     
152.    int sume=qa->exp+qb->exp;
     
153.    /*结果存入新的节点*/
     
154.    Node* newnode=new Node;
     
155.    newnode->cof=sumc;
     
156.    newnode->exp=sume;
     
157.    newnode->next=tmp->next;
     
158.    tmp->next=newnode;
     
159.    tmp=newnode;
     
160.    qb=qb->next;
     
161.   }
     
162.   /*qb回到第一个qa指向下一个*/
     
163.   qb=lb->next;
     
164.   qa=qa->next;
     
165. }
     
166. delete tmp;
     
167. return hc;
     
168. }
     
169. int main()
     
170. {
     
171. Node* head1=new Node;
     
172. Node* head2=new Node;
     
173. Node* head3=new Node;
     
174. Node n1;
     
175. n1.CreateLink(head1,2);
     
176. cout<<"Ploy1:";
     
177. n1.Display(head1);
     
178. n1.CreateLink(head2,2);
     
179. cout<<"Ploy2:";
     
180. n1.AddNode(head1,head2);
     
181. cout<<"Ploy1 add ploy2:";
     
182. n1.Display(head1);
     
183. n1.MultiNode(head1,head2,head3);
     
184. cout<<"Ploy1 mut ploy2:";
     
185. n1.Display(head3);
     
186. return 0;
     
187. }

复制代码

现在我累计了7道了，外国朋友Hjin（后来得知不是中国的至于哪国他也没说），势如破竹累计了17道，现在他还在做，差距还在拉大，更可怕的是压轴的第76题他已经KO了，胜负已分了:funk ，所以现在比赛已经演变为了Hjin的程序设计艺术展了:titter，我放假后个把星期不能上，可能会被追上

[ 本帖最后由 zkkpkk 于 2007-7-4 19:20 编辑 ]

zkkpkk

沙发，都不喜欢算法......