本节复习链表的增删查改
首先, 链表不是连续的, 而是通过指针联系起来的。 如图:
这四个节点不是连续的内存空间, 但是彼此之间使用了一个指针来连接。 这就是链表。
现在我们来实现链表的增删查改。
目录
单链表的全部接口:
准备文件
建立结构体蓝图
申请链表节点函数接口
单链表的打印函数接口
单链表尾插函数接口
单链表头插函数接口
单链表尾删函数接口
单链表的头删函数接口
单链表查找函数接口
单链表pos位置之后插入数据接口
单链表删除pos之后位置的数据
单链表在pos位置之前插入数据接口
单链表删除pos位置数据接口
单链表的销毁
单链表的全部接口:
//申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删函数接口
void SListPopBack(SLNode** pphead);
//单链表的头删函数接口
void SListPopFront(SLNode** pphead);
//单链表查找函数接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//单链表在pos位置之后插入数据接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//单链表在pos之后的位置删除数据
void SListPopAfter(SLNode* pos);
//单链表在pos位置之前插入数据接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//单链表在pos位置删除数据接口
void SListPop(SLNode** pphead, SLNode* pos);
//单链表的销毁函数接口
void SLTDestory(SLNode** pphead);
---------------------------------------------------------------------------------------------------------------------------------
准备文件
首先准备好三个文件夹, 一个main.c文件夹, 一个.h文件夹用来声明链表的接口以及定义结构体等。 一个.c文件夹用来实现单链表。
---------------------------------------------------------------------------------------------------------------------------------
建立结构体蓝图
首先包含一下头文件, 定义一下数据类型。
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;
接着再建立一个链表的结构体
#include<stdio.h> #include<assert.h> #include<stdlib.h>typedef int SLTDataType;typedef struct SListNode {struct SListNode* next;SLTDataType data; }SLNode;
---------------------------------------------------------------------------------------------------------------------------------
申请链表节点函数接口
申请链表的节点操作, 在尾插, 头插, 或者特定位置插入的时候都需要, 所以可以封装成一个函数。 后续直接进行复用就可以。
.h函数声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode //创建结构体
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
.c函数实现
单链表函数实现函数接口//单链表申请节点函数接口
SLNode* BuySListNode(SLTDataType x)
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申请节点失败\n");return;}//NewNode->data = x;NewNode->next = NULL;
}
在实现的过程中,可以将数据直接储存到新节点中。 然后让新节点指向NULL, 然后返回该节点。 然后将链表直接连接到这个节点就可以。
---------------------------------------------------------------------------------------------------------------------------------
单链表的打印函数接口
为了便于后续的函数接口的调试, 我们先实现单链表的打印操作。
.h函数声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
.c函数实现
单链表函数实现函数接口//单链表申请节点函数接口
SLNode* BuySListNode(SLTDataType x)
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申请节点失败\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//单链表的节点打印操作
void SListPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一个NULL{printf("NULL");}}
---------------------------------------------------------------------------------------------------------------------------------
单链表尾插函数接口
.h函数声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
.c函数实现
单链表函数实现函数接口//单链表申请节点函数接口
SLNode* BuySListNode(SLTDataType x)
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申请节点失败\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//单链表的节点打印操作
void SListPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一个NULL{printf("NULL");}}//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点SLNode* cur = *pphead; //让cur指向phead所指向空间if (cur == NULL) //cur == NULL代表着phead指向NULL, 这时候让phead改变指向。传送phead指针的原因就是{ //要改变phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //让cur遍历到最后一个节点{cur = cur->next;}cur->next = newnode;//最后}}
尾插接口时传送phead的指针的原因是因为phead可能改变指向,从空指针变为指向一个节点。要改变phead的指向那就是意味着形参要相对于phead传址调用, 而phead本身就是一个一级指针, phead取地址就是一个二级指针, 所以形参是二级指针。
---------------------------------------------------------------------------------------------------------------------------------
单链表头插函数接口
.h函数接口
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
.c函数实现
单链表函数实现函数接口//单链表申请节点函数接口
SLNode* BuySListNode(SLTDataType x)
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申请节点失败\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//单链表的节点打印操作
void SListPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一个NULL{printf("NULL");}}//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点SLNode* cur = *pphead; //让cur指向phead所指向空间if (cur == NULL) //cur == NULL代表着phead指向NULL, 这时候让phead改变指向。传送phead指针的原因就是{ //要改变phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //让cur遍历到最后一个节点{cur = cur->next;}cur->next = newnode;//最后}}//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//SLNode* cur = *pphead;newnode->next = cur;*pphead = newnode;}
现在我们来利用打印接口调试一下我们写的是否存在问题。
在main.c中输入如下代码
void TestSListNode()
{SLNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPushBack(&phead, 5);SListPushFront(&phead, 0);SListPrint(phead);printf("\n");/*SListPopFront(&phead);SListPopFront(&phead);SListPopFront(&phead);SListPopBack(&phead);SListPrint(phead);printf("\n");SLTDestory(&phead);SListPrint(phead);printf("\n");*/}int main()
{
// TestTree();
// TestStack();
// TestQueue();
// TestSeqList();TestSListNode();
// TestDSLNode();
// TestOJ();return 0;
}
运行图如下:
通过检验,没有问题。 继续往下走。
---------------------------------------------------------------------------------------------------------------------------------
单链表尾删函数接口
.h文件声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删函数接口
void SListPopBack(SLNode** pphead);
.c函数实现
首先pphead不能为空, 如果phead指向空的话就直接返回。 然后定义cur和prev两个指针, 遍历寻找尾节点。 cur领先prev一个节点, cur指向尾节点的时候, 就释放掉这个节点。 然后prev指向空节点。 寻找尾节点的过程是这样的:
代码实现
单链表函数实现函数接口//单链表申请节点函数接口
SLNode* BuySListNode(SLTDataType x)
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申请节点失败\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//单链表的节点打印操作
void SListPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一个NULL{printf("NULL");}}//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点SLNode* cur = *pphead; //让cur指向phead所指向空间if (cur == NULL) //cur == NULL代表着phead指向NULL, 这时候让phead改变指向。传送phead指针的原因就是{ //要改变phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //让cur遍历到最后一个节点{cur = cur->next;}cur->next = newnode;//最后}}//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//SLNode* cur = *pphead;newnode->next = cur;*pphead = newnode;}//单链表尾删函数接口
void SListPopBack(SLNode** pphead)
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;SLNode* prev = *pphead;while (cur->next != NULL) //对链表进行遍历。 cur最终会指向尾节点。 prev用来维护链表{prev = cur;cur = cur->next;}if (prev == cur) {free(cur);*pphead = NULL;}else {free(cur);prev = NULL;}}
---------------------------------------------------------------------------------------------------------------------------------
单链表的头删函数接口
.h函数声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删函数接口
void SListPopBack(SLNode** pphead);
//单链表的头删函数接口
void SListPopFront(SLNode** pphead);
.c函数实现
单链表函数实现函数接口//单链表申请节点函数接口
SLNode* BuySListNode(SLTDataType x)
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申请节点失败\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//单链表的节点打印操作
void SListPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一个NULL{printf("NULL");}}//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点SLNode* cur = *pphead; //让cur指向phead所指向空间if (cur == NULL) //cur == NULL代表着phead指向NULL, 这时候让phead改变指向。传送phead指针的原因就是{ //要改变phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //让cur遍历到最后一个节点{cur = cur->next;}cur->next = newnode;//最后}}//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//SLNode* cur = *pphead;newnode->next = cur;*pphead = newnode;}//单链表尾删函数接口
void SListPopBack(SLNode** pphead)
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;SLNode* prev = *pphead;while (cur->next != NULL) //对链表进行遍历。 cur最终会指向尾节点。 prev用来维护链表{prev = cur;cur = cur->next;}if (prev == cur) {free(cur);*pphead = NULL;}else {free(cur);prev = NULL;}}//单链表的头删函数接口
void SListPopFront(SLNode** pphead)
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;*pphead = cur->next;free(cur);
}
代码的意思是, 首先pphead不能为空, 然后phead不能指向空。 然后让一个cur指针指向头节点。 然后修改phead的指向, 使其指向第二个节点(当第二个节点是空的时候, 就是指向空)。然后释放cur指向的节点也就是头节点。 如图为过程:
---------------------------------------------------------------------------------------------------------------------------------
单链表查找函数接口
.h接口声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删函数接口
void SListPopBack(SLNode** pphead);
//单链表的头删函数接口
void SListPopFront(SLNode** pphead);
//单链表查找函数接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
.c接口实现
单链表函数实现函数接口//单链表申请节点函数接口
SLNode* BuySListNode(SLTDataType x)
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申请节点失败\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//单链表的节点打印操作
void SListPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一个NULL{printf("NULL");}}//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点SLNode* cur = *pphead; //让cur指向phead所指向空间if (cur == NULL) //cur == NULL代表着phead指向NULL, 这时候让phead改变指向。传送phead指针的原因就是{ //要改变phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //让cur遍历到最后一个节点{cur = cur->next;}cur->next = newnode;//最后}}//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//SLNode* cur = *pphead;newnode->next = cur;*pphead = newnode;}//单链表尾删函数接口
void SListPopBack(SLNode** pphead)
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;SLNode* prev = *pphead;while (cur->next != NULL) //对链表进行遍历。 cur最终会指向尾节点。 prev用来维护链表{prev = cur;cur = cur->next;}if (prev == cur) {free(cur);*pphead = NULL;}else {free(cur);prev = NULL;}}//单链表的头删函数接口
void SListPopFront(SLNode** pphead)
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;*pphead = cur->next;free(cur);
}//单链表查找函数接口
SLNode* SListFind(SLNode* phead, SLTDataType x)
{SLNode* cur = phead;//定义一个指向头节点的指针, 用于遍历while (cur != NULL) //向后遍历{if (cur->data == x) //找到节点后就返回节点的地址。{return cur;}cur = cur->next;}return NULL;
}
代码太长, 之后.c文件的代码只展示相应接口的代码
---------------------------------------------------------------------------------------------------------------------------------
单链表pos位置之后插入数据接口
.h接口声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删函数接口
void SListPopBack(SLNode** pphead);
//单链表的头删函数接口
void SListPopFront(SLNode** pphead);
//单链表查找函数接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//单链表在pos位置之后插入数据接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
.c接口实现
//单链表在pos位置之后插入数据接口
void SListInsertAfter(SLNode* pos, SLTDataType x)
{assert(pos);SLNode* newnode = BuySListNode(x);//SLNode* cur = pos->next;newnode->next = cur;pos->next = newnode;
}
该接口的实现过程如下:
令指针cur指向pos的下一个节点, newnode的next指向cur, pos的next指向newnode
---------------------------------------------------------------------------------------------------------------------------------
单链表删除pos之后位置的数据
.h接口声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删函数接口
void SListPopBack(SLNode** pphead);
//单链表的头删函数接口
void SListPopFront(SLNode** pphead);
//单链表查找函数接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//单链表在pos位置之后插入数据接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//单链表在pos之后的位置删除数据
void SListPopAfter(SLNode* pos);
.c接口实现
//单链表在pos之后的位置删除数据
void SListPopAfter(SLNode* pos)
{assert(pos);//SLNode* cur = pos->next;pos->next = pos->next->next;free(cur);
}
该接口实现和单链表在pos位置之后插入数据接口实现方式类似, 都是利用一个cur指针指向pos之后的位置作为记忆保存,然后进行插入或者删除操作。
---------------------------------------------------------------------------------------------------------------------------------
单链表在pos位置之前插入数据接口
该接口的实现有点复杂, 但是实现该接口之后, 对于尾插还有头插就很好实现了, 尾插和头插是该接口的两个特殊情况。 假如pos是头节点,就是头插, 假如pos是尾节点, 就是尾插。
.h接口声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删函数接口
void SListPopBack(SLNode** pphead);
//单链表的头删函数接口
void SListPopFront(SLNode** pphead);
//单链表查找函数接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//单链表在pos位置之后插入数据接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//单链表在pos之后的位置删除数据
void SListPopAfter(SLNode* pos);
//单链表在pos位置之前插入数据接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
.c接口实现
//单链表在pos位置之前插入数据接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{assert(pphead);//SLNode* newnode = BuySListNode(x);//if (*pphead == NULL) {*pphead = newnode;return;}//if (*pphead == pos) {newnode->next = pos;*pphead = newnode;return;}SLNode* cur = *pphead;while (cur != NULL && cur->next != pos) {cur = cur->next;}newnode->next = pos;cur->next = newnode;
}
该接口分为三种情况:
第一种是链表为空, 这个时候直接插入节点。
第二种情况是pos的位置在第一个节点的位置, 这个时候需要改变phead的指向。
第三种情况就是最普通的情况, 在除头节点, 链表的任意节点前插入。如图:
---------------------------------------------------------------------------------------------------------------------------------
单链表删除pos位置数据接口
和pos位置插入数据接口一样, 实现了该接口对于尾删, 头删接口就很简单了。 头删, 尾删都是单链表删除pos位置数据接口的特殊情况。 pos是头节点, 就是头删, pos是尾节点。 就是尾删。
.h接口声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删函数接口
void SListPopBack(SLNode** pphead);
//单链表的头删函数接口
void SListPopFront(SLNode** pphead);
//单链表查找函数接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//单链表在pos位置之后插入数据接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//单链表在pos之后的位置删除数据
void SListPopAfter(SLNode* pos);
//单链表在pos位置之前插入数据接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//单链表在pos位置删除数据接口
void SListPop(SLNode** pphead, SLNode* pos);
.c接口实现
//单链表在pos位置删除数据接口
void SListPop(SLNode** pphead, SLNode* pos)
{assert(pphead);//if (*pphead == pos) {*pphead = (*pphead)->next;free(pos);}else {SLNode* cur = *pphead;while (cur->next != pos) {cur->next = pos->next;free(pos);}}
}
pos位置删除分两种情况
一种是头删, 需要phead改变指向。
一种是其他位置删除节点
单链表的销毁
链表使用完之后应该销毁, 放置内存泄漏
.h接口声明
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删函数接口
void SListPopBack(SLNode** pphead);
//单链表的头删函数接口
void SListPopFront(SLNode** pphead);
//单链表查找函数接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//单链表在pos位置之后插入数据接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//单链表在pos之后的位置删除数据
void SListPopAfter(SLNode* pos);
//单链表在pos位置之前插入数据接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//单链表在pos位置删除数据接口
void SListPop(SLNode** pphead, SLNode* pos);
//单链表的销毁函数接口
void SLTDestory(SLNode** pphead);
.c接口实现
//单链表的销毁函数接口
void SLTDestory(SLNode** pphead)
{assert(pphead);if (*pphead == NULL) {return;}SLNode* prev = (*pphead);SLNode* cur = (*pphead)->next;if (cur == NULL) {*pphead = NULL;free(prev);}else {*pphead = NULL;while(cur != NULL){free(prev);prev = cur;cur = cur->next;}free(prev);}}
销毁需要一步一步的进行, 如下图:
现在来看一下总体代码:
.h文件
链表的增删查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode
{struct SListNode* next;SLTDataType data;
}SLNode;//链表接口声明///申请链表节点函数接口
SLNode* BuySListNode(SLTDataType x);
//单链表的打印函数接口
void SListPrint(SLNode* phead);
//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删函数接口
void SListPopBack(SLNode** pphead);
//单链表的头删函数接口
void SListPopFront(SLNode** pphead);
//单链表查找函数接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//单链表在pos位置之后插入数据接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//单链表在pos之后的位置删除数据
void SListPopAfter(SLNode* pos);
//单链表在pos位置之前插入数据接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//单链表在pos位置删除数据接口
void SListPop(SLNode** pphead, SLNode* pos);
//单链表的销毁函数接口
void SLTDestory(SLNode** pphead);
.c文件
单链表函数实现函数接口//单链表申请节点函数接口
SLNode* BuySListNode(SLTDataType x)
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申请节点失败\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//单链表的节点打印操作
void SListPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一个NULL{printf("NULL");}}//单链表尾插函数接口
void SListPushBack(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点SLNode* cur = *pphead; //让cur指向phead所指向空间if (cur == NULL) //cur == NULL代表着phead指向NULL, 这时候让phead改变指向。传送phead指针的原因就是{ //要改变phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //让cur遍历到最后一个节点{cur = cur->next;}cur->next = newnode;//最后}}//单链表头插函数接口
void SListPushFront(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = BuySListNode(x);//SLNode* cur = *pphead;newnode->next = cur;*pphead = newnode;}//单链表尾删函数接口
void SListPopBack(SLNode** pphead)
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;SLNode* prev = *pphead;while (cur->next != NULL) //对链表进行遍历。 cur最终会指向尾节点。 prev用来维护链表{prev = cur;cur = cur->next;}if (prev == cur) {free(cur);*pphead = NULL;}else {free(cur);prev = NULL;}}//单链表的头删函数接口
void SListPopFront(SLNode** pphead)
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;*pphead = cur->next;free(cur);
}//单链表查找函数接口
SLNode* SListFind(SLNode* phead, SLTDataType x)
{SLNode* cur = phead;//定义一个指向头节点的指针, 用于遍历while (cur != NULL) //向后遍历{if (cur->data == x) //找到节点后就返回节点的地址。{return cur;}cur = cur->next;}return NULL;
}//单链表在pos位置之后插入数据接口
void SListInsertAfter(SLNode* pos, SLTDataType x)
{assert(pos);SLNode* newnode = BuySListNode(x);//SLNode* cur = pos->next;newnode->next = cur;pos->next = newnode;
}//单链表在pos之后的位置删除数据
void SListPopAfter(SLNode* pos)
{assert(pos);//SLNode* cur = pos->next;pos->next = pos->next->next;free(cur);
}//单链表在pos位置之前插入数据接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{assert(pphead);//SLNode* newnode = BuySListNode(x);//if (*pphead == NULL) {*pphead = newnode;return;}//if (*pphead == pos) {newnode->next = pos;*pphead = newnode;return;}SLNode* cur = *pphead;while (cur != NULL && cur->next != pos) {cur = cur->next;}newnode->next = pos;cur->next = newnode;
}//单链表在pos位置删除数据接口
void SListPop(SLNode** pphead, SLNode* pos)
{assert(pphead);//if (*pphead == pos) {*pphead = (*pphead)->next;free(pos);}else {SLNode* cur = *pphead;while (cur->next != pos) {cur->next = pos->next;free(pos);}}
}//单链表的销毁函数接口
void SLTDestory(SLNode** pphead)
{assert(pphead);if (*pphead == NULL) {return;}SLNode* prev = (*pphead);SLNode* cur = (*pphead)->next;if (cur == NULL) {*pphead = NULL;free(prev);}else {*pphead = NULL;while(cur != NULL){free(prev);prev = cur;cur = cur->next;}free(prev);}}