[数据结构]一元n次多项式的抽象数据类型

一、问题描述

一元n次多项式是代数学中经常出现的代数式，对于一元n次多项式的操作有很重要的实际意义。由于一个一元n次多项式最多有n+1项，且互不相关，所以可以用一个线性表来保存一个多项式，从前至后次数递增。对于一个一元n次多项式，我们可以定义操作：多项式的加法、减法、乘法。

本次小作业采用了链式表示的线性表实现，且只实现了多项式的加法。我认为如果要实现多项式的乘法，顺序表示的线性表更合适。

二、数据结构——线性表

1、链式表示：

链式表示的线性表，每个单位元由数据域和指针域组成，数据域保存当前结点的数值，而指针域保存的是下一个逻辑位置的地址，以便于通过这个指针访问下一个结点。与顺序表示相比，链式表示具有插入、删除灵活方便的特点，然而访问不方便，只能够从头指针处遍历。

2、顺序表示：

顺序表示的线性表，用一段物理存储上连续的空间模拟线性表，以物理上的位置的顺序关系，表示逻辑上的顺序关系。由于其物理地址的相近，所以在访问方便的同时，出现了两个麻烦：一是当一次申请的空间不够时，只能重新申请一段更大的空间，把之前的所有数据按顺序“搬”过去，否则无法保证其物理顺序的连续性；二是当线性表需要插入、删除操作时，需要对一部分数据进行“移位”操作，时间复杂度高。

3、基于本小作业对两种表示的对比分析：

此次作业是要求做两个一元n次多项式的加法，抽象到ADT上来看，就是两个线性表的分项加法，所以不涉及到结点的插入、删除操作，于是链式表示的优势被削弱，而顺序表示的劣势不那么明显了。相比较而言，两者的实现没什么区别，所以我选择了链式表示来实现。

更多地来想，如果需要做多项式的乘法，那么顺序表示就比链式表示的优势要大了。多项式乘法的算法核心可以大致说明为：LC(i+j-1) += LA(i)*LB(j)。这里涉及到寻找i+j-1位置的LC的值并进行修改的操作，如果使用顺序表示更方便找到该位置。

三、算法的设计及实现

（1）建立线性表LA和LB，并读入数据。

（2）将LB中的每一项按顺序逐项加到LA中对应的项。

（3）如果LB比LA长，则把LB中剩余元素按顺序依次加到LA中。

（4）最后得到的LA就是最终结果。

四、预期结果和实验中的问题

1、预期结果：

输入两个一元n次多项式的各项系数后，按照次数递增分别保存在LA和LB中，然后将LB中的每一项对应加在LA中。

如LA={1,2,3,4,5,6}表示fa(x)=1+2*x+3*x^2+4*x^3+5*x^4+6*x^5，LB={2,2,3}表示fb(x)=2+2*x+3*x^2，则得到的结果应该是{3,4,6,4,5,6}表示fa(x)+fb(x)=3+4*x+6*x^2+4*x^3+5*x^4+6*x^5。

2、实验中的问题：

除去线性表实现的一些细节问题以外，还有针对此次小作业的问题。

上面有提到的是，如果要实现多项式的乘法，若使用顺序表示的线性表，则可以直接遍历LA和LB，每一个合法位置执行LC(i+j-1) += LA(i)*LB(j)就可以了；而假如要使用链式表示的线性表来实现，如果继续按照顺序表示的方式来遍历LA和LB，这样处理LC的位置在不停地变动，查找该位置时间开销很大，所以可以选择遍历i+j-1的值，对于一个固定的i+j-1，通过遍历i求出j的值来计算LC(i+j-1)的值。

我也思考了多项式除法的问题，发现涉及到数论的一些结论，类似于高精度数除以高精度数，还没有比较好的处理方式。当然，带余除法是可以用LA一直减去LB直到0<LA<LB为止。

