链表知识总结
逻辑结构：线性结构（元素之间存在一对一关系）
存储结构（物理结构）：链式存储（存储顺序和逻辑顺序不在乎是否一致）1.链表的特点：擅长进行动态删除和增加操作，不擅长随机访问（需要遍历，因为链表不按顺序存放）
2.链表分类：单双向链表
单链表：元素节点有两部分组成（数据域-存储当前的元素、指针域-指向下一个节点地址）
双链表：元素节点有三部分组成（数据域-存储当前元素节点，2个指针域，1个用来指向上一个元素节点地址，1个用来指向下一个元素节点地址）带头不带头：是否带有头指针
循环不循环：尾结点的next指针指向空-不循环，指向首元素节点或头指针-循环3.链表的操作：创建、销毁、增（头插、尾插、中间插）删（头删、尾删、中间删）改查
由此得出：链表的分类的一共有8种 讲解单向、不带头、不循环链表
1、链表的介绍 链表是一种链式存储的线性表
1.1、链表的特点 节点定义成结构体类型
链表是一种基本的数据结构，它由一系列节点组成，每个节点包含一个值和指向下一个节点的指针
特点：1.不要求大片连续空间，改变容量方便。2.可以动态的添加和删除节点
缺点：不方便随机存取，要耗费一定空间存放指针。
2、链表的分类
链表可以分为三种类型：
- 单向链表：每个节点只有一个指针指向下一个节点，最后一个节点的指针指向NULL。
- 双向链表：每个节点有两个指针，分别指向上一个节点和下一个节点，可以在O(1)时间内实现向前和向后遍历。
- 循环链表：在单向或双向链表的基础上，将最后一个节点的指针指向头节点，形成一个环。
链表的种类其实有很多种，按照单双向、带头不带头、循环不循环，一共可以分为8种类型，但最常见就是单向链表（单向不带头不循环）和双向链表（双向带头）
带头：有一个指针，专门指向首元素节点
3、链表的操作
链表的操作包括插入、删除、查找、遍历等。
- 插入操作：可以在链表头或尾插入节点，也可以在指定位置插入节点。 头插、尾插、中间插
- 删除操作：可以删除指定节点或按照值删除节点。 头删、尾删、中间删
- 查找操作：可以查找指定节点或按照值查找节点。
- 遍历操作：可以遍历整个链表，输出每个节点的值或执行其他操作
4、单向链表
单向链表是由若干个节点组成的数据结构，每个节点包含两个部分：数据域和指针域。
数据域存储节点的数据，指针域存储下一个节点的地址。
单链表的一个存储节点包含两部分：
data部分称为数据域，用于存储线性表的一个数据元素； 放的是元素值也可以叫值域
link部分称为指针域，用于存放一个指针，该指针指示链表下一个结点的开始存储地址
指向下一个节点的指针
5、单链表的操作
5.1、main.c
#include <stdio.h>
#include "01.h"int main() {
fn3();
return 0;
}
5.2、01.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h> //包含有调试文件//定义单向、不带头、不循环链表的元素节点结构体类型
typedef int eleT;
typedef struct Link_Node {
eleT val;//数据域 存储节点元素值
struct Link_Node* next;//指针域 指向下一个节点
}LKNode;
void fn3(void);
void printf_menu(void);
LKNode* init_Link(eleT val);
void print_Link(LKNode* LinkNode);
void head_insert(LKNode** LinkNode, eleT val);
void tail_insert(LKNode* LinkNode, eleT val);
void head_delete(LKNode** LinkNode);
void tail_delete(LKNode** LinkNode);
LKNode* find_item(LKNode* LinkNode, eleT val);
void middle_delete(LKNode* LinkNode, eleT val);//中间删除1.0
void mid_del(LKNode* temp);//中间删除2.0
void mid_insert(LKNode* temp, eleT newval);
void destory(LKNode** LinkNode);
5.3、01.c
#include "01.h"
void fn3(void) {
int order = 0;//接收用户输入的命令
printf_menu();
LKNode* LinkNode = NULL; //存放头结点指针（地址）
eleT val = 0;
LKNode* temp = NULL;while (1) {
printf("请输入您的操作指令：");
scanf("%d", &order);
switch (order) {
case 1:
//初始化 初始化一个头结点，不包含头（头结点包含元素）
printf("请输入头结点元素值：");
scanf("%d", &val);
LinkNode=init_Link(val);
break;
case 2:
//遍历
print_Link(LinkNode);
break;
case 3:
//链表头插
printf("请输入要头插的元素");
scanf("%d", &val);
head_insert(&LinkNode,val);//头插，头结点要变，只能传地址
break;
case 4:
//链表尾插
printf("请输入要尾插的元素");
scanf("%d", &val);
tail_insert(LinkNode, val);//尾部插入，头结点不变，也可以传值
break;
case 5:
//链表头删
head_delete(&LinkNode);
break;
case 6:
//链表尾删
tail_delete(&LinkNode);
break;
case 7:
//链表的查找
//思路：找到了返回当前元素节点的指针 找不到返回NULL
printf("请输入要查找的元素");
scanf("%d", &val);
temp = find_item(LinkNode, val);
if (temp == NULL) {
printf("没有此元素");
}
else {
printf("找到的元素值为：%d\n", temp->val);
}
break;
case 8:
//链表的中间删（随机删），至少需要两个元素（要删除的目标元素以及它的前一个元素）/*
printf("请输入要删除的元素");
scanf("%d", &val);
middle_delete(LinkNode, val);
*/
printf("请输入要删除的前一个元素");
scanf("%d", &val);
temp = find_item(LinkNode, val);
if (temp == NULL) {
printf("没有此元素==》要删除的前一个\n");
}
else {
//删除查找的元素temp的后一个元素
mid_del(temp);
}
break;
case 9:
//链表的中间插
printf("请输入您要在哪个元素后面插入：");
scanf("%d", &val);
printf("请输入要中间插的新元素");
eleT newval = 0;
scanf("%d", &newval);
temp = find_item(LinkNode, val);
if (temp == NULL) {
printf("无法插入\n");
}
else {
//正常中间插
mid_insert(temp, newval);
}
break;
case 10:
//链表销毁
destory(&LinkNode);
break;
case 11:
return;
default:
printf("指令输入有误");
}
}
}//打印菜单
void printf_menu(void) {
system("cls");//系统函数 用于屏幕清空
printf("操作指令说明:\n");
printf("1:链表初始化\n2:打印链表\n");
printf("3:链表头插\n4:链表尾插\n");
printf("5:链表头删\n6:链表尾删\n");
printf("7:链表的查找\n8:链表的中间删\n");
printf("9:链表的中间插\n10:链表销毁\n");
printf("11:退出\n");
}//初始化头结点
LKNode* init_Link(eleT val) {
//申请节点内存
LKNode* newnode = (LKNode*)malloc(sizeof(LKNode));
//判断内存是否申请成功
/*
if (!newnode) {
printf("内存申请失败\n");
return NULL;
}
*/
assert(newnode);//如果为空，报错
newnode->val = val;
newnode->next = NULL;
printf("初始化成功\n");
return newnode;
}//遍历
void print_Link(LKNode* LinkNode) {
assert(LinkNode);//是否初始化
//正常遍历
//方法1
/*
LKNode* temp = LinkNode;
while (temp->next != NULL) {
printf("%d ", temp->val);//输出不是尾结点的元素
temp = temp->next;
}
printf("%d ", temp->val);//输出尾结点的元素值
}
*/
//方法2
LKNode* temp = LinkNode;
while (1) {
printf("%d ", temp->val);
if (temp->next == NULL) {//尾结点
break;
}
temp = temp->next;
}
printf("\n");
}
//头插
void head_insert(LKNode **LinkNode, eleT val) {
assert(*LinkNode);//是否初始化
//1.创建新节点
LKNode* newnode = (LKNode*)malloc(sizeof(LKNode));
assert(newnode);
//2.给新节点赋值
newnode->val = val;
newnode->next = *LinkNode;
//3.更新头结点
*LinkNode = newnode;//更新头结点
printf("头插成功\n");
}//补充调试代码常用的函数：
//exit() 用于终止程序执行，输出一些参数，一般用0表示正常退出，!0异常退出
//assert() 导入<assert.h>头文件 用于调试代码，条件为真，程序正常执行，条件为假，程序报错
//尾插
void tail_insert(LKNode* LinkNode, eleT val) {
assert(LinkNode);//判断是否初始化
//1.创建新节点
LKNode* newnode = (LKNode*)malloc(sizeof(LKNode));
assert(newnode);//内存申请成功
//2.给新节点成员赋值
newnode->val = val;
newnode->next = NULL;//3.将新节点放到链表的尾部，首先找到链表的尾结点
LKNode* temp = LinkNode;
while (1) {
if (temp->next == NULL) {
//4.说明找到尾结点,将新节点插到尾结点后面
temp->next = newnode;
break;
}
temp = temp->next;
}
printf("尾插成功！\n");
}
//头删
void head_delete(LKNode** LinkNode) {
assert(LinkNode);//判断是否初始化
LKNode* temp = (*LinkNode)->next;//保存当前头结点的后一个节点
free(*LinkNode);//释放原来的头结点
*LinkNode = temp;//更新头结点
printf("头删成功！\n");
}//尾删
void tail_delete(LKNode** LinkNode) {
assert(*LinkNode);//判断是否初始化//考虑只有一个结点时
if ((*LinkNode)->next == NULL) {
free(*LinkNode);//释放当前节点
*LinkNode = NULL;
}
else {
//找到链表的倒数第二个元素节点
LKNode* temp = *LinkNode;
while (1) {
if (temp->next->next == NULL) {
//4.说明找到倒数第二个节点
break;
}
temp = temp->next;
}
free(temp->next);//释放尾结点
temp->next = NULL;//更新尾结点
printf("尾删成功！\n");
}
}//查找
LKNode* find_item(LKNode* LinkNode, eleT val) {
assert(LinkNode);//判断是否初始化
LKNode* temp = LinkNode;
while (temp) {
if (temp->val == val) {
//找到了查找的元素
return temp;
}
temp = temp->next;
}
return NULL;
}//中间删1.0
void middle_delete(LKNode* LinkNode, eleT val) {
assert(LinkNode);//判断是否初始化
int flag = 0;//表示查找元素的状态
//查找到删除元素的前一个元素的地址
LKNode* temp = LinkNode;
while (temp) {
if (temp->next->val == val) {
flag = 1;
//找到了,删除temp->next
LKNode* ptr = temp->next;//保存要删除的节点
temp->next = temp->next->next;
free(ptr);//释放要删除的节点
printf("中间删成功！\n");
break;
}
temp=temp->next;
}
if(flag==0){
printf("没有找到要删除的元素\n");
}
}
//中间删2.0，至少需要两个元素（要删除的目标元素以及它的前一个元素）,才能实现中间的随机删除
void mid_del(LKNode* temp) {
//temp是要删除元素的前一个元素
LKNode* ptr = temp->next->next;//保存要删除元素的后一个元素
free(temp->next);//释放要删除的元素
temp->next = ptr;
printf("中间删成功！\n");
}//中间插
void mid_insert(LKNode* temp, eleT newval) {
LKNode* newnode =(LKNode*) malloc(sizeof(LKNode));
assert(newnode);
//给新节点赋值
newnode->val = newval;
//将新节点插入
newnode->next = temp->next;
temp->next = newnode;
printf("中间插入成功！\n");
}//销毁 遍历后一个一个删除
void destory(LKNode** LinkNode) {
assert(*LinkNode);//*LinkNode头结点
while (*LinkNode) {
LKNode* temp = (*LinkNode)->next;
free(*LinkNode);
*LinkNode = temp;
}
*LinkNode = NULL;//更新头结点
printf("销毁成功！\n");
}
