单链表的实现、查找、插入和删除
定义单链表
typedef int ElemType;
// 定义单链表结点结构体
typedef struct LNode{
ElemType data; //数据域：存储结点的实际数据
struct LNode *next; //指针域：存储下一个结点的内存地址
}LNode,*LinkList;LNode* 与 LinkList 与 struct LNode* 等价，后续有使用不同方式。
实现单链表（带头结点）
头插法创建单链表
void list_head_insert(LinkList &L){ //改变L的值，使用引用&
// 1.申请头结点空间，头指针L指向头结点
L=(LNode*)malloc(sizeof(LNode));
L->next=NULL;
ElemType x;
scanf("%d",&x);
LNode *s; //指针变量：用来指向申请的新结点
// 2.循环创建结点并执行头插操作
while (x!=9999){
// 2.1 为新结点申请堆内存，同时指向新结点
s=(LNode*)malloc(sizeof(LNode));
// 2.2 给新结点赋值
s->data=x; //给新结点的数据域赋值为输入的x
s->next=L->next; //新结点的指针域指向“头结点指向的结点”；第一次赋值时为NUll，表示最后一个结点，标志链表结束
// 2.3 头插核心
L->next=s; //头结点的指针域指向“新结点”，新结点成为链表第一个有效结点，完成头插操作
scanf("%d",&x); //继续读取下一个结点数据
}
}重点：新结点的指针域指向“头结点指向的结点”，头结点的指针域指向“新结点”
尾插法创建单链表
void list_tail_insert(LinkList &L){ //改变L的值，使用引用&
// 1.申请头结点空间，头指针L指向头结点
L=(LNode*)malloc(sizeof(LNode));
L->next=NULL;
ElemType x;
scanf("%d",&x);
LNode *s,*r=L; //s：临时指针，指向每次新申请的结点；r：尾指针，始终指向链表最后一个结点（初始指向头结点）
// 2.循环创建结点并执行尾插操作
while (x!=9999){
// 2.1 为新结点申请堆内存，同时指向新结点
s=(LNode*)malloc(sizeof(LNode));
// 2.2 给新结点赋值
s->data=x;
r->next=s; //将新结点链接到尾结点的后面（尾结点的指针域指向新结点）
// 2.3 尾插核心
r=s; //更新尾指针：让r指向新的尾结点（即刚创建的s结点）
scanf("%d",&x); //继续读取下一个结点数据
}
r->next=NULL; //链表创建完成，将最后一个尾结点的next赋为NULL，标志链表结束
}重点：尾插法需要使用尾指针。核心是通过尾指针r减少遍历操作，避免每次找尾结点都遍历链表。每插入一个新结点，r就更新为这个新结点，始终保持指向链表最后一个结点。
单链表的查找
- 链表的第一个有效结点的位置是1，头结点（L指向的结点）的位置是0。
- 若遇到 “位置 0 是第一个有效结点” 的说法，大概率是不带头结点的链表 / 数组式计数。
- 返回的值是指针，类型是LinkList
按位置查找
LinkList GetElem(LinkList L,int SearchPos){
int i=0;
// 查找的位置小于0，属于无效位置，直接返回NULL
if(SearchPos<0){
return NULL;
}
// 循环遍历链表：
// 条件1（L）：当前结点不为NULL（未遍历到链表尾）
// 条件2（i<SearchPos）：未到达目标位置
while (L && i<SearchPos){
L=L->next;
i++;
}
// 循环结束后：
// 1. 若找到目标位置（i=SearchPos），L指向对应结点，返回L
// 2. 若遍历到链表尾仍未到目标位置（L=NULL），返回NULL
return L;
}按值查找
LinkList LocateElem(LinkList L,ElemType SearchVal){
// 循环遍历链表：条件L等价于L!=NULL，未遍历到链表尾则继续
while (L){
if(L->data==SearchVal){
return L;
}
L=L->next;
}
return NULL;
}单链表的插入
bool ListFrontInsert(LinkList L,int i,ElemType InsertVal){
// 找到第i-1个位置的结点（插入位置的前驱结点）
LinkList p= GetElem(L,i-1);
// 如果前驱结点不存在（i位置不合法），插入失败
if(p==NULL){
return false;
}
LinkList s=(LinkList) malloc(sizeof (LNode));
s->data=InsertVal;
// 新结点的后继指向原前驱结点的后继（先连后面，防止断链）
s->next=p->next;
// 前驱结点的后继指向新结点，完成插入
p->next=s;
return true;
}单链表的删除
删除元素（L是不会变的，不需要引用）
bool ListDelete(LinkList L,int i){
LinkList p= GetElem(L,i-1);
if(p==NULL){
return false;
}
LinkList q= p->next;
// 当链表有x个结点时，删除x+1个结点，出现这种异常情况时，避免程序崩溃
if(q==NULL){
return false;
}
p->next=q->next;
free(q);
return true;
}打印看看
打印函数
void print_list(LNode* L){
L=L->next; //跳过头结点，指向第一个有效结点
while (L!=NULL){
printf("%3d",L->data);
L=L->next; //指针后移，指向下一个结点
}
}头插法
LinkList L; //定义链表头指针(结构体类型指针)
list_head_insert(L);
print_list(L);
尾插法
LinkList L; //定义链表头指针(结构体类型指针)
list_tail_insert(L);
print_list(L);按位置查找（使用尾插法创建）
LinkList search;
search=GetElem(L,2);
if(search!=NULL){
printf("Succeeded in searching by GetElem\n");
printf("data:%d,netx:%p\n",search->data,search);
} else{
printf("netx:%p\n",search);
}按值查找（使用尾插法创建）
LinkList search;
search=LocateElem(L,12);
if(search!=NULL){
printf("Succeeded in searching by LocateElem\n");
printf("data:%d,netx:%p\n",search->data,search);
} else{
printf("netx:%p\n",search);
}链表的插入
LinkList L; //定义链表头指针(结构体类型指针)
list_tail_insert(L);
print_list(L);
bool ret;
ret=ListFrontInsert(L,3,99);
print_list(L);
printf("ret=%s",ret ? "true" : "false");LinkList L; //定义链表头指针(结构体类型指针)
list_tail_insert(L);
print_list(L);
ListDelete(L,4);
print_list(L);
return 0;运行看看
头插法
1 2 3 4 78 12 45 52 9999
52 45 12 78 4 3 2 1尾插法
1 2 3 4 78 12 45 52 9999
1 2 3 4 78 12 45 52按位置查找
Succeeded in searching by GetElem
data:2,netx:0000000000BD1490按值查找
Succeeded in searching by LocateElem
data:12,netx:0000000000BD1510链表的插入
1 2 3 4 78 12 45 52 9999
1 2 3 4 78 12 45 52
1 2 99 3 4 78 12 45 52
ret=true链表的删除
1 2 3 4 78 12 45 52 9999
1 2 3 4 78 12 45 52
1 2 3 78 12 45 52