投稿
  1. 极客之音首页
  2. 数据结构

【数据结构】单链表的应用——有序多项式合并化简

小半 • • 数据结构 • 阅读 188

导读：本篇文章讲解 【数据结构】单链表的应用——有序多项式合并化简，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

 写在前面的话：本人是学生，水平有限，测试用例较少，如果有纰漏还请见谅。

有如下俩个多项式：

【数据结构】单链表的应用——有序多项式合并化简

 【数据结构】单链表的应用——有序多项式合并化简

 利用链表将他们合并成一个并且化简。

结点结构：

typedef struct node {
    float coef;     //系数
    int exp;        //指数
    struct node *next;  //链
} PolyNode;

算法1：一般算法，将合并后的结果表存在新的链表中：

优点：该算法执行完后原链表都不被破坏

缺点：空间复杂度为O(N）

算法实现（C）：

void Add(PolyNode *ha, PolyNode *hb, PolyNode *&hc) {
    PolyNode *pa = ha->next, *pb = hb->next, *s, *tc;
    double c;
    hc = (PolyNode *) malloc(sizeof(PolyNode));
    tc = hc;
    while (pa != NULL && pb != NULL) {
        if (pa->exp > pb->exp) {
            //建立新结点
            s = (PolyNode *) malloc(sizeof(PolyNode));
            s->exp = pa->exp;   //配置新结点信息
            s->coef = pa->coef; //配置新结点信息
            tc->next = s;   //链入该节点
            tc = s; //指针移到当前结点
            pa = pa->next;  //扫描下一结点
        } else if (pa->exp < pb->exp) {
            //同上
            s = (PolyNode *) malloc(sizeof(PolyNode));
            s->exp = pb->exp;
            s->coef = pb->coef;
            tc->next = s;
            tc = s;
            pb = pb->next;
        } else {
            //计算系数和
            c = pa->coef + pb->coef;
            if (c != 0) {   //如果系数和不0则配置新结点
                s = (PolyNode *) malloc(sizeof(PolyNode));
                s->exp = pa->exp;
                s->coef = c;
                tc->next = s;
                tc = s;
            }
            pa = pa->next;  //同时移动俩指针
            pb = pb->next;
        }
    }
    if (pb != NULL) {
        pa = pb;    //如果a式扫描完了就换成扫描b，只是化简，少一部判断和置换
    }
    while (pa != NULL) {
        //将剩余全部结点复制一份并链入新表
        s = (PolyNode *) malloc(sizeof(PolyNode));
        s->exp = pa->exp;
        s->coef = pa->coef;
        tc->next = s;
        tc = s;
        pa = pa->next;
    }
    tc->next = NULL;    //新结点指针置空
}

算法2：利用原有链表构建新结果链表：

优点：空间复杂度为O(N)

缺点：算法执行完后原链不能再使用

算法实现（C）：

//不创建空间复杂度为O(1)的多项式合并算法
void AddNew(PolyNode *ha, PolyNode *hb, PolyNode *&hc) {
    PolyNode *pa = ha->next, *pb = hb->next, *tc, *fp1, *fp2;
    double c;
    hc = ha;    //结果表头结点指针
    tc = hc;    //结果表头结点赋值给tc，让tc去操作
    while (pa != NULL && pb != NULL) {
        if (pa->exp < pb->exp) {//如果有b表项比a表项大
            tc->next = pb;    //tc指向b表最大项节点，
            pb = pb->next;    //移动pb指针，防止b表扫描指针pb丢失链表
            tc = tc->next;    //此时移动到b表当前最大节点
            tc->next = pa;    //让该节点指针域重新指回a表
        } else if (pa->exp > pb->exp) {
            //如果没有比当前a表大的项
            tc->next=pa;      //链入该结点
            tc = tc->next;    //移动结果表指针
            pa = pa->next;    //移动a表指针
        } else {
            c = pa->coef + pb->coef;    //计算系数和
            fp1 = pa;
            fp2 = pb;   //保存可能被合并指针
            if (c != 0) {
                pa->coef = c;   //重置该结点系数
                tc->next=pa;    //链入该结点
                tc = tc->next;  //结果表指针后移动
            }
            pa = pa->next;  //扫描指针后移动
            pb = pb->next;
            if (c == 0)
                free(fp1);  //释放被合并节点
            free(fp2);  //释放被合并节点
        }
    }
    if (pb != NULL) {
        pa = pb;    //同样是化简下一步
    }
    tc->next = pa;  //将剩余节点全部链入结果表
}

关键步骤：

【数据结构】单链表的应用——有序多项式合并化简

 此处算法思想如下图： 

【数据结构】单链表的应用——有序多项式合并化简

 如果你想直接拿代码跑一把，复制下面代码即可：

#include <stdlib.h>
#include <stdio.h>

#define Max 50
typedef struct node {
    float coef;     //系数
    int exp;        //指数
    struct node *next;  //链
} PolyNode;

//空间复杂度O(N)
void Add(PolyNode *ha, PolyNode *hb, PolyNode *&hc) {
    PolyNode *pa = ha->next, *pb = hb->next, *s, *tc;
    double c;
    hc = (PolyNode *) malloc(sizeof(PolyNode));
    tc = hc;
    while (pa != NULL && pb != NULL) {
        if (pa->exp > pb->exp) {
            //建立新结点
            s = (PolyNode *) malloc(sizeof(PolyNode));
            s->exp = pa->exp;   //配置新结点信息
            s->coef = pa->coef; //配置新结点信息
            tc->next = s;   //链入该节点
            tc = s; //指针移到当前结点
            pa = pa->next;  //扫描下一结点
        } else if (pa->exp < pb->exp) {
            //同上
            s = (PolyNode *) malloc(sizeof(PolyNode));
            s->exp = pb->exp;
            s->coef = pb->coef;
            tc->next = s;
            tc = s;
            pb = pb->next;
        } else {
            //计算系数和
            c = pa->coef + pb->coef;
            if (c != 0) {   //如果系数和不0则配置新结点
                s = (PolyNode *) malloc(sizeof(PolyNode));
                s->exp = pa->exp;
                s->coef = c;
                tc->next = s;
                tc = s;
            }
            pa = pa->next;  //同时移动俩指针
            pb = pb->next;
        }
    }
    if (pb != NULL) {
        pa = pb;    //如果a式扫描完了就换成扫描b，只是化简，少一部判断和置换
    }
    while (pa != NULL) {
        //将剩余全部结点复制一份并链入新表
        s = (PolyNode *) malloc(sizeof(PolyNode));
        s->exp = pa->exp;
        s->coef = pa->coef;
        tc->next = s;
        tc = s;
        pa = pa->next;
    }
    tc->next = NULL;    //新结点指针置空
}

//建立多项式列表
void CreateListR(PolyNode *&L, double a[], int b[], int n) {
    PolyNode *s, *tc;
    L = (PolyNode *) malloc(sizeof(PolyNode));
    tc = L;                 //tc始终指向尾结点，初始时间指向头结点
    for (int i = 0; i < n; ++i) {
        s = (PolyNode *) malloc(sizeof(PolyNode));
        s->coef = a[i];     //创建新结点
        s->exp = b[i];
        tc->next = s;       //将假设s插入tc结点之后
        tc = s;
    }
    tc->next = NULL;        //尾结点next域置为NULL
}

//销毁链表
void DestroyList(PolyNode *&L) {
    PolyNode *pre = L, *p = pre->next;  //保存下一个结点的地址
    while (p != NULL) {
        free(pre);  //释放当前指针所指内存空间
        pre = p;        //记录当前结点地址
        p = p->next;    //移向下一结点
    }
    free(pre);  //释放最后一个结点
}

//输出多项式链表
void DispPoly(PolyNode *&L) {
    PolyNode *p = L->next;
    while (p != NULL) { //如果当前指针不为空
        printf("(%gx^%d)", p->coef, p->exp);    //打印结点存储的信息
        p = p->next;
        if (p != NULL) {
            printf("+");
        }
    }
    printf("\n");
}

//不创建空间复杂度为O(1)的多项式合并算法
void AddNew(PolyNode *ha, PolyNode *hb, PolyNode *&hc) {
    PolyNode *pa = ha->next, *pb = hb->next, *tc, *fp1, *fp2;
    double c;
    hc = ha;    //结果表头结点指针
    tc = hc;    //结果表头结点赋值给tc，让tc去操作
    while (pa != NULL && pb != NULL) {
        if (pa->exp < pb->exp) {//如果有b表项比a表项大
            tc->next = pb;    //tc指向b表最大项节点，
            pb = pb->next;    //移动pb指针，防止b表扫描指针pb丢失链表
            tc = tc->next;    //此时移动到b表当前最大节点
            tc->next = pa;    //让该节点指针域重新指回a表
        } else if (pa->exp > pb->exp) {
            //如果没有比当前a表大的项
            tc->next=pa;      //链入该结点
            tc = tc->next;    //移动结果表指针
            pa = pa->next;    //移动a表指针
        } else {
            c = pa->coef + pb->coef;    //计算系数和
            fp1 = pa;
            fp2 = pb;   //保存可能被合并指针
            if (c != 0) {
                pa->coef = c;   //重置该结点系数
                tc->next=pa;    //链入该结点
                tc = tc->next;  //结果表指针后移动
            }
            pa = pa->next;  //扫描指针后移动
            pb = pb->next;
            if (c == 0)
                free(fp1);  //释放被合并节点
            free(fp2);  //释放被合并节点
        }
    }
    if (pb != NULL) {
        pa = pb;    //同样是化简下一步
    }
    tc->next = pa;  //将剩余节点全部链入结果表
}
 
int main(){
    PolyNode *Poly1,*Poly2,*Poly3;
    double a[Max];
    int b[Max],n;
    //第一个链表
    a[0]=6;b[0]=7;
    a[1]=1,b[1]=6;
    a[2]=0.5;b[2]=4;
    a[3]=-5;b[3]=2;
    a[4]=-5;b[4]=-1;
    n=5;
    CreateListR(Poly1,a,b,n);
    printf("第一个多项式：");
    DispPoly(Poly1);
    //第二个链表
    a[0]=-1;b[0]=6;
    a[1]=4;b[1]=5;
    a[2]=-3;b[2]=4;
    a[3]=5;b[3]=2;
    a[4]=-5;b[4]=1;
    a[5]=8;b[5]=-1;
    n=6;
    CreateListR(Poly2,a,b,n);
    printf("第二个多项式：");
    DispPoly(Poly2);
//    Add(Poly1,Poly2,Poly3); //空间复杂度O(N)
    AddNew(Poly1,Poly2,Poly3); //空间复杂度O(1)
    printf("相加后的多项式：");
    DispPoly(Poly3);
    DestroyList(Poly1);
    DestroyList(Poly2);
    DestroyList(Poly3);
    return 0;
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/82644.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！