精华内容
下载资源
问答
  • 一元n次多项式是代数学中经常出现的代数式,对于一元n次多项式的操作有很重要的实际意义。由于个一元n次多项式最多有n+1项,且互不相关,所以可以用个线性表来保存个多项式,从前至后次数递增。对于个一元n...

    一、问题描述

    一元n次多项式是代数学中经常出现的代数式,对于一元n次多项式的操作有很重要的实际意义。由于一个一元n次多项式最多有n+1项,且互不相关,所以可以用一个线性表来保存一个多项式,从前至后次数递增。对于一个一元n次多项式,我们可以定义操作:多项式的加法、减法、乘法。

    本次小作业采用了链式表示的线性表实现,且只实现了多项式的加法。我认为如果要实现多项式的乘法,顺序表示的线性表更合适。

    二、数据结构——线性表

    1、链式表示:

    链式表示的线性表,每个单位元由数据域和指针域组成,数据域保存当前结点的数值,而指针域保存的是下一个逻辑位置的地址,以便于通过这个指针访问下一个结点。与顺序表示相比,链式表示具有插入、删除灵活方便的特点,然而访问不方便,只能够从头指针处遍历。

    2、顺序表示:

    顺序表示的线性表,用一段物理存储上连续的空间模拟线性表,以物理上的位置的顺序关系,表示逻辑上的顺序关系。由于其物理地址的相近,所以在访问方便的同时,出现了两个麻烦:一是当一次申请的空间不够时,只能重新申请一段更大的空间,把之前的所有数据按顺序“搬”过去,否则无法保证其物理顺序的连续性;二是当线性表需要插入、删除操作时,需要对一部分数据进行“移位”操作,时间复杂度高。

    3、基于本小作业对两种表示的对比分析:

    此次作业是要求做两个一元n次多项式的加法,抽象到ADT上来看,就是两个线性表的分项加法,所以不涉及到结点的插入、删除操作,于是链式表示的优势被削弱,而顺序表示的劣势不那么明显了。相比较而言,两者的实现没什么区别,所以我选择了链式表示来实现。

    更多地来想,如果需要做多项式的乘法,那么顺序表示就比链式表示的优势要大了。多项式乘法的算法核心可以大致说明为:LC(i+j-1) += LA(i)*LB(j)。这里涉及到寻找i+j-1位置的LC的值并进行修改的操作,如果使用顺序表示更方便找到该位置。

    三、算法的设计及实现

    (1)建立线性表LA和LB,并读入数据。

    (2)将LB中的每一项按顺序逐项加到LA中对应的项。

    (3)如果LB比LA长,则把LB中剩余元素按顺序依次加到LA中。

    (4)最后得到的LA就是最终结果。

    四、预期结果和实验中的问题

    1、预期结果:

    输入两个一元n次多项式的各项系数后,按照次数递增分别保存在LA和LB中,然后将LB中的每一项对应加在LA中。

    如LA={1,2,3,4,5,6}表示fa(x)=1+2*x+3*x^2+4*x^3+5*x^4+6*x^5,LB={2,2,3}表示fb(x)=2+2*x+3*x^2,则得到的结果应该是{3,4,6,4,5,6}表示fa(x)+fb(x)=3+4*x+6*x^2+4*x^3+5*x^4+6*x^5。

    2、实验中的问题:

    除去线性表实现的一些细节问题以外,还有针对此次小作业的问题。

    上面有提到的是,如果要实现多项式的乘法,若使用顺序表示的线性表,则可以直接遍历LA和LB,每一个合法位置执行LC(i+j-1) += LA(i)*LB(j)就可以了;而假如要使用链式表示的线性表来实现,如果继续按照顺序表示的方式来遍历LA和LB,这样处理LC的位置在不停地变动,查找该位置时间开销很大,所以可以选择遍历i+j-1的值,对于一个固定的i+j-1,通过遍历i求出j的值来计算LC(i+j-1)的值。

    我也思考了多项式除法的问题,发现涉及到数论的一些结论,类似于高精度数除以高精度数,还没有比较好的处理方式。当然,带余除法是可以用LA一直减去LB直到0<LA<LB为止。

     

    附:c++源代码:

      1 #include <iostream>
      2 #include <cstdio>
      3 
      4 using namespace std;
      5 
      6 struct node
      7 {
      8     int Num;
      9     node *next;
     10 };
     11 
     12 class MyList
     13 {
     14 private:
     15     int Len;
     16     node *pHead;
     17 
     18 public:
     19     void InitList()//构造一个空的线性表
     20     {
     21         Len = 0;
     22         pHead = NULL;
     23     }
     24     void ClearList()//重置为空表
     25     {
     26         node *Tmp;
     27         while(pHead)
     28         {
     29             Tmp = pHead;
     30             pHead = pHead -> next;
     31             delete Tmp;
     32         }
     33         Len = 0;
     34     }
     35     bool ListEmpty()//判断L是否为空表
     36     {
     37         return pHead == NULL;
     38     }
     39     int ListLength()//返回L中数据元素个数
     40     {
     41         return Len;
     42     }
     43     bool GetElem(int Pos, int &e)//返回第Pos个元素,出错返回true
     44     {
     45         if(Pos < 1 || Pos > Len)
     46         {
     47             printf("Wrong position!\n");
     48             return true;
     49         }
     50         node *Cur = pHead;
     51         int Index = 0;
     52         while(++Index < Pos && Cur)
     53             Cur = Cur -> next;
     54         e = Cur -> Num;
     55         return false;
     56     }
     57     //LocateElem(L, e, compare())//返回L中第一个与e满足关系compare()的元素的位序,不存在返回0
     58     bool PriorElem(int e, int &Pre_e)//若e是L中的元素,返回e的前躯,失败时返回true
     59     {
     60         if(pHead -> Num == e)
     61         {
     62             printf("Cannot find the precursor!\n");
     63             return true;
     64         }
     65         node *Cur = pHead, *Prev;
     66         while(Cur)
     67         {
     68             if(Cur -> Num == e)
     69                 break;
     70             Prev = Cur;
     71             Cur = Cur -> next;
     72         }
     73         if(!Cur)
     74         {
     75             printf("Cannot find the element!\n");
     76             return true;
     77         }
     78         Pre_e = Prev -> Num;
     79         return false;
     80     }
     81     bool NextElem(int e, int &Next_e)//若e是L中的元素,返回e的后继,错误时返回true
     82     {
     83         node *Cur = pHead;
     84         while(Cur)
     85         {
     86             if(Cur -> Num == e)
     87                 break;
     88             Cur = Cur -> next;
     89         }
     90         if(!Cur)
     91         {
     92             printf("Cannot find the element!\n");
     93             return true;
     94         }
     95         Cur = Cur -> next;
     96         if(!Cur)
     97         {
     98             printf("Cannot find the successor!\n");
     99             return true;
    100         }
    101         Next_e = Cur -> Num;
    102         return false;
    103     }
    104     bool ListInsert(int Pos, int e)//在Pos位置插入元素e,失败时返回true
    105     {
    106         if(Pos < 1 || Pos > Len + 1)
    107         {
    108             printf("Wrong position!\n");
    109             return true;
    110         }
    111         node *InsElem = new node;
    112         if(Pos == 1)
    113         {
    114             InsElem -> next = pHead;
    115             pHead = InsElem;
    116             InsElem -> Num = e;
    117         }
    118         else
    119         {
    120             node *Cur = pHead;
    121             int Index = 0;
    122             while(++Index + 1 < Pos && Cur)
    123                 Cur = Cur -> next;
    124             InsElem -> next = Cur -> next;
    125             Cur -> next = InsElem;
    126             InsElem -> Num = e;
    127         }
    128         Len++;
    129         return false;
    130     }
    131     bool ListDelete(int Pos, int &e)//删除Pos位置的元素,用e返回,错误时返回true
    132     {
    133         if(Pos < 1 || Pos > Len)
    134         {
    135             printf("Wrong position!\n");
    136             return true;
    137         }
    138         node *DelElem = pHead;
    139         if(Pos == 1)
    140         {
    141             pHead = DelElem -> next;
    142             e = DelElem -> Num;
    143             delete DelElem;
    144         }
    145         else
    146         {
    147             node *Prev;
    148             int Index = 0;
    149             while(++Index < Pos && DelElem)
    150             {
    151                 Prev = DelElem;
    152                 DelElem = DelElem -> next;
    153             }
    154             Prev -> next = DelElem -> next;
    155             e = DelElem -> Num;
    156             delete DelElem;
    157         }
    158         Len--;
    159         return false;
    160     }
    161     //ListTraverse(L, visit())//依次对L中的每个数据元素调用函数visit(),一旦visit()失败,则操作失败
    162     void PrintList()
    163     {
    164         if(ListEmpty())
    165         {
    166             printf("The List is empty!\n");
    167             return ;
    168         }
    169         node *Cur = pHead;
    170         int Index = 0;
    171         while(++Index < Len && Cur)
    172         {
    173             printf("%d ",Cur -> Num);
    174             Cur = Cur -> next;
    175         }
    176         printf("%d\n",Cur -> Num);
    177     }
    178     bool ElemPrio(node a, node b)
    179     {
    180         return a.Num < b.Num;
    181     }
    182     bool ChangeElem(int Pos, int El) //把Pos位置元素的值改为El,失败返回true
    183     {
    184         if(Pos < 1 || Pos > Len)
    185         {
    186             printf("Wrong position!\n");
    187             return true;
    188         }
    189         node *Cur = pHead;
    190         int Index = 0;
    191         while(++Index < Pos && Cur)
    192             Cur = Cur -> next;
    193         Cur -> Num = El;
    194         return false;
    195     }
    196     void MergeList(MyList Lb) //把Lb插入L中
    197     {
    198         int aElem, bElem, aIndex = 0;
    199         while(aIndex < Len && (!Lb.ListEmpty()))
    200         {
    201             GetElem(++aIndex, aElem);
    202             Lb.GetElem(1, bElem);
    203             if(aElem > bElem)
    204             {
    205                 Lb.ListDelete(1, bElem);
    206                 ListInsert(aIndex, bElem);
    207             }
    208         }
    209         while(!Lb.ListEmpty())
    210         {
    211             Lb.ListDelete(1, bElem);
    212             ListInsert(Len + 1, bElem);
    213         }
    214     }
    215     void AddList(MyList Lb) //按项加法,把Lb往L中加
    216     {
    217         if(Lb.ListEmpty())
    218             return ;
    219         int bElem;
    220         node *Cur = pHead;
    221         while(Cur && (!Lb.ListEmpty()))
    222         {
    223             Lb.ListDelete(1, bElem);
    224             Cur -> Num += bElem;
    225             Cur = Cur -> next;
    226         }
    227         while(!Lb.ListEmpty())
    228         {
    229             Lb.ListDelete(1, bElem);
    230             ListInsert(Len, bElem);
    231         }
    232     }
    233     void PrintList_ForPolynomial()
    234     {
    235         if(ListEmpty())
    236         {
    237             printf("There is something wrong!\n");
    238             return ;
    239         }
    240         node *Cur = pHead;
    241         int Index = 0;
    242         while(++Index < Len && Cur)
    243         {
    244             if(Index == 1)
    245                 printf("%d + ", Cur -> Num);
    246             else if(Index == 2)
    247                 printf("%d * x + ", Cur -> Num);
    248             else
    249                 printf("%d * x^%d + ", Cur -> Num, Index - 1);
    250             Cur = Cur -> next;
    251         }
    252         if(Index == 1)
    253             printf("%d\n", Cur -> Num);
    254         else if(Index == 2)
    255             printf("%d * x\n", Cur -> Num);
    256         else
    257             printf("%d * x^%d\n", Cur -> Num, Index - 1);
    258     }
    259 };
    260 
    261 void Read(MyList &L)
    262 {
    263     int n, i, Elem;
    264     L.InitList();
    265     printf("Please input a number n.\n");
    266     scanf("%d", &n);
    267     printf("Please input n+1 numbers means a0+a1*x+a2*x^2+...+an*x^n.\n");
    268     for(i = 1; i <= n + 1; i++)
    269     {
    270         scanf("%d", &Elem);
    271         L.ListInsert(i, Elem);
    272     }
    273 }
    274 
    275 int main()
    276 {
    277     MyList La, Lb;
    278     Read(La);
    279     Read(Lb);
    280     printf("La(x) = ");
    281     La.PrintList_ForPolynomial();
    282     printf("Lb(x) = ");
    283     Lb.PrintList_ForPolynomial();
    284     La.AddList(Lb);
    285     printf("La(x) + Lb(x) = ");
    286     La.PrintList_ForPolynomial();
    287     return 0;
    288 }
    View Code

     

    转载于:https://www.cnblogs.com/CQBZOIer-zyy/p/5185416.html

    展开全文
  • (输出的行式:段式子为一元n次多项式的表达形式,后面加结果; (程序所能达到的功能:计算一元n次多项式的加法运算; (测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出果。 正确的输入与正确的结果...

    一.实现一元n次多项式的加法
    (输出的行式:一段式子为一元n次多项式的表达形式,后面加结果;
    (程序所能达到的功能:计算一元n次多项式的加法运算;
    (测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出果。
    正确的输入与正确的结果:
    在这里插入图片描述
    错误的输入与结果
    在这里插入图片描述

    2.概要设计:
    抽象数据类型:LNode与SqList分别为结点类和线性表类,结点类中定义了系数项和指数项,线性表类定义了容量和项数与未知数,主程序为先建立一个线性表然后定义其系数和项数,再输入其系数和项数,在初始化线性表,给出线性的容量,再计算结果,然后输出。
    调用关系:在主程序中配用三个函数,分别为EnlargeList//扩充容量,GetResult//计算结果,InitList//初始化链表中的系数项和指数项。
    3.详细设计:
    伪代码:

    Struct LNode{
    系数;
    指数;
    };
    Struct sqlist{
    线性表;
    结点;
    };
    Enlargelist{
    新结点;
    分配位置;
    扩充新的容量;
    }
    Initlist{
    循环1到n个数初始化线性表的系数项和指数项
    }
    Getsult{
    计算最后的结果
    }
    Main{
    定义一个新的线性表;
    输入指数和系数;
    Initlist
    S=getresult;
    输出结果
    }

    4.调试分析:
    经计算,程序的时间复杂度平均为4n-1;
    改进可以将扩充容量的容量大小适当调高,但是这样空间复杂度可能会提高;
    体会:可以利用函数的知识借助matlab计算出最适合的填充容量;
    5.用户使用说明:
    将程序用devC++打开进行调试和编译,最后按照程序的提示输入正确的形式从而计算出用户想要的节果。
    6.测试结果
    例如:
    计算3x7+2x5+5x3+7x2+13,当x为14时:
    在这里插入图片描述
    结果即为所求
    当输入为-1等不合法的数时:
    在这里插入图片描述
    即会输出error提醒错误;
    7.附录:

    #include<iostream>
    #include <stdlib.h>
    #include<math.h> 
    #define LIST_INIT_SIZE 100 //初始分配量
    #define LISTINC 50 //增长量
    using namespace std;
     
    struct LNode{   //节点类
    	double p;//系数项
    	int  e;//指数项
    };
     
    struct SqList  //顺序存储线性表类
    {
    	SqList()
    	{
    	 elem = (LNode *)malloc(LIST_INIT_SIZE*sizeof(LNode));;
    	 capacity = LIST_INIT_SIZE;
    	 size = 0;
    	 mx = 0;
    	}
    	LNode * elem;
    	size_t size;//项数
    	size_t capacity;//当前存储容量
    	double mx;
    };
     
     
     
    //链表扩充函数
    bool EnlargeList(SqList & list)
    {
    	 LNode * newbase;
    	
    	 newbase = (LNode *)realloc(list.elem,(list.capacity + LISTINC)*sizeof(LNode));
    	if(!newbase)
    	{
    	   return false;
    	}
    	list.elem = newbase;
    	list.capacity += LISTINC;
    	return true;
    }
     
    //初始化一元多项式线性表中的系数项、指数项
    void InitList(SqList & list1,double ps[],int es[],int n)//ps代表系数项数组,es代表指数项数组,n代表该一元多项式的个数
    {
    	int i =0;
    	for(;i<n;i++)
    	{
    		if(list1.size>=list1.capacity)
    		{
    			EnlargeList(list1);
    		}
    		list1.elem[list1.size].p = ps[i];
    		list1.elem[list1.size].e = es[i];
    		list1.size++;
    	}
    }
     
    //计算该一元多项式结果
    double GetResult(SqList & list1)
    {
     double sum =0;
     for(size_t i=0;i<list1.size;i++)
     {
    	 sum+= list1.elem[i].p*(pow(list1.mx,list1.elem[i].e));
     }
     return sum;
    }
     
    //清空一个一元多项式线性表
    void clear(SqList & list1)
    {
    	list1.size = 0;
    	//如果空间过大将空间进行压缩
    	if(list1.capacity>LIST_INIT_SIZE)
    	{
    		free(list1.elem);
    		list1.elem = (LNode *)malloc(LIST_INIT_SIZE*sizeof(LNode));;
    		list1.capacity = LIST_INIT_SIZE;
    		list1.size = 0;
    		list1.mx = 0;
    	}
    }
     
    int main()
    {
     //建立一个线性表
    	SqList myList;
    	int n;
    	cout<<"输入该一元多项式的项数:"<<endl;
    	cin>>n;
     //保存系数项和指数项
     	if(n<0){cout<<"error";}
    	 else{
    	 
    	double* ps = new double[n];//系数项
    	int* es = new int[n];//指数项
     
     //输入数据
    	int i = 0;
    	cout<<"依次输入系数和对应指数,共";
    	cout<<n<<"对"<<endl;
    	while (i<n)
    	{ cin>>ps[i]>>es[i];
    	  i++;
    	}
    	cout<<"输入该一元多项式的变量x值"<<endl;
    	cin>>myList.mx;
     
    //初始化线性表
    	InitList(myList,ps,es,n);
     
     //计算结果
    	double s = GetResult(myList);
    	i=0;
    	for( i=0;i<int(myList.size-1);i++)
     {
    	 cout<< myList.elem[i].p<<"*"<<myList.mx<<"^"<<myList.elem[i].e<<"+";
     }
    	 cout<< myList.elem[i].p<<"*"<<myList.mx<<"^"<<myList.elem[i].e<<" = ";
    	 cout<<s<<endl;
    }
     return 0;
    }
    

    二.线性表的插入,删除,查找
    用数组实现:
    1.需求分析:
    输入的形式:按照程序编译后的提示进行输入:
    程序所能达到的功能:可以实现线性表的插入删除和查找;
    测试数据:
    当输入格式正确时:
    在这里插入图片描述
    当输入格式不正确时:
    在这里插入图片描述
    将会出现error提示
    2.概要设计:
    主程序即要通过数组先定义一个数组,再进行查找,再进行删除
    3.详细设计:
    伪代码:
    main(){
    定义数组;
    输入数据;
    插入元素;
    查找元素;
    删除元素;
    }
    4.调试分析:
    平均时间复杂度为:
    (5/2)*n
    调试过程中遇到的问题:
    关于边界点的问题,删除第几个,是否需要加一或者减一;
    体会:要认真考虑问题,边界点的问题要考虑清楚;
    5.用户使用说明:
    将程序在devC++中打开,调试编译以后即可根据提示得到结果;
    6.测试结果:
    当输入结果正确时
    在这里插入图片描述
    当输入结果不正确时:
    在这里插入图片描述
    7.附录

    #include<iostream>
    using namespace std;
    
    int main(){
    	int a[100];
    	int n,i,j,k,s;
    	cout<<"请输入线性表的元素个数\n"; 
    	cin>>n;
    	cout<<"请输入"<<n<<"个数"<<endl;
    	for(i=0;i<n;i++) 
    	{
    		cin>>a[i];
    	}
    	cout<<"请输入添加的位置和数\n";
    	cin>>j>>k;
    	i=n-1; 
    	for(s=n;s>j;s--,i--)
    	{
    		a[s]=a[i];
    	}
    	a[j]=k;
    	cout<<"新的数组为:\n";
    	for(i=0;i<n+1;i++)
    	{
    		cout<<a[i]<<" ";
    		
    	}
    	cout<<"\n输入要查找的数\n";
    	int w;
    	cin>>w;
    	cout<<"位置为 ";
    	for(i=0;i<n+1;i++)
    	{
    		if(a[i]==w)
    		{
    			cout<<i+1;
    			break;
    		}
    	}
    	cout<<"\n你要删除第几个数\n";
    	int z;
    	cin>>z;
    	if(z>n+1){
    		cout<<"error";
    	}
    	else{
    		cout<<"删除后\n";
    		for(s=z;s<n+1;s++)
    		{
    			a[s-1]=a[s];
    		}
    		for(i=0;i<n;i++){
    			cout<<a[i]<<" ";
    		}
    	}
    	
    }
    

    用链表实现:
    1.需求分析:
    输入的形式:
    根据交流框的提示输入正确的格式:
    程序所能达到的功能:
    构建一个动态链表,然后对动态链进行插入,删除,查找的操作;
    测试数据:
    正确的形式:
    在这里插入图片描述
    错误的输入的输出结果:

    在这里插入图片描述
    2.概要设计:
    抽象数据类型:
    SqList, 与pList两个线性链表
    主程序的流程:构造线性链表,调用查找,插入,删除函数;
    3.详细设计
    伪代码:
    typedef struct
    {
    构造链表
    }SqList, *pList;
    //构造一个空的线性表
    int InitList_Sq(SqList &L)
    {
    L.elem = (ElemType )malloc(LIST_INIT_SIZEsizeof(ElemType));

    }
    //在顺序线性表L中第i个位置之前插入新的元素e
    //i的值必须符合1 《= i 《= ListLength_Sq(L)+1
    int ListInsert_Sq(SqList &L,int i,ElemType e)
    {

    q为插入位置
    for(p = &(L.elem[L.length-1]);p >= q;p–) //在插入位置后面的元素依次后移一位
    *(p+1) = *p;

    插入位置赋上插入的元素
    动态数组内个数加一
    return OK;
    }
    //在顺序表中删除第i个元素,并用e返回其值
    int ListDelete_Sq(SqList &L,int i,ElemType &e)
    {
    找到删除元素
    P->next=p->next->next;
    }
    //查找与给出值的第一各位置,若找到,返回他的位序
    int LocateElem_Sq(SqList L,ElemType e)
    {
    查找元素;
    }
    //输出动态数组中的数据
    void PrintList(SqList L)
    {
    打印线性表的元素
    }

    int main()
    {

    if(InitList_Sq(List))
    {
       
            ListInsert_Sq(List,i,num);  //调用添加功能函数
        }
        PrintList(List);  //输出数组元素
    
          
        if(ListDelete_Sq(List,i,num))  //调用删除功能函数
        {
           
            PrintList(List);  //输出动态数组元素
        }else
        {
            printf("删除位置不合法!\n");
        }
    
               
        i = LocateElem_Sq(List,num);  //调用查找功能函数}
    

    4.调试分析:
    与通过数组计算一样,同样是对临界点的把握。
    经计算时间复杂度为:(5/2)*n

    	5.用户使用说明:
    

    将所写的程序通过devC++打开,经过调试和编译,经过对话框的提示输入正确格式的数字,从而可以操纵一个动态链表。
    6.测试结果:
    正确的输入
    在这里插入图片描述
    错误的输入:
    在这里插入图片描述
    7.附录:

    #include <stdio.h>
    #include <stdlib.h>
     
    #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
    #define LISTINCREMENT 10//线性表存储空间的分配增量
    #define ElemType int
    #define OK 1
    #define ERROR 0
     
    typedef struct
    {
        ElemType *elem;//存放分配地址的首地址,类似于数组的首地址
        int length;     //存放数组的长度
        int listsize;   //数组的总长度
    }SqList, *pList;
    //构造一个空的线性表
    int InitList_Sq(SqList &L)
    {
        L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
        if( ! L.elem)  //存储分配失败
        {
            return ERROR;
        }
        L.length = 0;    //数组初始状态长度为0
        L.listsize = LIST_INIT_SIZE;  //数组初始状态总长度
        return OK;
    }
    //在顺序线性表L中第i个位置之前插入新的元素e
    //i的值必须符合1 《= i 《= ListLength_Sq(L)+1
    int ListInsert_Sq(SqList &L,int i,ElemType e)
    {
     
        int *q,*p;    //设置p q 为int型指针变量
        ElemType  *newbase;
        if(i < 1 || i > L.length+1) //i值不合法的情况
        {
            return ERROR;
        }
        if(L.length >= L.listsize) //当前存储空间已满,增加分配
        {
           newbase = (ElemType *)realloc(L.elem,(L.listsize + LISTINCREMENT) *sizeof(ElemType));
           if(!newbase) //存储分配失败
            {
                return ERROR;
            }
            L.elem = newbase;  //新基址
            L.listsize += LISTINCREMENT;//增加存储容量
        }
     
        q = &(L.elem[i-1]);  //q为插入位置
        for(p = &(L.elem[L.length-1]);p >= q;p--) //在插入位置后面的元素依次后移一位
            *(p+1) = *p;
     
        *q = e;   //插入位置赋上插入的元素
        ++L.length;   //动态数组内个数加一
            return OK;
    }
    //在顺序表中删除第i个元素,并用e返回其值
    int ListDelete_Sq(SqList &L,int i,ElemType &e)
    {
        int *p,*q;
        if(i < 1 || i > L.length)   // 删除元素位置不合法
            return ERROR;
     
        e = L.elem[i-1];    //删除元素赋值给e,并由e返回
        p = &(L.elem[i-1]);    //p被赋值为删除元素位置,作为删除元素后面元素前移一位的标兵
        q = L.elem + L.length -1;
     
        for(;p < q;++p)
        {
            *p = *(p+1); //被删除元素后面的元素向前移
        }
        --L.length;  //表长减1
        return OK;
    }
    //查找与给出值的第一各位置,若找到,返回他的位序
    int LocateElem_Sq(SqList L,ElemType e)
    {
        int i = 0;
        int *p;
        p = L.elem;
        while(i < L.length )   //判断在数组内是否有元素与给出的元素相同
        {
            if(*p == e)
            {
                break;
            }else
            {
                p++;
                i++;
            }
        }
        if(i >= L.length)
        {
            return ERROR;
        }else
        {
            return i+1;  //返回元素位置
        }
    }
    //输出动态数组中的数据
    void PrintList(SqList L)
    {
        int i = 0;
        printf("动态数组为:\n");
        for(i;i < L.length;i++)
        {
            printf("%d ",L.elem[i]);
        }
        printf("\n\n");
    }
     
    int main()
    {
        SqList List;
        int sum = 0;      //计算数的个数
        int i;
        int num;   //输入的数据
     
        if(InitList_Sq(List))
        {
            /********添加功能展示*******/
     
            printf("输入添加的数的个数\n");
            scanf("%d",&sum);
            for(i = 1;i <= sum;i++)
            {
                printf("输入第%d个数:",i);
                scanf("%d",&num);
                ListInsert_Sq(List,i,num);  //调用添加功能函数
            }
            PrintList(List);  //输出数组元素
     
            /********删除功能展示********/
            printf("请输入删除位置\n");
            scanf("%d",&i);
            if(ListDelete_Sq(List,i,num))  //调用删除功能函数
            {
                printf("删除元素为:");
                printf("%d\n",num);
                PrintList(List);  //输出动态数组元素
            }else
            {
                printf("删除位置不合法!\n");
            }
     
            /********查找功能展示********/
            printf("请输入查找元素\n");
            scanf("%d",&num);
            i = LocateElem_Sq(List,num);  //调用查找功能函数
            if( i )
            {
                printf("位置为:%d\n",i);
            }else
            {
                printf("数组内不存在该元素\n");
            }
     
     
        }else
        {
            printf("空间存储分配失败\n");
        }
     
        return 0;
    }
    
    展开全文
  • 多项式 什么是多项式 满足如下条件表达式才是多项式: 1 包含变量或者变量与常量 ...多项式项总次数要么是1,要么是0 3x + 7y //是线性 5x + 8y + 2 //线性 7xy + 9x + 10y + 3 //非线性...

    多项式

    什么是多项式

    满足如下条件的表达式才是多项式:

    1 包含变量或者变量与常量

    2 涉及的运算只有加运行,减运算,乘法运算与指数运算(指数必须>=0,不可以是负数),不包含除法运算

     

    线性多项式

    多项式中的每一项总次数要么是1,要么是0

    3x + 7y //是线性的
    5x + 8y + 2 //线性的
    7xy + 9x + 10y + 3  //非线性的,7xy未知数指数和为2,不是1

     

    齐次多项式

    多项式中每一项的总次数都相等

    8x + 6y + 3z  //齐次的,次数为1
    7xy + x^2 + y^2 //齐次的,次数为2
    x + 3y + 1 //不是齐次的,含有常数项,常数项次数为0,其他项次数为1

     

    既是线性的,又是齐次的,就称为齐次线性多项式

     

    函数

    线性函数

    线性函数的定义分为两类,在微积分、解析几何等相关领域,满足线性多项式的函数是线性函数

    f(x, y, z) = 3x + 7y + z + 3 //线性函数
    f(x, y, z) = xy + 10z //非线性函数 xy指数总和为2
    f(x, y ,z) = x/y + 9z + 5 //非线性函数, x/y不符合多项式定义

    在线性代数领域,线性函数的定义为

    f(x + y) = f(x) + f(y)
    f(ax) = af(x)

    其中xy都是向量空间,a是一个常量

     

    齐次函数

    齐次函数的定义为,如果函数的每一个参数变为原来的a倍,函数的值就变为原来的a^k倍(其中k是整数,称为齐次的degree<度>),那么这个函数就是齐次的。注意,这里的函数的表达式可以不用满足多项式的定义

    f(ax, ay) = a^kf(x, y)

    推广到向量空间,齐次函数可以定义为

    f(ax, ay) = a^kf(x, y)

    其中xy为向量空间,根据齐次函数的定义, 线性函数f(ax) = af(x)是齐次度为1的齐次函数

     

    既是线性的,又是齐次的函数称为线性齐次函数

     

    参考资料

    https://en.wikipedia.org/wiki/Polynomial

    https://en.wikipedia.org/wiki/Linear_function

    https://en.wikipedia.org/wiki/Homogeneous_function

     

    转载于:https://www.cnblogs.com/chaoguo1234/p/6847822.html

    展开全文
  • 在主函数中调用函数CreatePolyn ()函数创建两个多项式: 2 + 3X + 5X3 + 2X4 3 + 2X + 4X2 然后调用函数AddPolyn求它们和,最后打印.../*①多项式数据结构定义*/ typedef struct pnode{  float coef; //系数  int

    在主函数中调用函数CreatePolyn ()函数创建两个多项式:

    2 + 3X + 5X3 + 2X4

    3 + 2X + 4X2

    然后调用函数AddPolyn求它们的和,最后打印出求和后的结果。

    提示:

    /*①多项式数据结构定义*/

    typedef  struct pnode{

          float coef;                 //系数

          int expn;                  //指数

    } ElemType;

    typedef  LinkList  Polynomial;    //一元n次多项式类型定义

     

    /*②多项式操作接口定义*/

    // 创建一个一元多项式 

    Status CreatePolyn(Polynomial &P);

     

    // 打印该链表的结果 

    void PrintPolyn(Polynomial pList);

     

    // 比较两个结点的指数的大小

    int cmp(ElemType a, ElemType b);

     

    // 把两个一元多项式相加 

    Polynomial AddPolyn(Polynomial pa, Polynomial pb);

     

    /*③部分操作的实现函数*/

    // 创建一个一元多项式 

    Status CreatePolyn(Polynomial &P)

    {

    InitList_L(P); //初始化链表

    printf("请输入多项式项数m:\n");

    scanf("%d",&m);

    printf("请输入多项式每项的系数和指数,格式如(3.0, 2):\n");

    for(i=1;i<=m;i++)

    {

    输入一个结点,将其根据指数从小到大的排列顺序插入链表

    }



    #include<stdio.h>
    #include<stdlib.h>
    #define OK     1
    #define ERROR  0
    typedef int Status ;
    typedef int ElemType ;
    
    typedef  struct pnode
    {
          float coef;                 //系数 
          int expn;                  //指数 
    	  struct pnode *next;
    }pnode,*Polynomial; 
    
    //初始化
    Status  InitList_L(Polynomial &P);
    
    // 创建一个一元多项式 
    Status CreatePolyn(Polynomial & P);
    
    // 打印该链表的结果 
    Status PrintPolyn(Polynomial pList);
    
    // 比较两个结点的指数的大小 
    int cmp(ElemType a, ElemType b);
    
    // 把两个一元多项式相加 
    Polynomial AddPolyn(Polynomial pa, Polynomial pb);
    //单链表的初始化
    Status  InitList_L(Polynomial &P)
    {
           P=new pnode;
           P->next=NULL;
    	   return OK;
    }
    
    // 创建一个一元多项式 
    Status CreatePolyn(Polynomial &P)
    {
    	InitList_L(P); //初始化链表
    	Polynomial q;
    	int i,m;
    	P=(pnode*)malloc(sizeof(pnode));//生成结点
    	P->next=NULL;
    	q=P;
    	printf("请输入多项式项数m:\n");
    	scanf("%d",&m);
    	printf("请输入多项式每项的系数和指数,格式如(3.0, 2):\n");
    	for(i=1;i<=m;i++)
    	{ // 依次输入m个非零项(可按任意顺序) 
    		q=(pnode*)malloc(sizeof(pnode));
    		scanf("%f,%d",&q->coef,&q->expn);
    		q->next =P->next ;
    		P->next =q;
    	}
    	return OK;
    }//CreatPolyn
    
    // 打印该链表的结果 
    Status PrintPolyn(Polynomial P)
    {
        while(P->next !=NULL)
    	{ 
           P=P->next;
           printf("(%5.2f)x^%d+",P->coef,P->expn); 
    	}
    	printf("0");
    	printf("\n");
    	return OK;
    }
    
    // 比较两个结点的指数的大小 
    int cmp(int a,int b) 
    {
    	if(a>b) return 1;
    	else if(a<b) return -1;
    	else return 0;
    }
    
    // 把两个一元多项式相加 
    Polynomial AddPolyn(Polynomial pa, Polynomial pb)
    { 
    	 Polynomial 	qc;	/* 用来指向新链表的尾结点的 */
    	 Polynomial 	qa;	/* 指向第一个链表的当前结点 */
    	 Polynomial 	qb;	/* 指向第二个链表的当前结点*/
    	 Polynomial 	temp;	/* 删除结点时做临时变量用 */
    	 ElemType   a,b;             /* 分别存放两个链表当前结点的数据 */
    	 float	sum;	               /* 存放两个链表中当前结点的系数和 */
    
    	 qc = pa;
    	 qa = pa->next;
    	 qb = pb->next;
    
    	while( qa && qb )
    	{
    		a = qa->expn ; 
    		b = qb->expn ;
    		switch( cmp(a,b) )
    		{
        	case -1:	  /* 第一个链表中当前结点的指数值小 */
    			qc->next=qa;	/* Link the node to the end of qc */
    			qc=qa;			/* move the tail pointer to qa */
    			qa=qa->next;	/* move to the next node of qa */
    			break;
    		case 0:		/* 指数值相等 */
    			sum = qa->coef + qb->coef;
    			if( sum != 0.0)
    			{
    				qa->coef=sum;
    				qc->next=qa;	  /* Link qa to the result polyn */
    				qc=qa;		    /* Let qc still point to the tail */
    				qa=qa->next;
    			}
    			else
    			{	/* 释放qa所指向的结点的空间 */
    				temp=qa ; /* qa is to be deleted, let temp point to it */
    				qa=qa->next;	/* Let qa point to the next node */
    				free(temp);		/* Free the space */
    			}
    				/* 释放qb所指向的结点的空间 */
    			temp = qb;
    			qb = qb->next;		/* let qb point to the next node */
    			free(temp);
    			break;
    		case 1:		/* 第一个链表中当前结点的指数值大 */
    			qc->next = qb;
    			qc = qb;
    			qb = qb->next;
    			break;
    		}	/* End of Switch */
    	}	/* End of while(!qa && !qb) */
    
    	qc->next = qa?qa:qb;	/* Link the rest nodes of polynomial 1 or 2 */
    
    	free(pb);    /* Free the head node of the 2nd polynomial  */
    	return (pa);
    }
    void main()
    {
    	Polynomial Pa,Pb;
    	printf("***************一元多项式加法运算*********************\n");
    	printf("\n______________第一个多项式______________\n");
    	CreatePolyn(Pa);
        printf("第一个多项式为:");
    	PrintPolyn(Pa);
    	printf("\n\n______________第一个多项式______________\n");
    	CreatePolyn(Pb);
    	printf("第二个多项式为:");
    	PrintPolyn(Pb);
        AddPolyn(Pa,Pb);
    	printf("\n\n两个多项式的和为:");
    	PrintPolyn(Pa);
    	system("pause");
    }


    展开全文
  • 如题:一般的的二元一次方程组的...所以首先应该定义一个二次多项式的类;与 各项的系数a,b,c相关;class Quadratic { // 二次多项式 public: const double a,b,c; // 分别表示二次项、一次项和常数项等三个系数 ...
  • 一元二次方程,是初中阶段方程中比较重要一个。不止可以单独考查,还可以结合函数来出题。从历年期末、中考卷就可以看出它重要性。...一元二次方程一般形式: (a≠0),其中a为二次项系数,b为一次项...
  • 为了用种模型实现逼近与插值统一,在多项式函数空间上构造了含两组参数混合函数,并由之定义了基于四点分段的多项式曲线和相应张量积曲面。当参数取特殊值时,新曲线曲面成为三均匀B样条曲线曲面。除了...
  • 货郎担问题实例是给定n个结点和任意一对结点{i,j}之间距离di,j,要求找出一条封闭回路,该回路经过每个结点一次且仅一次,并且费用最小,这里费用是指回路上相邻结点间距离和.货郎担问题是NP难组合优化问题,...
  • 多项式回归是种线性回归形式,其中自变量x和因变量y之间关系被建模为n次多项式。多项式回归拟合x值与y相应条件均值之间非线性关系,表示为E(y | x) 为什么多项式回归: 研究人员假设某些关系是曲线...
  • 首先,例如一条直线,两点可以定义一条直线,而直线的定义式可以写为:y=kx+b,可用一次函数表示;即一阶的曲线(直线)由两个点定义。同理又例如:二阶的抛物线y=ax²+bx+c由三个点定义。  也即:两点确定一条直线...
  • 在链表个节点中,保存每指数以及系数,同时使用节点指针指向下个低项,定义数据结构如下: struct PolyNode{ int coef; int expon; struct PolyNode *link; }; typedef s...
  • 1.1 多项式的定义 有限的单项式之和称为多项式,其中每个单项式叫做多项式的项,不含字母的项叫做常数项。 多项式里,次数最高的项的次数叫做这个多项式的次数。 多项式按某个字母降或升幂排序。 单项式与多项式...
  • C++多项式除法探讨

    2020-01-02 10:15:26
    明显是除不尽的,但是按照普通的除法去做,余数就会被舍弃,当涉及到求值或者求导时,就会产生极大的误差,尤其是在实现牛顿法求解高次多项式的数值解时,需要计算迭代点的函数值以及导数值,余数的舍弃必然使...
  • 个一元四次多项式按升幂形式可写成: p(x) = ????0 + ????1???? + ????2????² + ????3????³ + ????4????4, 形式,因此组数(????0, ????1, ????2, ????3, ????4) 可以唯一表示个多项式。 定义...
  • PAGE 1 多项式加法报告书 1100400310 王肖伊...作业要求 将两个一元高次多项式AB从外部无序输入处理成降序排列最后相加得到降序多项式再输出 算法思想 分别建立功能不同子函数最后将它们都写到主函数中实现首先定义
  • 多项式求和

    千次阅读 2016-09-26 18:44:24
    一般情况下,一元n次多项式可写成: 其中,pi是指数为ei非零系数,且满足 因此,我们可以采用线性表(定义:线性表是由n个数据元素构成有限序列,比如数组、向量、链表等等)来表示: ...
  • 数据结构与算法分析练习3.7 编写个函数将两个多项式相乘,用链表实现 本题解题思路可借鉴添加链接描述 #include ... //以幂(指)数降序排序的多项式 typedef PtrToNode Position; //节点 //链
  • 一次学习线性表一定会马上接触到一种叫做顺序表(顺序存储结构),经过上一篇分析顺序表优缺点是很显然,它虽然能够很快访问读取元素,但是在解决如插入和删除等操作时候,却需要移动大量元素,效率较低...
  • 插值什么是插值首先看一下 百度百科的定义在离散数据的基础上补插连续函数,使得这条连续曲线通过全部给定的离散数据点。从古到今,百度百科的定义一直。。。欲哭无泪这是啥意思?简而言之就是 我现在有n个点对应的...
  • 多项式运算

    2018-12-29 14:36:47
    多项式(Polynomial)是代数学中基础概念,是由称为未知数变量和称为系数常数通过有限加减法、乘法以及自然数幂次的乘方运算得到代数表达式。多项式是整式的一种。未知数只有...
  • 03-多项式的加减乘除

    2020-01-17 18:31:58
    多项式链表表示输入: ... //对p一次定义 for (i = 0; i < num; i++){ p = (Node*)malloc(sizeof(Node)); //相当于是对p第二次定义,把p值给改了,而不是在q后面接上,断链了 ...
  • 多项式全家桶

    2019-01-15 22:07:07
    施工现场 多项式 在数学中,由若干个单项式相加组成代数式叫做多项式(若有减法:减个数...为了方便接下来瞎逼逼,我们定义n次多项式A(x)=∑i=1nai⋅xiA(x)=\sum\limits_{i=1}^n a_i\cdot x^iA(x)=i=1∑n​...
  • 多项式回归学习笔记

    2017-08-05 00:13:00
    多项式的定义及展现形式 多项式(Polynomial)是代数学中的基础概念,是由称为不定元的变量和称为系数的常数通过有限加减法、乘法以及自然数幂的乘方运算得到的代数表达式。 多项式分为一元多项式和多元多项式...
  • 多项式的渐近行为)假设是个关于n的d次多项式,其中,k是个常量。使用渐近记号的定义来证明下面的性质。 a. 若,则。 b. 若,则。 c. 若,则。 d. 若,则。 e. 若,则。 解答: a. 根据的形式化定义,...
  • 多项式

    千次阅读 2007-11-06 12:58:00
    给定多项式f(x)=anxn+an-1xn-1+…+a0x0,如果an,我们称f(x)是个n次多项式。类似自然数里“质数”概念,也可以给出“质多项式”概念。给定多项式f(x),如果找不到次数至少为1多项式g(x)和h(x)满足f(x)=g...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 375
精华内容 150
关键字:

一次多项式的定义