数据结构——单链表接口实现(C语言)

男娘i 2022-12-27 04:52 169阅读 0赞

### 单链表的接口实现 ###

*  github代码下载
 *  一、链表的概念及结构
 *   *  1.1 概念
     *  1.2 结构
 *  二、链表的接口实现
 *   *  2.1 链表的存储定义
     *  2.2 动态申请一个节点
     *  2.3 单链表打印
     *  2.4 单链表尾插
     *  2.5 单链表头插
     *  2.6 单链表尾删
     *  2.7 单链表头删
     *  2.8 单链表查找
     *  2.9 单链表任意位置之后插入
     *  2.10 单链表删除任意位置之后的值
 *  三、多文件实现
 *   *  3.1 ListNode.h
     *  3.2 ListNode.c
     *  3.3 test.c

# github代码下载 #

github代码：  
[https://github.com/Kyrie-leon/Data\_Structures/tree/main/ListNode][https_github.com_Kyrie-leon_Data_Structures_tree_main_ListNode]

# 一、链表的概念及结构 #

## 1.1 概念 ##

链表是一种**物理结构上非连续**、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

## 1.2 结构 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]

# 二、链表的接口实现 #

## 2.1 链表的存储定义 ##

typedef int SLTDataType;
    
    //单链表的定义
    typedef struct SListNode
    {
        
    	SLTDataType data;	
    	struct SListNode * next; //next指向当前节点的下一个节点
    }SListNode;

## 2.2 动态申请一个节点 ##

> 申请一个节点首先使用malloc开辟一块结构内存  
> 然后将数据元素x放入data数据区  
> 将next置空  
> ![在这里插入图片描述][20201210201100808.png]

//2.2 动态申请一个节点
    SListNode * BuyListNode(SLTDataType x)
    {
        
    	
    	SListNode * plist=(SListNode *)malloc(sizeof(SListNode));
    	//判断申请是否成功
    	if (plist==NULL)
    	{
        
    		printf("申请新节点失败\n");
    		exit(-1);
    	}
    	plist->data = x;
    	plist->next = NULL;
    	return plist;
    }

## 2.3 单链表打印 ##

//2.3 单链表打印
    void SListPrint(SListNode * plist)
    {
        
    
    	//打印链表
    	while (plist)
    	{
        
    		printf("%d->", plist->data);
    		plist = plist->next;	//节点指向下一个
    	}
    	printf("NULL\n");
    }

## 2.4 单链表尾插 ##

*  首先申请一个新节点  
    ![在这里插入图片描述][20201210201100808.png]
 *  判断链表是否为空，**如果为空则直接将新节点插入**
 *  不是空的话，遍历链表找到尾节点  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]
 *  找到后，申请新节点，让原链表尾节点指向新节点  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 2]  
    **注意：由于尾插可能存在空链表的情况，因此当链表为空时传入一级指针不会改变链表的状态，所以传入二级指针。**

//2.4 单链表尾插
    void SListPushBack(SListNode** pplist, SLTDataType x)
    {
        
    	//申请一个新节点
    	SListNode* NewNode = BuyListNode(x);
    
    	//判断链表是否为空，如果为空则申请节点直接插入，否则找到尾节点插入
    	if ((*pplist) == NULL)
    	{
        
    		*pplist = NewNode;
    	}
    	else
    	{
        
    		//定义一个当前节点tail去找链表的尾节点
    		SListNode* tail = *pplist;
    
    		//遍历节点找尾节点
    		while (tail->next)
    		{
        
    			tail = tail->next;
    		}
    
    		//尾节点的next指向新节点
    		tail->next = NewNode;
    	}
    
    }

## 2.5 单链表头插 ##

*  首先申请新节点
 *  判断链表是否为空，若为空直接插入
 *  不为空，让NewNode的next指向Plist，然后让Plist指向NewNode  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 3]

//2.5 单链表头插
    void SListPushFront(SListNode** pplist, SLTDataType x)
    {
        
    	//申请新节点
    	SListNode * NewNode = BuyListNode(x);
    	//判断链表是否空
    	if (*pplist == NULL)
    	{
        
    		//链表为空直接插入
    		*pplist = NewNode;
    
    	}
    	else 
    	{
        
    		NewNode->next = *pplist;	//新节点next指向pplist
    		*pplist=NewNode;			//更新头结点
    	}
    
    }

