数据结构实验四 线性表的基本操作及应用

1. #include<iostream>
2. #include<string>
3. #include<fstream>
4. using namespace std;
5. #define ERROR 0
6. 
7. typedef struct PNode {
8.  float coef; //系数
9.  int expn; //指数
10.   struct PNode *next;
11. } PNode, *Polynomial;
12. string head_1, head_2;
13. int temp;
14. char st = 'A';
15. 
16. void CreatPolyn(Polynomial &P, int m) //算法2.18 多项式的创建
17. {
18.   //输入m项的系数和指数，建立表示一个多项式的有序链表P
19.   Polynomial q, pre, s;
20.   int i;
21.   P = new PNode;
22.   P->next = NULL; //先建立一个带头结点的单链表
23.   char filename[20] = { 0 };
24.   cout << "请输入有关多项式p" << char(st + 32)  << endl;
25.   ++st;
26.   gets(filename);
27.   fstream file;
28.   file.open(filename);
29.   if (!file) {
30.     cout << "未找到相关文件，无法打开！" << endl;
31.     exit(ERROR);
32.   }
33.   file >> head_1 >> head_2;
34.   while (!file.eof())
35.   {
36.     s = new PNode; //生成新结点
37.     file >> s->coef >> s->expn; //输入元素值
38.     pre = P; //pre用于保存q的前驱，初值为头结点
39.     q = P->next;
40.     while (q && q->expn < s->expn) //通过比较指数找到第一个大于输入项指数的项q
41.     {
42.       pre = q;
43.       q = q->next;
44.     } //while
45.     s->next = q; //将输入项s插入到q和其前驱结点pre之间
46.     pre->next = s;
47.   }//for
48.   file.close();
49. } //CreatPolyn
50. 
51. void AddPolyn(Polynomial &Pa, Polynomial &Pb) //算法2.19 多项式的相加
52. {
53.   //多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成"和多项式"
54.   Polynomial r, p1, p2, p3;
55.   float sum;
56.   p1=Pa->next;  //补充代码
57.     p2=Pb->next;  //补充代码
58. //p1和p2初值分别指向Pa和Pb的第一个结点
59.   p3=Pa;  //补充代码
60. //p3指向和多项式的当前结点，初值为Pa
61.   while (p1 && p2) //p1和p2均非空
62.   {
63.     if (p1->expn == p2->expn) //指数相等
64.     {
65.       sum = p1->coef + p2->coef; //sum保存两项的系数和
66.       if (sum != 0) //系数和不为0
67.       {
68.         p1->coef=sum;//补充代码//修改Pa当前结点p1的系数值为两项系数的和
69.         p3->next = p1;
70.         p3 = p1; //将修改后的Pa当前结点p1链在p3之后，p3指向p1
71.         p1 = p1->next; //p1指向后一项
72.         r = p2;
73.         p2 = p2->next;
74.         delete r; //删除Pb当前结点r
75.       } else //系数和为0
76.       {
77.         r=p1;p1=p1->next;delete r;
78. 
79. //删除Pb当前结点p1
80.         r = p2;
81.         p2 = p2->next;
82.         delete r; //删除Pb当前结点p2
83.       }
84.     } else if (p1->expn < p2->expn) //Pa当前结点p1的指数值小
85.     {
86.       p3->next=p1;  //将p1链在p3之后
87.       p3=p1;     //p3指向p1
88.       p1=p1->next;     //p1指向后一项
89.     } else //Pa当前结点p2的指数值小
90.     {
91.       p3->next = p2; //将p2链在p3之后
92.       p3 = p2; //p3指向p2
93.       p2 = p2->next; //p2指向后一项
94.     }
95.   } //while
96.   p3->next = p1 ? p1 : p2; //插入非空多项式的剩余段
97.   delete Pb; //释放Pb的头结点
98. } //AddPolyn
99. 
100. 
101. int main() {
102.  Polynomial Pa, Pb;
103.  Polynomial p;
104.  int i;
105. 
106.  //创建多项式Pa
107.  CreatPolyn(Pa, temp); //调用函数，输入Pa每一项的系数和指数
108. 
109.  //创建多项式Pb
110.  CreatPolyn(Pb, temp); //调用函数，输入Pa每一项的系数和指数
111. 
112.  AddPolyn(Pa, Pb);
113.  cout << "多项式Pa和Pb相加后的结果是：\n";
114.  p = Pa->next;
115.  i = 0;
116.  while (p) //输出相加后的结果，每一项以x^n表示
117.  {
118.    if (i)
119.      cout << " + ";
120.    cout << "(" << p->coef << ") * x^" << p->expn;
121.    p = p->next;
122.    i = 1;
123.  }
124.  cout << endl;
125.  return 0;
126. }