【数据结构】一元多项式的表示与相加（无序输入 有序输出）

分类:热门推荐日期:2024-04-15浏览:1评论:0

一元多项式的表示与运算——课程设计（无序输入 有序输出）

目录

  • 一元多项式的表示与运算——课程设计（无序输入 有序输出）
    • 一.例题：（输入无序，指数升序排列的一元多项式）
      • 1. 链表结点定义
      • 2. 创建单链表存放一元多项式(将无序的输入有序存放于链表)
      • 3. 输出一元多项式
      • 4. 一元多项式求值
      • 5. 删除一元多项式中的指定项
      • 6. 实现两个一元多项式相加 ha = ha + hb
      • 二.例题：（有序）指数升序排列输出一元多项式
        • 1. 链表结点定义
        • 2. 创建单链表存放一元多项式（按照指数升序排列）
        • 3. 按升序输出一元多项式
        • 4. 计算一元多项式的值
        • 5. 实现两个一元多项式相加 ha = ha + hb

          ∙ 主要内容：用线性表表示一元多项式。实现一元多项式的相加、求导、求值、相减等运算

          相加算法实现：首先确定表示一元多项式的线性表的存储方式----顺序存储结构，链式存储结构均可；

          两种存储方式：顺序存储结构和链式存储结构（本文采用链式存储方式解题）

          1. 一元多项式的指数很高且相邻的指数相差很大时，宜只存放系数非零项的系数和相应的指数，否则浪费存储,且系数非零项仍按指数升序排列方便运算实现。（存储中根据系数的稀疏性来选择）
          2. 对于次数低的,方便多项式之间的运算,可采用按项顺序存储的形式。

          一.例题：（输入无序，指数升序排列的一元多项式）

          【问题描述】读入一元多项式中每一项的系数和指数，建立单链表存放输入的一元多项式，写出遍历单链表输出所存放的一元多项式，一元多项式相加，求一元多项式的值，删除一元多项式中指定项等相关操作

          【输入形式】x的值，2个一元多项式各项（顺序随意），要删除相加后多项式的指数项

          【样例输入1】

          2 
-1 0 8 3 10 8 2 20 0 0
1  0 5  3  6  2  2 20 0 0
8

          【样例说明1】 输入： 第1行的2是一元多项式x的值 第2行和第3行是两个一元多项式每一项的系数和指数，不要求有序输入，以0 0结束

          第4行是删除的相加后多项式的指数项

          输出 第1、2、3行，参照例子 第4行为删除相加后指数项之后的多项式.

          【样例输入2】

          2
1 2 3 5 4 3 0 0
2 0 -3 5 3 3  2 1 0 0
3

          1. 链表结点定义

          /* 链表结点定义 */
typedef struct LNode{ int exp, coef; //coef为指数, exp为系数
    struct LNode *next;
}LNode, *LinkList;

          2. 创建单链表存放一元多项式(将无序的输入有序存放于链表)

          /* 创建单链表存放一元多项式*/
