单链表-多项式

用链表的每个节点存储表达式的每一项，因此每个链表就是一个表达式。

写在前头：这个程序只是为了让我熟悉链表这种数据结构，只支持 + / - 两种运算符，如果系数是正数，那么在打印表达式的时候，在该项前面打印一个 ‘+’；如果是系数是负数，那么不用打印，因为负数的符号就可以代表运算符了。

算法实现步骤 C(x) = A(x) + B(x)
1> pa、pb分别指向首元结点， 产生C(x)的空链表， pc指向头结点；
2> pa不为空，并且pb不为空， 重复一下步骤：
2-1> pa->expan = pb->expan
(a) pa->coed + pb->coed不等于0，产生新结点，添加到pc后， pc指向新结点。pa、pb后移。
(b) pa->coed + pb->coed等于0，不产生新结点。pa、pb后移。
2-2> pa->expan < pb->expan：根据pa产生新结点，添加到pc，pc指向新结点。pa向后移。
2-3> pa->expan > pb->expan：根据pb产生新结点，添加到pc，pc指向新结点。pb向后移。

结构体

3> pa为空取pb剩余结点产生新结点，pb为空取pa剩余结点产生新结点，依次添加到pc的后面。

#include "polynomial.h"
#include <stdlib.h>
#include <assert.h>
typedef int ElemType;

typedef struct polynomial {
    ElemType coed;
    ElemType expan;
    struct ploy *link;
}polynomial, *Ppolynomial;

创建多项式项

//创建结点
Ppolynomial NewNode(ElemType coed, ElemType expan) {
    Ppolynomial node = (polynomial *)malloc(sizeof(polynomial));
    node->coed = coed;
    node->expan = expan;
    node->link = NULL;
    return node;
}

多项式表达式初始化

//初始化
void InitPolynomial(Ppolynomial *phead) {
    *phead = (polynomial *)malloc(sizeof(polynomial));
    (*phead)->link = NULL;
}

创建多项式表达式

//尾插
void InsertPolynomiaTail(Ppolynomial *head, ElemType coed, ElemType expan) {
    assert(*head);
    Ppolynomial node = NewNode(coed, expan);
    Ppolynomial p = (*head)->link;
    if (p == NULL) {
        (*head)->link = node;
        return;
    }
    while (p->link != NULL) {
        p = p->link;
    }
    p->link = node;
}

多项式相加

//计算多项式
void CalculatePolynomia(Ppolynomial *La, Ppolynomial *Lb, Ppolynomial *result) {
    assert(*La);
    assert(*Lb);
    Ppolynomial pa = (*La)->link;
    Ppolynomial pb = (*Lb)->link;
    Ppolynomial p = *result;
    if (pa == NULL && pb) {
        p->link = pb;
        return;
    }
    if (pb == NULL && pa) {
        p->link = pa;
        return;
    }
    while (pa && pb) {
        if (pa->expan == pb->expan) {
            int coed = pa->coed + pb->coed;
            if (coed != 0) {
                Ppolynomial new = NewNode(coed, pa->expan);
                p->link = new;
                p = new;
                pa = pa->link;
                pb = pb->link;
            }
            else {
                pa = pa->link;
                pb = pb->link;
            }
        }
        else if(pa->expan < pb->expan) {
            Ppolynomial new = NewNode(pa->coed, pa->expan);
            p->link = new;
            p = new;
            pa = pa->link;
        }
        else {
            Ppolynomial new = NewNode(pb->coed, pb->expan);
            p->link = new;
            p = new;
            pb = pb->link;
        }
    }
    while(pa) {
        Ppolynomial new = NewNode(pa->coed, pa->expan);
        p->link = new;
        p = new;
        pa = pa->link;
    }
    while(pb) {
        Ppolynomial new = NewNode(pb->coed, pb->expan);
        p->link = new;
        p = new;
        pb = pb->link;
    }
}

多项式输出

//打印
void PrintPolynomial(Ppolynomial head) {
    assert(head);
    Ppolynomial p = head->link;
    if (p == NULL) {
        printf("空表...\n");
        return;
    }
    if ((head)->link) {
        if (p->expan == 0) {
            printf("%d", p->coed);
        }
        else if (p->expan == 1) {
            printf("%dX", p->coed);
        }
        else {
            printf("%dX^%d", p->coed, p->expan);
        }
    }
    p = p->link;
    while (p->link != NULL) {
        if (p->coed >= 0) {
            if (p->expan == 0) {
                printf(" +%d", p->coed);
            }
            else if (p->expan == 1) {
                printf(" +%dX", p->coed);
            }
            else {
                printf(" +%dX^%d", p->coed, p->expan);
            }
        }
        else {
            if (p->expan == 0) {
                printf(" %d", p->coed);
            }
            else if (p->expan == 1) {
                printf(" %dX", p->coed);
            }
            else {
                printf(" %dX^%d", p->coed, p->expan);
            }
        }
        p = p->link;
    }
    if (p->link == NULL) {
        if (p->expan == 0) {
            printf(" +%d", p->coed);
        }
        else if (p->expan == 1) {
            printf(" +%dX", p->coed);
        }
        else {
            printf(" +%dX^%d", p->coed, p->expan);
        }
    }
    printf("\n");
}

测试

void testPolynomial() {
    polynomial link;
    Ppolynomial head = &link;
    InitPolynomial(&head);
    Ppolynomial head2 = &link;
    InitPolynomial(&head2);
    Ppolynomial head3 = &link;
    InitPolynomial(&head3);
    InsertPolynomiaTail(&head, 23, 0);
    InsertPolynomiaTail(&head, 34, 1);
    InsertPolynomiaTail(&head, 23, 2);
    PrintPolynomial(head);
    InsertPolynomiaTail(&head2, 23, 1);
    InsertPolynomiaTail(&head2, 34, 2);
    InsertPolynomiaTail(&head2, 23, 6);
    PrintPolynomial(head2);
    CalculatePolynomia(&head, &head2, &head3);
    PrintPolynomial(head3);
}