6-40 构造有序稀疏多项式-链式存储

本题构造有序稀疏多项式的链式存储过程，输入的多项式有两项：系数和指数。

注意 ：输入的指数是无序的。请用链式存储保存多项式。

输出时按指数从小到大的顺序输出。

为简化链表构造，默认构造链表为加监督元单链表。

函数接口定义：

ptr creat();

creat函数是构造链表。

裁判测试程序样例：

#include 
#include 


typedef struct node
{
    float ceof;
    int exp;
    struct node *next;
}node,*ptr;

ptr creat();

void output(ptr h)
{
    ptr p;
    p=h->next;
    while(p!=NULL)
    {
        printf("%+.1fx^%d",p->ceof,p->exp);
        p=p->next;
    }
    printf("n");
}

int main()
{
    ptr head;
    head=creat();
    output(head);
    return 0;
}

输入样例：

100.3  10
90  5
18  92
21.8  2
-19  0
0  0

结尾无空行

输出样例：

-19.0x^0+21.8x^2+90.0x^5+100.3x^10+18.0x^92

 思路：构造一个链式存储结构，然后使输入的数据按照指数有序即可，这里我提供两个思路：一个是我们边输入边排序，一个是我们构造好了以后再去排序，下面我提供边输入边排序的算法

，上代码

ptr creat()
{
    ptr p;
    p = (ptr)malloc(sizeof(node));//申请结点空间
    node* q, * pre, * s;
    p ->next = NULL;//尾结点置空
    
    while(1)
    {
        
        s = (ptr)malloc(sizeof(node));
        scanf("%f %d", &s->ceof, &s->exp);//输入值
        pre = p;
        q = p -> next;
        while (q && q->exp < s->exp)//边输入边比较
        {
            pre = q;
            q = q->next;

        }
        if(s->ceof==0)//循环结束条件，就是输入的值和指数都为0
            break;
        s->next = q;
        pre->next = s;
        
        
            
    }

}