1.链表的概念及结构

        概念：链表是一种物理存储结构上非连续 、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。         链表结构图如下：         链表的结构与火车的原理相同，火车是由火车头拉着一节一节的车厢而运动，链表也如此，创建链表结构的时候，通常使用一个指针指向下一个结构的地址，（双向链表需要额外创建一个指针，指向前一个节点）。         以带头节点不循环单向链表为例：

typedef int SLTDateType;          //先重命名一个类型声明，方便修改数据类型

typedef struct SListNode          //定义链表结构体

{

    SLTDateType data;               //数据元素

    struct SListNode* next;        //这个为结构体指针，指向下一个结构体位置的指针

}SListNode;                              //结构体类型重命名为SListNode  

        注意：

        （1）在图上可以看出，链式结构在逻辑上是连续的，但在物理上不一定连续。

        （2）现实中的节点一般都是从堆上申请出来的。

        （3)  从堆上申请的空间，是按照一定策略来分配的，两次申请的空间可能连续，也可能不连续。

2.链表的常用功能实现

        2.1   初始化并创建带头节点（头节点不存储有效数据！）

SListNode* SListInit()

{

    SListNode* set = (SListNode*)malloc(sizeof(SListNode));

    if (set == NULL)                                                //避免malloc失败，

    {

        printf("malloc error...\n");

        exit(-1);

    }

    set->data = 0;                                                //该数据不是有效数据，可以忽略

    set->next = NULL;                                        //把下一个节点置空；

    return set;

}

         2.2 为了代码能够简洁些，我们可以添加一个动态申请节点的一个接口，方便插入。

// 动态申请一个节点

SListNode* BuySListNode(SLTDateType x)                

{

    SListNode* cur = (SListNode*)malloc(sizeof(SListNode));

    if (cur == NULL)

    {

        perror("BuySListNode( ):error...");

        exit(-1);

    }

    cur->data = x;             

    cur->next = NULL;

    return cur;                   //创建一个结构体，并返回改结构体地址

}

        2.3 单链表的头插

void SListPushFront(SListNode* pplist, SLTDateType x)        //x：插入的数据

{

    assert(pplist);                        //断言一下pplist，防止为空；

    SListNode* pvr = BuySListNode(x);        //动态申请一个节点

    pvr->next = pplist->next;                       

    pplist->next = pvr;

}

         2.4单链表头删

void SListPopFront(SListNode* pplist)      //该函数同理，把next指针的方向搞清楚

{

    assert(pplist);

    SListNode* cur = pplist->next;

    pplist->next = cur->next;

    free(cur);

    cur = NULL;

}

        2.5 单链表尾插

void SListPushBack(SListNode* pplist, SLTDateType x)

{

    assert(pplist);

    SListNode* pvr = BuySListNode(x);

    SListNode* nex = pplist;

    while (nex->next!=NULL)               //循环走到最后一个位置，

    {

        nex = nex->next;

    }

    nex->next = pvr;

}

        2.6 单链表的尾删

void SListPopBack(SListNode* pplist)        //与上面尾插一样，

{

    assert(pplist);

    SListNode* cur = pplist; 

    while (cur->next->next)                       //走到最后倒数第二个位置

    {

        cur = cur->next;

    }

    free(cur->next);                                //free最后一个位置

    cur->next = NULL;                            //把cur置空；完成尾删    

}

         2.7单链表查找

SListNode* SListFind(SListNode* plist, SLTDateType x)

{

    SListNode* tmp = plist->next;        //单链表查找的话，只能遍历一遍链表

    while (tmp)

    {                                                       

        if (tmp->data == x)                      //如果找到x，就返回tmp指针

            return tmp;

        tmp = tmp->next;

    }

    return NULL;                        //没找到就返回空值

         2.8单链表的销毁

void SLTDestroy(SListNode* pphead)

{

    SListNode* cur = pphead;

    while (cur)                                

    {

        SListNode* next = cur->next;              //保存cur下一个指针

        free(cur);                                              //free掉cur指向的位置；

        cur = next;                                           

    }                                                              //循环直至cur为空为止；

    pphead->next = NULL;

}

3 顺序表与链表的区别