数据结构——单链表

定义：

本质是用链式结构实现线性表，即逻辑上相邻的数据元素之间通过指针连接
由数据（数据域data）与记录下一组数据地址的指针（指针域next）组成的部分称为结点（node），
比如火车是由一节一节车厢连接起来的。

相比于顺序表的区别

代码实现：

#define type_data int

typedef struct LNode {//LNode 指 LinklistNode链表结点的缩写，重命名后续方便
type_data data;//数据域，这里数据默认为int
struct LNode* next; //指针域，要指向下一个结点，也就是同类型的自己，所以类型是struct LNode*
//此时由于typedef还没有执行完，所以这里需要写上struct
}LNode;

单链表创建：

不带头结点的尾插：

代码实现：

LNode* list_tailcreat() //不带头结点的尾插法
{
LNode* L = NULL;//创建空链表
LNode* tail = L;//tail的作用是通过在尾部设置一个指针，避免了到达链表尾部需要遍历的情况

int size = 0;//以输入的方式创建
printf("请输入链表长度:");
int r = scanf("%d", &size);//这里和后续的scanf只是用r接受一下返回值，毕竟太多警告看着不舒服
printf("请输入数据：");
for (int i = 0; i < size; i++)//通过创立新结点并用指针相连得到链表
{
LNode* s = (LNode*)malloc(sizeof(LNode));//这里不写LNode s，临时变量会在函数结束时销毁
//此时s为当前节点的地址
int r = scanf("%d", &s->data);
s->next = NULL;

if (L == NULL)//链表为空时
{
L = tail = s;//直接接入链表
}
else {
tail->next = s;//令当前尾节点指向新结点
tail = s;//令新结点成为尾节点
}

}
return L;
}

注意：

带头结点的尾插：

代码实现：

LNode* list_tailbuliding() //带头结点的尾插法
{
LNode* L = (LNode*)malloc(sizeof(LNode));//创建空链表

assert(L);

L -> next = NULL;//创建头结点
LNode* tail = L;//tail的作用是通过在尾部设置一个指针，避免了到达链表尾部需要遍历的情况

int size = 0;//以输入的方式创建
printf("请输入链表长度:");

int r = scanf("%d", &size);
printf("请输入数据：");
for (int i = 0; i < size; i++)//通过创立新结点并用指针相连得到链表
{
LNode* s = (LNode*)malloc(sizeof(LNode));//这里不写LNode s，临时变量会在函数结束时销毁
//此时s为当前节点的地址
int r = scanf("%d", &s->data);
s->next = NULL;

//直接在头结点的基础上尾插
tail->next = s;
tail = s;
}
return L;
}

带头结点的头插法：

代码实现：

LNode* list_headbuliding()
{
LNode* L = (LNode*)malloc(sizeof(LNode));
assert(L);

L->next = NULL;//创建头结点
int size;

printf("请输入表长：");
int r = scanf("%d", &size);

printf("请输入数据：");

for (int i = 0; i < size; i++)
{
LNode* s = (LNode*)malloc(sizeof(LNode)); //创建新节点
assert(s);
int r =scanf("%d",&s->data);//新节点数据域

s->next = L->next;//顺序不能反
L->next = s;

}

return L;
}

注意：

单链表打印：

代码实现：

void list_printf(LNode* s)//带头结点打印
{
//可以通过指针遍历
LNode* p = 0;
//printf("%d ", s->data); //这里看带不带头结点，如果不带，就需要执行这一行，之后默认带头结点
for ( p= s->next; p != NULL; p = p->next)
{
printf("%d ", p->data);
}
printf("\\n");
}

如果同时打印数据为0 1 2 3 4的链表，头尾插的差距如下图：

单链表查找：

查找的核心就是遍历与比较，遍历通过循环与指针实现，比较分为按值查找和按位序查找，注意一点，头结点不算有效数据，因此第一个结点是头结点的下一个结点(L->next)

按值查找：

按值查找，其时间复杂度为O(n)

代码实现：

LNode* list_find(LNode*L,type_data x)//按值查找
{
assert(L);
LNode* s;

for (s = L->next; s != NULL; s = s->next)
{
if (s->data == x)
{
return s;
}
}
printf("找不到\\n");
return s;
}

按位序查找：

时间复杂度也是O(n)

代码实现：

LNode* list_get(LNode* L, int x)//按位序查找
{
//位序是从零到表长的范围
assert(L);
if (x < 0)
return NULL;

LNode* s = L;//从头结点开始
int i = 0;//用于计数

while (s != NULL && i < x)
{
s = s->next;
i++;
}

return s;
}

插入：

这个可以结合之前说的头插法与按位序查找辅助理解，比如在第三位插入5，则需要找到第二个节点，然后结合头插法，将新结点与第二个节点的下一个节点连接，然后将第二个节点与新结点连接，顺序不能反，否则将丢失原本第三个节点之后的地址。

简易动画：

代码实现：

void list_insert(LNode* L, int x, type_data i)//插入，在第x个位置插入i
{
assert(L);

LNode* p = list_get(L, x – 1);

assert(p);

LNode* s = (LNode*)malloc(sizeof(LNode));

assert(s);

s->data = i;
s->next = p->next;
p->next = s;//注意顺序别弄错了

}

删除：

与查找类似，不过要注意释放掉被删除的内存空间，以免造成内存泄漏

简易动画：

代码实现：

void list_delete(LNode* L, int x)//删除
{
assert(L);
LNode* p = list_get(L, x – 1);
assert(p&&p->next);//防止p为空，或要删除的节点为空

LNode* s = p->next;
p->next = s->next;
free(s);

}

销毁：

销毁就是遍历和释放空间结合，不过释放前要先记录下一个节点的位置而已

简易动画：

代码实现：

void list_destory(LNode* L)//销毁
{
assert(L);

LNode* p = L->next;

while (p)
{
LNode* s = p-> next;
free(p);
p = s;
}

free(L);
}

总结：

链表与顺序表的区别如下图