1 #define _CRT_SECURE_NO_DEPRECATE  2 #include "Polynomial.h"  3 #include <stdio.h>  4 #include <stdlib.h>  5   6 int ListLength(NormLinkList *L)  7 {  8     int num = 0;  9     Link p = NextPos(L, GetHead(L)); 10     while(p) 11     { 12         num++; 13         p = NextPos(L, p); 14     } 15     return num; 16 }//PolynLength()个人觉得这两个函数功能一样 17  18 Status MakeNode(Link *p, ElemType e) 19 { 20     //分配由*p指向的值为e的节点，并返回OK；若分配失败，则返回ERROR（此处使用了指向指针的指针p，*p为节点的地址） 21     *p = (Link)malloc(sizeof(NormLNode)); 22     if(!(*p)) 23         return ERROR; 24     (*p)->data =http://www.mamicode.com/ e; 25     (*p)->next = NULL; 26     return OK; 27 } 28  29 void FreeNode(Link p) 30 { 31     //释放p所指节点 32     free(p); 33 } 34  35  36 Status InitList(NormLinkList *L) 37 { 38     //构造一个空的线性链表L 39     L->head = (Link)malloc(sizeof(NormLNode));//生成头节点 40     if(!(L->head)) 41         return ERROR; 42     L->head->next = NULL; 43     L->tail = L->head; 44     L->len = 0; 45     return OK; 46 } 47  48  49 Status DestroyList(NormLinkList *L) 50 { 51     //销毁线性链表L，L不再存在 52     Link p = L -> head -> next;//p指向L的第一个节点 53     Link q; 54     while(p) 55     { 56         q = p -> next; 57         free(p); 58         p = q; 59     } 60     free(L -> head);//释放头节点空间 61     free(L); 62     return OK; 63 } 64  65  66 Status ClearList(NormLinkList *L) 67 { 68     //将线性链表L重置为空表(仅有头节点)，并释放原链表的存储空间 69     Link p = L -> head -> next;//p指向L的第一个节点 70     Link q; 71     while(p) 72     { 73         q = p -> next; 74         free(p); 75         p = q; 76     } 77     L -> head -> next = NULL; 78     L -> tail = L -> head; 79     L -> len = 0; 80     return OK; 81 } 82  83  84 Status InsFirst(Link h, Link s) 85 { 86     //将s所指节点插入在第一个节点之前 87     if(h && s) 88     { 89         s -> next = h -> next; 90         h -> next = s; 91         return OK; 92     } 93     else 94         return ERROR; 95 } 96  97  98 Status DelFirst(Link h, Link *q) 99 {100     //删除链表中的第一个节点，并用q返回101     *q = h -> next;//*q指向待删除节点102     h -> next = (*q) -> next;103     (*q)->next = NULL;//非常重要，否则*q会链接到剩余的节点104     return OK;105 }106 107 108 Status Append(NormLinkList *L, Link s)109 {110     //将指针s所指（彼此以指针相链接）的一串节点链接在线性链表L的最后一个节点之后，111     //并改变链表L的尾指针指向新的尾节点112     Link p = s, q = s;//p指向s，q保持在p前面113     int j = 0;//指示s中的节点个数，用于更新L->len，考虑到了s为空的情况，此时while条件不满足，j为0114     if(!UpdateTail(L))115         return ERROR;116     L -> tail -> next = s;117     while(p)118     {119         //退出时，q指向s中最后一个节点，j为s中的节点个数120         j++;121         q = p;122         p = p -> next;123     }124     L -> tail = q;125     L -> len += j;126     return OK;127 }128 129 130 Status UpdateTail(NormLinkList *L)131 {132     //注意L为空表的情况133     //更新L的尾节点，并更新链表长度134     Link p = L -> head -> next, q = L -> head -> next;//p指向链表第一个节点，q保持在p前面135     int j = 0;//指示s中的节点个数，用于更新L->len，考虑到了s为空的情况，此时while条件不满足，j为0136     if(!(L->head->next))//考虑L为空的情况，此时若执行后面语句，会导致L->tail指向NULL，使得Append函数的L->tail->next = s;语句访存冲突137         return OK;138     while(p)139     {140         //退出时，q指向L中最后一个节点，j为L中的节点个数(仅在L非空时有效)141         j++;142         q = p;143         p = p -> next;144     }145     L -> tail = q;146     L -> len = j;147     return OK;148 }149 150 151 Position GetHead(NormLinkList *L)152 {153     //返回线性链表L中头节点的位置154     return L -> head;155 }156 157 158 Position NextPos(NormLinkList *L, Link p)159 {160     //已知p指向线性链表L中的一个节点，返回p所指节点的直接后继的位置，若无后继，则返回NULL161     return p->next;162 }163 164 165 ElemType GetCurElem(Link p)166 {167     //已知p指向线性链表中的一个节点，返回p所指节点中数据元素的值168     return p -> data;169 }170 171 172 Status LocatePos(NormLinkList *L, int i, Link *p)173 {174     //用*p返回线性链表L中第i个节点的位置并返回OK，i值不合法时返回ERROR。此处p为指向指针的指针，用于返回第i个节点的地址175     //0 <= i <= 表长；（i取0时，返回头节点位置，用于在L的第一个节点前插入元素，ListInsert_NL调用时会用到）176     Link q = L -> head;//q指向L中的头节点177     int j = 0;178     while(q && j < i)179     {180         //退出时，q == NULL，或者j == i181         q = q->next;182         j++;183     }184     if(!q || j > i)//q为空，或者 i < 0，即第i个元素不存在185         return ERROR;186     *p = q;//此时q指向L中第i个节点的位置187     return OK;188 }189 190 191 Status SetCurElem(Link p, ElemType e)192 {193     //已知p指向线性链表中的一个节点，用e更新p所指节点中数据元素的值194     if(p)195         p->data =http://www.mamicode.com/ e;196     else197         return ERROR;198     return OK;199 }200 201 202 Status LocateElem(NormLinkList *L, ElemType e, Position *q, Status (* compare)(ElemType, ElemType))203 {204     //若有序链表L中存在与e满足判定函数compare()取值为0的元素，则*q指示L中第一个值为e的节点的位置，并返回TRUE205     //否则*q指示第一个与e满足判定函数compare()取值>0的元素的前驱的位置，并返回FALSE。此处p为指向指针的指针，用于返回满足条件的节点的地址206     Position p = L -> head, r = L -> head -> next;//p指向L中的头节点,r作为p的直接后继207     while(r && (* compare)(r -> data, e) < 0)208     {209         //退出时，要么r为NULL，要么r->data的指数项等于或者大于e的指数项210         p = r;211         r = r->next;212     }213     if(r == NULL)214     {215         //要么表为空，要么e的指数项大于L中的最高指数项，此时返回r的直接前驱p216         *q = p;217         return FALSE;218     }219     else220     {221         //r不为空222         if((* compare)(r->data, e) == 0)223         {224             //存在与e指数项相同的节点，此时r指向该节点225             *q = r;226             return TRUE;227         }228         else229         {230             //不存在与e指数项相同的节点，此时r->data的指数项大于e的指数项，此时返回r的直接前驱p231             *q = p;232             return FALSE;233         }234     }235 236 }237 238 239 Status ListEmpty(NormLinkList *L)240 {241     //若线性链表L为空表，则返回TRUE，否则返回FALSE242     if(L -> head -> next == NULL)243         return TRUE;244     else245         return FALSE;246 }247 248 249 Status ListInsert_NL(NormLinkList *L, int i, ElemType e)250 {251     //在带头节点的单链线性表L的第i个元素之前插入元素e252     Link *h = (Link *)malloc(sizeof(Link));253     Link *s = (Link *)malloc(sizeof(Link));254     if(!LocatePos(L, i-1, h))//i值在链表范围之外，即i<=0,或者i>表长；否则，通过*h返回L中的第i-1个节点的位置255         return ERROR;256     if(!MakeNode(s, e))//结点存储分配失败；否则，通过*s返回新生成的节点地址257         return ERROR;258     InsFirst(*h, *s);//将节点*s插入到节点*h后面259     return OK;260 }261 262 263 Status MergeList_NL(NormLinkList *La, NormLinkList *Lb, NormLinkList *Lc, int (* compare)(ElemType, ElemType))264 {265     //UpdateTail函数中未处理表为空的情况266     //已知单链线性表La和Lb的元素按值非递减排列267     //归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列268     Position ha = GetHead(La);269     Position hb = GetHead(Lb);//ha，hb分别指向La，Lb的头节点270     Position pa = NextPos(La, ha);271     Position pb = NextPos(Lb, hb);//pa,pb分别指向La，Lb的当前节点（第一个节点）272     ElemType a, b;273     Link *q = (Link *)malloc(sizeof(Link));274     while(pa && pb)275     {276         //pa，pb均不为空277         a = GetCurElem(pa);278         b = GetCurElem(pb);//a,b为两表中待比较元素279         if((* compare)(a, b) <= 0)280         {281             //a <= b282             DelFirst(ha, q);283             Append(Lc, *q);284             pa = NextPos(La, ha);285         }286         else287         {288             //a > b289             DelFirst(hb, q);290             Append(Lc,*q);291             pb = NextPos(Lb, hb);292         }293     }294     if(pa)295         Append(Lc, pa);296     else297         Append(Lc, pb);298     FreeNode(ha);299     FreeNode(hb);300     return OK;301 }302 303 304 int cmp(term a, term b)305 {306     //根据a的指数值<(或=)(或>)b的指数值，分别返回-1,0,+1307     if(a.expn < b.expn)308         return -1;309     else if(a.expn == b.expn)310         return 0;311     else312         return 1;313 }314 315 316 void CreatePolyn(polynomial *P, int m)317 {318     //输入m项的系数和指数，建立表示一元多项式的有序链表P319     //最多能输入m项，若输入指数相同的项，则后输入项会被丢弃320     Position h;321     Position *q = (Position *)malloc(sizeof(Position));//指针使用前一定要先初始化322     Position *s = (Position *)malloc(sizeof(Position));323     term e;324     int i;325     InitList(P);326     h = GetHead(P);327     e.coef = 0.0;328     e.expn = -1;329     SetCurElem(h, e);330     for(i = 1; i <= m; i++)331     {332         scanf("%f %d", &(e.coef), &(e.expn));333         if(!(LocateElem(P, e, q, cmp)))334         {335             //当前链表不存在该指数项336             if(MakeNode(s, e))//生成节点并插入链表337                 InsFirst(*q, *s);338         }339     }340 }341 342 343 void PrintPolyn(polynomial *P)344 {345     //打印输出一元多项式346     Position p = P -> head -> next;//p指向链表P的第一个节点347     int i = 1;348     while(p)349     {350         if(i != 1)351             printf(" + ");352         printf("%fx^%d", p->data.coef, p->data.expn);353         p = p->next;354         i++;355     }356     printf("\n\n");357 }358 359 360 void AddPolyn(polynomial *Pa, polynomial *Pb)361 {362     //完成多项式相加运算，即：Pa = Pa + Pb，并销毁一元多项式Pb363     term a, b;364     int diff;365     float sum;366     Position *dp = (Position *)malloc(sizeof(Position));//*dp中用于保存被删除节点的地址367     Position ha = GetHead(Pa);368     Position hb = GetHead(Pb);//ha,hb分别指向Pa,Pb的头节点369     Position qa = NextPos(Pa, ha);370     Position qb = NextPos(Pb, hb);//qa,qb分别指向Pa,Pb的当前待处理结点371     while(qa && qb)372     {373         //qa与qb均为非空374         a = GetCurElem(qa);375         b = GetCurElem(qb);//a,b为当前待比较元素376         diff = cmp(a, b);377         if(diff == -1)378         {379             //多项式Pa中当前结点的指数值小380             ha = qa;381             qa = NextPos(Pa, qa);//ha指向qa，qa往后走382         }383         else if(diff == 0)384         {385             sum = a.coef + b.coef;386             if(sum != 0.0)387             {388                 //修改多项式Pa中当前结点的系数值389                 a.coef = sum;390                 SetCurElem(qa, a);//教材此处有误，第二个参数应为term类型391                 ha = qa;//此处为后面qa = NextPos(Pa, ha)做准备，使得当qa指向节点不被删除时，ha即相当于qa392             }393             else394             {395                 //删除多项式Pa中当前结点396                 DelFirst(ha, dp);//此处使用dp，为了跟DelFirst的函数原型匹配，因此与教材写法不同397                 FreeNode(*dp);//实际*dp的内容就是qa398             }399             DelFirst(hb,dp);//此处使用dp，为了跟DelFirst的函数原型匹配，因此与教材写法不同400             FreeNode(*dp);//实际*dp的内容就是qb401             qb = NextPos(Pb, hb);402             qa = NextPos(Pa, ha);403         }404         else405         {406             //多项式Pb中当前结点的指数值小407             DelFirst(hb, dp);//此处使用dp，为了跟DelFirst的函数原型匹配，因此与教材写法不同408             InsFirst(ha, *dp);//将Pb的当前节点接在ha后面,实际*dp的内容就是qb409             qb = NextPos(Pb, hb);410             ha = NextPos(Pa, ha);//ha指向刚插入的节点，即*dp411         }412     }//while413     if(!ListEmpty(Pb))414         Append(Pa, qb);//链接Pb中剩余节点415     FreeNode(hb);416 }417 418 419 void Multpolyn(polynomial *Pa, polynomial *Pb)420 {421     //实现两个一元多项式的乘法422     float coef0 = 0.0; int expn0 = 0; ElemType a;423     Link mid0 = NULL, mid1 = NULL, mid2 = NULL;424     Link PaH = GetHead(Pa);425     polynomial *pa = (polynomial *)malloc(sizeof(polynomial));426     polynomial *Pc = (polynomial *)malloc(sizeof(polynomial));427     polynomial *Pd = (polynomial *)malloc(sizeof(polynomial));428 429     PaH = NextPos(Pa, PaH);//PaH -> next430     a = GetCurElem(PaH);//PaH->data431     coef0 = a.coef;432     expn0 = a.expn;433 434     InitList(pa); InitList(Pc); InitList(Pd);//init435 436     pa -> head -> data = http://www.mamicode.com/GetCurElem(GetHead(Pa));//Pa ->head->data;437     mid0 = NextPos(Pa, (GetHead(Pa)));//mid0 = Pa -> head->next438     pa -> head -> next = NULL;439     mid1 =GetHead(pa);//pa -> head;440     while(mid0)441     {442         //完成Pa的copy443         mid1 -> next = (Link)malloc(sizeof(NormLNode));444         mid1 = NextPos(pa,mid1);//mid1 -> next,445         mid1 ->next = NULL;446         mid1->data =http://www.mamicode.com/ GetCurElem(mid0);447         //mid1 -> data.coef = mid0 -> data.coef, mid1 -> data.expn = mid0 -> data.expn;448         mid0 = NextPos(Pa, mid0);//mid0 -> next;449     }450     pa -> tail = mid1, pa -> len = Pa -> len;//处理pa的尾结点和长度451 452     mid0 = NextPos(Pa, GetHead(Pa));//Pa -> head -> next453     while(mid0)454     {455         //完成Pa 与 Pb第一项相乘456         mid0 -> data.coef = mid0 -> data.coef * coef0, mid0 -> data.expn = mid0 -> data.expn + expn0;457         mid0 = NextPos(Pa, mid0);//mid0 -> next;458     }459 460     //完成后续工作461     //mid0 = pa -> head -> next;462     //mid1 = Pc -> head;463     mid2 = NextPos(Pb,NextPos(Pb,GetHead(Pb)));//Pb -> head -> next -> next;464     while(mid2)465     {466         mid1 = GetHead(Pc);//Pc -> head;467         mid0 = NextPos(pa,GetHead(pa));//pa -> head -> next;468         while(mid0)469         {470             mid1 -> next = (Link)malloc(sizeof(NormLNode));471             mid1 = NextPos(Pc, mid1);//mid1 -> next;472             mid1 -> data.coef = mid0 -> data.coef * mid2 -> data.coef;473             mid1 -> data.expn = mid0 -> data.expn +mid2 -> data.expn;474             mid0 = NextPos(pa, mid0);//mid0 -> next;475         }476         mid1 -> next = NULL;//处理尾巴，否则Append（）函数中while循环无法判定477         Pc -> tail = mid1;478         AddPolyn(Pa, Pc);479         Pc = (polynomial *)malloc(sizeof(polynomial));480         InitList(Pc);481         mid2 = NextPos(Pb, mid2);//mid2 -> next;482     }483     Pa -> len = ListLength(Pa);484 }485 486 487 int main()488 {489 /*******************************测试一元多项式加法*******************************/490     polynomial *Pa = (polynomial *)malloc(sizeof(polynomial));491     polynomial *Pb = (polynomial *)malloc(sizeof(polynomial));492     printf("分别输入一个4项的多项式和一个3项的多项式\n");493     CreatePolyn(Pa, 4);494     printf("Pa:\n");495     PrintPolyn(Pa);496     CreatePolyn(Pb, 3);497     printf("\nPb:\n");498     PrintPolyn(Pb);499     AddPolyn(Pa, Pb);500     printf("\nPa+Pb:\n");501     PrintPolyn(Pa);502     DestroyList(Pa);503 /*******************************测试一元多项式乘法*******************************/504     Pa = (polynomial *)malloc(sizeof(polynomial));505     Pb = (polynomial *)malloc(sizeof(polynomial));506     printf("分别输入一个4项的多项式和一个3项的多项式\n");507     CreatePolyn(Pa, 4);508     printf("Pa:\n");509     PrintPolyn(Pa);510     CreatePolyn(Pb, 3);511     printf("\nPb:\n");512     PrintPolyn(Pb);513     printf("\nPa * Pb\n");514     Multpolyn(Pa, Pb);515     PrintPolyn(Pa);516     DestroyList(Pa);517 return 0;518 }