c語言單鏈表實現多項式計算

多項式鏈表的結構和接口均參考嚴蔚敏老師的（c語言版）《數據結構》。

加法的實現：

假設指針pa，pb分別指向多項式A和B當前進行比較的某個結點，則比較這兩個結點的指數項，有下列三種情況：

指針pa所指結點的指數值 < 指針pb所指結點的指數值：則應摘取pa指針所指結點插入到“和多項式”鏈表中去 指針pa所指結點的指數值 < 指針pb所指結點的指數值：則應摘取pb指針所指結點插入到“和多項式“鏈表中去 指針pa所指結點的指數值 = 指針pb所指結點的指數值：則兩個結點中的系數相加，若和數部位零，pa所指結點的系數值，同時釋放pb所指的結點；反之，從多項式鏈表中刪除相應的結點，同時釋放pa和pb所指向的結點。

減法的實現：

簡單的思路：先把減數多項式的系數一一取相反數，然後調用加法函數即可實現。

乘法的實現：

M (x)　＝　A(x) x B(x)　
　　　　＝　Ａ(x) x [b1xe1+b2xe2＋...+bnxen]
　　　　=∑ni=1biA(x)xei

所以，乘法也可以轉換成加法實現。

對於鏈表的操作有幾點需要牢記：

需要對鏈表進行有效性判斷

對於鏈表的操作過程中，首先要創建一個節點，並將頭結點復制給新節點

如果要構建新的鏈表是，表頭需要單獨保存；同時每個節點需要創建新節點，完成賦值、指針操作；組後需要一個游標節點，負責將各個節點串聯起來。 對於尾節點，最後一定要將其next指向NULL。 若在對鏈表操作時不想改變鏈表的值，則需要使用malloc函數重新定義一個鏈表，並把 原鏈表的內容賦給新鏈表。此時切記，不要把原鏈表的指針賦給新生成的結點，否則，在使用的過程中依舊會改變原鏈表，這是因為指針的特性。

c語言代碼實現

/* 接口聲明和數據結構聲明頭文件 */

/* 項的表示 
 * 多項式的項作為單鏈表的數據元素
*/
typedef struct{
    /* 系數 */
    int coef;
    /* 指數 */
    int expn;
}datatype;

/* 線性單鏈表的存儲結構 */
typedef struct l_node{
    /* 數據域表示多項式的項 */
    datatype data;
    /* 指針域 */
    struct l_node *next;
}l_node,*link_list;

/* 用帶頭結點的有序鏈表表示多項式 */
typedef link_list polynomial;

#define true 1
#define false 0

/* 定義ccompare函數的返回值 */
#define a_e_b 0  //a = b
#define a_g_b 1  //a > b
#define a_s_b -1 //a < b


/* 定義polyn_locate函數的返回值 */
#define prior -1  //要找元素值不存在且小於鏈表中的某些結點
#define curor 0   //要找元素存在
#define nextor 1  //要找元素值不存在且大於鏈表中的結點


/* -------------------基本操作的函數原型說明------------------- */



/* 比較兩個類型為datatype的變量
 * 若a = b,返回a_e_b
 * 若a > b,返回a_g_b
 * 若a < b,返回a_s_b
*/
int compare(datatype a, datatype b);


/* 定義polyn_locate函數的返回類型 */
typedef struct{
    /* 指向某結點的指針 */
    polynomial p;
    /* 類型 */
    int type;
}locate;

/* 若有序鏈表中HEAD中存在與e滿足判定函數compare()取值為a_e_b的元素
 則p為指向HEAD中第一個值為e的結點的指針,並返回curor

 *若有序鏈表中HEAD中存在與e滿足判定函數compare()取值為a_g_b的元素
 則p為指向HEAD中最後一個結點的指針,並返回nextor

 *若有序鏈表中HEAD中存在與e滿足判定函數compare()取值為a_s_b的元素
 則p為指向HEAD中第一個大於e的結點的指針,並返回prior
*/
locate polyn_locate(polynomial HEAD, datatype e, int(*compare)(datatype, datatype));

/* 按有序判定函數compare()的約定,將值為e的結點插入到有序鏈表的適當位置
*/
void polyn_order_insert(polynomial HEAD, datatype e, int(*compare)(datatype, datatype));

/* 輸入m項的系數和指數,建立表示一元多項式的有序鏈表 
 * HEAD為鏈表的頭指針
*/
void polyn_create(polynomial HEAD);

/* 銷毀一元多項式 */
void polyn_destroy(polynomial HEAD);

