单链表实现稀疏多项式完整代码

柔情只为你懂 2023-02-20 02:13 18阅读 0赞

[原文链接][Link 1]

## 单链表 ##

单链表是由一个个结点构成的，上一个结点指向下一个结点的位置。与顺序表不同，单链表的结点除了存储数据元素外，还有一个指针域，用来指示下一个节点的位置。根据这一特性，虽然单链表多储存了一个指针域，存储密度没有顺序表大，但是更加灵活，多少个数据就创建多少个结点。  
根据链表结点所含指针的个数，指针指向和指针连接方式，可将链表分成单链表，循环链表，双向链表，二叉链表，十字链表，邻接表，邻接多重表。其中，这里只简单介绍单链表。

## LNode 和 LinkList ##

对于LNode和LinkList，可能大家不太了解这两个作用，也可能看到这样定义一个结构体很奇怪。首先大家要先了解一下struct结构体的基本用法，我在这一篇博客专门说了这个问题，大家可以看一下。

[C语言struct简述][C_struct]

总的来说，在书中的这个例子中，LNode为这个结构体的一个变量，而LinkList为指向这个结构体的指针类型。相当于 struct LNode LNode 和struct LNode\* LinkList。其中`Lnode *p`中的p和`LinkList L`中的L是一样，都是指向结构体Lnode的指针变量，这里是为了让LinkList L特意指向头节点，与其他普通的节点分开，才特意多设置一个LinkList指针类型。

在后边的代码中，L一直指向的就是头结点。而LNode \*p就是创建了一个新的结点。

## 头结点 ##

关于头结点，首元结点，头指针的概念，书中说的很清楚了，这里就不过多赘述。  
对于下文的代码，为带有有头结点的单链表代码。设置头结点的好处有很多，书上也介绍了，就不多说废话。  
其中，`LinkList L`创建的就是头指针，并且L一直指向的就是头结点。L->next指向的才是第一个元素的数据，也就是首元结点。初试化的时候L->next=NULL。

## 初始化 ##

对于书中的初始化单链表代码，用到了引用。按照c语言没办法这样写。  
我是这样写这个函数的，虽然看着有点奇怪，但是没办法。

LinkList L;
    L = (LNode *)malloc(sizeof(LNode));
    InitList(L);
    
    int InitList(LinkList L)
    {
        L->next =NULL;
        return OK;
    }

这样写算是最简单的解决，如果把`L = (LNode *)malloc(sizeof(LNode));`这条语句写在InitList函数里面，就会出现错误。虽然不报错，但是会产生大问题。我当时就在这被坑了好久。  
具体不能这样写的原因是，你把L指针传到InitList中，然后再函数里面使用malloc函数。你就把L指向的地址改变了，然后函数里面的L指针是就和外边那个L指针不是同一个了，也就是InitList函数就没用了。

## 遍历 ##

遍历函数再我上一篇的顺序表中说过了，只要就是将整个单链表遍历一遍。方便查看使用函数后单链表的变化，方便查错。

int TraverseList(LinkList L)
    {
        LNode *p;
        p = L->next;
        while(p)
        {
            printf("%d %f\n",p->data.expn,p->data.coef);
            p=p->next;
        }
    }

## 取值 ##

该函数的作用就是把单链表第i个元素存到e的地址，没啥说的。

int GetElem(LinkList L, int i,Polynomial *e)
    {
        LNode *p;
        p = L->next;
        j=1;
        while(p&&j<i)
        {
            p=p->next;
            j++;
        }
        if(!p||j>i)
            return ERROR;
        e = p->data;
        return OK;
    }

## 查找 ##

由于是查找指定的数据的位置，返回的是地址。所以要注意函数前面的返回类型为LNode。

LNode *LocateElem(LinkList L,Polynomial e)
    {
        LNode *p;
        p=L->next;
        while(p->data!= e && p)
            p->next;
        return p;
    }

## 插入 ##

关键就是遍历单链表，然后找到第i个位置，然后再创建一个Lnode结构体，插入到该位置就行。

