第四章 数据结构-线性表.ppt

* * * * * * * * * * * * * * * * * 3、算法实现 方法一：使用pa和pb指针分别沿着两个链表向表尾移动，以指示当前被检测的结点。当paNULL且pbNULL时，可能出现３种情况： (1)pa-exppb-exp：将pa所指结点的数据域写入一个新的结点，并将新结点插入到ch链表尾，pa指针移向下一个元素。 (2) pa-exp=pb-exp：将pa和pb所指结点的系数相加，若结果不为零则产生一个新结点，将系数和结果写入数据域，并插入到ch链表尾。pa和pb指针都移向下一个元素。 (3) pa-exppb-exp：将pb所指结点的数据域写入一个新的结点，并将新结点插入到ch链表尾，pb指针移向下一个元素。 相加过程演示： 直到qa或qb为NULL 若qa==NULL，将B中剩余部分复制C上即可 若qb==NULL，将A中剩余部分复制C上即可 9 8 3 1 5 17 ah 22 7 8 1 ^ -9 8 bh 7 0 ^ pa pa pa pa pb pb pb ch pc 22 7 11 1 5 17 7 0 ^ pc pc pc pc pb=NULL pa=NULL 算法实现： /*建立以系数为c,指数为e的新结点,并把它插在pc所指结点的后面.链表后pc指向新链入的结点*/ void attach(float c, int e, polynom *pc) { term *s; s=new term; s-coef=c; s-exp=e; (*pc)-next=s; *pc=s; } /*以ah和bh为头指针的单链表分别表示多项式A(x)和B(x),ch为表示A(x)与B(x)和的多项式C(x)的链表头指针。为便于复算，本算法不破坏A(x)与B(X),C(x)另辟空间。多项式A(x)和B(x)均无表头结点*/ void PolyAdd1(polynom ah, polynom bh, polynom ch) { polynom pa,pb,pc,q; float x; int k; pa=ah; pb=bh; ch=new term; pc=ch; while(pa!=NULL pb!=NULL) { if(pa-exppb-exp) k=1; else if(pa-exp==pb-exp) k=2; else k=3; switch(k) { case 1:attach(pa-coef, pa-exp, pc); pa=pa-next;break; case 2:x=pa-coef+pb-coef; if(x!=0) attach(x, pa-exp, pc); pa=pa-next;pb=pb-next;break; case 3:attach(pb-coef, pb-exp, pc); pb=pb-next; } } 　while(pb!=NULL) 　　 {attach(pb-coef, pb-exp, pc); pb=pb-next;} while(pa!=NULL) 　　 {attach(pa-coef, pa-exp, pc); pa=pa-next;} pc-next=NULL; q=ch; 　ch=ch-next; 　free(q); } 方法二: 在运算过程中直接利用原来多项式的空间，其中A(x)和B(x)都是带表头结点的单链表。 9 8 3 1 5 17 ah 22 7 8 1 ^ -9 8 bh 7 0 ^ pa pa pa pa pb pb pb pb=NULL pa1 pb1 pa1 pa1 pa1 Pb1-next=NULL 11 算法描述： void PolyAdd2(polynom ah, polynom bh) { polynom pa,pa1,pb,pb1; float sum; int k; pa1=ah; pa=ah-next; pb1=bh; pb=bh-next ; while(pa!=NULL pb!=NULL) { if(pa-exppb-exp) k=1; else if(pa-exp==pb-exp) k=2; else k=3; switch(k) { case 1: pa1=pa; pa=pa-next;