6.在pos结点位置删除数据（删除pos结点）
如图所示：
代码如下：
//在pos位子删除数据 void ListErase(List** ps, List* pos) { assert(ps); assert(pos); if (*ps == pos) { ListPopFront(ps); } else { List* next = *ps; while (next->next != pos) { next = next->next; } //这个时候next->next == pos next->next = next->next->next; /*free(next->next);*/ free(pos); pos = NULL; } }
7.删除pos位置之后一个结点
如图所示：
代码如下：
//在pos位置之后一位删除数据 void ListEraseAfter(List* pos) { assert(pos); List* next = pos->next;//将pos 的下一个结点赋值给next if (next != NULL) { pos->next = pos->next->next;//表示pos的下一个的下一个结点的地址赋值给pos的指针域 实质上是将pos的下一个结点给跳过 free(next); //将pos的下一个结点给free释放 next = NULL; //next指向为NULL 防止野指针 } }
8.摧毁链表
代码如下：
//链表的摧毁 直接将头指针指针域指向NULL void ListDestory(List** ps) { //assert(ps); //防止空链表 一个结点一个结点释放 //List* next = *ps; //while (next) { // List* cur = next->next; // free(next); // next = cur; //} *ps = NULL; }
因为是二级指针，所以直接 *ps=NULL 即可，或者一个一个free
三、完整代码
1.LinkList.h
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<assert.h> typedef int SLDataType; //单向链表的实现、 typedef struct ListNode { SLDataType data;//数据域 struct ListNode* next;//指针域 }List; //打印单链表 void ListPrint(List* ps); //单链表的尾插 void ListPushBack(List** ps, SLDataType data); //单链表的头插 void ListPushFront(List** ps, SLDataType data); //单链表的尾删 void ListPopBack(List** ps); //单链表的头删 void ListPopFront(List** ps); //单链表的查找 List* ListFind(List* ps); //在pos位置上插入数据 void ListInsertBefore(List** ps, SLDataType x, List* pos); //在pos位置之后插入数据 void ListInsertAfter(List** ps, SLDataType x, List* pos); //在pos位子删除数据 void ListErase(List** ps, List* pos); //在pos位置之后一位删除数据 void ListEraseAfter(List* pos); //单链表的摧毁 void ListDestory(List** ps);
2.LinkList.c
#define _CRT_SECURE_NO_WARNINGS #include"单向链表.h" //链表的使用，在插入上面 // 如果是尾部插入，如果是空链表直接将新节点给ps 是先找到链表尾部，然后创建新节点，连接即可 // 如果是头部插入，先进行断言判空，之后创建新节点，将新节点的数据 // new->next=ps 这个是找到对应的位置，连接起来 // ps=new; 将新节点的信息传递给ps，这样ps还是头节点 // // // // // //进行单链表的实现 //初始化链表 void InitList(List* ps) { ps->data = 0; ps->next = NULL; } //打印单链表 void ListPrint(List* ps) { List* cur = ps; while ((cur) != NULL) { printf("%d -> ", cur->data); cur = cur->next; } printf("NULL\n"); } //创建一个新节点 List* CreateNode(SLDataType x) { List* newNode = (List*)malloc(sizeof(List)); if (newNode == NULL) { perror("malloc fail\n"); exit(-1); } else { newNode->data = x; newNode->next = NULL; } return newNode; } //单链表的尾插 void ListPushBack(List** ps, SLDataType data) { //创建新的节点 assert(ps);//断言 List* newNode = CreateNode(data); if (*ps == NULL) { //说明是空链表 *ps = newNode; } else { List* tail = *ps; while (tail->next != NULL) { tail = tail->next; } tail->next = newNode; } } //单链表的头插 void ListPushFront(List** ps, SLDataType data) { //先断言是否为空 assert(ps); //将新地址指向头结点下一个next结点的地址，然后在用头结点指向新节点 List* newNode = CreateNode(data); newNode->next = (*ps); //new指向ps当前的位置，然后new是第一个位置了，将new赋值给ps，这样new就作为头部连接链表了 (*ps) = newNode;//原本ps位置的数值不变，这样的话就成 new->next=ps,new数值在前，ps的数值在后 } //单链表的尾删 void ListPopBack(List** ps) { assert(ps);//断言 //三种情况 //1.空链表 //2.一个节点 //3.多个节点 if (*ps == NULL) { return; } //只有一个节点的情况为 else if ((*ps)->next == NULL) { free(*ps); //如果只有一个头节点的话 *ps = NULL; } else { //多个节点的情况下、 List* tail = *ps; while (tail->next->next!= NULL) { tail = tail->next; } free(tail->next); tail->next= NULL; } } //单链表的头删 void ListPopFront(List** ps) { assert(ps); //1.空 //2.非空 if (*ps == NULL) { //为空 return; } else { List* tail = (*ps)->next;//创建临时变量tail，将头节点之后的地址给tail free(*ps);//滞空头节点 *ps = NULL;//可有可不有，接下来也要用 *ps = tail;//将tail也就是ps的下一个List节点给ps } } //单链表的查找 List* ListFind(List* ps,SLDataType data) { //进行查找就是进行判断是否为空链表，为空直接返回 if (ps == NULL) { printf("链表为空、无法查找\n"); return; } List* tail = ps; while (tail != NULL) {//从头节点开始，进行循环， if (tail->data == data) { return tail; } tail = tail->next; } return tail; } //在pos位置上插入数据 void ListInsertBefore(List** ps, SLDataType x, List* pos) { //先判断是否为空 assert(ps); assert(pos); //空链表排除 //1.pos是第一个节点 //2.pos不是第一个节点 if (*ps == pos) { //是第一个节点，那就直接头插 ListPushFront(ps, x); } else { List* prev = *ps; while (prev->next != pos) { prev = prev->next; } List* newnode = CreateNode(x); prev->next = newnode; newnode->next = pos; } } //在pos位置之后插入数据 void ListInsertAfter(List** ps, SLDataType x, List* pos) { assert(ps); //assert(pos);//断言 List* newnode = CreateNode(x); newnode->next = pos->next; pos->next = newnode; } //在pos位子删除数据 void ListErase(List** ps, List* pos) { assert(ps); assert(pos); if (*ps == pos) { ListPopFront(ps); } else { List* next = *ps; while (next->next != pos) { next = next->next; } //这个时候next->next == pos next->next = next->next->next; /*free(next->next);*/ free(pos); pos = NULL; } } //在pos位置之后一位删除数据 void ListEraseAfter(List* pos) { assert(pos); List* next = pos->next;//将pos 的下一个结点赋值给next if (next != NULL) { pos->next = pos->next->next;//表示pos的下一个的下一个结点的地址赋值给pos的指针域 实质上是将pos的下一个结点给跳过 free(next); //将pos的下一个结点给free释放 next = NULL; //next指向为NULL 防止野指针 } } //链表的摧毁 直接将头指针指针域指向NULL void ListDestory(List** ps) { //assert(ps); //防止空链表 一个结点一个结点释放 //List* next = *ps; //while (next) { // List* cur = next->next; // free(next); // next = cur; //} *ps = NULL; }
3.test.c
#define _CRT_SECURE_NO_WARNINGS #include"单向链表.h" void test() { List* phead=NULL;//作为头节点 //单链表的尾插 ListPushBack(&phead, 1); ListPushBack(&phead, 2); ListPushBack(&phead, 3); ListPushBack(&phead, 4); ListPushBack(&phead, 5); ListPrint(phead); ListPushFront(&phead, 1); ListPrint(phead); ListPopBack(&phead); ListPrint(phead); ListPopFront(&phead); ListPrint(phead); ListErase(&phead, phead->next); ListInsertAfter(&phead, 10, phead->next); ListEraseAfter(phead->next); ListPrint(phead); ListDestory(&phead); } int main() { test(); return 0; }
总结
本文主要讲解了链表的分类是什么，两种常用的类型，无头单向非循环链表、有头双向循环链表，我们实现了无头单向非循环链表，这是比较简单的一种链表的实现，我们使用的是二级指针传参，当然使用一级指针传参也可以，主要实现函数为头尾插入，头尾删除，pos指定结点位置前后添加或者删除元素。
接下来，下文我们将跟大家介绍一下最常用链表的另一种形式，带头双向循环链表。