## 2.6 单链表尾删 ##

尾删有三种情况：

*  单链表为空则返回
 *  单链表只有一个节点，直接删除  
    ![在这里插入图片描述][20201211200851758.png]
 *  单链表有一个以上节点，定义两个指针，一个指向尾节点，一个指向尾节点前的一个节点。首先找到尾节点删除，  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 4]  
    然后将prev的next置空  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 5]

//2.6 单链表尾删
    void SListPopBack(SListNode** pplist)
    {
        
    	//1.单链表为空
    	if (*pplist == NULL)
    	{
        
    		return;
    	}
    	//2.单链表只有一个节点
    	else if((*pplist)->next==NULL)
    	{
        
    		free(*pplist);
    		*pplist = NULL;
    	}
    	//3.单链表有一个以上节点
    	else
    	{
        
    		//tali指向第1个节点，prev为空
    		SListNode * prev = NULL;
    		SListNode * tail = *pplist;
    
    		
    		//遍历链表找到尾节点
    		while (tail->next!=NULL)
    		{
        
    			//注意先后顺序，prev先走才不会丢失节点
    			//prev向后走一个节点
    			prev = tail;
    			//tail向后走一个节点
    			tail = tail->next;
    		}
    		//删除尾节点
    		free(tail);
    		//prev作为新的尾节点
    		prev->next = NULL;
    
    	}
    }

## 2.7 单链表头删 ##

链表三种情况同上  
首先找到头结点，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 6]  
让\*pplist指向下一个节点  
删除头结点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 7]

//2.7 单链表头删
    void SListPopFront(SListNode** pplist)
    {
        
    	//1.空单链表
    	if (*pplist == NULL)
    	{
        
    		return;
    	}
    	//2.一个节点
    	else if ((*pplist)->next == NULL)
    	{
        
    		free(*pplist);
    		*pplist = NULL;
    	}
    	//3.一个以上
    	else
    	{
        
    
    		SListNode * phead = *pplist;
    		//现移动删除后的头结点
    		*pplist = phead->next;
    		//再释放原来的头结点
    		free(phead);
    	}
    }

## 2.8 单链表查找 ##

//2.8 单链表查找
    SListNode * SListFind(SListNode * plist, SLTDataType x)
    {
        
    	SListNode * cur = plist;
    	//1.空链表直接返回
    	//遍历链表
    	while (cur)
    	{
        
    		//如果找节点值等于x则返回
    		if (x == cur->data)
    		{
        
    			return cur;
    		}
    		//没找到继续遍历
    		cur = cur->next;
    	}
    	return NULL;
    }

## 2.9 单链表任意位置之后插入 ##

在pos位置之后插入新节点容易实现，首先让新节点指向当前节点cur的下一个节点，然后让cur当前节点指向新节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 8]

//2.9 单链表在任意位置之后插入x
    void SListInsertAfter(SListNode* pos, SLTDataType x)
    {
        
    	assert(pos);
    	SListNode * newNode = BuyListNode(x);
    	newNode->next = pos->next;
    	pos->next = newNode;
    }

## 2.10 单链表删除任意位置之后的值 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 9]

//2.10 单链表删除任意位置之后的值
    void SListEraseAfter(SListNode* pos)
    {
        
    	assert(pos);
    	if (pos->next)
    	{
        
    		SListNode * next = pos->next;	//找到pos位置后面的节点保存起来，防止删除后丢失
    		pos->next = next->next;			//pos位置节点指向next后的节点
    		free(next);		//释放pos后的节点
    	}
    }

# 三、多文件实现 #

## 3.1 ListNode.h ##

#ifndef _LISTNODE_H
    #define _LISTNODE_H
    
    #include<stdio.h>
    #include<windows.h>
    #include<stdlib.h>
    #include<assert.h>
    
    typedef int SLTDataType;
    
    //单链表的定义
    typedef struct SListNode
    {
        
    	SLTDataType data;	//data
    	struct SListNode * next; //next指向当前节点的下一个节点
    }SListNode;
    
    
    //动态申请一个节点
    SListNode * BuyListNode(SLTDataType x);
    //单链表打印
    void SListPrint(SListNode * plist);
    //单链表尾插
    void SListPushBack(SListNode** pplist, SLTDataType x);
    //单链表头插
    void SListPushFront(SListNode** pplist, SLTDataType x);
    //单链表尾删
    void SListPopBack(SListNode** pplist);
    //单链表头删
    void SListPopFront(SListNode** pplist);
    //单链表查找
    SListNode * SListFind(SListNode * plist, SLTDataType x);
    //单链表在任意位置之后插入x
    void SListInsertAfter(SListNode* pos, SLTDataType x);
    //单链表删除任意位置之后的值
    void SListEraseAfter(SListNode* pos);
    //单链表的销毁
    void SListDestory(SListNode* plist);
    
    
    #endif

