顺序表实现稀疏多项式完整代码

素颜马尾好姑娘i 2023-02-27 08:29 5阅读 0赞

# 顺序表实现稀疏多项式 #

[原文链接][Link 1]  
由于书上给的代码都是只有核心的代码，没法直接实现，所以我就尝试将书上提到的函数都用c语言实现了一下。仅供参考，用来对照一下书中的代码，加深理解。如果有错误的话，希望大家指出来。

## 注意点 ##

书中说是给的C语言的伪代码，但是给的代码还是用到了一些c++的东西，比如说`status InitList(SqList &L)`,这个地方就是用到了c++的引用。具体c语言的指针和c++的引用的区别，这里就不过多赘述，想要了解可以查其他资料。

书中所有提到的函数基本上我都实现了，亲测可以运行。其中main()函数每一个注释块中都是对某个函数的功能的尝试。想要运行特定函数，直接删除注释就可以直接使用。由于函数太多，下面我直挑重要的讲解。

## 线性表结构 ##

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hwdV95YW5nY2hlbg_size_16_color_FFFFFF_t_70_pic_center]

## 顺序表结构 ##

在结构体polynomial中存储了每个多项式的系数和指数，在Sqlist结构体中存储了所有的多项式，length存储了多项式的个数。

typedef struct 
    {
        float coef;             //系数
        int expn;               //指数
    }Polynomial;
    
    typedef struct
    {
        Polynomial *elem;
        int length;
    }SqList;

## 初始化 ##

我们使用C语言的malloc函数为顺序表的Polynomial结构体分配特定大小的空间。

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

## 顺序表元素的插入 ##

在顺序表元素的插入这一点，我写了两个函数。ListInput函数是直接在顺序表的末尾插入元素。ListInsert函数是在指定的i元素之前插入新的元素。

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 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;
    }

## 顺序表取值 ##

顺序表的取值是为了获得第i个元素的值，并将结果保存在结构体e中。

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

## 顺序表的查找 ##

顺序表的查找功能是为了查找第一个等于元素e的元素的位置。

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;
    }

## 顺序表的删除 ##

顺序表的删除功能是删除第i个元素。实现的操作就是从i+1位置的元素统一往前挪一位就行。然后单链表的长度减一位。

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;
    }

## 有序顺序表的合并 ##

由于书中也提到了有序线性表的合并，所以就一并在这个地方写下来了。首先，一定要知道是有序线性表才可以这样写。无序的更加麻烦，在这里就不写了。  
有序线性表的合并采用的就是归并排序的思想。创建另一个顺序表L3，然后比较两个指针，分别指向有序线性表L1和L2的首个元素。然后比较大小。选择小的元素进入L3，然后指针挪到下一位，继续比较。

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=L1->elem[i];
                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=L2->elem[j];
                ListInput(L3,x);
                j++;
            }
        }
        while(j<L2->length)
        {
            x= L2->elem[j];
            ListInput(L3,x);
            j++;
        }
        while(i<L1->length)
        {
            x = L1->elem[i];
            ListInput(L3,x);
            i++;
        }
        return OK;
    }

## 完整代码 ##

#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;
    }
    ].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;
    }

[Link 1]: https://mp.weixin.qq.com/s/ldlnWVNAwi8CSTms4ZI8Hw
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hwdV95YW5nY2hlbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/4298e4ef30484ed08c34f7675c42f0b7.png