重拾 ”多项式“ 给我的启示

多项式问题，是编程入门的一个基础题，可以使用数组或是指针来实现。当然使用数组会比较麻烦，因为需要大量的元素移动与删除操作，而这恰恰是链表所擅长的。顺便补充一点，对于删除较频繁的一组数据，使用链表可以省去大量时间以及少写很多代码；对于要求对特定元素进行操作（更新）的数据，我们通常使用数组。今天用链表再次写了一遍多项式，感触很深，同时也使我很无奈，因为指针这东西，好是好，只是它很暴躁！

先来照常贴一下题目吧：

一个多项式可以表达为x的各次幂与系数乘积的和，比如：2x6+3x5+12x3+6x+20。现在，你的程序要读入两个多项式，然后输出这两个多项式的和，也就是把对应的幂上的系数相加然后输出。

代码如下：

  1 #include <iostream>
  2 using namespace std;
  3 typedef struct prim {
  4     double factor;
  5     double exp;
  6     prim* next;
  7 }*pprim;
  8 
  9 //清空链表
 10 void mydelete(pprim& p)
 11 {
 12     if (!p)
 13     {
 14         return;
 15     }
 16     if (p->next)
 17     {
 18         mydelete(p->next);
 19     }
 20     delete p;
 21     p = NULL;
 22     return;
 23 }
 24 
 25 int main(int argc, char* argv[])
 26 {
 27     pprim hA, hB, tmp = NULL;
 28 
 29     //使用这些变量给多项式赋值
 30     pprim* ppApre = NULL, *ppAcur = NULL;
 31     pprim* ppBcur = NULL, *ppBpre = NULL;
 32 
 33     //使用这些变量让多项式相加
 34     pprim papre = NULL, pacur = NULL;
 35     pprim pbpre = NULL, pbcur = NULL;
 36 
 37     //n、m表示多项式A、B的项数
 38     int n, m;
 39     cin >> n >> m;
 40     hA = new prim;
 41     hA->next = NULL;
 42     hB = new prim;
 43     hB->next = NULL;
 44 
 45     cout << "多项式A:";
 46     while (n)
 47     {
 48         tmp = new prim;
 49         cin >> tmp->factor >> tmp->exp;
 50         tmp->next = NULL;
 51 
 52         //升序插入 
 53         ppApre = &hA;
 54         ppAcur = &(hA->next);
 55         if (*ppAcur == NULL)
 56         {
 57             *ppAcur = tmp;
 58         }
 59         else
 60         {
 61             while (*ppAcur && tmp->exp >= (*ppAcur)->exp)
 62             {
 63                 ppApre = ppAcur;
 64                 ppAcur = &((*ppAcur)->next);
 65             }
 66             tmp->next = *ppAcur;
 67             (*ppApre)->next = tmp;
 68         }
 69 
 70         --n;
 71     }
 72 
 73     cout << "多项式B:";
 74     while (m)
 75     {
 76         tmp = new prim;
 77         cin >> tmp->factor >> tmp->exp;
 78         tmp->next = NULL;
 79 
 80         //升序插入 
 81         ppBpre = &hB;
 82         ppBcur = &(hB->next);
 83         if (*ppBcur == NULL)
 84         {
 85             tmp->next = *ppBcur;
 86             (*ppBpre)->next = tmp;
 87         }
 88         else
 89         {
 90             while (*ppBcur && tmp->exp >= (*ppBcur)->exp)
 91             {
 92                 ppBpre = ppBcur;
 93                 ppBcur = &((*ppBcur)->next);
 94             }
 95             tmp->next = *ppBcur;
 96             (*ppBpre)->next = tmp;
 97         }
 98         --m;
 99     }
100 
101     //相加 
102     papre = hA;
103     pacur = hA->next;
104     pbpre = hB;
105     pbcur = hB->next;
106 
107     while (pacur && pbcur)
108     {
109         if (pacur->exp == pbcur->exp)
110         {
111             pacur->factor += pbcur->factor;
112             if (pacur->factor == 0.0)
113             {
114                 papre->next = pacur->next;
115                 delete pacur;
116                 pacur = papre->next;
117             }
118             else
119             {
120                 papre = pacur;
121                 pacur = papre->next;
122             }
123             pbpre->next = pbcur->next;
124             delete pbcur;
125             pbcur = pbpre->next;
126         }
127         else if (pacur->exp > pbcur->exp)
128         {
129             pbpre->next = pbcur->next;
130 
131             pbcur->next = pacur;
132             papre->next= pbcur;
133             papre = pacur;
134             pacur = papre->next;
135 
136             pbcur = pbpre->next;
137         }
138         else
139         {
140             papre = pacur;
141             pacur = papre->next;
142         }
143     }
144     if (pacur == NULL)
145     {
146         papre->next = pbcur;
147     }
148 
149     //输出 
150     pprim p = hA->next;
151     while (p)
152     {
153         cout << p->factor << "x(" << p->exp << ")";
154         p = p->next;
155         if (p)
156         {
157             cout << " + ";
158         }
159     }
160     cout << endl; 
161 
162     mydelete(hA);
163     return 0;
164 }
165

写这段代码时，让我很头痛的就是怎样定义指针变量。对指针还不熟悉或者想要加强一下的，可以看这里：http://www.cnblogs.com/ggjucheng/archive/2011/12/13/2286391.html 在我的第一版本代码里，用于给多项式赋值的指针我使用了一重指针，然程序每次运行都显示多项式为空（没有项），于是我仔细思索，发现我若要给多项式赋值，需要修改的是内存本身，而不是一个该内存的副本，但是我第一版本里边的一重指针在初始化时，恰恰被赋予了一个将要修改的内存的副本，于是，失败在所难免。解决办法是，你需要把你所要修改的内存地址赋值给一个二重指针，这样通过地址来访问并修改内存的内容是可行的。其实，恨多时候我们都会遇到这样的问题，就是虽然很明确的知道你要修改某个东西的值，可是总会不自觉的修改了它的副本，导致这个东西本身并没有改变。在这写出来警示自己同时也警示给位朋友。不过人非圣贤，孰能无过？不小心落入这个泥沼不要紧，很快反应过来并解决问题才是最要紧的。

最后补充一些可以修改内存本身的方法：①引用，c++特有的操作，它相当于给变量取了别名，对其修改也就相当于对内存本身做了修改。但高级引用的高级用法并不是拿来修改值，而是在参数传递时为了不产生临时变量而设置常量引用；或者是以引用作为函数返回值类型，这样可以进行一些特殊的操作（例如可以给函数赋值）等。②是指针，这就不用多说了，指针能修改内存是很基础的，但是应该提醒一点：如果要修改指针的值，则需要将指针的地址赋给指针的指针（话有点拗口，不过是真理）。

学习路上，大家共勉！

温润如玉，坚毅如铁。