数据结构 --- c语言实现有头单链表

数组：查找效率极高插入删除效率很低
链表：查找效率极低插入删除效率很高

链式结构

链式结构可以理解为内存不连续的数组，通过计算机中的零散内存组合在一起

单链表的组成

数据域：用来存放用户使用的数据
指针域：用来存放下一个节点的地址

数据结构：具有相似结构的单一个体的组合

struct Node              //节点
{
 	int data;            //数据域
    struct Node* next;   //指针域:包含下一个节点的地址
};

如何表示链表

用线性结构的第一个节点去表示整个链表：由于可以通过第一个节点找到后面的节点

单链表的长相

一般情况下，单一节点的 next 指针赋值为空，单一节点是单独的结构体变量，单链表就是多个结构体变量连接在一起
3个独立的节点不能称为链表(链表是多个结构体变量)：把指针做修改，让它指向第2个节点的首地址 &Node2，做连接过程
一般情况下，最后一个节点赋值为NULL，遍历链表时以空作为结束的标记

有头链表和无头链表的区别

有头链表：多了一个头结点，头节点不会变(构建一个结构体变量，第一个节点的数据不做处理，也可以做处理：第一个节点的数据域用来存储链表中有多少个节点)
无头链表：头结点会改变(第一个节点有数据头插法可以改变表头)

链表的结构体描述

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>       //断言 判空处理
typedef int DataType;
typedef struct  Node
{
	DataType data;        //数据域
	struct Node* next;    //指针域
}NODE,*LPNODE;

创建表头

创建表头：用指针表示指针要变成一个变量做动态内存申请

//创建结构体变量
LPNODE  createHead() 
{                        
	LPNODE  headNode = (LPNODE)malloc(sizeof(NODE));
	assert(headNode);
	//headNode->data        数据不做初始化
	headNode->next = NULL;//指针域--->单一的节点通常置为空
	return headNode;      //返回新节点
}

创建节点

插入数据：需要把用户的数据先变成一个节点，只有相同结构的东西才能组合在一起

//和创建表头类似 多了数据的处理--->对新节点的数据做处理
LPNODE  createNode(int data) 
{
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
	assert(newNode);
	newNode->data = data; //data为传过来的数据
	newNode->next = NULL;
	return newNode;
}

头插法

参数：要插入的链表(用头节点表示一个链表) 要插入的数据
插入前需要创建节点，连接时先连后断

void push_front(LPNODE headNode, int data) 
{
	LPNODE newNode = createNode(data);			//插入前需要创建节点
	newNode->next = headNode->next;             //先连后断
	headNode->next = newNode;
}

    //测试代码
    LPNODE list = createHead();                 //创建链表
    //插入
	for (int i = 0; i < 3; i++) 
	{
		push_front(list, i);                    //0  / 1 0   /  2 1 0
	}
	printList(list);                            //2 1 0

打印链表

以 headNode 为头节点的链表，有头节点，从第2个节点 headNode->next 开始打印

void printList(LPNODE headNode) 
{
	LPNODE pmove = headNode->next;    //从第2个节点开始打印
	while (pmove != NULL) 
	{
		printf("%d\t", pmove->data);  //当前节点不为空 打印数据
		pmove = pmove->next;          //打印完当前节点 走到下一个节点的位置
	}
	printf("\n");
}

尾插法

参数：要插入的链表要插入的数据
要找表尾，定义一个节点 pMove 去做移动
从headNode开始找，如果 headNode 为空，直接插到 headNode->next，注意不要从第2个节点 headNode->next 开始找，因为第2个节点可能为空，会出现非法访问的情况 while( NULL->next != NULL)

void push_back(LPNODE  headNode, int data) 
{
	LPNODE pmove = headNode;	        
	while (pmove->next != NULL)         
	{
		pmove = pmove->next;            //一直往下走
	}
	LPNODE newNode = createNode(data);  //创建节点
	pmove->next = newNode;              //找到表尾后做插入
}
    //测试代码
    push_back(list,666);
    printlist(list);                    //2 1 0 666

指定位置插入

一般用数据作为指定节点 || 用第几个节点的方式去指定
可以选择在指定位置前 || 指定位置后插入
把问题转换为找到节点后做插入