int ListInsert(LinkList L, int i, Polynomial e)
    {
        LNode *p;
        p = L;
        j=0;
        while(p && (j<i-1))
        {
            p = p->next;
            j++;
        }
        if(!p && j>i-1)
            return ERROR;
        LNode *s;
        s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return OK;
    }

## 删除 ##

想要删除第i个元素，只需要将第i-1个元素的指针指向第i+1个元素的地址就行，然后释放第i个元素占的内存空间。

int ListDelete(LinkList L,int i)
    {
        LNode *p;
        p = L;
        j = 0;
        while((p->next) && (j<i-1))
        {
            p=p->next;
            j++;
        }
        if(!(p->next) || j>i-1)
            return ERROR;
        LNode *q;
        q=p->next;
        p->next = q->next;
        free(q);
        return OK;
    }

## 前插法创建单链表 ##

前插法，就是把元素每次都插入到头指针的后边。如果将1，2，3，4，5按照前插法插入到单链表中，那么输出来就是5，4，3，2，1的顺序。

int CreateList_H(LinkList L,int n)
    {
        LNode *p;
        for(i=0;i<n;i++)
        {
            p=(LNode *)malloc(sizeof(LNode));
            scanf("%d %f",&p->data.expn,&p->data.coef);
            p->next=L->next;
            L->next = p;
        }
    }

## 使用后插法创建单链表 ##

使用后插法创建单链表就是在单链表末尾插入元素。如果将1，2，3，4，5按照后插法创建单链表，那么最后输出来还是1，2，3，4，5的顺序。注意我这个代码是从空表开始使用后插法创建单链表，如果不是空表的话，需要循环r=r->next，知道r指向单链表的最后一个元素。

nt CreateList_R(LinkList L,int n)
    {
        LNode *p;
        LNode *r;
        r=L;
        for(i=0;i<n;i++)
        {
            p=(LNode *)malloc(sizeof(LNode));
            scanf("%d %f",&p->data.expn,&p->data.coef);
            p->next=NULL;
            r->next = p;
            r=p;
        }
    }

## 获取前驱结点的值 ##

这个函数是这一章最开始的函数，是为了获取指定节点cur\_e前面那个结点的值pre\_e。所以，只要要再多加一个指针存储p指针的前驱指针即可。

int PriorElem(LinkList L,Polynomial cur_e,Polynomial *pre_e)
    {
        LNode *p;
        LNode *pre;
        p=L->next;
        pre = NULL;
        while(p&& p->data != cur_e)
        {
            pre = p;
            p=p->next;
        }
        if(!pre)
            return ERROR;
        pre_e = pre->data;
        return OK;
    }

## 获取后驱结点的值 ##

该函数的作用就是获取后驱结点的值。跟前驱结点的获取类似，多设一个指针存储后一个结点指针就行。

int NextElem(LinkList L,Polynomial cur_e,Polynomial *next_e)
    {
        LNode *p;
        LNode *next;
        p=L->next;
        next = NULL;
        while(p&& p->data != cur_e))
        {
            p=p->next;
            next=p->next;
        }
        if(!next)
            return ERROR;
        next_e = next->data;
        return OK;
    }

## 合并两个有序单链表 ##

跟合并两个顺序表的方法一样，在顺序表那一篇说过了，这里就不多赘述。

int margc(LinkList L1,LinkList L2,LinkList L3)
    {
        LNode *p;
        LNode *l1,*l2;
        l1=L1->next;
        l2 = L2->next;
        p=L3;
        while(l1&&l2)
        {
            if(l1->data.expn<=l2->data.expn)
            {
                p->next= l1;
                l1=l1->next;
            }
            else
            {
                p->next = l2;
                l2=l2->next;
            }
            p=p->next;    
        }
        while(l1)
        {
            p->next=l1;
            l1 = l1->next;
            p=p->next;
        }
        while(l2)
        {
            p->next=l2;
            l2=l2->next;
            p=p->next;
        }
        return OK;
    }

## 其他地方 ##

其他地方就没有什么可说的了。除了书上的给的函数，我还自己写了几个可能会用到的函数，算是补充吧。如果还有需要用到的函数，可以说一下。可能写的有错误，可以指出了。

