顺序表实现稀疏多项式

原文链接
由于书上给的代码都是只有核心的代码，没法直接实现，所以我就尝试将书上提到的函数都用c语言实现了一下。仅供参考，用来对照一下书中的代码，加深理解。

注意点

书中说是给的C语言的伪代码，但是给的代码还是用到了一些c++的东西，比如说status InitList(SqList &L),这个地方就是用到了c++的引用。具体c语言的指针和c++的引用的区别，这里就不过多赘述，想要了解可以查其他资料。还有就是，C语言没有办法这样给结构体赋值e=L.elem[i-1];,想要这样写必须要用c++的重载，类似这样的写法struct e1 = struct e2，在C语言中是无法实现的。

书中的代码基本上我都实现了，亲测可以运行。其中main()函数每一个注释块中都是对某个函数的功能的尝试。想要运行特定函数，直接删除注释就可以直接使用。

线性表结构

为了能够更好的说明线性表Sqlist的结构，我画了一个插图来说明。第一次画，画的不好请见谅。请结合稀疏多项式代码理解。

线性表插图.png

完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100
#define OK 1
#define OVERFLOW -1
#define error -2
#define False 0 

int i,j,k;

typedef struct 
{
    float coef;             //稀疏多项式系数
    int expn;               //稀疏多项式指数
}Polynomial;

typedef struct
{
    Polynomial *elem;
    int length;
}SqList;

int InitList(SqList *L);                        //构建一个空的线性表
int DestroyList(SqList *L);                     //销毁一个已经存在的线性表
int ListInput(SqList *L,Polynomial e);          //在线性表末尾添加一个新元素
int ListInsert(SqList *L, int i, Polynomial e); //在指定的i元素之前添加一个新元素
int TraverseList(SqList *L);                    //遍历整个线性表
int ListDelete(SqList *L,int i);                //删除第i个元素
int ClearList(SqList *L);                       //将线性表设为空表
int ListEmpty(SqList *L);                       //检查线性表是不是为空，返回true或者false
int ListLength(SqList *L);                      //返回线性表中的元素个数
int GetElem(SqList *L, int i,Polynomial *e);    //返回第i个元素
int LocateElem(SqList *L,Polynomial e);         //返回第一个与e相同的数据元素的位置
int margc(SqList *L1,SqList *L2,SqList *L3);    //合并两个有序线性表


int main()
{
    int status;
    float f;
    int d;
    int cnt;
    /*  //这一段代码是初始化一个线性表
    SqList L1;
    InitList(&L1);
    */
    /*  //这段代码是在末尾添加数据的方法创建一个线性表
    Polynomial e;
    while(scanf("%f %d",&f,&d)&&(f!=-1&&d!=-1))
    {
        e.coef = f;
        e.expn = d;
        ListInput(&L1,e);

    }
    */

    /*   //这一段代码是在特定位置插入的方法实现一个线性表
    scanf("%d %f %d",&i,&f,&d);
    e.coef = f;
    e.expn = d;
    ListInsert(&L1,i,e);
    */

   /*   //这段代码是为了删除线性表第i个元素
    scanf("%d",&i);
    ListDelete(&L1,i);
    */

    /*  //这段代码是为了判断线性表是否为空
    status = ListEmpty(&L1);
    printf("%d",status);
    */

    /*  //这段代码是为了获得线性表的长度
    status = ListLength(&L1);
    printf("%d",status);
    */

    /*  //这段代码是为了返回线性表第i个元素，并将值保存在结构体e中
    scanf("%d",&i);
    GetElem(&L1, i,&e);
    printf("%f %d",e.coef,e.expn);
    */

    /* //这段代码是为了返回第一个与e相同的数据元素的位置
    scanf("%f %d",&f,&d);
    e.coef=f;
    e.expn = d;
    status = LocateElem(&L1,e);
    printf("%d",status);
    */

    /*  //这段代码是为了合并两个有序线性表，并将结果保存在L3这个线性表中
    SqList L1,L2,L3;
    InitList(&L1);
    InitList(&L2);
    InitList(&L3);
    Polynomial e;
    while(scanf("%f %d",&f,&d)&&(f!=-1&&d!=-1))
    {
        e.coef = f;
        e.expn = d;
        ListInput(&L1,e);

    }
    while(scanf("%f %d",&f,&d)&&(f!=-1&&d!=-1))
    {
        e.coef = f;
        e.expn = d;
        ListInput(&L2,e);
    }
    margc(&L1,&L2,&L3);
    */


    TraverseList(&L3);    //遍历整个线性表
    //printf("%d",status);
    //ClearList(SqList *L)
    //DestroyList(&L1);
    return 0;
}

