多项式加减运算：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("");
}