## 3.2 ListNode.c ##

#include "ListNode.h"
    
    //2.2 动态申请一个节点
    SListNode * BuyListNode(SLTDataType x)
    {
        
    	
    	SListNode * plist=(SListNode *)malloc(sizeof(SListNode));
    	//判断申请是否成功
    	if (plist==NULL)
    	{
        
    		printf("申请新节点失败\n");
    		exit(-1);
    	}
    	plist->data = x;
    	plist->next = NULL;
    	return plist;
    }
    
    //2.3 单链表打印
    void SListPrint(SListNode * plist)
    {
        
    
    	//打印链表
    	while (plist)
    	{
        
    		printf("%d->", plist->data);
    		plist = plist->next;	//节点指向下一个
    	}
    	printf("NULL\n");
    }
    
    //2.4 单链表尾插
    void SListPushBack(SListNode** pplist, SLTDataType x)
    {
        
    	//申请一个新节点
    	SListNode* NewNode = BuyListNode(x);
    
    	//判断链表是否为空，如果为空则申请节点直接插入，否则找到尾节点插入
    	if ((*pplist) == NULL)
    	{
        
    		*pplist = NewNode;
    	}
    	else
    	{
        
    		//定义一个当前节点tail去找链表的尾节点
    		SListNode* tail = *pplist;
    
    		//遍历节点找尾节点
    		while (tail->next)
    		{
        
    			tail = tail->next;
    		}
    
    		//尾节点的next指向新节点
    		tail->next = NewNode;
    	}
    
    }
    
    //2.5 单链表头插
    void SListPushFront(SListNode** pplist, SLTDataType x)
    {
        
    	//申请新节点
    	SListNode * NewNode = BuyListNode(x);
    	//判断链表是否空
    	if (*pplist == NULL)
    	{
        
    		//链表为空直接插入
    		*pplist = NewNode;
    
    	}
    	else 
    	{
        
    		NewNode->next = *pplist;	//新节点next指向pplist
    		*pplist=NewNode;			//更新头结点
    	}
    
    }
    
    //2.6 单链表尾删
    void SListPopBack(SListNode** pplist)
    {
        
    	//1.单链表为空
    	if (*pplist == NULL)
    	{
        
    		return;
    	}
    	//2.单链表只有一个节点
    	else if((*pplist)->next==NULL)
    	{
        
    		free(*pplist);
    		*pplist = NULL;
    	}
    	//3.单链表有一个以上节点
    	else
    	{
        
    		//tali指向第1个节点，prev为空
    		SListNode * prev = NULL;
    		SListNode * tail = *pplist;
    
    		
    		//遍历链表找到尾节点
    		while (tail->next!=NULL)
    		{
        
    			//注意先后顺序，prev先走才不会丢失节点
    			//prev向后走一个节点
    			prev = tail;
    			//tail向后走一个节点
    			tail = tail->next;
    		}
    		//删除尾节点
    		free(tail);
    		//prev作为新的尾节点
    		prev->next = NULL;
    
    	}
    }
    
    //2.7 单链表头删
    void SListPopFront(SListNode** pplist)
    {
        
    	//1.空单链表
    	if (*pplist == NULL)
    	{
        
    		return;
    	}
    	//2.一个节点
    	else if ((*pplist)->next == NULL)
    	{
        
    		free(*pplist);
    		*pplist = NULL;
    	}
    	//3.一个以上
    	else
    	{
        
    
    		SListNode * phead = *pplist;
    		//现移动删除后的头结点
    		*pplist = phead->next;
    		//再释放原来的头结点
    		free(phead);
    	}
    }
    
    //2.8 单链表查找
    SListNode * SListFind(SListNode * plist, SLTDataType x)
    {
        
    	SListNode * cur = plist;
    	//1.空链表直接返回
    	//遍历链表
    	while (cur)
    	{
        
    		//如果找节点值等于x则返回
    		if (x == cur->data)
    		{
        
    			return cur;
    		}
    		//没找到继续遍历
    		cur = cur->next;
    	}
    	return NULL;
    }
    
    //2.9 单链表在任意位置之后插入x
    void SListInsertAfter(SListNode* pos, SLTDataType x)
    {
        
    	assert(pos);
    	SListNode * newNode = BuyListNode(x);
    	newNode->next = pos->next;
    	pos->next = newNode;
    }
    
    //2.10 单链表删除任意位置之后的值
    void SListEraseAfter(SListNode* pos)
    {
        
    	assert(pos);
    	if (pos->next)
    	{
        
    		SListNode * next = pos->next;	//找到pos位置后面的节点保存起来，防止删除后丢失
    		pos->next = next->next;			//pos位置节点指向next后的节点
    		free(next);		//释放pos后的节点
    	}
    }