int InitList(SqList *L)
{
    L->elem = (Polynomial *)malloc(MAXSIZE * sizeof(Polynomial));
    if(!L->elem)
        return OVERFLOW;
    L->length = 0;
    return OK;
}

int DestroyList(SqList *L)
{
    free(L->elem);
    L->length = 0;
    return 1;
}

int ClearList(SqList *L)
{
    L->length == 0;
    return 0;
}

int ListEmpty(SqList *L)
{
    if(L->length==0)
        return False;
    return OK;

}

int ListLength(SqList *L)
{
    return L->length;
}

int GetElem(SqList *L, int i,Polynomial *e)
{
    if(i<1||i>L->length)
        return error;
    e = &(L->elem[i-1]);
    return OK;
}

int LocateElem(SqList *L,Polynomial e)
{
    for(i=0;i<L->length;i++)
        if(L->elem[i].coef == e.coef&&L->elem[i].expn == e.expn)
            return i+1;
    return error;
}

int ListInput(SqList *L,Polynomial e)
{
    i=L->length;
    L->elem[i]=e;
    L->length++;
    return OK;
}

int ListInsert(SqList *L, int i, Polynomial e)
{
    if(i<1||i>L->length+1)
        return error;
    if(L->length == MAXSIZE)
        return error;
    for(j=L->length-1;j>=i-1;j--)
        L->elem[j+1] = L->elem[j];
    L->elem[i-1] = e;
    ++L->length;
    return OK;
}

int ListDelete(SqList *L,int i)
{
    if(i<1||i>L->length)
        return error;
    for(j=i;j<=L->length-1;j++)
        L->elem[j-1]=L->elem[j];
    --L->length;
    return OK;
}

int TraverseList(SqList *L)
{
    for(i=0;i<L->length;i++)
        printf("%d,%f,%d \n",i,L->elem[i].coef,L->elem[i].expn);
    return OK;
}

int margc(SqList *L1,SqList *L2,SqList *L3)
{
    Polynomial x;   //为了跟上边e区别，这里使用x
    i=0,j=0;
    while(i<L1->length&&j<L2->length)
    {
        if(L1->elem[i].expn<L2->elem[j].expn)
        {
            x.coef = L1->elem[i].coef;
            x.expn = L1->elem[i].expn;
            ListInput(L3,x);
            i++;
        }
        else if(L1->elem[i].expn==L2->elem[j].expn)
        {
            x.coef = L1->elem[i].coef+L2->elem[j].coef;
            x.expn = L1->elem[i].expn;
            ListInput(L3,x);
            i++;
            j++;
        }
        else
        {
            x.coef = L2->elem[j].coef;
            x.expn = L2->elem[j].expn;
            ListInput(L3,x);
            j++;
        }
    }
    while(j<L2->length)
    {
        x.coef = L2->elem[j].coef;
        x.expn = L2->elem[j].expn;
        ListInput(L3,x);
        j++;
    }
    while(i<L1->length)
    {
        x.coef = L1->elem[i].coef;
        x.expn = L1->elem[i].expn;
        ListInput(L3,x);
        i++;
    }
    return OK;
}