再封装的方式，用 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; //当前元素个数为0return 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 1printList(list);
打印链表
从第1个节点开始打印
void printList(LPLIST list) {LPNODE pmove = list->frontNode;while (pmove != NULL) //不为空打印数据{printf("%d ", pmove->data); pmove = pmove->next;}printf("
");}
尾插法
不需要找尾巴，因为记录了尾巴的位置
//插入的链表 插入的数据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 999printList(list);
指定位置插入
根据指定数据做插入，插在指定位置(数据)前面，不需要考虑表尾(尾插)
分改变表头、不改变表头两种情况：指定数据，数据可能插在表头前面(头节点的数据==指定数据)
前驱节点的 next 指针指向新节点，新节点的 next 指针指向当前节点
void push_appoin(LPLIST list, int posData, int data) {if (list == NULL || list->curSize == 0) //为空无法做插入{printf("无法插入链表为空!
");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("没有找到指定位置，无法插入！
");}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("链表为空，无法删除!
");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("链表为空，无法删除!
");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("链表为空，无法删除!
");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("未找到指定位置，无法删除!
");}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 999printList(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
总结
到此这篇关于C语言实现无头单链表详解的文章就介绍到这了,更多相关C语言无头单链表内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/weixin_60569662/article/details/122878134
