程式師世界 >> 編程語言 >> C語言 >> C >> C語言入門知識 >> 多項式加減運算：C語言描述

多項式加減運算：C語言描述

編輯：C語言入門知識

數據結構

//節點
typedef struct node {
    float coefficient; //系數
    int exponent;  //指數
    struct node * next;
} Node;

//多項式鏈表
typedef struct list {
    Node * head;
} List;

算法描述

示例圖以減法為例
1. 創建兩個指針：
p: 指向鏈表A的頭節點
node：指向鏈表B的頭節點
2. node指針與p->next比較：
1. 如果大於：就插入p指針後，然後p指針後移，node後移；

2. 如果等於，則直接進行與運算。若運算後p->next的系數為0，則刪除該節點。p指針後移，node後移；

3. 如果小於，則p指針後移。
4. 若p->next為空，則直接將node所指節點接在p之後。p後移，node後移
5. 重復步驟2，直至node為空（鏈表B完成運算）

算法實現

插入一個節點

//插入一個項，返回插入位置
Node * insertNode(Node * head, Node * node) {
    Node * pNode = head;
    while (pNode->next != NULL) {
        if (node->exponent == pNode->next->exponent) {
            //如果系數相等，則直接把系數相加
            pNode->next->coefficient += node->coefficient;
            if (pNode->next->coefficient == 0) {
                //如果相加後系數為0，則刪除該節點
                pNode->next = pNode->next->next;
                return pNode;
            }
            return pNode->next;
        } else if (node->exponent > pNode->next->exponent) {
            //如果系數不等，則比較系數和下一向的系數，若比下一項的小，則插入這一項的後面。
            Node * newNode = cloneNode(*node);
            newNode->next = pNode->next;
            pNode->next = newNode;
            return newNode;
        }
        pNode = pNode->next;
    }
    //比較到最後，說明這項為最小的，則直接插入最後
    pNode->next = cloneNode(*node);
    return pNode->next;
}

返回值：
插入node後，p後移後的值

相加

//將兩個多項式相加
void subList(List * listA, List * listB) {
   //操作多項式A的指針
   Node * pNodeA = listA->head;
   //操作多項式B的指針
   Node * pNodeB = listB->head->next;
   while (pNodeB != NULL) {
      //插入節點，將pNodeA更新到處於插入位置的節點（相當於後移）
      pNodeA = insertNode(pNodeA, pNodeB); //1
      //pNodeB指針後移
      pNodeB = pNodeB->next;
   }
}

insertNode函數如上

相減

//將兩個多項式相減
void subList(List * listA, List * listB) {
    //操作多項式A的指針
    Node * pNodeA = listA->head;
    //操作多項式B的指針
    Node * pNodeB = listB->head->next;

    while (pNodeB != NULL) {
        //系數變為相反數再插入，達到相減的效果
        pNodeB->coefficient *=-1 ;
        //插入節點，將pNodeA更新到處於插入位置的節點（相當於後移）
        pNodeA = insertNode(pNodeA, pNodeB); //○1
        //pNodeB指針後移
        pNodeB = pNodeB->next;
    }
}

分析

這個算法兩條鏈的指針都沒有回溯，算法復雜度為O(n)

測試

測試方法

int main() {
    //系數
    float coef1[5] = { 2, 3, 5, -3, 9 };
    //指數
    int exp1[5] = { 2, 5, 4, 5, 6 };
    //創建多項式
    List * list1 = createList(coef1, exp1, 5);
    puts("------ List1: ------");
    printList(*list1);

    float coef2[6] = { 5, 4, 5, -6, 1, 5 };
    int exp2[6] = { 3, 8, 4, 6, 2, 7 };
    List * list2 = createList(coef2, exp2, 6);
    puts("------ List2: ------");
    printList(*list2);

    puts("===== (List1 - List2 =====");
    //相減
    subList(list1,list2);
    printList(*list1);

    return 0;
}

結果

完整代碼

/*
 * Polynomials.c
 *
 *  Created on: 2016年10月20日
 *      Author: BaiYunfei
 */

#include 
#include 
#include 

//節點
typedef struct node {
    float coefficient;    //系數
    int exponent;        //指數
    struct node * next;
} Node;

//多項式
typedef struct list {
    Node * head;
} List;