## 完整代码 ##

#include <stdio.h>
    #include <stdlib.h>
    
    #define OK 1
    #define ERROR -1
    
    typedef struct 
    {
        float coef;
        int expn;
    }Polynomial;
    
    typedef struct LNode
    {
        Polynomial data;
        struct LNode *next;
    }LNode, *LinkList;
    
    int InitList(LinkList L);  //初始化函数
    int GetElem(LinkList L, int i,Polynomial *e);      //获取第i个结点的数据
    LNode *LocateElem(LinkList L,Polynomial e);         //获取结点数据为e的结点地址
    int ListInsert(LinkList L, int i, Polynomial e);    //在i位置插入结点e
    int TraverseList(LinkList L);                       //遍历整个单链表，输出每个单链表的值
    int ListDelete(LinkList L,int i);                   //删除第i个结点
    int CreateList_H(LinkList L,int n);                 //前插法建立单链表
    int CreateList_R(LinkList L,int n);                 //后插法建立单链表
    int PriorElem(LinkList L,Polynomial cur_e,Polynomial *pre_e);       //获取结点值为cur_e的前面那个结点的值，并存储在pre_e中
    int NextElem(LinkList L,Polynomial cur_e,Polynomial *next_e);       //获取结点值为cur_e的后面那个结点的值，并存储在next_e中
    int margc(LinkList L1,LinkList L2,LinkList L3);                     //将两个有序线性表按指数从小到大组合到L3单链表中
    
    int i,j,k;
    int main()
    {
        int status;
        LinkList L;
        L = (LNode *)malloc(sizeof(LNode));           //重要提醒,这一条语句只能放到函数外边
        InitList(L);
        Polynomial e;
        int d;
        float f;
        i=0;
        
        /*  //利用ListInsert创建一个单链表
        while(scanf("%d %f %d",&d,&f,&i)&&(d!=-1&&f!=-1))
        {
            e.coef = f;
            e.expn = d;
            status = ListInsert(L, i, e);
        }
        TraverseList(L);
        */
    
        /*
        scanf("%d",&i);
        CreateList_H(L,i);
        TraverseList(L);
        */
    
        /*
        scanf("%d",&i);
        CreateList_R(L,i);
        TraverseList(L);
        */
    
        /*
        scanf("%d",&i);
        GetElem(L,i,&e);
        printf("%d %f\n",e.expn,e.coef);
        */
    
        /*
        scanf("%d %f",&d,&f);
        e.coef=f;
        e.expn=d;
        LNode *p;
        p = LocateElem(L,e);
        printf("%p\n",p);
        */
    
        /*
        scanf("%d",&i);
        ListDelete(L,i);
        TraverseList(L);
        */
    
        /*
        Polynomial cur_e,pre_e;
        scanf("%d %f",&cur_e.expn,&cur_e.coef);
        PriorElem(L,cur_e,&pre_e);
        printf("%d %f\n",pre_e.expn,pre_e.coef);
        */
        /*
        Polynomial cur_e,next_e;
        scanf("%d %f",&cur_e.expn,&cur_e.coef);
        NextElem(L,cur_e,&next_e);
        printf("%d %f\n",next_e.expn,next_e.coef);
        */
    
        /*  //验证margc函数
        LinkList L1,L2,L3;
        L1 = (LNode *)malloc(sizeof(LNode));
        L2 = (LNode *)malloc(sizeof(LNode));
        L3 = (LNode *)malloc(sizeof(LNode));
        InitList(L1);
        InitList(L2);
        InitList(L3);
        while(scanf("%d %f %d",&d,&f,&i)&&(d!=-1&&f!=-1))
        {
            e.coef = f;
            e.expn = d;
            status = ListInsert(L1, i, e);
        }
        TraverseList(L1);
        while(scanf("%d %f %d",&d,&f,&i)&&(d!=-1&&f!=-1))
        {
            e.coef = f;
            e.expn = d;
            status = ListInsert(L2, i, e);
        }
        TraverseList(L2);
        margc(L1,L2,L3);
        TraverseList(L3);
        */
        return 0;
    }
    
    int InitList(LinkList L)
    {
        L->next =NULL;
        return OK;
    }
    
    int GetElem(LinkList L, int i,Polynomial *e)
    {
        LNode *p;
        p = L->next;
        j=1;
        while(p&&j<i)
        {
            p=p->next;
            j++;
        }
        if(!p||j>i)
            return ERROR;
        e = p->data;
        return OK;
    }
    
    LNode *LocateElem(LinkList L,Polynomial e)
    {
        LNode *p;
        p=L->next;
        while(p->data!= e && p)
            p->next;
        return p;
    }
    
    int ListInsert(LinkList L, int i, Polynomial e)
    {
        LNode *p;
        p = L;
        j=0;
        while(p && (j<i-1))
        {
            p = p->next;
            j++;
        }
        if(!p && j>i-1)
            return ERROR;
        LNode *s;
        s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return OK;
    }
    
    int TraverseList(LinkList L)
    {
        LNode *p;
        p = L->next;
        while(p)
        {
            printf("%d %f\n",p->data.expn,p->data.coef);
            p=p->next;
        }
    }
    
    int ListDelete(LinkList L,int i)
    {
        LNode *p;
        p = L;
        j = 0;
        while((p->next) && (j<i-1))
        {
            p=p->next;
            j++;
        }
        if(!(p->next) || j>i-1)
            return ERROR;
        LNode *q;
        q=p->next;
        p->next = q->next;
        free(q);
        return OK;
    }
    
    int CreateList_H(LinkList L,int n)
    {
        LNode *p;
        for(i=0;i<n;i++)
        {
            p=(LNode *)malloc(sizeof(LNode));
            scanf("%d %f",&p->data.expn,&p->data.coef);
            p->next=L->next;
            L->next = p;
        }
    }
    
    int CreateList_R(LinkList L,int n)
    {
        LNode *p;
        LNode *r;
        r=L;
        for(i=0;i<n;i++)
        {
            p=(LNode *)malloc(sizeof(LNode));
            scanf("%d %f",&p->data.expn,&p->data.coef);
            p->next=NULL;
            r->next = p;
            r=p;
        }
    }
    
    int PriorElem(LinkList L,Polynomial cur_e,Polynomial *pre_e)
    {
        LNode *p;
        LNode *pre;
        p=L->next;
        pre = NULL;
        while(p&& p->data != cur_e)
        {
            pre = p;
            p=p->next;
        }
        if(!pre)
            return ERROR;
        pre_e = pre->data;
        return OK;
    }
    
    int NextElem(LinkList L,Polynomial cur_e,Polynomial *next_e)
    {
        LNode *p;
        LNode *next;
        p=L->next;
        next = NULL;
        while(p&& p->data != cur_e))
        {
            p=p->next;
            next=p->next;
        }
        if(!next)
            return ERROR;
        next_e = next->data;
        return OK;
    }
    
    int margc(LinkList L1,LinkList L2,LinkList L3)
    {
        LNode *p;
        LNode *l1,*l2;
        l1=L1->next;
        l2 = L2->next;
        p=L3;
        while(l1&&l2)
        {
            if(l1->data.expn<=l2->data.expn)
            {
                p->next= l1;
                l1=l1->next;
            }
            else
            {
                p->next = l2;
                l2=l2->next;
            }
            p=p->next;    
        }
        while(l1)
        {
            p->next=l1;
            l1 = l1->next;
            p=p->next;
        }
        while(l2)
        {
            p->next=l2;
            l2=l2->next;
            p=p->next;
        }
        return OK;
    }

[Link 1]: https://mp.weixin.qq.com/s/B-ctXAeXOeWQhM7tpL29uA
[C_struct]: https://mp.weixin.qq.com/s?__biz=Mzg2MzA4ODE1Nw==&mid=2247483715&idx=1&sn=34638b3fe634dc322b0ec7321472da58&chksm=ce7cba31f90b332727311a0f10b83830c996cd2e4c030e807415f140184c19acaac066cbb3fb&token=691071959&lang=zh_CN#rd