《数据结构》严蔚敏 算法2.22
用链表实现两个多项式相加
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef struct
{
int coef; //coefficient
int expn; //exponent
}term,ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*Link,*Position;
typedef struct
{
Link head,tail; //just like two sides linklist
int len;
}LinkList; // Algorithm 2.20 define
typedef LinkList polynomial;
Status
InitList(LinkList *L)
{
Link p;
p = (Link)malloc(sizeof(LNode));
if(!p)
exit(OVERFLOW);
L->head = L->tail = p;
L->len = 0;
p->next = NULL;
return OK;
}
Position
GetHead(LinkList L)
{
return L.head;
}
Status
SetCurElem(Link p,ElemType e)
{
p->data = e;
return OK;
}
ElemType
GetCurElem(Link p)
{
return p->data;
}
Status
LocateElem(LinkList L,ElemType e,Position *q,int (*cmp)(ElemType,ElemType))
{
Link p,pre;
p = L.head;
do
{
pre = p;
p = p->next;
}while( p != NULL && cmp(p->data,e) < 0);
if( p == NULL || cmp(p->data,e) > 0)
{
*q = pre;
return FALSE;
}
else
{
*q = p;
return TRUE;
}
}
int
cmp(term a,term b)
{
if(a.expn > b.expn)
return 1;
else if(a.expn == b.expn)
return 0;
else
return -1;
}
Status
MakeNode(Link *p,ElemType *e)
{
*p = (Link)malloc(sizeof(LNode));
if(!*p)
exit(OVERFLOW);
(*p) -> data = *e;
(*p) -> next = NULL;
return OK;
}
Status
InsFirst(LinkList *L,Link h,Link *s) // Insert Node into the first address
{
(*s) -> next = h -> next;
h -> next = *s;
L -> len++;
if( h == L->tail)
L->tail = h->next;
return OK;
}
void CreatePolyn(polynomial * P,int m)
{
Link h,q,s;
term e;
int i;
InitList(P);
h = GetHead(*P);
e.coef = 0.0;
e.expn = -1;
SetCurElem(h,e);
for(i = 0; i<m ; ++i)
{
printf("please enter %d coefficient and %d exponent: ",i,i);
scanf("%d",&e.coef);
scanf("%d",&e.expn);
if(!LocateElem(*P,e,&q,cmp))
{
if(MakeNode(&s,&e))
InsFirst(P,q,&s);
}//if
}//for
}
void
TraversePolyn(polynomial p)
{
Link h;
h = p.head -> next;
printf("the polynomial is this:\n");
while(h)
{
printf("%dx^%d",h->data.coef,h->data.expn);
if(h->next)
printf(" + ");
h = h->next;
}
printf("\n");
}
Position
NextPos(LinkList L,Link p)
{
return p->next;
}
Status
DelFirst(LinkList *L,Link h,Link *q)
{
Link p;
*q = h->next;
h->next = (*q)->next;
if(!h->next)
(*L).tail = h;
L->len--;
return OK;
}
void FreeNode(Link p)
{
p = NULL;
free(p);
}
Status Append(LinkList *L,Link *s)
{
int i = 0;
(*L).tail->next = *s;
while(*s){
*s = (*s)->next;
i++;
}
(*L).tail = *s;
(*L).len += i;
return OK;
}
Status ListEmpty(LinkList L)
{
return (L.len == 0);
}
void
AddPolyn(polynomial *Pa,polynomial *Pb)
{
Link ha,hb,qa,qb;
term a,b;
int sum;
ha = GetHead(*Pa);
hb = GetHead(*Pb);
qa = NextPos(*Pa,ha);
qb = NextPos(*Pb,hb);
while(qa && qb)
{
a = GetCurElem(qa);
b = GetCurElem(qb);
switch (cmp(a,b))
{
case -1:
ha = qa;
qa = NextPos(*Pa,qa);
break;
case 0:
sum = a.coef + b.coef;
if(sum != 0.0)
{
qa -> data.coef = sum;
SetCurElem(qa,qa->data);
ha = qa;
}
else
{
DelFirst(Pa,ha,&qa);
FreeNode(qa);
}
DelFirst(Pb,hb,&qb);
FreeNode(qb);
qb = NextPos(*Pb,hb);
qa = NextPos(*Pa,ha);
break;
case 1:
DelFirst(Pb,hb,&qb);
InsFirst(Pa,ha,&qb);
qb = NextPos(*Pb,hb);
ha = NextPos(*Pa,ha);
break;
}
}
if(!ListEmpty(*Pb))
Append(Pa,&qb);
FreeNode(hb);
}
int main(int argc, char const *argv[])
{
polynomial Pa,Pb;
printf("create unitary polynomial Pa: \n");
CreatePolyn(&Pa,4);
TraversePolyn(Pa);
printf("\ncreate unitary polynomial Pb: \n");
CreatePolyn(&Pb,3);
TraversePolyn(Pb);
printf("\nafter add two polynomials:\n");
AddPolyn(&Pa,&Pb);
TraversePolyn(Pa);
return 0;
}