读书笔记: 链表多项式(link Polynomial)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#define IS_FULL (ptr) (!(ptr))
#define SWAP(x,y,t) ((t) = (x),(x)=(y),(y)=(t))
#define COMPARE(x,y) ( ((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1)

typedef struct poly_node *poly_pointer;
typedef struct poly_node{
    int coef;//系数
    int expon;//指数
    poly_pointer link;
}poly_node;

poly_pointer padd(poly_pointer a, poly_pointer b);
void attach(float coefficient, int exponent, poly_pointer *ptr);
void print_poly(poly_pointer p);

Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

poly_pointer padd(poly_pointer a,poly_pointer b){
    poly_pointer front,rear,temp;
    int sum;
    rear = (poly_pointer)malloc(sizeof(poly_node));
    //    if (IS_FULL(rear)){
    //        fprintf(stderr, "full");
    //        exit(1);
    //    }
    front = rear;
    while(a && b) {
        switch(COMPARE(a->expon,b->expon)){
            case -1:
                attach(b->coef, b->expon, &rear);
                b=b->link;
                break;
            case 0:
                sum = a->coef + b->coef;
                if(sum) attach(sum, a->expon, &rear);
                a=a->link;b=b->link;
                break;
            case 1:
                attach(a->coef, a->expon, &rear);
                a=a->link;
                break;
        }
    }
    for(;a;a=a->link) attach(a->coef, a->expon, &rear);
    for(;b;b=b->link) attach(b->coef, b->expon, &rear);
    
    rear->link=NULL;
    
    temp = front;
    front=front->link; //去掉表头空节点
    free(temp);
    return front;
}

void attach(float coefficient,int exponent,poly_pointer *ptr){
    poly_pointer temp;
    temp = (poly_pointer)malloc(sizeof(poly_node));
    //    if(IS_FULL()){
    //        fprintf(stderr, "full");
    //        exit(1);
    //    }
    temp->coef= coefficient;
    temp->expon= exponent;
    (*ptr)->link = temp; //第一次执行时造成ptr为空
    *ptr = temp;
}

Print

1
2
3
4
5
6
7

void print_poly(poly_pointer p){
    printf("The list:");
    for(;p;p=p->link){
        printf("%dX^%d ",p->coef,p->expon);
    }
    printf("\n");
}

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

int main (int argc, const char * argv[])
{
    poly_pointer a,b,d;
    poly_pointer a2,a3,b2,b3;
    a = (poly_pointer)malloc(sizeof(poly_node));
    a2 = (poly_pointer)malloc(sizeof(poly_node));
    a3 = (poly_pointer)malloc(sizeof(poly_node));
    a->coef = 3;
    a->expon = 14;
    a2->coef = 2;
    a2->expon = 8;
    a3->coef = 1;
    a3->expon = 0;
    a->link = a2;
    a2->link = a3;
    a3->link = NULL;
    
    b = (poly_pointer)malloc(sizeof(poly_node));
    b2 = (poly_pointer)malloc(sizeof(poly_node));
    b3 = (poly_pointer)malloc(sizeof(poly_node));
    b->coef = 8;
    b->expon = 14;
    b2->coef = -3;
    b2->expon = 10;
    b3->coef = 10;
    b3->expon = 6;
    b->link= b2;
    b2->link= b3;
    a3->link= NULL;
    
    poly_pointer sum;
    sum = padd(a,b);
    
    printf("List A:");
    print_poly(a);
    printf("List B:");
    print_poly(b);
    printf("Final List:");
    print_poly(sum);
    
    return 0;
}

Output

1
2
3

List A:The list:3X^14 2X^8 1X^0 
List B:The list:8X^14 -3X^10 10X^6 
Final List:The list:11X^14 -3X^10 2X^8 10X^6 1X^0