《数据结构与算法》
（6）转入语句（4）；
（7）置q的直接后继为p，置L的直接后继为q。 算法实现
void Contray_L(LinkList &L) { if(!L->next||!L->next->next) return; LinkList p=L->next,q=p->next,r; p->next=NULL; while(r=q->next) { q->next=p;p=q;q=r;} q->next=p; L->next=q; } 算法分析
设链表的长度为n，由算法设计过程可知该算法的时间复杂度为O(n)，空间复杂度为O(1)。 【例2.8】现有两个递增有序的带有头结点的单链表L1、L2，要求将L2中的结点归并到L1中并保持L1仍然有序，并且在归并过程中不另设结点。 算法思想
总的想法是，从前往后将L2中的结点逐个插入到L1中，如果在此过程中有一个结点插入到L1的末尾，则将L2中剩余的部分链接到L1的尾部即可。 算法实现
void Merger_L(LinkList& L1,LinkList& L2) { LinkList p=L1,q=L2->next,r; L2->next=NULL; while(p->next&&q) { if(p->next->data
设L1的长度为m，L2的长度为n。算法的时间复杂度为O(m+n)，空间复杂度为O(1)。 【例2.9】用线性表表示一元多项式并实现多项式的加法、减法和乘法运算。
-.38.-
第2章 线性表及其应用
1．多项式的线性表示法
在数学上，一个n次多项式Pn(x)可按升幂写成：Pn(x)?p0?p1x?p2x2???pnxn，可见，Pn(x)由其n+1个系数组成的系数向量P?(p0,p1,p2,?,pn)唯一确定。因此，在计算机中一个n次多项式可用一个长度为n+1的线性表P来表示，其中pi表示多项式中x的系数。
设多项式Qm(x)的系数向量为Q?(q0,q1,q2,?,qm)且
m iRn(x)?Pn(x)?Qm(x)的系数向量为: R?(p0?q0,p1?q1,p2?q2,?,pm?qm,pm?1,?,pn)。 显然，对线性表P、Q、R，若均采用顺序存储结构，那么作多项式的加法运算十分简便。但是，在实际应用中多项式的次数可能很高，且其中有大量的系数为零。 例如，多项式：S(x)??8?6.5x50?3.7x2500，要用顺序存储时必须占用2501个元素的存储单元（期中有大量的0系数），这显然是不合理的。 为此，我们考虑只储存多项式的非零系数，此时必须连同它所表示的项的指数一起存放才行。这样，用（系数，指数）的序列就可以唯一地确定一个多项式了。此时，S(x)可表示为：S=((-8,0),(6.5,50),(3.7,2500))。这显然也是一个线性表，表中元素是一个数对（实数，整数），并且关于元素中的第二个数据项（整数项）是递增有序的。 既然S是线性表，同样存在其存储结构的选择问题。由于多项式相加的运算结果可能增加若干非零项，也可能减少若干个非零项，因此线性表会执行大量的插入和删除操作，在这种情况下不宜采用顺序存储结构，采用带有指针域的单链表表示一个多项式为宜。上述多项式S(x)的单链表表示结构如图2.13所示。其中，头结点的指数域为-1，以示区别。 在C++语言中多项式的链表结构类型定义如下： #include\ struct PData //定义多项式中每一项的系数和指数结构类型:PData{系数，指数} { double coef; int expn; }; typedef struct PNode //定义多项式链表的结点结构类型:PNode{data,next} { PData data; PNode* next; -.39.- 《数据结构与算法》 }*Poly; //定义指向该结点PNode的指针类型Poly. 2．初始化一个零多项式的操作 void InitPoly(Poly &p) { p=new PNode; p->next=NULL; p->data.expn=-1; } 3．多项式加单项式的操作（poly<=poly+data） 算法思想 计算Poly+data的方法是：从前往后将poly->data.expn项逐个取出并与data.expn项进行比较，将其插入到poly中的适当位置（按指数expn由小到大）。如果在poly中存在相同的指数域（expn），则求相应的系数域（coef）的和，如果和为零，则删除掉poly中相应的结点。 算法实现 void InsertAddPData(Poly &poly,PData data) { Poly p=poly,q; while(p->next&&p->next->data.expn 4．按序创建一个多项式 void CreatePoly(Poly &poly) { PData data; InitPoly(poly); cout<<\输入多项式的系数和相应的指数(expn =-1结束):\\n\ -.40.- 第2章 线性表及其应用 } while(1) { cin>>data.coef>>data.expn; if(data.coef==0||data.expn<0)break; InsertAddPData(poly,data); } 5．按指数形式显示一个多项式 void DispPoly(Poly poly) { Poly p=poly; if(!p->next) cout<<\当前为一个0多项式:P=0\\n\ else { cout<<\ while(p->next) { p=p->next; if(p->data.coef>0)cout<<'+'; cout< 6．多项式加多项式操作（p<=p+p1） void AddPoly(Poly &p,Poly p1) { Poly pp=p1->next; while(pp) { InsertAddPData(p,pp->data); pp=pp->next; } } 7．多项式减多项式操作（p<=p-p1） void SubPoly(Poly &p,Poly p1) { Poly pp=p1->next; PData data; while(pp) { data=pp->data; data.coef*=-1; InsertAddPData(p,data); pp=pp->next; -.41.- 《数据结构与算法》 } } 8．多项式乘以多项式操作（p<=p1×p2） （1）操作：p<=p+p1×d void MulData(Poly &p,Poly p1,PData d) { PData dd; Poly h=p1->next; while(h) { dd=h->data; dd.coef*=d.coef; dd.expn+=d.expn; InsertAddPData(p,dd); h=h->next; } } （2）操作：返回p×p1的值 Poly MulPoly(Poly p,Poly p1) { Poly pm,pp=p1->next; InitPoly(pm); while(pp) { MulData(pm,p,pp->data); pp=pp->next; } return pm; } 9．多项式操作的综合演示主程序 void main() { Poly p,p1,p2,p3,p4; cout<<\ CreatePoly(p); DispPoly(p); cout<<\ CreatePoly(p1); DispPoly(p1); /////p2<=p+p1////////// InitPoly(p2); AddPoly(p2,p); AddPoly(p2,p1); cout<<\DispPoly(p2); /////p3<=p-p1////////// InitPoly(p3); AddPoly(p3,p); -.42.-