5-17.c

数据结构经典算法一书源代码和习题解答实现代码。

#include "stdio.h"
typedef struct   poly_node{
    float  coef;
    int  expon;
    struct   poly_node  *link;
};
typedef struct   poly_node  *poly_pointer;
int COMPARE(float coef1,float coef2)
{
	if(coef1==coef2)
		return 0;
	else if (coef1>coef2)
		return 1;
	else
		return -1;
}
poly_pointer get_node(void)
{
    poly_pointer node,avail;
    if ( avail ) {
        node = avail;
        avail = avail->link;
	}
   else {
        node = (poly_pointer)malloc(sizeof(poly_pointer));
        if (node==NULL) {
             fprintf(stderr, "The memory is full\n");
             exit(1);
        }
    }
    return node;
}
void attach(float coefficient, int exponent, poly_pointer *ptr)
{    /* 生成一个新结点，并连在ptr的后继指针上*/
		poly_pointer temp;
		temp = (poly_pointer)malloc(sizeof(poly_pointer));
		if (temp==NULL)
		{
			printf("The memory is full\n");
			exit(1);
		}
		temp->coef = coefficient;
		temp->expon = exponent;
		(*ptr)->link = temp;
		*ptr = temp;
}
poly_pointer padd(poly_pointer a, poly_pointer b)
{     /*返回多项式a和b的和 */
    poly_pointer starta, d, lastd,rear;
	int sum, done = 0;
	starta = a;		/* record start of a */
	a = a->link;		/* 跳过头指针 */
	b = b->link;
	d = get_node();	/* 生成新结点*/
	d->expon = -1; 
	lastd = d;
    do{
        switch ( COMPARE(a->expon, b->expon) ) {
           case -1:	/* a->expon < b->expon 的情况*/
                attach(b->coef, b->expon,&rear);
                b = b->link;
                break;
           case 0:	/* a->expon = b->expon 的情况*/
				if ( starta == a ) done =1;
                else {
                    sum = a->coef + b->coef;
                    if ( sum ) attach(sum, a->expon, &lastd);
                    a = a->link;
					b = b->link;
                }
                break;                
           case 1:	/* a->expon > b->expon 的情况*/
                attach(a->coef, a->expon, &rear);
                a = a->link;
		}
     }while(!done);
	lastd->link = d;
    return d;
}
void main()
{
	poly_pointer p=get_node();
//	attach(1.0,3,p);
}