C语言实现无头单链表详解
时间：2022-08-16 12:38:13 | 栏目：C代码 | 点击：次
再封装的方式，用 c++ 的思想做无头链表
链表的结构体描述(节点)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
//节点
typedef struct Node
{
DataType data;
struct Node* next;
}NODE,*LPNODE;
再定义一个结构体(链表)
通过记录头节点和尾节点的方式去描述链表
typedef struct list
{
LPNODE frontNode; //头节点
LPNODE backNode; //尾节点
int curSize; //当前节点个数
}LIST,*LPLIST;
断言处理 & 判空处理
如果 list 为空，会引发中断(申请内存可能失败)
防御性编程，如果申请内存失败，操作无效，NULL 里面没有 frontNode，backNode，curSize，存在安全隐患C6011：取消对 NULL 指针"list"的引用
如果申请内存失败，assert()直接让程序直接中断，并且告诉你程序断在哪一行
#include<assert> //断言处理宏
#define assert(expression) (void)( \
(!!(expression)) || \
(_wassert(_CRT_WIDE(#expression), _CRT_WIDE(__FILE__), (unsigned)(__LINE__)), 0) \
)
LPLIST createList()
{
LPLIST list = (LPLIST)malloc(sizeof(LIST));
list = NULL; //list为空 引发中断
assert(list);
//if(list == NULL)
//return NULL; //可以替换
list->frontNode = NULL;
list->backNode = NULL;
list->curSize = 0;
return list;
}
//abort() has been called line 25
创建链表
描述链表最初的状态
LPLIST createList()
{
LPLIST list = (LPLIST)malloc(sizeof(LIST)); //用结构体变量去描述 做动态内存申请
assert(list);
list->frontNode = NULL; //链表刚开始是空的 头尾节点指向空
list->backNode = NULL;
list->curSize = 0; //当前元素个数为0
return list;
}
创建节点
LPNODE createNode(int data)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
assert(newNode);
//初始化数据
newNode->data = data;
newNode->next = NULL;
return newNode;
}
头插法
插入一个节点，节点插在原表头前面，表头会改变，在1(表头)前面插入666(数据)
把新节点的 next 指针指向原来的表头
把原来表头指针从原来的位置挪到新节点的位置
//插入的链表 插入的数据
void push_front(LPLIST list,int data)
{
LPNODE newNode = createNode(data); //创建新节点
newNode->next = list->frontNode;
list->frontNode = newNode;
//护头也要护尾
if (list->curSize == 0) //只有一个节点 链表为空尾节点也是指向新节点
list->backNode = newNode; //把尾节点置为新节点
list->curSize++;
}
//测试代码
LPLIST list = createList();
push_front(list, 1);
push_front(list, 2); //2 1
printList(list);
打印链表
从第1个节点开始打印
void printList(LPLIST list)
{
LPNODE pmove = list->frontNode;
while (pmove != NULL) //不为空打印数据
{
printf("%d\t", pmove->data);
pmove = pmove->next;
}
printf("\n");
}
尾插法
不需要找尾巴，因为记录了尾巴的位置
//插入的链表 插入的数据
void push_back(LPLIST list, int data)
{
LPNODE newNode = createNode(data); //创建新节点
if (list->curSize == 0)
{
list->frontNode = newNode; //只有1个节点的情况 表头也是指向新节点
//list->backNode = newNode; //表尾指向新节点
}
else
{
list->backNode->next = newNode; //把原来链表的尾节点的next指针置为新节点
//list->backNode = newNode; //原来的表尾挪到新节点的位置
}
list->backNode = newNode; //相同代码
list->curSize++;
}
//测试代码
push_back(list, 666);
push_back(list, 999); //2 1 666 999
printList(list);
指定位置插入
根据指定数据做插入，插在指定位置(数据)前面，不需要考虑表尾(尾插)
分改变表头、不改变表头两种情况：指定数据，数据可能插在表头前面(头节点的数据==指定数据)
前驱节点的 next 指针指向新节点，新节点的 next 指针指向当前节点
void push_appoin(LPLIST list, int posData, int data)
{
if (list == NULL || list->curSize == 0) //为空无法做插入
{
printf("无法插入链表为空!\n");
return;
}
//其他情况可以插入
if (list->frontNode->data == posData) //头节点的数据==指定数据
{
push_front(list, data); //会改变表头 用头插法插入
return;
}
//正常插入的情况
LPNODE preNode = list->frontNode; //定义一个前驱节点指向第1个节点
LPNODE curNode = list->frontNode->next; //定义一个当前节点指向第1个节点的下一个节点
//当前节点!=NULL && 当前节点的数据!=指定数据
while (curNode != NULL && curNode->data != posData) //并排往下走
{
preNode = curNode; //前1个节点走到当前节点的位置
curNode = preNode->next; //当前节点走到原来位置的下一个
}
//分析查找结果做插入
if (curNode == NULL) //没找到无法做插入
{
printf("没有找到指定位置，无法插入！\n");
}
else
{
LPNODE newNode = createNode(data); //创建新节点
preNode->next = newNode; //连接
newNode->next = curNode;
list->curSize++;
}
}
//测试代码
push_appoin(list, 666, 888);
printList(list); //2 1 888 666 999
头删法
只有一个节点的情况：表尾也要改变(表尾指向了一段删除的内存)，表尾也要置为空
void pop_front(LPLIST list)
{
if (list == NULL || list->curSize == 0) //判空处理
{
printf("链表为空，无法删除!\n");
return;
}
LPNODE nextNode = list->frontNode->next; //头节点的下一个--->第2个节点
free(list->frontNode); //直接删除表头
list->frontNode = nextNode; //把原来的表头节点置为下一个节点
if (list->curSize == 1) //只有1个节点的情况
{
list->backNode = NULL; //表尾也要置为空
}
list->curSize--;
}
//测试代码
pop_front(list);
pop_front(list);
pop_front(list);
pop_front(list);
printList(list); //999
尾删法
要找到表尾的上一个节点
//要删除的链表
void pop_back(LPLIST list)
{
if (list == NULL || list->curSize == 0)
{
printf("链表为空，无法删除!\n");
return;
}
//从第1个节点开始找 做移动
LPNODE preNode = list->frontNode; //头节点
LPNODE backNode = list->frontNode; //头节点的下一个
while (backNode->next != NULL)
{
preNode = backNode; //并排往下走
backNode = preNode->next;
}
free(backNode);
if (list->curSize == 1) //只有一个节点的情况
{
backNode = NULL; //释放后置空
list->frontNode = NULL; //表头也要置为空
list->backNode = NULL; //表尾置为空
list->curSize--;
}
else
{
backNode = NULL;
preNode->next = NULL;
list->backNode = preNode;
list->curSize--;
}
}
//测试代码
pop_back(list);
printList(list);
指定位置删除
void pop_appoin(LPLIST list,int posData)
{
if (list == NULL || list->curSize == 0)
{
printf("链表为空，无法删除!\n");
return;
}
if (list->frontNode->data == posData) //头节点的数据==指定数据
{
pop_front(list); //头删法
return;
}
if (list->backNode->data == posData) //尾节点的数据==指定数据
{
pop_back(list); //尾删法
return;
}
//中间的某个情况
LPNODE preNode = list->frontNode; //原来的头部
LPNODE curNode = list->frontNode->next;
while (curNode != NULL && curNode->data != posData)
{
preNode = curNode; //并排往下走
curNode = preNode->next;
}
if (curNode == NULL)
{
printf("未找到指定位置，无法删除!\n");
}
else
{
preNode->next = curNode->next; //先连后断
free(curNode);
curNode = NULL;
list->curSize--;
}
}
//测试代码
pop_appoin(list, 2);
pop_appoin(list, 999);
pop_appoin(list, 888); //2 1 888 666 999
printList(list); //1 666
查找链表
//要查找的链表 要查找的数据
LPNODE searchlist(LPLIST list, int posData)
{
if (list == NULL) //list为空 返回NULL无法做删除
return NULL;
LPNODE pmove = list->frontNode; //定义一个移动的节点
while (pmove != NULL && pmove->data != posData)
{
pmove = pmove->next; //数据!=指定数据一直往下走
}
return pmove; //退出循环直接返回
}
删除所有指定相同的元素
void pop_all(LPLIST list, int posData)
{
while (searchlist(list, posData) != NULL) //!=NULL说明里面有指定数据
{
pop_appoin(list, posData); //持续做删除
}
}
//测试代码
LPLIST test = createList();
push_back(test, 1);
push_back(test, 1);
push_back(test, 1);
push_back(test, 2);
pop_all(test, 1);
printList(test); //2