/* 打印輸出一個一元多項式 */
void polyn_print(polynomial HEAD);

/* 返回一元多項式的項數 */
int polyn_length(polynomial HEAD);

/* 完成多項式的相加
 * pa = pa + pb
 * 然後銷毀一元多項式pb
*/
polynomial polyn_add(polynomial pa, polynomial pb);

/* 完成多項式的相減
 * pa = pa -pb
 * 並銷毀一元多項式pb
*/
polynomial polyn_subtract(polynomial pa, polynomial pb);

/* 完成多項式的相乘
 * pa = pa * pb
 * 並銷毀一元多項式pb
*/
polynomial polyn_multiply(polynomial pa, polynomial pb);



/* 復制一個單鏈表 */
polynomial polyn_clone(polynomial HEAD);




/* 接口的實現文件 */
#include
#include
#include"polynomial.h"




int compare(datatype a, datatype b)
{
    if(a.expn == b.expn)
        return a_e_b;
    if(a.expn > b.expn)
        return a_g_b;
    if(a.expn < b.expn)
        return a_s_b;
}


void polyn_print(polynomial HEAD)
{
    /* p指向第一個結點 */
    polynomial p = HEAD -> next;
    if(!p)
        printf("此鏈表為空\n");
    else
    {
        while(p -> next)
        {
            if (p -> next -> data.coef >= 0)
                printf("%dx^%d + ",p -> data.coef,p -> data.expn);
            else
                printf("%dx^%d ",p -> data.coef,p -> data.expn);   

            p = p -> next;
        }
        printf("%dx^%d\n",p -> data.coef,p -> data.expn);
    }

}


locate polyn_locate(polynomial HEAD, datatype e, int(*compare)(datatype, datatype))
{
    /* 初始化ptr指向頭指針 */
    locate ptr; 
    ptr.p = HEAD;
    while((ptr.p) -> next)
    {
        if(compare( (ptr.p -> next -> data), e) == a_e_b)
        {
            ptr.p = ptr.p -> next;
            ptr.type = curor;
            return ptr;
        }
        if(compare( ptr.p -> next -> data, e) == a_g_b)
        {
            ptr.type = prior;
            return ptr;
        }
        if(compare( ptr.p -> next -> data, e) == a_s_b)
        {
            ptr.p = ptr.p -> next;
        }
    }
    ptr.type = nextor;
    return ptr;
}




void polyn_order_insert(polynomial HEAD, datatype e, int(*compare)(datatype, datatype))
{

    locate ptr = polyn_locate(HEAD, e, compare);
    if (ptr.type == nextor)
    {
        /* 新建結點 */
        polynomial new_node = (polynomial)malloc(sizeof(l_node));
        new_node -> data = e;
        /* 修改指針域 */
        ptr.p -> next = new_node;
        new_node -> next = NULL;
    }
    if (ptr.type == prior)
    {
        /* 新建結點 */
        polynomial new_node = (polynomial)malloc(sizeof(l_node));
        new_node -> data = e;
        /* 修改指針域 */
        new_node -> next = ptr.p -> next;
        ptr.p -> next = new_node;
    }
    /* 若該項已存在 */
    if (ptr.type == curor)
    {
        (ptr.p -> data).coef += e.coef;
    }
}


void polyn_create(polynomial HEAD)
{
    /* 初始化頭指針 */
    HEAD -> next = NULL;
    datatype temp;
    scanf("%d %d",&(temp.coef), &(temp.expn));
    /* 系數為零,指數為任意值時退出 */
    while(temp.coef != 0)
    {
        /* 建立新結點 */
        polyn_order_insert(HEAD, temp, compare);
        scanf("%d %d",&(temp.coef), &(temp.expn));
    }
}

void polyn_destroy(polynomial HEAD)
{
    while(HEAD)
    {
        polynomial p = HEAD;
        HEAD = HEAD -> next;
        free(p);
    }
}


int polyn_length(polynomial HEAD)
{
    polynomial p = HEAD -> next;
    int i = 0;
    while(p)
    {
        i += 1;
        p = p -> next;
    }
    return i;

}

