数据结构——多项式问题（顺序存储结构or链式存储结构）

补充：malloc函数：

malloc 函数是 C 语言标准库中的一个重要函数，位于 <stdlib.h> 头文件中，主要用于在程序运行时动态分配内存。以下将详细介绍其用法。

前面的返回值指针可以自己定义，如  （int*）malloc....

优点：

• 动态内存分配（堆上分配）的优势：使用 malloc 函数可以在堆上动态分配内存。堆上的内存不会随着函数的结束而自动释放，只要不调用 free 函数，这块内存就会一直存在。因此，MakeEmpty 函数能够返回一个指向堆上分配的内存的指针，调用者可以在后续的程序中持续使用这块内存。
• 自动分配的固定生命周期：栈上分配的变量生命周期与函数的执行周期紧密相关。一旦函数结束，变量就会失效，无法在函数外部继续使用。
• 动态分配的可控生命周期：使用 malloc 分配的内存，其生命周期由程序员手动管理。程序员可以在需要的时候分配内存，在不再使用时通过 free 函数释放内存。这使得程序能够根据实际需求灵活地管理内存，避免了内存的浪费或泄漏。
• 动态分配允许多个实例：在实际应用中，可能需要创建多个线性表实例。使用 malloc 可以多次调用 MakeEmpty 函数，每次都会在堆上分配一块新的内存，从而创建多个独立的线性表实例。

一、对于一个一元多项式，我们如何用c语言表示它？还有我们如何用c语言对他进行相加减、相乘？

关键数据：多项式项数n

                  各项系数a（i），以及指数i；

1.如何表示多项式？

（1）顺序存储结构直接表示：

数组各分量对应多项式各项：下标代表指数：

但是如果遇到指数很大的多项式怎么办？

（2）顺序存储结构二元组：

用结构数组表示，数组分量是由系数a（i）和指数i组成的结构；

（3）链式结构存储：

链表中每个结点存储多项式中的一个非零项，包括系数和指数以及指向下个结点的指针；

typedef struct PoleNode*Polynomial;   //对结构体的指针重命名
struct PolyNode    //定义结构体
{
    int coef;    //系数
    int expon;   //指数
    Polynomial link;   //指向下一个结构体的指针
};

2.线性表的顺序存储实现：

利用数组的连续存储空间顺序存放线性表的各元素：

typedef struct LNode*List;    //定义结构体指针；
struct LNode
{
    ElementType Data[MAXSIZE];   //定义存放数据的数组
    int Last;  //作为计数工具；
};
struct LNode L;   //定义结构体L
List Ptrl;   //定义结构体指针Ptrl

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode*List;
struct LNode1
{
    ElementType Data[MAXSIZE];
    int Last;
};
struct LNode L;
List Ptrl;

List MakeEmpty()   //初始化线性表
{
    List Ptrl;   //定义一个结构体指针；
    Ptrl = (List)malloc(sizeof(struct LNode));
    Ptrl->Last = -1;
    return Ptrl；
}   //得到一个初始化的结构体的指针；

int Find(ELementType X, List Ptrl)   //实现查找功能；传入要查找的值以及结构体数组地址；
{
    int i = 0;
    while(i <= Ptrl->Last && Ptrl->Data[i] != X)    //从0到last进行查找
        i++;
    if(i > Ptrl->Last) 
        return -1;
    else return i;    //返回查找值的下标；
}

void Insert(ElementType X, int i, List Ptrl)    //实现插入功能；传入插入对象，插入位置；
   int j;       
    if(Ptrl->Last == MAXSIZE - 1)  //达到最大内存，无法插入
    {
        printf("表满")；
        return;
    }
    if(i < 1 || i > Ptrl->Last+2}  
       {
           printf("位置不合法")；
       return;
       }
    for(j = Ptrl->Last; j >= i-1; j--)   //从最后位置开始
        Ptrl->Data[j + 1] = Ptrl->Data[j];   //将元素向后移
    Ptrl->Data[i-1] = X;   //插入元素
    Ptrl->Last++;   //改变大小标记
    return;
    
void Delete(int i, List Ptrl)   //实现删除功能
{
    int j;
    if(i < 1||i>Ptrl->Last+1)  
    {
        printf("不存在第%d个元素"， i);
        return;
    }
    for(j = i; j <= Ptrl->Last; j++)
        Ptrl->Data[j-1] = Ptrl->Data[j];    //将要删除的值用下一个值覆盖,实现删除功能
    Ptrl->Last--;
    return;
}