附：c++源代码：

  1 #include <iostream>

  2 #include <cstdio>

  3

  4 using namespace std;

  5

  6 struct node

  7 {

  8     int Num;

  9     node *next;

 10 };

 11

 12 class MyList

 13 {

 14 private:

 15     int Len;

 16     node *pHead;

 17

 18 public:

 19     void InitList()//构造一个空的线性表

 20     {

 21         Len = 0;

 22         pHead = NULL;

 23     }

 24     void ClearList()//重置为空表

 25     {

 26         node *Tmp;

 27         while(pHead)

 28         {

 29             Tmp = pHead;

 30             pHead = pHead -> next;

 31             delete Tmp;

 32         }

 33         Len = 0;

 34     }

 35     bool ListEmpty()//判断L是否为空表

 36     {

 37         return pHead == NULL;

 38     }

 39     int ListLength()//返回L中数据元素个数

 40     {

 41         return Len;

 42     }

 43     bool GetElem(int Pos, int &e)//返回第Pos个元素，出错返回true

 44     {

 45         if(Pos < 1 || Pos > Len)

 46         {

 47             printf("Wrong position!\n");

 48             return true;

 49         }

 50         node *Cur = pHead;

 51         int Index = 0;

 52         while(++Index < Pos && Cur)

 53             Cur = Cur -> next;

 54         e = Cur -> Num;

 55         return false;

 56     }

 57     //LocateElem(L, e, compare())//返回L中第一个与e满足关系compare()的元素的位序，不存在返回0

 58     bool PriorElem(int e, int &Pre_e)//若e是L中的元素，返回e的前躯，失败时返回true

 59     {

 60         if(pHead -> Num == e)

 61         {

 62             printf("Cannot find the precursor!\n");

 63             return true;

 64         }

 65         node *Cur = pHead, *Prev;

 66         while(Cur)

 67         {

 68             if(Cur -> Num == e)

 69                 break;

 70             Prev = Cur;

 71             Cur = Cur -> next;

 72         }

 73         if(!Cur)

 74         {

 75             printf("Cannot find the element!\n");

 76             return true;

 77         }

 78         Pre_e = Prev -> Num;

 79         return false;

 80     }

 81     bool NextElem(int e, int &Next_e)//若e是L中的元素，返回e的后继，错误时返回true

 82     {

 83         node *Cur = pHead;

 84         while(Cur)

 85         {

 86             if(Cur -> Num == e)

 87                 break;

 88             Cur = Cur -> next;

 89         }

 90         if(!Cur)

 91         {

 92             printf("Cannot find the element!\n");

 93             return true;

 94         }

 95         Cur = Cur -> next;

 96         if(!Cur)

 97         {

 98             printf("Cannot find the successor!\n");

 99             return true;

100         }

101         Next_e = Cur -> Num;

102         return false;

103     }

104     bool ListInsert(int Pos, int e)//在Pos位置插入元素e，失败时返回true

105     {

106         if(Pos < 1 || Pos > Len + 1)

107         {

108             printf("Wrong position!\n");

109             return true;

110         }

111         node *InsElem = new node;

112         if(Pos == 1)

113         {

114             InsElem -> next = pHead;

115             pHead = InsElem;

116             InsElem -> Num = e;

117         }

118         else

119         {

120             node *Cur = pHead;

121             int Index = 0;

122             while(++Index + 1 < Pos && Cur)

123                 Cur = Cur -> next;

124             InsElem -> next = Cur -> next;

125             Cur -> next = InsElem;

126             InsElem -> Num = e;

127         }

128         Len++;

129         return false;

130     }

131     bool ListDelete(int Pos, int &e)//删除Pos位置的元素，用e返回，错误时返回true

132     {

133         if(Pos < 1 || Pos > Len)

134         {

135             printf("Wrong position!\n");

136             return true;

137         }

138         node *DelElem = pHead;

139         if(Pos == 1)

140         {

141             pHead = DelElem -> next;

142             e = DelElem -> Num;

143             delete DelElem;

144         }

145         else

146         {

147             node *Prev;

148             int Index = 0;

149             while(++Index < Pos && DelElem)

150             {

151                 Prev = DelElem;

152                 DelElem = DelElem -> next;

153             }

154             Prev -> next = DelElem -> next;

155             e = DelElem -> Num;

156             delete DelElem;

157         }

158         Len--;

159         return false;

160     }

161     //ListTraverse(L, visit())//依次对L中的每个数据元素调用函数visit()，一旦visit()失败，则操作失败

162     void PrintList()

163     {

164         if(ListEmpty())

165         {

166             printf("The List is empty!\n");

167             return ;

168         }

169         node *Cur = pHead;

170         int Index = 0;

171         while(++Index < Len && Cur)

172         {

173             printf("%d ",Cur -> Num);

174             Cur = Cur -> next;

175         }

176         printf("%d\n",Cur -> Num);

177     }

178     bool ElemPrio(node a, node b)

179     {

180         return a.Num < b.Num;

181     }

182     bool ChangeElem(int Pos, int El) //把Pos位置元素的值改为El，失败返回true

183     {

184         if(Pos < 1 || Pos > Len)

185         {

186             printf("Wrong position!\n");

187             return true;

188         }

189         node *Cur = pHead;

190         int Index = 0;

191         while(++Index < Pos && Cur)

192             Cur = Cur -> next;

193         Cur -> Num = El;

194         return false;

195     }

196     void MergeList(MyList Lb) //把Lb插入L中

197     {

198         int aElem, bElem, aIndex = 0;

199         while(aIndex < Len && (!Lb.ListEmpty()))

200         {

201             GetElem(++aIndex, aElem);

202             Lb.GetElem(1, bElem);

203             if(aElem > bElem)

204             {

205                 Lb.ListDelete(1, bElem);

206                 ListInsert(aIndex, bElem);

207             }

208         }

209         while(!Lb.ListEmpty())

210         {

211             Lb.ListDelete(1, bElem);

212             ListInsert(Len + 1, bElem);

213         }

214     }

215     void AddList(MyList Lb) //按项加法，把Lb往L中加

216     {

217         if(Lb.ListEmpty())

218             return ;

219         int bElem;

220         node *Cur = pHead;

221         while(Cur && (!Lb.ListEmpty()))

222         {

223             Lb.ListDelete(1, bElem);

224             Cur -> Num += bElem;

225             Cur = Cur -> next;

226         }

227         while(!Lb.ListEmpty())

228         {

229             Lb.ListDelete(1, bElem);

230             ListInsert(Len, bElem);

231         }

232     }

233     void PrintList_ForPolynomial()

234     {

235         if(ListEmpty())

236         {

237             printf("There is something wrong!\n");

238             return ;

239         }

240         node *Cur = pHead;

241         int Index = 0;

242         while(++Index < Len && Cur)

243         {

244             if(Index == 1)

245                 printf("%d + ", Cur -> Num);

246             else if(Index == 2)

247                 printf("%d * x + ", Cur -> Num);

248             else

249                 printf("%d * x^%d + ", Cur -> Num, Index - 1);

250             Cur = Cur -> next;

251         }

252         if(Index == 1)

253             printf("%d\n", Cur -> Num);

254         else if(Index == 2)

255             printf("%d * x\n", Cur -> Num);

256         else

257             printf("%d * x^%d\n", Cur -> Num, Index - 1);

258     }

259 };

260

261 void Read(MyList &L)

262 {

263     int n, i, Elem;

264     L.InitList();

265     printf("Please input a number n.\n");

266     scanf("%d", &n);

267     printf("Please input n+1 numbers means a0+a1*x+a2*x^2+...+an*x^n.\n");

268     for(i = 1; i <= n + 1; i++)

269     {

270         scanf("%d", &Elem);

271         L.ListInsert(i, Elem);

272     }

273 }

274

275 int main()

276 {

277     MyList La, Lb;

278     Read(La);

279     Read(Lb);

280     printf("La(x) = ");

281     La.PrintList_ForPolynomial();

282     printf("Lb(x) = ");

283     Lb.PrintList_ForPolynomial();

284     La.AddList(Lb);

285     printf("La(x) + Lb(x) = ");

286     La.PrintList_ForPolynomial();

287     return 0;

288 }

巴特西