数据结构——链表
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 顺序表与链表的区别
