武汉软件工程职业学院《数据结构讲义》第06讲 线性表的应用.doc

第二章 线性表和数组第六讲 线性表的应用1巩固线性表的概念及操作。2了解并熟悉线性表的典型应用多项式相加。 教学重点： 线性表的概念及操作 教学难点： 多项式相加 授课内容2.5 线性表的应用 一元多项式相加问题多项式的相加操作是线性表处理的典型例子。在数学上，一个多项式可写成下列形式：P（x）=anxn+an-1x n-1+ +a1x+a0其中ai为xi的非零系数。在多项式相加时，至少有两个或两个以上的多项式同时并存，而且在实现运算的过程中所产生的中间多项式和结果多项式的项数和次数都是难以预料的。因此计算机实现时，可采用单链表来表示。多项式中的每一项为单链表中的一个结点，每个结点包含三个域：系数域、指数域和指针域，其形式如下：现在设有两个多项式：A(x)=5x9+8x7+3x2-12B(x)=6x12+10x9 -3x2它们的链表结构见图2-5-1。图2-5-1 多项式的单链表结构多项式相加的运算规则为：两个多项式中所有指数相同的项，对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不同的项均复制到“和多项式”中。实现时，可采用另建多项式的方法，也可采用把一个多项式归并到另一个多项式中去的方法。这里介绍后一种方法。下面是一个完整的C程序，包含三个算法：PolyAdd、Creat_Linkst和Print_Linkst。核心算法PolyAdd是把分别由pa和pb所指的两个多项式相加，结果为pa所指的多项式。相加时，首先设两个指针变量qa和qb分别从多项式的首项开始扫描(见图2-5-1)，比较qa和qb所指结点指数域的值，可能出现下列三种情况之一：（1）qa-exp大于qb-exp,则qa继续向后扫描。（2）qa-exp等于qb-exp,则将其系数相加。若相加结果不为零，将结果放入qa-coef中，并删除qb所指结点，否则同时删除qa和qb所指结点。然后qa、qb继续向后扫描。（3）qa-exp小于qb-exp,则将qb所指结点插入qa所指结点之前，然后qa、qb继续向后扫描。扫描过程一直进行到qa或qb有一个为空为止，然后将有剩余结点的链表接在结果链表上。所得pa指向的链表即为两个多项式之和。算法 Creat_Linkst是建立表示多项式的单链表。建立链表的过程是一个动态生成的过程，即从“空表”的初始状态起，依次输入数据元素，每输入一个就生成一个新结点并插入到表尾。为了方便新结点的插入，算法中设置一个指针pre使其始终指向当前链表的表尾结点，初始指向pa(见图2-5-1)。算法Print_Linkst是输出多项式的单链表。C语言源程序如下：#include #include typedef struct polynode /*结点结构描述*/int coef; /*系数域*/int exp ; /*指数域*/struct polynode *next; /* 指针域*/PNode;PNode *Creat_Linkst ( int n );void PolyAdd (PNode *pa, PNode *pb );void Print_Linkst( PNode *H);main() PNode *HA,*HB; /* 多项式链表的头指针*/int la,lb;printf(enter la,lb:);scanf(%d,%d,&la,&lb); /* 输入多项式A和B的项数*/printf(ncreat HAn); HA=Creat_Linkst(la); /*建立多项式A*/printf(A(x)=); Print_Linkst(HA); /*输出多项式A */printf(ncreat HBn); HB=Creat_Linkst(lb); /*建立多项式B*/printf(B(x)=); Print_Linkst(HB); /*输出多项式B */PolyAdd(HA,HB); /*多项式相加*/printf(nA(x)+B(x)=); Print_Linkst(HA); /*输出和多项式 */ PNode * Creat_Linkst ( int n )/* 顺序输入n个元素的值，建立带表头结点的单链表 */ PNode *head,*p,*s; int i;head=( PNode *) malloc(sizeof(PNode ); /* head为表头指针 */head-next=NULL; /* 先建立一个带表头结点的空表*/p=head;printf(enter coef,exp:n);for (i=1; i=n; +i ) s=( PNode *) malloc(sizeof(PNode ); /* 生成新结点*/scanf (“%d,%d”,&s-coef,&s-exp); /*输入结点的系数和指数*/s-next=NULL;p-next=s; p=s; /* 新结点插入在表尾*/return (head);void PolyAdd (PNode *pa, PNode *pb )/* 以pa 和pb为头指针的单链表分别表示两个多项式，实现pa=pa+pb */ PNode *pre,*qa,*qb,*q; int sum;pre=pa; /* pre始终指向当前和多项式的最后一个结点 */qa=pa-next; qb=pb-next; /* qa、qb分别指向pa、pb中的当前结点 */while ( qa & qb ) /* qa、qb均非空*/if ( qa-exp=qb-exp) /* 指数相同*/sum=qa-coef+qb-coef ;if (sum) qa-coef =sum; pre=qa; else pre-next=qa-next; free(qa); qa=pre-next;q=qb; qb=qb-next; free(q);else /* 指数不相同*/if (qa-expqb-exp ) pre=qa; qa=qa-next; else pre-next=qb; pre=qb;qb=qb-next; pre-next=qa;if ( qb) pre-next=qb; /* 链接pb中剩余结点*/free(pb); /*释放pb头结点*/void Print_Linkst( PNode *H) PNode