实验一 一元稀疏多项式的计算
一、实验目的
通过一元稀疏多项式的表示和计算，帮助学生熟练掌握线性表的基本操作，以及用线性链表表示线性表的存储结构和操作的实现。
二、实验内容
实现一元稀疏多项式的如下运算：
(1)两个一元稀疏多项式相加运算
(2)两个一元稀疏多项式相减运算
(3)两个一元稀疏多项式相乘运算
三、实验原理
1、一元多项式的逻辑表示
一元多项式pn(x)可表示成:
pn(x)=p0+p1x+p2x2+„+pnxn
n+1个系数可用线性表来表示：
p0，p1，p2，„，pn）
其中每一项的指数i隐含在其系数pi的序号中。
一个一元多项式，如果其系数不为0的项相对于其多项式的次数（最大指数）而言要少得多，则称该一元多项式为一元稀疏多项式。
对一元稀疏多项式，若采用顺序存储结构，需n+1个元素单元存放系数。当n很大且为零的系数较多时，既浪费存储空间，又浪费运算时间。如：
s(x)=1+3x10000+2x20000
采用顺序存储分配需20001个元素空间，但只有3个元素有意义。若参与同数量级的加法运算，要运行2000次以上。因此，对一元多项式采用链式存储结构是必然的选择。上例的链表表示形式如图1-1所示。
图1-1：一元稀疏多项式的链表表示示意图 2、一元稀疏多项式的链式存储表示
结点结构定义如下：
typedef struct Item{
double coef;
int expn;
struct Item *next;
}Item,*Polyn;
3、一元稀疏多项式运算原理
设有两个稀疏多项式A和B，其运算原理如下：
（1）两个多项式相加(C=A＋B)的运算原则：
指数相同，系数相加，若不为0，则在结果多项式中构成一新项。
指数不同，则两项分别抄入结果多项式中。
（2）两个多项式相减(C=A－B)的运算原则：
指数相同，系数相减，若不为0，则构成一新项。
指数不同，对A多项式的项，直接抄入结果多项式中。
对B多项式的项，系数符号变换后，再将放入结果多项式中
（3）两个多项式相乘(C=A×B)的运算原则
用B多项式的每一项分别去乘A多项式的每一项，并将乘得得结果放入结
果多项式中。
若结果多项式中有指数相同的项，则应把它们合并为一项。
四、实现
1、约定使用带头结点的链表表示一元稀疏多项式。
（2） 用线性链表表示的一元稀疏多项式中，各结点按指数的升序排列。
（3） 每个多项式都独立存在，即参与运算的两个多项式的数据不能因运算而受到破坏，加、减、乘运算的结果应相互不受影响。因此，对于每种情况都必须单独建立一个链表进行表示。
（4） 每一种重复性的操作都要进行确认，以免破坏原有操作的结果。如需要输入A多项式，而A多项式已经存在，这时通过“确认”后再确定是否真正需要输入。
2、基本功能
(1)多项式的输入
(2)两个一元稀疏多项式相加运算：P(x)+Q(x
(3)两个一元稀疏多项式相减运算：P(x)－Q(x)
(4)两个一元稀疏多项式相乘运算：P(x)×Q(x)
(5)多项式打印
3、辅助功能
(1)菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互式控制程序运行。
(2)插入结点位置查找：确定将一个新结点插入到多项式链表结构中的位置，以保证链表中结点按指数升序排列。
(3)交互选择：当出现重复性操作时，提供交互式选择方式，以确定其重复操作是否进行。
(4)撤消多项式：释放表示多项式链表中所有结点的存储空间。
(5)多项式项插入：将表示多项式中一项的结点插入到链表中给定的位置。
(6)判多项式非空：判断某个多项式是否存在。
(7)判断两个多项式的当前运算项的关系（指数大于，等于，小于）
4、程序结构
本程序可以由13个函数组成，其中主函数1个，基本功能函数5个，辅助功能函数7个。函数间的调用关系图1-2所示。
图1-2：程序结构示意图
5、程序函数
（1）主函数：main
功能：通过菜单选择控制对系统功能的操作
（2）菜单选择函数：menu
函数格式： int menu(void)
函数功能：构造功能菜单，并选择下一步要操作的功能。
函数参数：无参数。
函数返回值：1～11中的一个序号。
可供选择的功能如下：
1--create P(x) 表示生成P多项式
2--create Q(x) 表示生成Q多项式
3--p(x)+Q(x) 表示两多项式相加
4--P(x)-Q(x) 表示两多项式相减
5--p(x)*Q(x) 表示两多项式相乘
6--print P(x) 表示打印P多项式
7--print Q(x) 表示打印Q多项式
8--print P(x)+Q(x) 表示打印两多项式相加的结果
9--print P(x)-Q(x) 表示打印两多项式相减的结果
10--print P(x)*Q(x) 表示打印两多项式相乘的结果
11—Quit 表示退出系统，结束程序的运行
在运行过程中，输入其中一个序号，即表示下一步执行后面的功能。如输入3，
表示执行P(x)+(x)额运算。
(3)输入多项式函数：input
函数格式：Polyn Input(void)
函数参数：无参数
函数功能：输入多项式各项的系数和指数，生成一个多项式链表。
函数返回值：指向一个多项式链表的头指针
(4)两多项式相加函数： AddPolyn
函数格式 Polyn AddPolyn(Polyn h1,Polyn h2)
函数功能：实现两个多项式h1和h2相加。
函数参数：Polyn h1—指向第一个多项式链表的头指针
Polyn h2—指向第二个多项式链表的头指针
函数返回值：指向相加后的结果链表的头指针
(5)两多项式相减函数： SubtractPolyn
函数格式 Polyn SubtractPolyn(Polyn h1,Polyn h2)
函数功能：实现两个多项式h1和h2相减。
函数参数：Polyn h1—指向第一个多项式链表的头指针
Polyn h2—指向第二个多项式链表的头指针
函数返回值：指向相减后的结果链表的头指针
(6)两多项式相乘函数： MultPolyn
函数格式 Polyn MultPolyn(Polyn h1,Polyn h2)
函数功能：实现两个多项式h1和h2相乘。
函数参数：Polyn h1—指向第一个多项式链表的头指针
Polyn h2—指向第二个多项式链表的头指针
函数返回值：指向相乘后的结果链表的头指针
(7)显示多项式函数：Output
函数格式：void Output(Polyn h,char *title)
函数功能：输出多项式的完整表示。如：
P(x)=1.00+2.50x^3-3.5x^9
函数参数：Polyn h－要输出的多项式链表的头指针
char *title－字符串，提示要输出一个什么样的多项式，如“P(x)”。
函数返回值：无返回值。
(8)判断选择函数：Select
函数格式：int Select(char *str)
函数功能：根据str提示的内容判断是执行指定的操作，还是不执行。输入
“Y”则表示执行，若输入“N”表示不执行。如当P(x)多项式已经产生
后，若再选择产生P(x)，这是提示：
P(x) is not Empty,Create P(x) again?
Input Y or N:
若输入“Y”则表示重新产生多项式P(x)，若输入“N”表示维持原多
项式不变。
函数参数：char *str－将要确定的内容。
函数返回值：1－表示执行指定的操作
0－表示不执行指定的操作
(9)插入位置定位函数：InsertLocate
函数格式： int InsertLocate(Polyn h,int expn,Item **p)
函数功能：确定新结点的插入位置。其插入位置的确定是保证多项式链表按
指数递增排列的关键。
函数参数：Polyn h－要查找的多项式链表的头指针
int expn－新插入项的指数值。
Item **p－插入位置的前驱结点指针，由该函数的调用而被确定的内
容。新结点一定插入到该结点的后面。
函数返回值：-1－若指数expn值在某两个结点之间，则返回－1，参数p带回
的值为指数值小于expn的结点指针。
0－若指数expn值等于某结点的指数值，则返回0，参数p带回
的值为指数值等于expn的结点指针。
1－若指数expn值大于最后一个结点的指数值，则返回1，参数
p带回最后一个结点的指针
（10）结点插入函数：insert
函数格式：void insert(Item *pre,Item *p)
函数功能：在指定结点pre后插入一个新结点p。
函数参数：Item *pre－被插入结点的前驱结点
Item *p－要插入的新结点
函数返回值：无
（11）撤消链表函数：Destroy
函数格式：void Destroy(Polyn h)
函数功能：释放链表所占用的存储空间
函数参数：Polyn h－被撤消的链表的头指针
函数返回值：无
（12）判链表非空函数： PolynNotEmpty
函数格式：int PolynNotEmpty(Polyn h,char *p)
函数功能：判断链表是否非空，即代表了一个真正的多项式。
函数参数：Polyn h－多项式链表的头指针
char *p－多项式名
函数返回值：0—链表为空
1—链表不为空
(13)比较多项式两项关系函数：ItemComp
函数格式：int ItemComp(Item x Item y)
函数功能：根据两个多项式项的指数判断它们的关系。
函数参数：Item x－表示多项式项的变量
Item y－表示多项式项的变量
函数返回值：-1—x项的指数小于y项的指数
0—x项的指数等于y项的指数
1—x项的指数大于y项的指数
五、部分算法描述
两个多项式相加运算的算法参见教科书的描述。
两个多项式相减运算算法与多项式相加运算的算法结构一致，只是把Q(x)多项式的结点作为独立的一项时，其系数应改变其正/负号。
这里只对两个多项式相乘运算的算法加以描述。两个多项式相乘运算的基本原理是：用Q(x)多项式的每一项分别去乘P(x)多项式的每一项，并将乘得得结果放入结果多项式中。若结果多项式中有指数相同的项，则应把它们合并为一项。这实际上是运用加法运算来实现乘法运算，实现时有两种不同的方法把每次计算的结果与原来的中间结果进行相加。
【算法1】基本思想：把Q(x)多项式的每一项分别去乘P(x)多项式的每一项所得到的每一个结果（一个结点）插入到结果多项式中，若结果多项式中无相同指数的项，则生成一个新结点插入；若有相同指数的项，则系数相加。算法如图1-3所示。
【算法2】基本思想：把Q(x)多项式的每一项分别去乘P(x)多项式得到一个新的多项式，然后把新多项式与结果多项式相加。算法如图3
所示。图1-3 两个多项式相乘算法1描述
七、思考题 图1-4 两个多项式相乘算法2描述
修改一元多项式相加运算的函数，实现：
1、 两个有序表合并为一个有序表。
2、 假设具有整数值的集合用有序的线性链表表示，实现求两个集合的联合运算，要求
结果集合中不能有两个值相同的元素。
八、部分函数代码
【说明】：为了使学生掌握复杂程序设计的基本方法和程序的结构，下面给出了几乎所有的辅助函数的程序代码，学生只需要完成稀疏多项式的加、减、乘运算的程序代码编写工作。希望学生通过下面程序代码的阅读、编码、测试和运算，掌握一个完整程序的基本结构和设计一个程序的基本方法。
#include
#include
#include
typedef struct Item{
double coef;
int expn;
struct Item *next;
}Item,*Polyn;
#define CreateItem(p) p=(Item *)malloc(sizeof(Item));
#define DeleteItem(p) free((void *)p);
/************************************************************/ /* 判断选择函数 */ /************************************************************/ int Select(char *str)
{ char ch;
printf(
printf(
do{ ch=getch();
}while(ch!='Y'&&ch!='y'&&ch!='N'&&ch!='n');
printf(
if(ch=='Y'||ch=='y') return(1);
else return(0);
}
/************************************************************/ /* 插入位置定位函数 */ /**************************************************************/ int InsertLocate(Polyn h,int expn,Item **p)
{ Item *pre,*q;
pre=h;
q=h->next;
while(q&&q->expn
{ pre=q;
q=q->next;
}
if(!q)
{ *p=pre;
return(1); }
else if(q->expn==expn)
{ *p=q;
return(0); }
else
{ *p=pre;
return(-1);
}
}
/************************************************************/ /* 插入结点函数 */ /************************************************************/ void insert(Item *pre,Item *p)
{
p->next=pre->next;
pre->next=p;
}
/************************************************************/ /* 输入多项式 */ /************************************************************/ Polyn Input(void)
{
double coef;
int expn,flag;
Item *h,*p,*q,*pp;
CreateItem(h);//产生头结点
h->next=NULL;
printf(
while(1)
{
scanf(
p->coef=coef;
p->expn=expn;
insert(pp,p);
}
else if(Select(
}
return h;
}
/************************************************************/ /* 撤消多项式 */ /************************************************************/ void Destroy(Polyn h)
{
Item *p=h,*q;
while(p!=NULL)
{
q=p;
p=p->next;
DeleteItem(q);
}
}
/************************************************************/ /* 输出多项式 */ /************************************************************/ void Output(Polyn h,char *title)
{
int flag=1;
Item *p=h->next;
printf(
while(p)
{ if(flag) //表示是否是多项式的第一项
{ flag=0;
if(p->expn==0) } printf(
else
{ if(p->coef>0) printf(
if(p->expn==0) printf(
p=p->next;
}
printf(
}
/************************************************************/ /* 判断两个多项式项的关系 */ /************************************************************/ int ItemComp(Item x,Item y)
{ if(x.expn
return(-1);
else if(x.expn==y.expn)
return(0);
else return(1);
}
/************************************************************/ /* 两多项式多项式相加 */
/************************************************************/ Polyn AddPolyn(Polyn h1,Polyn h2)
{
Item *head,*last,*pa=h1->next,*pb=h2->next,*s,*s0;
double coef;
CreateItem(head);
last=head;
last->next=NULL;
return head;
}
/************************************************************/ /* 两多项式多项式相减 */ /************************************************************/ Polyn SubtractPolyn(Polyn h1,Polyn h2)
{ int flag;
Item *head,*last,*pa=h1->next,*pb=h2->next,*s,*s0;
double coef;
CreateItem(head);
last=head;
last->next=NULL;
return head;
}
/************************************************************/ /* 两多项式多项式相乘 */ /************************************************************/ Polyn MultPolyn(Polyn h1,Polyn h2) //两个多项式相乘
{ int item,expn;
Item *head,*pa,*pb=h2->next,*s,*pp;
double coef;
CreateItem(head);
head->next=NULL;
return head;
}
/************************************************************/ /* 菜单选择 */ /************************************************************/ int menu(void)
{ int num;
clrscr();
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
do{
scanf(
return(num);
}
/************************************************************/ /* 判断多项式是否存在 */ /************************************************************/ int PolynNotEmpty(Polyn h,char *p)
{ if(h==NULL)
{ printf(
getchar();
return(0);
}
else return(1);
}
/************************************************************/ /* 主函数 */ /************************************************************/ void main()
{ int num;
Polyn h1=NULL; //p(x) Polyn h2=NULL; //Q(x)
Polyn h3=NULL; //P(x)+Q(x) Polyn h4=NULL; //P(x)-Q(x) Polyn h5=NULL; //P(x)*Q(x) while(1)
{ num=menu();
getchar();
switch(num)
{
case 1: //输入第一个多项式，若多项式存在，首先撤消然后再输入 if(h1!=NULL) { if(Select(
case 5: //两多项式相乘 { h5=MultPolyn(h1,h2); printf(
if(h4!=NULL) Destroy(h4); if(h4!=NULL) Destroy(h5); }
if(num==11) break; }
getch();
}
实验一 一元稀疏多项式的计算
一、实验目的
通过一元稀疏多项式的表示和计算，帮助学生熟练掌握线性表的基本操作，以及用线性链表表示线性表的存储结构和操作的实现。
二、实验内容
实现一元稀疏多项式的如下运算：
(1)两个一元稀疏多项式相加运算
(2)两个一元稀疏多项式相减运算
(3)两个一元稀疏多项式相乘运算
三、实验原理
1、一元多项式的逻辑表示
一元多项式pn(x)可表示成:
pn(x)=p0+p1x+p2x2+„+pnxn
n+1个系数可用线性表来表示：
p0，p1，p2，„，pn）
其中每一项的指数i隐含在其系数pi的序号中。
一个一元多项式，如果其系数不为0的项相对于其多项式的次数（最大指数）而言要少得多，则称该一元多项式为一元稀疏多项式。
对一元稀疏多项式，若采用顺序存储结构，需n+1个元素单元存放系数。当n很大且为零的系数较多时，既浪费存储空间，又浪费运算时间。如：
s(x)=1+3x10000+2x20000
采用顺序存储分配需20001个元素空间，但只有3个元素有意义。若参与同数量级的加法运算，要运行2000次以上。因此，对一元多项式采用链式存储结构是必然的选择。上例的链表表示形式如图1-1所示。
图1-1：一元稀疏多项式的链表表示示意图 2、一元稀疏多项式的链式存储表示
结点结构定义如下：
typedef struct Item{
double coef;
int expn;
struct Item *next;
}Item,*Polyn;
3、一元稀疏多项式运算原理
设有两个稀疏多项式A和B，其运算原理如下：
（1）两个多项式相加(C=A＋B)的运算原则：
指数相同，系数相加，若不为0，则在结果多项式中构成一新项。
指数不同，则两项分别抄入结果多项式中。
（2）两个多项式相减(C=A－B)的运算原则：
指数相同，系数相减，若不为0，则构成一新项。
指数不同，对A多项式的项，直接抄入结果多项式中。
对B多项式的项，系数符号变换后，再将放入结果多项式中
（3）两个多项式相乘(C=A×B)的运算原则
用B多项式的每一项分别去乘A多项式的每一项，并将乘得得结果放入结
果多项式中。
若结果多项式中有指数相同的项，则应把它们合并为一项。
四、实现
1、约定使用带头结点的链表表示一元稀疏多项式。
（2） 用线性链表表示的一元稀疏多项式中，各结点按指数的升序排列。
（3） 每个多项式都独立存在，即参与运算的两个多项式的数据不能因运算而受到破坏，加、减、乘运算的结果应相互不受影响。因此，对于每种情况都必须单独建立一个链表进行表示。
（4） 每一种重复性的操作都要进行确认，以免破坏原有操作的结果。如需要输入A多项式，而A多项式已经存在，这时通过“确认”后再确定是否真正需要输入。
2、基本功能
(1)多项式的输入
(2)两个一元稀疏多项式相加运算：P(x)+Q(x
(3)两个一元稀疏多项式相减运算：P(x)－Q(x)
(4)两个一元稀疏多项式相乘运算：P(x)×Q(x)
(5)多项式打印
3、辅助功能
(1)菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互式控制程序运行。
(2)插入结点位置查找：确定将一个新结点插入到多项式链表结构中的位置，以保证链表中结点按指数升序排列。
(3)交互选择：当出现重复性操作时，提供交互式选择方式，以确定其重复操作是否进行。
(4)撤消多项式：释放表示多项式链表中所有结点的存储空间。
(5)多项式项插入：将表示多项式中一项的结点插入到链表中给定的位置。
(6)判多项式非空：判断某个多项式是否存在。
(7)判断两个多项式的当前运算项的关系（指数大于，等于，小于）
4、程序结构
本程序可以由13个函数组成，其中主函数1个，基本功能函数5个，辅助功能函数7个。函数间的调用关系图1-2所示。
图1-2：程序结构示意图
5、程序函数
（1）主函数：main
功能：通过菜单选择控制对系统功能的操作
（2）菜单选择函数：menu
函数格式： int menu(void)
函数功能：构造功能菜单，并选择下一步要操作的功能。
函数参数：无参数。
函数返回值：1～11中的一个序号。
可供选择的功能如下：
1--create P(x) 表示生成P多项式
2--create Q(x) 表示生成Q多项式
3--p(x)+Q(x) 表示两多项式相加
4--P(x)-Q(x) 表示两多项式相减
5--p(x)*Q(x) 表示两多项式相乘
6--print P(x) 表示打印P多项式
7--print Q(x) 表示打印Q多项式
8--print P(x)+Q(x) 表示打印两多项式相加的结果
9--print P(x)-Q(x) 表示打印两多项式相减的结果
10--print P(x)*Q(x) 表示打印两多项式相乘的结果
11—Quit 表示退出系统，结束程序的运行
在运行过程中，输入其中一个序号，即表示下一步执行后面的功能。如输入3，
表示执行P(x)+(x)额运算。
(3)输入多项式函数：input
函数格式：Polyn Input(void)
函数参数：无参数
函数功能：输入多项式各项的系数和指数，生成一个多项式链表。
函数返回值：指向一个多项式链表的头指针
(4)两多项式相加函数： AddPolyn
函数格式 Polyn AddPolyn(Polyn h1,Polyn h2)
函数功能：实现两个多项式h1和h2相加。
函数参数：Polyn h1—指向第一个多项式链表的头指针
Polyn h2—指向第二个多项式链表的头指针
函数返回值：指向相加后的结果链表的头指针
(5)两多项式相减函数： SubtractPolyn
函数格式 Polyn SubtractPolyn(Polyn h1,Polyn h2)
函数功能：实现两个多项式h1和h2相减。
函数参数：Polyn h1—指向第一个多项式链表的头指针
Polyn h2—指向第二个多项式链表的头指针
函数返回值：指向相减后的结果链表的头指针
(6)两多项式相乘函数： MultPolyn
函数格式 Polyn MultPolyn(Polyn h1,Polyn h2)
函数功能：实现两个多项式h1和h2相乘。
函数参数：Polyn h1—指向第一个多项式链表的头指针
Polyn h2—指向第二个多项式链表的头指针
函数返回值：指向相乘后的结果链表的头指针
(7)显示多项式函数：Output
函数格式：void Output(Polyn h,char *title)
函数功能：输出多项式的完整表示。如：
P(x)=1.00+2.50x^3-3.5x^9
函数参数：Polyn h－要输出的多项式链表的头指针
char *title－字符串，提示要输出一个什么样的多项式，如“P(x)”。
函数返回值：无返回值。
(8)判断选择函数：Select
函数格式：int Select(char *str)
函数功能：根据str提示的内容判断是执行指定的操作，还是不执行。输入
“Y”则表示执行，若输入“N”表示不执行。如当P(x)多项式已经产生
后，若再选择产生P(x)，这是提示：
P(x) is not Empty,Create P(x) again?
Input Y or N:
若输入“Y”则表示重新产生多项式P(x)，若输入“N”表示维持原多
项式不变。
函数参数：char *str－将要确定的内容。
函数返回值：1－表示执行指定的操作
0－表示不执行指定的操作
(9)插入位置定位函数：InsertLocate
函数格式： int InsertLocate(Polyn h,int expn,Item **p)
函数功能：确定新结点的插入位置。其插入位置的确定是保证多项式链表按
指数递增排列的关键。
函数参数：Polyn h－要查找的多项式链表的头指针
int expn－新插入项的指数值。
Item **p－插入位置的前驱结点指针，由该函数的调用而被确定的内
容。新结点一定插入到该结点的后面。
函数返回值：-1－若指数expn值在某两个结点之间，则返回－1，参数p带回
的值为指数值小于expn的结点指针。
0－若指数expn值等于某结点的指数值，则返回0，参数p带回
的值为指数值等于expn的结点指针。
1－若指数expn值大于最后一个结点的指数值，则返回1，参数
p带回最后一个结点的指针
（10）结点插入函数：insert
函数格式：void insert(Item *pre,Item *p)
函数功能：在指定结点pre后插入一个新结点p。
函数参数：Item *pre－被插入结点的前驱结点
Item *p－要插入的新结点
函数返回值：无
（11）撤消链表函数：Destroy
函数格式：void Destroy(Polyn h)
函数功能：释放链表所占用的存储空间
函数参数：Polyn h－被撤消的链表的头指针
函数返回值：无
（12）判链表非空函数： PolynNotEmpty
函数格式：int PolynNotEmpty(Polyn h,char *p)
函数功能：判断链表是否非空，即代表了一个真正的多项式。
函数参数：Polyn h－多项式链表的头指针
char *p－多项式名
函数返回值：0—链表为空
1—链表不为空
(13)比较多项式两项关系函数：ItemComp
函数格式：int ItemComp(Item x Item y)
函数功能：根据两个多项式项的指数判断它们的关系。
函数参数：Item x－表示多项式项的变量
Item y－表示多项式项的变量
函数返回值：-1—x项的指数小于y项的指数
0—x项的指数等于y项的指数
1—x项的指数大于y项的指数
五、部分算法描述
两个多项式相加运算的算法参见教科书的描述。
两个多项式相减运算算法与多项式相加运算的算法结构一致，只是把Q(x)多项式的结点作为独立的一项时，其系数应改变其正/负号。
这里只对两个多项式相乘运算的算法加以描述。两个多项式相乘运算的基本原理是：用Q(x)多项式的每一项分别去乘P(x)多项式的每一项，并将乘得得结果放入结果多项式中。若结果多项式中有指数相同的项，则应把它们合并为一项。这实际上是运用加法运算来实现乘法运算，实现时有两种不同的方法把每次计算的结果与原来的中间结果进行相加。
【算法1】基本思想：把Q(x)多项式的每一项分别去乘P(x)多项式的每一项所得到的每一个结果（一个结点）插入到结果多项式中，若结果多项式中无相同指数的项，则生成一个新结点插入；若有相同指数的项，则系数相加。算法如图1-3所示。
【算法2】基本思想：把Q(x)多项式的每一项分别去乘P(x)多项式得到一个新的多项式，然后把新多项式与结果多项式相加。算法如图3
所示。图1-3 两个多项式相乘算法1描述
七、思考题 图1-4 两个多项式相乘算法2描述
修改一元多项式相加运算的函数，实现：
1、 两个有序表合并为一个有序表。
2、 假设具有整数值的集合用有序的线性链表表示，实现求两个集合的联合运算，要求
结果集合中不能有两个值相同的元素。
八、部分函数代码
【说明】：为了使学生掌握复杂程序设计的基本方法和程序的结构，下面给出了几乎所有的辅助函数的程序代码，学生只需要完成稀疏多项式的加、减、乘运算的程序代码编写工作。希望学生通过下面程序代码的阅读、编码、测试和运算，掌握一个完整程序的基本结构和设计一个程序的基本方法。
#include
#include
#include
typedef struct Item{
double coef;
int expn;
struct Item *next;
}Item,*Polyn;
#define CreateItem(p) p=(Item *)malloc(sizeof(Item));
#define DeleteItem(p) free((void *)p);
/************************************************************/ /* 判断选择函数 */ /************************************************************/ int Select(char *str)
{ char ch;
printf(
printf(
do{ ch=getch();
}while(ch!='Y'&&ch!='y'&&ch!='N'&&ch!='n');
printf(
if(ch=='Y'||ch=='y') return(1);
else return(0);
}
/************************************************************/ /* 插入位置定位函数 */ /**************************************************************/ int InsertLocate(Polyn h,int expn,Item **p)
{ Item *pre,*q;
pre=h;
q=h->next;
while(q&&q->expn
{ pre=q;
q=q->next;
}
if(!q)
{ *p=pre;
return(1); }
else if(q->expn==expn)
{ *p=q;
return(0); }
else
{ *p=pre;
return(-1);
}
}
/************************************************************/ /* 插入结点函数 */ /************************************************************/ void insert(Item *pre,Item *p)
{
p->next=pre->next;
pre->next=p;
}
/************************************************************/ /* 输入多项式 */ /************************************************************/ Polyn Input(void)
{
double coef;
int expn,flag;
Item *h,*p,*q,*pp;
CreateItem(h);//产生头结点
h->next=NULL;
printf(
while(1)
{
scanf(
p->coef=coef;
p->expn=expn;
insert(pp,p);
}
else if(Select(
}
return h;
}
/************************************************************/ /* 撤消多项式 */ /************************************************************/ void Destroy(Polyn h)
{
Item *p=h,*q;
while(p!=NULL)
{
q=p;
p=p->next;
DeleteItem(q);
}
}
/************************************************************/ /* 输出多项式 */ /************************************************************/ void Output(Polyn h,char *title)
{
int flag=1;
Item *p=h->next;
printf(
while(p)
{ if(flag) //表示是否是多项式的第一项
{ flag=0;
if(p->expn==0) } printf(
else
{ if(p->coef>0) printf(
if(p->expn==0) printf(
p=p->next;
}
printf(
}
/************************************************************/ /* 判断两个多项式项的关系 */ /************************************************************/ int ItemComp(Item x,Item y)
{ if(x.expn
return(-1);
else if(x.expn==y.expn)
return(0);
else return(1);
}
/************************************************************/ /* 两多项式多项式相加 */
/************************************************************/ Polyn AddPolyn(Polyn h1,Polyn h2)
{
Item *head,*last,*pa=h1->next,*pb=h2->next,*s,*s0;
double coef;
CreateItem(head);
last=head;
last->next=NULL;
return head;
}
/************************************************************/ /* 两多项式多项式相减 */ /************************************************************/ Polyn SubtractPolyn(Polyn h1,Polyn h2)
{ int flag;
Item *head,*last,*pa=h1->next,*pb=h2->next,*s,*s0;
double coef;
CreateItem(head);
last=head;
last->next=NULL;
return head;
}
/************************************************************/ /* 两多项式多项式相乘 */ /************************************************************/ Polyn MultPolyn(Polyn h1,Polyn h2) //两个多项式相乘
{ int item,expn;
Item *head,*pa,*pb=h2->next,*s,*pp;
double coef;
CreateItem(head);
head->next=NULL;
return head;
}
/************************************************************/ /* 菜单选择 */ /************************************************************/ int menu(void)
{ int num;
clrscr();
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
printf(
do{
scanf(
return(num);
}
/************************************************************/ /* 判断多项式是否存在 */ /************************************************************/ int PolynNotEmpty(Polyn h,char *p)
{ if(h==NULL)
{ printf(
getchar();
return(0);
}
else return(1);
}
/************************************************************/ /* 主函数 */ /************************************************************/ void main()
{ int num;
Polyn h1=NULL; //p(x) Polyn h2=NULL; //Q(x)
Polyn h3=NULL; //P(x)+Q(x) Polyn h4=NULL; //P(x)-Q(x) Polyn h5=NULL; //P(x)*Q(x) while(1)
{ num=menu();
getchar();
switch(num)
{
case 1: //输入第一个多项式，若多项式存在，首先撤消然后再输入 if(h1!=NULL) { if(Select(
case 5: //两多项式相乘 { h5=MultPolyn(h1,h2); printf(
if(h4!=NULL) Destroy(h4); if(h4!=NULL) Destroy(h5); }
if(num==11) break; }
getch();
}