void push_appoin(LPNODE headNode, int posData, int data)
{
	LPNODE preNode = headNode;
	LPNODE curNode = headNode->next;       //一前一后
	//先查找 当前节点数据!=指定数据 一直往下找 到curNode为空结束
	while (curNode != NULL && curNode->data != posData) //短路 前面不成立后面不判断
	{
		//preNode = preNode->next;         //前区节点和当前节点都往下走
		//curNode = curNode->next;
		preNode = curNode;                 //当前节点走到后一个节点的位置
		curNode = preNode->next;           //后一个节点走到原来位置的下一个
        //curNode = curNode->next;
	}
	//分析查找结果
	if (curNode == NULL)                   //未找到指定位置 无法做插入
	{
		printf("无法插入,没找到指定位置!\n");
	}
	else
	{
		LPNODE newNode = createNode(data); //不需要急着创建节点 没找到没必要创建
		preNode->next = newNode;           //连接
		newNode->next = curNode;
	}
}
    //测试代码
    push_appoin(list, 2, 999);             //999 2 1 0 666
	printList(list);

头删法

只能删除第2个节点，不能删除第1个节点，因为是有头链表
frontNode (第一个带数据的节点)--->要删除的节点
连接后释放 || 删除

void pop_front(LPNODE headNode)
{
	LPNODE frontNode = headNode->next;    //要删除的节点
	if (frontNode == NULL) 
	{
		printf("无法删除，链表为空!\n");   //为空无法做删除 一定要有一个节点
	}
	else 
	{
		headNode->next = frontNode->next; //头节点的下一个指向第一个节点的下一个
		free(frontNode);                  //释放后置空即可
		frontNode = NULL;
	}
}
    //测试代码
	pop_front(list);
	printList(list);                      //2 1 0 666

尾删法(和指定位置插入代码类似)

把最后一个节点删除了，注意要处理它的上一个节点的 next 指针
把 node3 删掉，要把 node2 的 next 指针置为空，不能让 node2 指向被释放的内存(要对指针做一下初始化)

void pop_back(LPNODE headNode)
{
	LPNODE preNode = headNode;         //前区节点
	LPNODE backNode = headNode->next;  //表尾节点
	while (backNode != NULL && backNode->next != NULL) //当前节点的next指针!=NULL
	{
		preNode = backNode;            //记录位置
		backNode = preNode->next;      //往下走
	}
	//分析查找结果
	if (backNode == NULL) 
	{
		printf("链表为空，无法删除!\n");
	}
	else 
	{
		free(backNode);                //释放最后一个节点
		backNode = NULL;
		preNode->next = NULL;          //把上一个节点的next指针置为空
	}
}
    //测试代码
    pop_back(list);
	printList(list);                    //2 1 0

指定位置删除

以数据作为指定

void pop_appoin(LPNODE headNode, int posData) 
{
	LPNODE preNode = headNode;
	LPNODE curNode = headNode->next;
	//先查找
	while (curNode != NULL && curNode->data != posData)
	{
		//preNode = preNode->next;
		//curNode = curNode->next;
		preNode = curNode;
		curNode = preNode->next;
	}
    //分析查找结果
	if (curNode == NULL) 
	{
		printf("未找到，无法删除!");
	}
	else 
	{
		preNode->next = curNode->next;    //把前面那个节点的指针指向当前节点的下一个
		free(curNode);                    //释放当前节点后置空
		curNode = NULL;        
	}
}
    //测试代码
    pop_appoin(list, 2);
	printList(list);                      //1 0

销毁链表

需要传二级指针：干掉所有的内存
删除的方式：定义一个移动的指针指向第一个节点，把下面的保存起来再做删除过程，从第1个节点删除到最后一个节点，删到空就结束

void destoryList(LPNODE* headNode)         //传二级指针
{
	LPNODE nextNode = NULL;
	while (*headNode != NULL)              //不为空 把下一个节点保存起来持续做删除
	{
		nextNode = (*headNode)->next;      //记录当前移动节点的下一个节点
		free(*headNode);                   //释放表头后把表头置为下一个节点
		*headNode = nextNode;              
	}
}
    //测试代码
    destoryList(&list);
	if (list == NULL)                      //判断是否为空
	{
		printf("删除成功！\n");
	}

查找链表

参数：要找的链表要找的位置
返回空：没找到返回不是空的节点：找到了

LPNODE searchNode(LPNODE headNode, int posData) 
{
	LPNODE pmove = headNode;                        //从第 2 个节点开始找
	while (pmove != NULL && pmove->data != posData)
	{
		pmove = pmove->next;                        //往下走
	}
	return pmove;
}

原文链接：https://blog.csdn.net/weixin_60569662/article/details/122836195