## 3.3 test.c ##

#include "ListNode.h"
    
    
    //测试单链表的头尾删除
    void TestListNode1()
    {
        
    	SListNode * Plist=NULL;	//定义一个单链表
    
    	//测试申请一个节点
    	Plist = BuyListNode(1);
    
    	//打印链表测试
    	SListPrint(Plist);
    
    	//2.4 单链表尾插测试
    	SListPushBack(&Plist, 2);
    	SListPushBack(&Plist, 3);
    	SListPushBack(&Plist, 4);
    	SListPushBack(&Plist, 5);
    	SListPrint(Plist);
    
    	//2.5 单链表头插
    	SListPushFront(&Plist, -1);
    	SListPrint(Plist);
    
    	//单链表尾删
    	//SListPopBack(&Plist);
    	//SListPopBack(&Plist);
    	//SListPopBack(&Plist);
    	//SListPopBack(&Plist);
    	//SListPopBack(&Plist);
    	//SListPopBack(&Plist);
    	//SListPopBack(&Plist);
    	//SListPopBack(&Plist);	
    	//SListPopBack(&Plist);	
    	//SListPopBack(&Plist);
    	//SListPrint(Plist);
    
    	//单链表头删
    	//SListPopFront(&Plist);
    	//SListPopFront(&Plist);
    	//SListPopFront(&Plist);
    	//SListPopFront(&Plist);
    	//SListPopFront(&Plist);
    	//SListPopFront(&Plist);
    	//SListPopFront(&Plist);
    	//SListPopFront(&Plist);
    	//SListPrint(Plist);
    
    	//2.8 单链表查找
    	SListNode * pos = SListFind(Plist, 3);
    	SListPrint(pos);
    
    	//2.9 单链表在任意位置之后插入x
    	SListInsertAfter(pos, 30);
    	SListPrint(Plist);
    
    	//2.10 单链表删除任意位置之后的值
    	SListEraseAfter(pos);
    	SListPrint(Plist);
    
    
    }
    
    
    
    int main()
    {
        
    	TestListNode1();
    	system("pause");
    	return 0;
    }

[https_github.com_Kyrie-leon_Data_Structures_tree_main_ListNode]: https://github.com/Kyrie-leon/Data_Structures/tree/main/ListNode
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]: /images/20221120/7f31403d2deb4b12b8bb9e36efbb86a0.png
[20201210201100808.png]: /images/20221120/4662bc94148a4b9686a3f1d83c064b4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]: /images/20221120/44794ee2b235401e9609e80014a8850f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 2]: /images/20221120/f520f77fca5049f0882f501a97f56ea9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 3]: /images/20221120/a1916331a90544bea53a5aaac779dffa.png
[20201211200851758.png]: /images/20221120/fcce9739c91042b5876ec6b528922b75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 4]: /images/20221120/547785335530417dbf82308865b8fa6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 5]: /images/20221120/cc48b8bd1fad479fbce6ceee82f3dcb2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 6]: /images/20221120/55d2531f5f9648fbba404e88c9a3a352.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 7]: /images/20221120/3a3b1f45dcc14f46b4cfa07a2aa377bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 8]: /images/20221120/f3641c76d03c43679c9854dde23cd3f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20201212222309830.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy,size_16,color_FFFFFF,t_70