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; //当前元素个数为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\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 999printList(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 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语言无头单链表内容请搜索编程宝库以前的文章，希望以后支持编程宝库！
关于C语言的编译与链接不懂的可以看一下下面的文章，先回顾一下以前的知识。详解C语言的编译与链接 1 函数重载的概念函数重载:是函数的一种特殊情况，C++允许在同一作用域中声明几个功能类似的同名函数，这 ...