//初始化
void Initialize(List * list);
//構建一個多項式
List * createList(float * coef, int * exp, int length);
//復制一個節點
Node * cloneNode(Node node);
//從head處開始，將node插入正確的位置，並返回插入處的節點
Node * insertNode(Node * head, Node * node);
//將listB加入到listA中
void addList(List * listA, List * listB);
//用多項式listA減去多項式listB
void subList(List * listA, List * listB);
//從頭開始插入節點
void insertNodeFromHead(List * list, Node * node);
//打印一個節點
void printNode(Node node);
//打印一個多項式
void printList(List list);

//初始化
void Initialize(List * list) {
    Node * head = (Node *) malloc(sizeof(Node));
    head->next = NULL;
    list->head = head;
}

//跟據系數矩陣和指數矩陣創建多項式鏈表
List * createList(float * coef, int * exp, int length) {
    List * list = (List *)malloc(sizeof(List));
    Initialize(list);
    for (int i = 0; i < length; ++i) {
        Node * node = (Node *) malloc(sizeof(Node));
        node->coefficient = coef[i];
        node->exponent = exp[i];
        insertNodeFromHead(list, node);
    }
    return list;
}

//插入一個項，返回插入位置
Node * insertNode(Node * head, Node * node) {
    Node * pNode = head;
    while (pNode->next != NULL) {
        if (node->exponent == pNode->next->exponent) {
            //如果系數相等，則直接把系數相加
            pNode->next->coefficient += node->coefficient;
            if (pNode->next->coefficient == 0) {
                //如果相加後系數為0，則刪除該節點
                pNode->next = pNode->next->next;
                return pNode;
            }
            return pNode->next;
        } else if (node->exponent > pNode->next->exponent) {
            //如果系數不等，則比較系數和下一向的系數，若比下一項的小，則插入這一項的後面。
            Node * newNode = cloneNode(*node);
            newNode->next = pNode->next;
            pNode->next = newNode;
            return newNode;
        }
        pNode = pNode->next;
    }
    //比較到最後，說明這項為最小的，則直接插入最後
    pNode->next = cloneNode(*node);
    return pNode->next->next;
}

//將兩個多項式相加
void addList(List * listA, List * listB) {
    Node * pNodeA = listA->head;
    Node * pNodeB = listB->head->next;

    while (pNodeB != NULL) {
        pNodeA = insertNode(pNodeA, pNodeB);
        pNodeB = pNodeB->next;
    }
}

//將兩個多項式相減
void subList(List * listA, List * listB) {
    //操作多項式A的指針
    Node * pNodeA = listA->head;
    //操作多項式B的指針
    Node * pNodeB = listB->head->next;

    while (pNodeB != NULL) {
        //系數變為相反數再插入，達到相減的效果
        pNodeB->coefficient *=-1 ;
        //插入節點，將pNodeA更新到處於插入位置的節點
        pNodeA = insertNode(pNodeA, pNodeB);
        //pNodeB指針後移
        pNodeB = pNodeB->next;
    }
}

//從鏈表的頭節點開始插入
void insertNodeFromHead(List * list, Node * node) {
    insertNode(list->head, node);
}

int main() {
    //系數
    float coef1[5] = { 2, 3, 5, -3, 9 };
    //指數
    int exp1[5] = { 2, 5, 4, 5, 6 };
    //創建多項式
    List * list1 = createList(coef1, exp1, 5);
    puts("------ List1: ------");
    printList(*list1);

    float coef2[6] = { 5, 4, -5, -6, 1, 5 };
    int exp2[6] = { 3, 8, 4, 6, 2, 7 };
    List * list2 = createList(coef2, exp2, 6);
    puts("------ List2: ------");
    printList(*list2);

    puts("===== (List1 - List2 =====");
    //相減
    subList(list1,list2);
    printList(*list1);

    return 0;
}

//復制一個節點
Node * cloneNode(Node node) {
    Node * pNode = (Node *) malloc(sizeof(Node));
    pNode->coefficient = node.coefficient;
    pNode->exponent = node.exponent;
    return pNode;
}

//打印一個項
void printNode(Node node) {
    printf("%.3fx^%d", node.coefficient, node.exponent);
}

//打印多項式
void printList(List list) {
    Node * pNode = list.head->next;
    while (pNode != NULL) {
        printNode(*pNode);
        pNode = pNode->next;
        if (pNode != NULL) {
            printf(" + ");
        }
    }
    puts("");
}