数据结构——多项式的创建（链式存储）

和顺序存储结构相比，利用链式存储结构更加灵活，更适合表示一般的多项式，合并过程的空间复杂度为O(1)，所以较为常用。本篇文章先来讲解多项式的创建。

多项式的创建方法类似于链表的创建方法，区别在于多项式链表是一个有序表，每项的位置要经过比较才能确定。首先初始化一个空链表用来表示多项式，然后逐个输入各项，通过比较，找到第一个大于该输入项指数的项，将输入项插到此项的前面，这样既可保证多项式链表的有序性。

算法步骤：

1.创建一个只有头结点的空链表。

2.根据多项式的项的个数n，循环n次执行以下操作：

① 生成一个新节点*s；

② 输入多项式当前项的系数和指数赋给新节点*s的数据域；

③ 设置一个前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre初值指向头结点；

④ 指针q初始化，指向首元结点；

⑤ 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q；

⑥ 将输入项结点*s插入到结点*q之前。

算法描述：

/**
*    结构体如下：
*/
typedef struct PNode
{
    float coef;            //系数
    int expn;              //指数
    struct PNode *next;    //指针域
}PNode,*Polynomial;

/**
*    核心代码如下：
*/
void CreatePolyn(Polynomial &p,int n)
{
    P = new PNode;
    P->next = NULL;                    //先建立一个带头结点的单链表
    for(i = 1;i <= n;++i)              //依次输入n个非零项
    {
         s = new PNode;                 //生成新节点
         cin>>s->coef>>s->expn;         //输入系数和指数
         pre = p;                       //pre用于保存q的前驱，初值为头结点
         q = p->next;                   //q初始化，指向首元结点
         while(q&&q->expn < s->expn)    //通过比较指数找到第一个大于输入项指数的项*q
         {
             pre = q;
             q = q-next;
         }
         s->next = q;
         pre->next = s;                 //将输入项s插入到q和其前驱结点pre之间
     }
}

因为是伪代码，可能看起来有点吃力，下面根据实例来重新理解一遍。

待创建多项式：A(x) = 7+3x+9x^8+5x^17

1、根据6，7行代码，首先创建一个空链表

数据结构——多项式的创建（链式存储）