void CreateList(LinkList &L)
{ L=(LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LinkList p;
    LinkList pre=L;//
    LinkList s=L;// 尾插法的尾指针
    L->coef = 0.0;//先初始化一下
    L->exp = 0;
    //一直输入  检测到 输入0 0 的时候截至
    while(true){ p=(LinkList)malloc(sizeof(LNode));
        p->next=NULL;
        if(p==NULL) return;//是否开辟成功
        scanf("%d",&p->coef);
        scanf("%d",&p->exp);
        if(!p->exp&&!p->coef){ free(p); //如果输入有误 就把多开辟的空间释放掉
            return;
        }
        if(p->exp>=s->exp){//输入正序的话就尾插
            s->next = p;
            s=p;
        }
        else{//输入比上一个小 说明输入无序 插入
            while(pre->next){ pre=pre->next;//从头向后找 插入的位置
                if(pre->next->exp>p->exp && pre->exp <= p->exp){ //找到插入的位置
                    p->next = pre->next;//插入
                    pre->next=p;
                    pre = L;//重置pre的指向位置 以便下一次找位置
                    break;//插入完成 退出循环
                }
            }
        }
    }
 }

          3. 输出一元多项式

          //遍历单链表,格式化输出一元多项式的每一项
void Display(LinkList L)
{ LinkList p = L->next;
    int First_Term = 1; 
    //表示当前处理的项是否是多项式的第一项 第一项前面不需要额外正负号
    while (p != NULL) { if (p->exp) { if (!First_Term && p->coef > 0) { //整数加上+号
                printf("+"); 
            }
            printf("%dx^%d", p->coef, p->exp);
        } else { //指数为零 直接打印
            printf("%d", p->coef);
        }
        First_Term = 0; //修改标签
        p = p->next;
    }
}

          4. 一元多项式求值

          /* 一元多项式求值 */
double Value(LinkList L, int x)
{ LinkList p=L->next;
    double function_sum=0.0;
    while(p!=NULL){ function_sum += p->coef*pow(x,p->exp);
        p=p->next;
    }
    return function_sum;
}/* 一元多项式求值 */

          5. 删除一元多项式中的指定项

          /*删除一元多项式中的指定项 */
void DeleteElem(LinkList &L, int e)
{ //在这里插入你的代码
    LinkList p=L->next;//线性表的第一个数据元素
    //p在前面 探路
    LinkList q=L;// q指向 p的前驱结点地址 
    while(p!=NULL){ if(p->exp==e){//发现指定指数项
            q->next=p->next;//删除该项
            free(p);
            return;
        } 
        else{ //未发现该指数项 两指针后移 继续探寻
            q=p;
            p=p->next;
        }
    }
}//DeleteElem

          6. 实现两个一元多项式相加 ha = ha + hb

          //ha = ha + hb 
void  AddPoly(LinkList ha,LinkList hb)
{ LinkList pa = ha->next;//探路
    LinkList pb = hb->next;//探路
    LinkList p = ha;// p指向 pa的前继结点 
    while(pa&&pb){ if(pa->expexp){ //情况一：当ha中该项的指数小时 指针p 和 pa 直接向后移动一位
            p = pa;//后移
            pa=pa->next;//后移
        }
        else if(pa->exp>pb->exp){ //情况二：当ha中该项的指数大时 需要将hb中该节点 连接进来
        //接入： 指针p 的后继指向pb  pb的后继指向pa  
        //后移： p 、pb均向后移动一位
            hb->next=pb->next;//ha 拿走该pb指向的这个结点
            pb->next=pa;//接入： 指针p 的后继指向pb  pb的后继指向pa  
            p->next=pb;
            p=pb;//后移： p 、pb均向后移动一位
            pb=hb->next;
        }
        else{ //情况三：相等的时候 需要求和
            pa->coef +=pb->coef;//求和：放入ha中
            hb->next=pb->next;//该pb指向的节点直接删 他的系数已经被ha加上了
            free(pb);//释放空间
            pb=hb->next;//更新pb的指向
            if(pa->coef){ //不为零时 正常后移
                p = pa;
            }
            else{//删除相加后 系数为0 的项
            //系数为零时
            // 节省储存空间
                p->next = pa->next;
                free(pa);//这个释放的原理 要搞清楚
                //更新pa的指向
            }
            pa=p->next;//更新pa的指向 pa
        }
    }
    p->next = pa?pa:pb;//接入剩余的结点
    free(hb);//释放空间
}

          二.例题：（有序）指数升序排列输出一元多项式

          从键盘读入一元多项式中每一项的系数和指数，请编写算法实现（类C语言算法描述，不是完整程序代码）：

          （1）建立带表头结点的单链表存放一元多项式（按照指数升序排列）； void CreatePoly(LinkList &pa)

          （2）输出一元多项式的所有数据元素(按照指数升序输出每一系数非0项的系数和指数)； void Display(LinkList pa)

          （3）输入自变量的值，计算一元多项式的值； int Evaluation(LinkList pa, int

          x)，pa为头结点，x为自变量，返回值为一元多项式的值 （4）输入两个一元多项式，求一元多项式的和多项式（不是求值）。 void

          AddPoly(LinkList ha,LinkList hb)，结果放入ha链表

          1. 链表结点定义

          typedef struct Node{ float coef_num;//系数的值
    int expn_num;//指数的值
    struct Node *next;
}Term,*LinkList;
//使用链表

          2. 创建单链表存放一元多项式（按照指数升序排列）

          //（1）建立带表头结点的单链表存放一元多项式（按照指数升序排列）；
//循环截至条件 按个数输入 
void CreatePoly(LinkList &pa) 
{ int m;
    cout<<"请输入 一元多项式的项数"<>m;
    pa=(LinkList)malloc(sizeof(Node));
    pa->next = NULL;
    LinkList p;
    LinkList s=pa;
    pa->coef_num = 0.0;;
    pa->expn_num = 0;
    // 输入到指定 个数停止
    for(int i = 0; i < m; i++){ p=(LinkList)malloc(sizeof(Node));
        p->next=NULL;
        if(p==NULL) return;
        cin>>p->coef_num;
        cin>>p->expn_num;
        //尾插法
        s->next = p;
        s=p;
    }
}
void CreatePoly1(LinkList &pa) 
{ cout<<"请输入 一元多项式的系数(系数不为零) 和 指数(输入0 0时停止)"<next = NULL;
    LinkList p;
    LinkList s=pa;
    pa->coef_num = 0.0;
    pa->expn_num = 0;
    //一直输入  检测到 输入0 0 的时候截至
    while(true){ p=(LinkList)malloc(sizeof(Node));
        p->next=NULL;
        if(p==NULL) return;
        cin>>p->coef_num;
        cin>>p->expn_num;
        if(!p->expn_num&&!p->coef_num){ free(p);
            return;
        }
        //尾插法
        s->next = p;
        s=p;
    }
}

          3. 按升序输出一元多项式

          //（2）输出一元多项式的所有数据元素(按照指数升序输出每一系数非0项的系数和指数)； 
void Display(LinkList pa) { LinkList p=pa->next;
    while(p!=NULL){ cout<< p->coef_num<<" "<expn_num<next;
    }
}

          4. 计算一元多项式的值

          //输入自变量的值，计算一元多项式的值； 
float Evaluation(LinkList pa, int x){//pa为头结点，x为自变量，返回值为一元多项式的值 
    LinkList p=pa->next;
    float function_sum=0.0;
    while(p!=NULL){ function_sum += p->coef_num*pow(x,p->expn_num);
        p=p->next;
    }
    return function_sum;
}

          5. 实现两个一元多项式相加 ha = ha + hb

          void AddPoly1(LinkList ha, LinkList hb){ LinkList pa = ha->next;//探路
    LinkList pb = hb->next;//探路
    LinkList p = ha;// pa的前继结点 //
    while(pa&&pb)
        if(pa->expn_numexpn_num){ //情况一：当ha中该项的指数小时 指针p 和 pa 直接向后移动一位
            p=pa;
            pa=pa->next;
        }
        else if(pa->expn_num == pb->expn_num){ //情况二：相等的时候 需要求和
            pa->coef_num += pb->coef_num;//求和：放入ha中
            hb->next=pb->next;//该pb指向的节点直接删 他的系数已经被ha加上了
            free(pb);
            pb=hb->next;
            
            if(!pa->coef_num){ //判断加和后系数是否为零
            //系数为零的情况 删除pa指向的这个结点
                p->next=pa->next;
                free(pa);//pa指向的释放了这个地址
                pa=p->next; 
            }
            else{ //如果不为零 正常后移
                p=pa;
                pa=pa->next;
            }
        }
        else{ //情况三：当ha中该项的指数大时 需要将hb中该节点 连接进来
        //接入： 指针p 的后继指向pb  pb的后继指向pa  
        //后移： p 、pb均向后移动一位
            hb->next=pb->next;//ha 拿走该pb指向的这个结点
            pb->next=pa;//接入： 指针p 的后继指向pb  pb的后继指向pa  
            p->next=pb;
            p=pb;//后移： p 、pb均向后移动一位
            pb=hb->next;
        }
        if(pb) p->next=pb;//接入剩余的结点
        free(hb);
}

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号