线性表的链式存储实现称为链表。
每一个节点都需要一个结构体变量存储。
前一个节点的指针域指向下一个节点的数据域起始位置。
最后一个节点的指针域内存储的是NULL（即0）。
::: tip
为了简单，考研设计时，单链表都会包含头节点，业界不使用。
头指针L指向的空间称为头节点，认为是0号位置，a1称为第一个节点。考研时认为头节点的数据域为空。
列表为空表示a1-an不存在。
:::
链表的初始化插入：
如下图，插入时的新节点q需要使用malloc申请一个结构体大小的空间（sizeof(LNode)），再强转成结构体指针的类型：
上图中，q->data为数据域，q->next为指针域。p->next为第一个节点a1的地址，保存在头节点p中。
链表的删除、查询：
上图中的第一二行代码作用是确定p和q节点的位置，i为删除位置，
::: warning
每一个节点的空间都是malloc出来的，删除节点后必须free。
:::
上图中while循环中的p用来控制是否遍历到列表的尾部（最后一个元素的指针域是NULL）
::: tip
while循环中的p!=NULL和p等价。
:::
头插法新建链表
头插法是每次新增节点时从头节点后的位置插入链表。
流程如下：
头插法代码：
#include <stdio.h>
#include <stdlib.h>
typedef int Elemtype;
typedef struct LNode
{
Elemtype data;
struct LNode* next;
}LNode,*LinkList;
//LNode*是结构体指针，等同于LinkList，写*LinkList只是为了方便认为是链表而非结构体节点指针
//void list_head_insert(LNode* &L)
//{
// L = (LinkList)malloc(sizeof(LNode)); //申请头节点空间（头指针指向头节点）
// //malloc开辟的空间默认是void类型，上述代码中LinkList可以换成LNode*
// Elemtype x; //读取的元素值放在第一个节点上（头节点是空的），需要再申请一个节点
// L->next = NULL;
// scanf("%d", &x);
// //申请第一个节点空间
// LNode* s = (LinkList)malloc(sizeof(LNode));
// s->data = x;
// s->next = NULL; //头插法中第一个创建的节点会变为最后一个节点，需要将next设置成NULL
// L->next = s; //使得L的next（指针域）指向第一个节点
// while (x!=9999)
// {
// scanf("%d", &x);
// s = (LinkList)malloc(sizeof(LNode)); //s指向新开辟的节点
// s->data = x;
// s->next = L->next; //新节点的next值为头节点L的next，即指向上一个创建的节点
// L->next = s; //头节点的next指向新建的节点
// }
//}
//上述函数在插入节点时会插入最后一个作为结束标志的9999的数据，函数改进如下：
void list_head_insert(LNode*& L)
{
L = (LinkList)malloc(sizeof(LNode)); //申请头节点空间（头指针指向头节点）
//malloc开辟的空间默认是void类型，上述代码中LinkList可以换成LNode*
Elemtype x; //读取的元素值放在第一个节点上（头节点是空的），需要再申请一个节点
L->next = NULL; //循环中将L的next赋给第一次循环创建的节点的next，即链表最后一个节点
scanf("%d", &x); //供while循环判断是否结束
//申请第一个节点空间
LNode* s = (LinkList)malloc(sizeof(LNode));
while (x != 9999)
{
s = (LinkList)malloc(sizeof(LNode)); //s指向新开辟的节点
s->data = x;
s->next = L->next; //新节点的next值为头节点L的next，即指向上一个创建的节点
L->next = s; //头节点的next指向新建的节点（头插法新建的节点在头节点后面一个位置）
scanf("%d", &x);
}
}
void print_list(LinkList L)
{
L = L->next;
while (L != NULL)
{
printf("%3d", L->data);
L = L->next;
}
}
int main()
{
LinkList L; //等同于LNode* L
list_head_insert(L);
print_list(L);
return 0;
}尾插法新建链表
流程如下：
链表的增删查改操作：
//输入9999表示输入结束
#include <stdio.h>
#include <stdlib.h>
typedef int Elemtype;
typedef struct LNode
{
Elemtype data;
struct LNode* next;
}LNode, * Linklist;
//尾插法插入
void list_tail_insert(Linklist& L)
{
L = (LNode*)malloc(sizeof(LNode)); //头节点
L->next = NULL;
LNode* s, * r = L; //r->next=NULL;
Elemtype x;
scanf("%d", &x);
while (x != 9999)
{
s = (LNode*)malloc(sizeof(LNode));
r->next = s;
s->data = x;
r = s;
scanf("%d", &x);
}
r->next = NULL;
}
//节点查找
LNode* value_find(LNode* L,Elemtype x)
{
Elemtype a = 0;
if (x < 0)
{
return NULL;
}
while (L && a < x)
{
L = L->next;
a++;
}
/*printf("%d\n", L->data);*/
return L;
}
//值插入
bool value_insert(LNode* L, Elemtype x, Elemtype y) //在某位置上插入节点
{
Elemtype i = 0;
LNode* s = value_find(L, x - 1); //找到要插入位置的前一个节点
if (s == NULL)
{
return false;
}
LNode* q = (LNode*)malloc(sizeof(LNode)); //新节点
q->data = y;
q->next = s->next;
s->next = q;
return true;
}
//删除节点
bool Dele_list(LNode* L, Elemtype x)
{
//1.调用位置查找函数
LNode* p = value_find(L, x - 1); //要删除节点的前一个节点
if (p == NULL)
{
return false;
}
LNode* q = p->next; //要删除的节点
p->next = q->next;
free(q);
return true;
//2.直接遍历查找
//Elemtype i = 0;
//while (L && i < x - 1)
//{
// L = L->next;
// i++;
//}
//LNode* s = L;
//L = L->next;
//s->next = L->next;
//free(L);
//return true;
}
//打印节点
void Print_list(LNode* L)
{
L = L->next;
while (L)
{
printf("%3d", L->data);
L = L->next;
}
printf("\n");
}
int main()
{
LNode* L;
list_tail_insert(L);
LNode* search = value_find(L, 2);
if (search != NULL)
{
printf("%d\n", search->data);
}
int ret = 0;
ret = value_insert(L, 2, 99);
if (ret)
{
Print_list(L);
}
else
{
printf("false\n");
}
ret = Dele_list(L, 4);
if (ret)
{
Print_list(L);
}
return 0;
}
