精华内容
下载资源
问答
  • 数据结构一元多项式运算分析

    千次阅读 多人点赞 2014-09-27 22:33:15
    1.建立多项式:尾插法建立一元多项式的链表,通过键盘输入多项式的系数和指数,以输入系数0为结束标志,并约定建立一元多项式链表时,总是按指数从小到大的顺序排列。 2.输出多项式:从单链表的第一项开始逐项读出...
     一元多项式的加法,减法,乘法用到比较多的是插入,删除操作。所以一般选择单链表作为存储结构。每个结点分别有系数,指针作为数据域,以及指针域。
    算法实现:
    一.一元多项式加法:
    1.建立多项式:尾插法建立一元多项式的链表,通过键盘输入多项式的系数和指数,以输入系数0为结束标志,并约定建立一元多项式链表时,总是按指数从小到大的顺序排列。
    2.输出多项式:从单链表的第一项开始逐项读出系数和指数,按多项式的形式输出。
    3.多项式相加:设La和Lb分别表示两个多项式。Lc表示和多项式。p,q,r分别表示指向单链表的当前项比较指数大小。
    (1)若La->exp<Lb->exp,则结点p应是和多项式中的一项,将p复制到r,并使p后移。
    (2)若La->exp = Lb->exp,则将两个结点中的系数相加,当和不为0时,La的系数域加上Lb的系数域作为Lc的系数域;若和为0,则和多项式中没有这一项,p,q后移。
    (3)若La->exp > Lb->exp,则将结点q复制到Lc中,q后移。

    二.一元多项式减法
    算法:将减数多项式的所有系数先变为相反数,然后调用多项式相加的函数进行运算。

    三.一元多项式乘法
    两个多项式相乘,应该是第一个多项式中的每一项分别与第二个多项式相乘,将相乘得到的结果都存在第一个多项式中,再调用合并多项式的函数。我写的多项式相乘用到了两重循环,合并多项式也用到了两重循环。


    小结:在这次代码实现中,主要还是基础的一些线性表的操作的练习,还可以进一步改良的地方就是可以在合并多项式这部分与多项式相加写成一个函数,这样可以减少代码量,代码的通用性更高。

    附:源代码
    #include<stdio.h>
    #include<stdlib.h>


    typedef struct NODE{
    int coef; //系数
    int exp; //指数
    struct NODE *next;
    }polynode,*Polylist;

    int output_list(Polylist head);

    Polylist Creat_list(){ //创建链表
    Polylist head,rear,s;
    head = (Polylist)malloc(sizeof(polynode));
    rear = head;

    while(1){
    printf("input the coef,exp:\n");
    s = (Polylist)malloc(sizeof(polynode));
    scanf("%d", &s->coef);
    if(!s->coef){
    free(s);
    break;
    }
    scanf("%d", &s->exp);
    rear->next = s;
    rear = s;
    }
    rear->next = NULL;
    return (head);
    }


    Polylist add_list(Polylist head1,Polylist head2){ //多项式加法
    Polylist p, q, s, head, tail; 
    p = head1->next;
    q = head2->next;
    tail = head = (Polylist)malloc(sizeof(polynode));
    while(p && q){
    s = (Polylist)malloc(sizeof(polynode));
    if(p->exp < q->exp){ //当P的指数小于Q的指数时
    s->coef = p->coef;
    s->exp = p->exp;
    tail->next = s; 
    tail = s;
    tail ->next = NULL;
    p = p->next;

    }
    else if(p->exp == q->exp){ //当指数相等时
    s->coef = p->coef + q->coef;
    s->exp = p->exp;
    if (!s->coef){
    free(s);
    }
    else{
    tail->next = s; 
    tail = s;
    tail ->next = NULL;
    }
    p = p->next;
    q = q->next;
    }

    else{
    s->coef = q->coef;
    s->exp = q->exp;
    tail->next = s; 
    tail = s;
    tail ->next = NULL; 
    q = q->next;
    }
    }
    if(p)
    tail->next = p;
    else
    tail->next = q;
    return head;
    }


    Polylist sub_list(Polylist head1,Polylist head2){ //多项式减法
    Polylist p ,head;
    p = head2->next;
    do{
    p->coef = -p->coef;
    p = p->next;
    }while(p);
    head =add_list(head1,head2);
    return head; 
    }



    Polylist polyadd_list(Polylist head){ //合并多项式
    Polylist p,q,m;
    p = m = head->next;
    while(p ->next ){
    m = p;
    q = p->next;
    while(q){
    if(q->exp == p->exp){ 
    p->coef += q->coef;
    m->next = q->next;
    free(q);
    q = m->next;
    }
    else{
    m = q;
    q = q->next;
    }
    }
    p = p->next;
    }
    return head;
    }


    Polylist multi_list(Polylist head1,Polylist head2){ //多项式乘法
    Polylist head,p,q,r,m;
    head = r = (Polylist)malloc(sizeof(polynode));

    for(p = head1->next;p != NULL;p = p->next)
    {
    for(q = head2->next;q != NULL;q = q->next)
    {
    m = (Polylist)malloc(sizeof(polynode));
    m->coef = p->coef * q->coef;
    m->exp = p->exp + q->exp;
    r->next = m;
    r = m;
    }
    }
    r->next = NULL;
    output_list(head);
    polyadd_list(head);
    return head;
    }



    int output_list(Polylist head){ //输出多项式
    Polylist p;
    int n = 1;
    for(p = head->next;p !=NULL;p = p->next){
    printf("第%d项:%d   %d   \n", n++,p->coef,p->exp);
    }
    return 0;
    }

     
    int main(){
    Polylist head1,head2,head;
    head1 = Creat_list();
    head2 = Creat_list();

     
    printf("多项式加法:\n");
        head =add_list(head1,head2);
    output_list(head);

    printf("多项式减法:\n");
    head = sub_list(head1,head2); 
     output_list(head);
     

    printf("多项式乘法:\n");
    head = multi_list(head1,head2);
    output_list(head);


    return 0;
    展开全文
  • 一元多项式的乘法与加法运算(java顺序存储结构实现) 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零项个数,再以指数递降方式输入一个多项式非零项系数和指数...

    一元多项式的乘法与加法运算(java顺序存储结构实现)

    设计函数分别求两个一元多项式的乘积与和。
    输入格式:
    输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。

    输出格式:
    输出分2行,分别以指数递降方式输出 乘积多项式 以及 和多项式 非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。零多项式应输出0 0。

    import java.util.Scanner;
    
    public class demo02 
    {
    	public static void main(String[] args) 
    	{
    		/**
    			一元多项式的乘法与加法运算
    			设计函数分别求两个一元多项式的乘积与和。
    输入格式:
    输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。
    
    输出格式:
    输出分2行,分别以指数递降方式输出 乘积多项式 以及 和多项式 非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。零多项式应输出0 0。
    		*/
    
    		Scanner scan = new Scanner(System.in);
    		System.out.print("请输入第一行数字:");
    		String str1 = scan.nextLine();
    		String[] arr1 = str1.split(" ");
    		int num1[] = new int[arr1.length];
    		for(int i = 0; i<num1.length; i++){
    			num1[i] = Integer.parseInt(arr1[i]);
    		}
    		System.out.print("请输入第二行数字:");
    		String str2 = scan.nextLine();
    		String[] arr2 = str2.split(" ");
    		int num2[] = new int[arr2.length];
    		for(int i = 0; i<num2.length; i++){
    			num2[i] = Integer.parseInt(arr2[i]);
    		}
    
    		long startTime=System.currentTimeMillis();     //计时器
    		/*
    			一、线性存储结构
    			做成数组形式
    		*/
    		int[] c = add(num1, num2);		//多项式之和
    		System.out.print("合并同类项:");
    		for (int i=0; i<c.length; i++ )
    		{
    			System.out.print(c[i]+" ");
    		}
    
    		int[] d = multi(num1,num2);		//多项式之积
    		System.out.println("多项式乘积:");
    		for (int i=0; i<d.length; i++ )
    		{
    			System.out.print(d[i]+" ");
    		}
    
    		
    		long endTime=System.currentTimeMillis(); 
    		long spentTime=(endTime-startTime);
    		System.out.print("耗时:"+spentTime+"ms");
    		scan.close();
    	}
    
    	public static int[] add(int[] a, int[] b){
    		/*顺序存储结构下的多项式之和
    			以两个数组的长度之和构造一个新数组,将计算值放入新数组中
    			使用same计算中间可能合并的项数
    			如果无法合并时,将较大项放入到新数组中
    		*/
    		int[] c = new int[(a.length+b.length-1)];    //新建立数组
    		int m = a[0];    //第一行的多项式项数
    		int n = b[0];    //第二行的多项式项数
    		int l = m+n;						   //新数组的项数
    		int i=1, j=1, k=1;
    		int same=0;
    		while(i<=a[0] && j<=b[0]){
    			if(a[2*i]<b[2*j]){
    				c[2*k] = b[2*j];
    				c[2*k -1] = b[2*j -1];
    				j++;
    				k++;
    			}
    			else if(a[2*i]>b[2*j]){
    				c[2*k] = a[2*i];
    				c[2*k -1] = a[2*i -1];
    				i++;
    				k++;
    			}
    			else if(a[2*i] == b[2*j]){
    				if(a[2*i-1]+b[2*j-1] == 0){
    					i++;
    					j++;
    					same = same+2;
    				}else{
    					c[2*k] = a[2*i];
    					c[2*k-1] = a[2*i-1]+b[2*j-1];
    					same = same+1;
    					i++;
    					j++;
    					k++;
    				}
    			}
    		}
    		while(i<=a[0]){
    			c[2*k] = a[2*i];
    			c[2*k -1] = a[2*i -1];
    			i++;
    			k++;
    		}
    		while(j<=b[0]){
    			c[2*k] = b[2*j];
    			c[2*k -1] = b[2*j -1];
    			j++;
    			k++;
    		}
    
    		l = l-same;
    		c[0]=l;
    		return c;
    	}
    
    	public static int[] multi(int[] a, int[] b){
    		/*
    			求解两个多项式的乘积
    			首先定义一个二维数组,行数为a[0],列数为b[0]*2+1,记为数组c[][],分别使用数组a的每一项去和b的每一项相乘,得到二维数组c
    			将二维数组c的每一行看做一个多项式,运用多项式的加法add函数进行组合
    		*/
    		int[][] c = new int[a[0]][b[0]*2 + 1];
    		int[] d = new int[a[0]*b[0]*2 + 1];
    		int k=1;
    
    		for(int i=1; i<a[0]; i++){
    			c[i-1][0] = b[0];
    			k=1;
    			for(int j=1; j<b[0]; j++){
    				c[i-1][2*k] = a[2*i] + b[2*j];	//指数项乘积
    				c[i-1][2*k-1] = a[2*i-1] * b[2*j-1];	//系数项乘积
    				k++;
    			}
    		}
    		for(int i=0; i<c.length; i++){
    			d = add(d, c[i]);
    		}
    		return d;
    	}
    }
    
    
    展开全文
  • 设计程序,输入两个一元稀疏多项式, 分别完成二者的加法、减法、乘法运算,输出和多项式、差多项式、乘积多项式, 并求多项式在x(double型)处的值。要求: ... 2、乘法运算的实现使用单链表为存储结构
  • 用 C语言实现一元多项式的运算(相加,相减,相乘) 1.创建多项式时,无论指数项按什么顺序输入,输出均能实现以升幂顺序输出,且输入时有相同指数项时能够实现合并。 2.能够代入确切X计算出最终多项式值。 ...

    用 C语言实现一元多项式的运算(相加,相减,相乘)
    1.创建多项式时,无论指数项按什么顺序输入,输出均能实现以升幂顺序输出,且输入时有相同指数项时能够实现合并
    2.能够代入确切的X计算出最终多项式的值。


    模块划分
    本程序划分为9个模块,分别是:                                     

    1.主函数模块                                                            2.LocateElem模块(定位排序)                                

    3.CreatePolyn模块(创建多项式)                          4.AddPolyn模块(多项式相加)                               

    5.PrintPolyn模块(打印多项式)                             6.SubPolyn模块(多项式相减)                               

    7.Reverse模块(升幂,降幂)                                8.MultiplyPolyn模块(多项式相乘)                            

    9.Calculate模块(代入X求值)

     

    定义部分

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h> 
    
    #define LEN sizeof(Poly)
    
    typedef struct term{
        float coef;        //系数 
        int expn;        //指数 
        struct term *next;
    }Poly,*Link;
    int LocateElem(Link p, Link s, Link &q); 
    void CreatePolyn(Link &p,int m);    //创建多项式 
    void PrintPolyn(Link p);            //打印多项式(表示)            
    int cmp(Link a, Link b);
    Link AddPolyn(Link pa, Link pb);    //多项式相加 
    Link SubPolyn(Link pa, Link pb);    //多项式相减 
    Link Reverse(Link p);                //逆置多项式 
    Link MultiplyPolyn(Link A,Link B);    //多项式相乘 
    void Calculate(Link p,float x);        //多项式求值 


    主函数部分

    int main()
    {
        Link P1,P2,P3;    //多项式 
        int L1,L2;        //多项式长度 
        printf("                        -------------------------------------------------------------------\n");
        printf("                        |==================       一元多项式的运算       =================|\n");
        printf("                        |==================          1.相加(+)         =================|\n");
        printf("                        |==================          2.相减(-)         =================|\n");
        printf("                        |==================          3.相乘(*)         =================|\n");
        printf("                        -------------------------------------------------------------------\n\n");
        printf("请输入第一个多项式的项数:");
        scanf("%d",&L1);
        CreatePolyn(P1,L1);
        printf("第一个多项式为:");
        printf("P1(X)=");
        PrintPolyn(P1);
        printf("请输入第二个多项式的项数:");
        scanf("%d",&L2);
        CreatePolyn(P2,L2);
        printf("第二个多项式为:");
        printf("P2(X)=");
        PrintPolyn(P2); 
        printf("\n");
        
        printf("请输入要选择的运算(+ , - , *): ");
        char ch1;
        getchar();        //清除掉缓冲区的回车符 
        scanf("%c",&ch1);
        getchar();        //清除掉缓冲区的回车符
         switch(ch1){
             case '+':{
                 printf("两个一元多项式相加:   ");
                 printf("P1(X)+P2(X)=");
                 P3=AddPolyn(P1, P2);
                PrintPolyn(P3);
             }break;
             case '-':{
                 printf("两个一元多项式相减:   ");
                 printf("P1(X)-P2(X)=");
                 P3=SubPolyn(P1, P2);
                PrintPolyn(P3);
             }break;
             case '*':{
                 printf("两个一元多项式相乘:   ");
                 printf("P1(X)*P2(X)=");
                 P3=MultiplyPolyn(P1, P2);
                PrintPolyn(P3);
             }break;
             default:printf("您输入了错误指令 %c !",ch1); 
         }
    
        char ch2;
        printf("\n是否代入X进行求值?(Y/N): ");
        ch2=getchar();        //清除掉缓冲区的回车符  
        getchar();
        switch(ch2){
            case 'Y':{
                float x;
                printf("\n请输入多项式中X的值:");
                scanf("%f",&x); 
                Calculate(P3,x);
                break;    
            }
            case 'N':break;
            default:printf("你输入了错误指令 %c !",ch2); 
        } 
        return 0;
    }


    创建多项式部分

    int LocateElem(Link p, Link s, Link &q){
    /*
    遍历链表p,每一个结点与s比较指数,
    若相同,q指向相同指数项的结点,返回1,
    若不相同,根据s所指指数大小在链表p中的位置来确定q的指向结点,返回0 
    */ 
        Link p1 = p->next;
        Link p2 = p;
        while(p1){
            if(s->expn > p1->expn){
                p1 = p1->next;
                p2 = p2->next;
            }else if(s->expn == p1->expn){
                q = p1; 
                return 1;
            }else{
                q = p2;
                return 0;
            }
        }
        if(!p1){
            q = p2;
            return 0;
        }
    }
    
    void CreatePolyn(Link &p,int m) 
    /*
    创建带头结点的链表(多项式) 
    且无论按什么顺序输入,或是有相同指数项
    最终在多项式中都是升幂顺序! 
    */
    {
        Link s,q;
        int i;
        p=(Link)malloc(LEN);
        p->next=NULL;
        for(i=0;i<m;i++)
        {
            s=(Link)malloc(LEN);
            printf("输入系数和指数(以空格隔开):");
            scanf("%f %d", &s->coef, &s->expn);
            if(!LocateElem(p, s, q)){    //若没有相同指数项,则链入 
                s->next = q->next;
                q->next = s;
            }else{                        //若有相同指数项,则系数相加                        
                q->coef+=s->coef;
            }
        }
    }


    打印多项式部分

    void PrintPolyn(Link p)
    //打印显示多项式 
    {
        Link s;
        s = p->next;
        while(s)
        {
                printf(" %.2f X^%d", s->coef, s->expn);
                s = s->next;
                if(s!=NULL)  
                    if(s->coef>=0) printf(" +");
                    //若下一项系数为正,则打印'+',否则不打印 
        }
        printf("\n");
    }


    多项式相加,相减部分

    int cmp(Link a, Link b)
    //比较两结点指数大小,根据情况返回不同值 
    {
        if (a->expn<b->expn) return  -1;
        else if(a->expn == b->expn) return  0;
        else return 1;
    }
    
    Link AddPolyn(Link pa, Link pb)//pa,pb均指向头结点 
    //两个多项式相加得一个新多项式,并且返回新多项式的头结点的指针   
    {
        Link newp, p, q, s, pc;
        float sum;
        p = pa->next; 
        q = pb->next;
        newp=(Link)malloc(LEN); //新多项式的头结点 
        pc = newp;    //pc指向新多项式的头结点
        while(p&&q){
            switch(cmp(p, q))
            {
                case -1:// //若指数:p<q,则将p所指结点链入头结点为newp的链表中,且p向后遍历   
                    s = (Link)malloc(LEN); 
                    s->coef = p->coef;
                    s->expn = p->expn;
                    pc->next = s;
                    pc = s;
                    p = p->next;
                    break;
                case 0://若比较两项的指数相等,则将两项系数相加后得到的项放入头结点为newp的链表中 ,且p,q同时向后遍历  
                    sum = p->coef+q->coef; 
                    if(sum!=0.0)//若两项系数相加为0,则不放入头结点为newp的链表中
                    {
                        s = (Link)malloc(LEN);
                        s->coef = sum;
                        s->expn = p->expn;
                        pc->next = s;
                        pc = s;
                    }
                    p = p->next;
                    q = q->next;
                    break;
                case 1://若指数:q<p,则将q所指结点链入头结点为newp的链表中,且q向后遍历    
                    s = (Link)malloc(LEN);
                    s->coef = q->coef;
                    s->expn = q->expn;
                    pc->next = s;
                    pc = s;
                    q = q->next;
                    break;
            }
        }
        pc->next=p?p:q;//链入pa或pb的剩余项 
        return newp;//返回新多项式的头指针 
    }
    Link SubPolyn(Link pa, Link pb)
    /*
    两个多项式相减得一个新多项式,并且返回新多项式的头结点的指针
    相减就是先将减数中每一项的系数变为负,再将两个多项式相加 
    */ 
    {
        Link newp, p, q, s, pc;
        float sum;
        newp=(Link)malloc(LEN); 
        pc = newp;
        p = pa->next; 
        q = pb->next;
        while(q){// 将pb中每一项的系数变为负 
            q->coef=0-q->coef;
            q=q->next;
        }
        q=pb->next;
        while(p&&q){
            switch(cmp(p, q))
            {
                case -1:  
                    s = (Link)malloc(LEN); 
                    s->coef = p->coef;
                    s->expn = p->expn;
                    pc->next = s;
                    pc = s;
                    p = p->next;
                    break;
                case 0: 
                    sum = p->coef + q->coef;//经提醒,由于前面减项系数已变,所以这里还是相加,谢谢! 
                    if(sum!=0.0)
                    {
                        s = (Link)malloc(LEN);
                        s->coef = sum;
                        s->expn = p->expn;
                        pc->next = s;
                        pc = s;
                    }
                    p = p->next;
                    q = q->next;
                    break;
                case 1:    
                    s = (Link)malloc(LEN);
                    s->coef = q->coef;
                    s->expn = q->expn;
                    pc->next = s;
                    pc = s;
                    q = q->next;
                    break;
            }
        }
        pc->next=p?p:q;
        return newp;
    }


    多项式相乘部分

    Link Reverse(Link p)
    /*
    用头插法逆置链表,
    使多项式由降幂变成升幂顺序
    或使多项式由升幂变成降幂顺序
    */ 
    {
        Link head=p; 
        Link q1,q2;
        q2=head->next;
        head->next=NULL;//断开头结点与第一个结点 
        while(q2)
        {
            q1=q2;      
            q2=q2->next; 
            q1->next=head->next; //头插 
            head->next=q1;  
        }      
        return head;//返回链表逆置后的头结点 
    }
    Link MultiplyPolyn(Link A,Link B)
    /*
        两个多项式相乘得一个新多项式,并且返回新多项式的头结点的指针
        相乘前,A,B两个多项式均是升幂排序 
        相乘时,A为降幂排序,B为升幂排序  
    */
    {
      Link pa,pb,pc,s,head;
      int k,maxExpn,minExpn;
      float coef;
      
      head=(Link)malloc(LEN);//头结点 
      head->next=NULL;
      
      if(A->next!=NULL&&B->next!=NULL){
          minExpn=A->next->expn+B->next->expn; //minExpn为两个多项式中指数和的最小值 
         A=Reverse(A);//将A降幂排列 
        B=Reverse(B);//将B降幂排列 
          maxExpn=A->next->expn+B->next->expn; //maxExpn为两个多项式中指数和的最大值
      }
      else{
              return head;
      }       
       pc=head;
       B=Reverse(B);//将B升幂排列 
       
       for(k = maxExpn;k>=minExpn;k--){ //多项式的乘积指数范围为:minExpn~maxExpn
               //根据两项的指数和使每一次循环都得到新多项式中一项  
               pa = A->next;
               while(pa !=NULL&&pa->expn>k){  //找到pa的位置 
                   pa = pa->next;
               }
               pb = B->next;
               while(pb!=NULL&&pa!=NULL&&pa->expn+pb->expn<k){//如果指数和和小于k,pb后移结点 
                   pb = pb->next;
               }
            coef=0.0;
            while(pa!=NULL&&pb!=NULL){
                if(pa->expn+pb->expn==k){ //如果指数和等于k,系数和累加,且pa,pb均后移结点 
                    coef+=pa->coef*pb->coef;
                    pa=pa->next;
                    pb=pb->next;
                }
                else if(pa->expn+pb->expn>k){//如果指数和大于k,pb后移结点
                    pa = pa->next;
                }
                else{//如果指数和和小于k,pb后移结点
                        pb = pb->next;
                }    
            }
            if(coef!=0.0){
            //如果系数和不为0,则生成新结点,将系数和指数赋给新结点后插入到新多项式中 
                s=(Link)malloc(LEN);
                s->coef=coef;
                s->expn=k;
                s->next=pc->next;
                pc->next=s;
                pc=s;
            }
       }
       B = Reverse(B);
       head=Reverse(head);
       return head;    //返回新多项式的头结点 
    }


    多项式求值部分

    void Calculate(Link p,float x)
    //代入确定的x到多项式中求值 
    {
        Link q=p->next;
        float sum;
        float result=0;//求的结果 
        while(q){
            sum=1.0;
            for(int i=1;i<=q->expn;i++){//先求每一项的 X^expn 的值 
                    sum=sum*x;
            }
            result+=sum*q->coef; //再使系数与sum相乘后求每一项的值,最后累加
            q=q->next; 
        }
        printf("将X的值代入多项式中计算的结果为:%.5f\n",result);
    } 

    代码测试
    输入时多项式时每项的幂按乱序输入,且两个多项式中有抵消项时:

    输入时多项式时每项的幂按乱序输入,两个多项式相乘:
     

    Over!!!

    展开全文
  • 数据结构-一元多项式计算器 顺序cun'chu 要求结果中无重复阶项和无零系数项 输出升幂排序的运算结果 设计实现菜单方式交互页面,界面友好,可重复操作</p>
  • 需要注意的是:顺序存储结构指的是用数组方法,使用数组方法实现时,在插入和删除的方面,数组不如链表灵活,方法复杂,删除其中一个需要将其后的数组元素改变位置,使其数组保持原有的顺序结构,在查找方面较链表...
  • 利用顺序表或链表表示两个一元多项式,并完成两多项式乘法运算。按指数升序输入第一个一元多项式polya各项指数和系数,且以输入0 0结束,按指数升序输入第一个一元多项式polyb各项指数和系数。输出两一元...

    两个一元多项式,并完成两多项式的乘法运算

    实验要求

    利用顺序表或链表表示两个一元多项式,并完成两多项式的乘法运算。按指数的升序输入第一个一元多项式polya各项的指数和系数,且以输入0 0结束,按指数的升序输入第一个一元多项式polyb各项的指数和系数。输出两一元多项式乘积的一元多项式polyc,并进行算法时间复杂度的分析
    例:(2+3x-3x^ 4)*(4x ^ 2+6x ^ 6 )= (8x^ 2+12x^ 3+18x^ 7-18x^10)
    这道实验题注意好指数和系数就好了分别计算即可。
    在这里插入图片描述

    代码实现

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include<string.h>
    #include<malloc.h>
    using namespace std;
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    typedef struct Polynode
    {
    	int coef; //系数 
    	int exp;  //指数 
    	Polynode* next;
    }Polynode, * Polylist;
    ==void IninPolylist(Polylist* poly)== {
    	*poly = (Polynode*)malloc(sizeof(Polynode));
    	if (*poly) {
    		(*poly)->next = NULL;
    	}
    	else {
    		printf("创建失败!\n");
    	}
    }
    ==void Polyadd(Polylist poly, int coef, int exp)==
    {
    	Polynode* p = (Polynode*)poly;
    	bool flag = 0;
    	//排序问题(主要是针对exp的大小进行排序)
    	while (p->next != NULL) {
    		if (p->next->exp < exp) {
    			p = p->next;
    		}
    		else if (p->next->exp == exp) {
    			p->next->coef += coef;
    			flag = 1;
    			break;
    		}
    		else if (p->exp < exp && p->next->exp > exp) {
    			Polynode* s = new Polynode;
    			s->exp = exp, s->coef = coef;
    			s->next = p->next;
    			p->next = s;
    			flag = 1;
    			break;
    		}
    	}
    	if (!flag) {
    		Polynode* s = (Polynode*)new Polynode;
    		s->exp = exp, s->coef = coef;
    		s->next = p->next;
    		p->next = s;
    	}
    }
    void PolyCreate(Polylist poly)
    {
    	int c, e;
    	scanf_s("%d%d", &e, &c);
    	while (c != 0)
    	{
    		Polyadd(poly, c, e);
    		scanf_s("%d%d", &e, &c);
    	}
    }
    void PolyMul(Polylist polya, Polylist polyb, Polylist polyc)
    {
    	Polynode* p = polya->next;
    	while (p != NULL) {
    		Polynode* pre = new Polynode;
    		pre = polyb->next;
    		while (pre != NULL) {
    			Polyadd(polyc, p->coef * pre->coef, p->exp + pre->exp);
    			pre = pre->next;
    		}
    		delete pre;
    		p = p->next;
    	}
    }
    void OutputPolylist(Polylist poly) //输出多项式 
    {
    	Polylist p = poly->next;
    	if (p != NULL)
    	{
    		if (p->coef < 0)
    			cout << "-";
    		cout << p->coef << "x^" << p->exp << " ";
    		p = p->next;
    	}
    	while (p != NULL)
    	{
    		if (p->coef > 0)
    			cout << "+ ";
    		if (p->coef)
    			cout << p->coef << "x^" << p->exp << " ";
    		p = p->next;
    	}
    	cout << endl;
    	return;
    }
    void DestoryPolylist(Polylist* poly) {
    	Polylist p;
    	while (*poly) {
    		p = (*poly)->next;
    		free(*poly);
    		*poly = p;
    	}
    }
    
    int main() {
    	Polylist polya, polyb, polyc;
    	printf("请输入多项式A中各项指数和系数:(以0,0结束!)\n");
    	IninPolylist(&polya);
    	PolyCreate(polya);
    	printf("请输入多项式B中各项指数和系数:(以0,0结束!)\n");
    	IninPolylist(&polyb);
    	PolyCreate(polyb);
    	IninPolylist(&polyc);
    	PolyMul(polya, polyb, polyc);
    	OutputPolylist(polyc);
    	DestoryPolylist(&polya);
    	DestoryPolylist(&polyb);
    	DestoryPolylist(&polyc);
    	return 0;
    }
    

    测试用例

    测试用例一:
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 实验目的:掌握用线性表实现一元多项式的基本运算。 实验内容:使用链式存储实现一元多项式的加法、减法、乘法和求导。即: C(x)= A(x)+B(x);C(x)= A(x)-B(x) C(x)= A(x)*B(x) C(x)= A’(x) 菜单: 1)C :分别创建...
  • 使用顺序存储结构或链式存储结构实现一元多项式的加法运算。 采用链式结构实现 #include using namespace std; struct Node { int coef; int exp; Node *next; }; //初始化 void InitList(Node * &L) { ...
  • 1、实现方式:可采用线性表的顺序存储结构,但是当多项式的每个项的指数差别很大时,会浪费很...3、一元多项式的加法运算: 设La和Lb分别表示两个多项式。Lc表示和多项式。p,q,r分别表示指向单链表的当前项比较指数...
  • 一元多项式加法减法乘法运算的实现 1.1设计内容及要求 1)设计内容 1使用顺序存储结构实现多项式加减乘运算 例如 , 求和结果 2使用链式存储结构实现多项式加减乘运算 求和结果 2设计要求 1用C语言编程实现上述实验...
  • [TOC]一、引言二、多项式加法运算2.1 算法思路更新、更全的《数据结构与算法》的更新网站...二、多项式加法运算采用不带头结点的单向链表,按照指数递减的顺序排列各项。/* c语言实现 */ 2.1 算法思路两个指针P1和...
  • 一元多项式加法减法乘法运算的实现 1.1设计内容及要求 1)设计内容 1使用顺序存储结构实现多项式加减乘运算 例如 , 求和结果 2使用链式存储结构实现多项式加减乘运算 求和结果 2设计要求 1用C语言编程实现上述实验...
  • 一元多项式的建立及其运算

    千次阅读 2016-02-05 14:28:10
    (一)一元多项式的表示:  一种方法是用顺序表表示,即顺序物理位置存储是多项式中x指数,而顺序表中物理位置相对应值便是与以物理位置为指数系数。但是这种方法有缺陷:对于稀疏多项式(缺很多...
  • C语言链表应用:一元多项式加法运算 首先科普一下线性表相关知识。线性表,即由n个性质相同数据元素组成有序序列。线性表是最基础线性结构,也是最基本数据结构形式。因此学好线性表,也是学习其余数据...
  • 一元多项式加法减法乘法运算的实现 1.1设计内容及要求 1)设计内容 1使用顺序存储结构实现多项式加减乘运算 例如 , 求和结果 2使用链式存储结构实现多项式加减乘运算 求和结果 2设计要求 1用C语言编程实现上述实验...
  • 1. 一元多项式加法减法乘法运算的实现 1.1 设计内容及要求 1) 设计内容 1使用顺序存储结构实现多项式加减乘运算 例如 6 5 4 2 5 4 3 2 f ( x ) 8 x 5 x 10 x 32 x x 10 , g ( x ) 7 x 10 x 20 x 10 x x 求和结果 f ...
  • 题目描述:思路:一开始我想法是用一个顺序表来存储多项式,然后进行运算。但后来发现顺序表适用于稠密多项式,对于稀疏多项式(即相邻项幂相差很大)来说时间就不可接受了。那怎么解决这个问题呢?那就是用一个...
  • 分别采用了顺序表、链表方式实现一元多项式完成多项式加、减运算并求值 1、实现功能描述: (1) 输入和输出: 需要输入信息有多项式系数和指数,用来向系统动态申请内存;系数和指数用来构造每个结点,形成表...
  • 链表都不知道咋写了,感觉写这个重点在于自己复习了一下单链表。 其实写这个用了好久,遇到问题就死磕,不过收获...解决第四个之后第三个也可以得到正确答案了,所以不需要拘泥于顺序 代码我会有详细注释,俗话说代...
  • 根据一元多项式相加的运算法则,对于两个多项式中所有指数相同项,对应系数相加,若其和不为零,则构成新多项式一项;对于两个多项式中所有指数不同项,分别复制到新多项式中。新多项式不必另外生成,而是在...
  • PAGE 实 验 报 告 课程名称 数据结构 实验名称 一元多项式计算器 作者 育人 实验目的 1掌握顺序表和单链表存储特点及插入删除等算法 2灵活运用顺序表和单链表相关算法实现一元多项式的计算 二实验内容及要求 ...
  • ![图片说明](https://img-ask.csdn.net/upload/201710/31/1509445699_779297.png)
  • 设计线性表动态或者静态链式存储结构,并实现一个一元多项式的计算器。 实验要求: 以动态或者静态链表存储一元多项式,在此基础上按要求完成对一元多项式 的运算。(为保证多项式准确性,多项式系数可以...
  • 虽然一元多项式可以用顺序和链式两种存储结构表示,但顺序结构的最大长度很难确定。比如当多项式系数较大时,此时就会浪费了巨大存储空间,所以应该选择用链式存储结构来存储一元多项式。单链表结构体可以用来...
  • 捕捉一元多项式的描述要点 一元多项式有多个数据项,每个数据项关键点是变量指数,变量系数 顺序存储,一维数组进行存储 对应关系:数组下标0-n-1,和变量系数对应,数组数据单元可以存储变量系数 ...
  • 题目按照指数递减的顺序给出两个一元多项式,输出两个多项式的乘积,还有 和 ,按照指数递减的顺序。 用链表实现一元多项式的乘法与加法运算。 首先来看加法运算 多项式 poly1 x^4 + 3x^3 + 6x 多项式 poly2 6...
  • 所实现的一元多项式结构如下图所示: ...若只对多项式进行“求值”等不改变多项式系数和指数的运算,采用类似顺序表的顺序存储结构即可,否则应采用链式存储结构,本文因为要进行一元多项式的加法,加法,乘法,
  • 在这里只简单介绍下一元多项式的表示: 对于线性表的两种存储结构一元多项式也可以有两种存储表示...若多项式只做求值运算,不做改变系数和指数的运算,则采用类似顺序表的顺序存储结构即可,否则采用链式存储表示。

空空如也

空空如也

1 2 3 4 5 6
收藏数 109
精华内容 43
关键字:

一元多项式运算的顺序结构