polynomial polyn_add(polynomial pa, polynomial pb)
{ 
    /* 和鏈表的頭結點 */
    polynomial hc = pa;
    /* 指向和鏈表的最後一個結點 */
    polynomial pc = hc;
    /* hb為鏈表b的頭結點 */
    polynomial hb = pb;
    /* 當前結點 */
    pb = pb -> next;
    /* 當前結點 */
    pa = pa -> next;
    int type;
    while(pa && pb)
    {
        type = compare(pa -> data, pb -> data);
        if (type == a_e_b)
        {
            /* 指數相同,系數相加 */
            (pa -> data).coef = (pa -> data).coef + (pb -> data).coef;
            if (pa -> data.coef == 0)
            {
                /* 刪除pa的當前結點 */
                pc -> next = pa;
                pa = pa -> next;
                free(pc -> next);
                pc -> next = NULL;
                /* 刪除pb的當前結點 */
                hb -> next = pb -> next;
                free(pb);
                pb = hb -> next;

            }
            else
            {
                /* 將結點存至和鏈 */
                pc -> next = pa;
                pc = pa;
                /* 改變b的頭結點 */
                hb -> next  = pb -> next;
                /* 釋放當前結點 */
                free(pb);
                /* 下一個結點 */
                pb = hb -> next; 
                /* 下一個結點 */
                pa = pa -> next;
            }
        }
        if (type == a_s_b)
        {
            /* 將結點存至和鏈 */
            pc -> next = pa;
            pc = pa;
            pa = pa -> next;
        }
        if (type == a_g_b)
        {
            /* 將b鏈的當前結點存至和鏈 */
            pc -> next = pb;
            pc = pb;
            pb = pb -> next;
            hb -> next = pb;
        }
    }

    if(pa == NULL)
    {
        if(pb == NULL)
            free(hb);
        else
        {
            pc -> next = pb;
            free(hb);
        }
    }
    else
    {
        free(hb);
        pc -> next = pa;
    }
    return hc;

}

polynomial polyn_subtract(polynomial pa, polynomial pb)
{
    /* 先把pb鏈(減數)取負,然後調用加法函數即可 */
    polynomial hb = pb -> next;
    while(hb)
    {
        hb -> data.coef = 0 - (hb -> data.coef);
        hb = hb -> next;     
    }
    polynomial pc = polyn_add(pa, pb);
    return pc;
}

polynomial polyn_multiply(polynomial pa, polynomial pb)
{
    /* 積的頭結點 */
    polynomial p =(polynomial)malloc(sizeof(l_node));
    p -> next = NULL;
    /* 被乘數的當前結點 */
    polynomial pac = pa -> next;
    /* 乘數的當前結點 */
    polynomial pbc = pb -> next;
    while(pbc)
    {
        /* 中間鏈的頭結點 */
        polynomial pc = polyn_clone(pa);
        /* 中間鏈的當前結點 */
        polynomial pcc = pc -> next;
        while(pac)
        {
            pcc -> data.coef = (pac -> data.coef) * (pbc -> data.coef);
            pcc -> data.expn = (pac -> data.expn) + (pbc -> data.expn);
            pcc = pcc -> next;
            pac = pac -> next;
        }
        pac = pa -> next;
        p = polyn_add(p, pc);
        pbc = pbc -> next;
    }
    polyn_destroy(pa);
    polyn_destroy(pb);
    return p;
}


polynomial polyn_clone(polynomial HEAD)
{
    /* 源鏈的當前結點 */
    polynomial pnode  = HEAD;
    /* 目的鏈的頭結點和當前結點 */
    polynomial pclone_head,pclone_node;
    if(pnode != NULL)
    {
        pclone_head = (polynomial)malloc(sizeof(l_node));
        pclone_head -> data = pnode -> data;
        pclone_head -> next = NULL;
        pclone_node = pclone_head;
        pnode = pnode -> next;
    }
    while(pnode != NULL)
    {
        polynomial temp_node = (polynomial)malloc(sizeof(l_node));
        temp_node -> data = pnode -> data;
        temp_node -> next = NULL;
        pclone_node -> next = temp_node;
        pclone_node = pclone_node -> next;
        pnode = pnode -> next;
    }
    return pclone_head;
}

int main()
{
    /* 創建pa鏈表 */
    polynomial pa = (polynomial)malloc(sizeof(l_node));
    polyn_create(pa);
    /* 打印pa鏈表 */
    polyn_print(pa);
    /* 創建pb鏈表 */
    polynomial pb = (polynomial)malloc(sizeof(l_node));
    polyn_create(pb);
    /* 打印pb鏈表 */
    polyn_print(pb);
    /* 兩個多項式相乘 */
    polynomial p = polyn_multiply(pa, pb);
    /* 打印結果 */
    polyn_print(p);
    /* 乘積的長度 */
    printf("length=%d\n", polyn_length(p));
    return 0;
}