●试题六 阅读下列程序说明和C＋＋代码,将应填入(n)处的字句写在答卷的对应栏内。 【程序6说明】 本

Question

●试题六

阅读下列程序说明和C++代码，将应填入(n)处的字句写在答卷的对应栏内。

【程序6说明】

本程序实现两个多项式的乘积运算。多项式的每一项由类Item描述，而多项式由类List描述。类List的成员函数有：

createList()：创建按指数降序链接的多项式链表，以表示多项式。

reverseList()：将多项式链表的表元链接顺序颠倒。

multiplyList(List L1，List L2)：计算多项式L1和多项式L2的乘积多项式。

【程序6】

#include<iostream.h>

class List；

class ltem{

friend class List；

private：

double quot；

int exp；

Item*next；

public：

Item(double_quot，int_exp)

{ (1) ；}

}；

class List{

private:

Item*list；

public：

List(){list=NULL；}

void reverseList()；

void multiplyList(List L1，List L2)；

void createList()；

}；

void List::createList()

{Item*p，*u，*pre；

int exp；

double quot；

list=NULL；

while (1) {

cout<<"输入多项式中的一项(系数、指数)："<<endl；

cin>>quot>>exp：

if(exp<0)break；//指数小于零，结束输入

if(quot==0)continue；

p=list；

while( (2) ){//查找插入点

pre=p；p=p->next；}

if(p!=NULL&&exp==p->exp){ p->quot+=quot；continue；}

u= (3) ；

if(p==list) list=u；

else pre->next=u；

u->next=p；}

}

void List::reverseList()

{Item*p，*u；

if(list＝＝NULL)return；

p=list->next；list->next=NULL；

while(p!=NULL){

u=p->next；p->next=list；

list=p；p=u；}

}

void List::multiplyList(List L1，List L2)

{Item*pLl，*pL2，*u；

int k，maxExp；

double quot；

maxExp= (4) ；

L2．reverseList()；list=NULL;

for(k=maxExp；k>=0；k--){

pL1=L1．list；

while(pL1!=NULL&&pL1->exp>k)pL1=pL1->next；

pL2=L2．list；

while(pL2!=NULL&& (5) pL2=pL2->next；

quot=0．0；

while(pL1!=NULL&&pL2!=NULL){

if(pL1->exp+pL2->exp==k){

(6) ；

pL1=pL1->next；pL2=pL2->next；

}else if(pL1->exp+pL2->exp>k)pL1=pL1->next；

else pL2=pL2->next；

}

if(quot!=0．0){

u=new Item(quot，k)；

u->next=list；list=u；}

}

reverseList()；L2．reverseList()：

}

void main()

{ListL1，L2，L；

cout<<"创建第一个多项式链表＼n"；L1．createList()；

cout<<"创建第二个多项式链表＼n"；L2．createList()；

L．multiplyList(L1，L2)；

}

Answer 1

正确答案：

●试题六

【答案】（1）quot=_quot；exp=_exp；next=NULL；（2）p!=NULL && exp < p -> exp

（3）new Item （quot，exp）（4）L1.list -> exp + L2.list -> exp

（5）pL1 -> exp +pL2 -> exp < k（6）quot += pL1 -> quot * pL2 -> quot

【解析】程序主要由类Item和List组成，其中类Item定义多项式中的项，由三个私有成员组成分别是：系数quot、指数exp和指向多项式的下一项的指针next，该类定义了一个构造函数，其作用是创建系数为_quot、指数为_exp的项，即创建类Item的一个对象，因此（1）处应该填"quot=_quot;exp=_exp;next=NULL"。类List定义了多项式的操作，数据成员list是多项式链表的链头指针，类成员函数creatlist（）的功能是创建按照指数降序链接的多项式，创建的方法是不断将新的项插入到链表的合适位置上。若链表中存在一项p，其指数大于待插入项的指数，则待查入项为p的前驱。该成员函数在链表上遍历，直到找到满足上述条件的项；若链表中不存在这样的项，那么待插入项称为新的链尾。因此（2）处应填"p!=NULL&&exp<p->exp"；（3）处应填"new Item（quot,exp）"，根据读入的指数和系数创建要插入的项。若链表中存在指数与待插入项指数相等的项则合并同类项。

成员函数multiplyList（List L1,List L2）计算多项式L1和L2的乘积。首先计算了L1和L2的乘积多项式的最高幂次，即多项式L1和L2的最高此项的指数之和。由于多项式L1和L2是按照指数的降序排列的，两个多项式的第一项分别是最高幂项，这两项的指数之和就是乘积多项式的最高次幂，因此（4）处填"L1.list->exp+L2.list->exp"。

为了实现系数的乘积求和计算，当多项式L1从幂次高至幂次低逐一考虑各项的系数时，多项式L2应从幂次低至幂次高的顺序考虑各项的系数，以便将两多项式所有幂次和为k的两项系数相乘后累计。由于是单链表，所以成员函数先将其中多项式L2的链接顺序颠倒，计算完成之后，再将多项式L2的链接顺序颠倒，即恢复原来的链接顺序。乘积多项式从高次幂系数至0次幂系数的顺序逐一计算。

为求k次幂这一项的系数，对于L1的考查顺序是从高次幂项至最低次幂项，而对于L2的考查相反。首先跳过多项式L1中高于k次幂的项，设低于k次幂的项最高次幂是j次幂；对于多项式L2，跳过低于k-j次幂的项，因此（5）处应该填"pL1->exp+pL2->exp<k"。

考虑多项式L1和L2剩余各项的循环，若两多项式的当前项幂次和为k，则累计他们系数的乘积，并分别准备考虑下一项，因此（6）处应该填"quot+=pL1->quot*pL2->quot"；若两多项式的当前幂次和大于k，则应考虑幂次和更小的项，这样应该准备考虑多项式L1的下一项；若两多项式的当前幂次和小于k，则应考虑幂次和更大的项，这样应该准备考虑多项式L2的下一项。若所有幂次和为k的项的系数乘积之和不等于0，则应该在乘积多项式中有这一项，生成这一项的新结点，并将它插在乘积多项式的末尾。