Data Structure--单链表大部分基本接口的实现(详细讲解)

爱被打了一巴掌 2022-10-29 09:10 117阅读 0赞

# 单链表 #

单链表,不是挨个顺序存储的数据,是互相相连的数据,按照逻辑顺序存放地数据  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]  
这里重点要明白的是其中的逻辑规律,会有点绕口.

**单链表**

typedef int LDataType;		//别名声明 
    
    typedef struct listNode{ 		//结构体用来存放数据和下一个地址
    	
    	LDataType _data;	
    	struct listNode* _next;	//下一个存放地址
    
    }listNode;
    
    typedef struct list{ 		//存储头结点的位置,也就是图中的第一个方框
    	//存放第一个节点的位置
    	listNode* _head;
    }list;

他就是按照这种连线形式进行存放的,注意理解

## 接口声明 ##

从接口这里我开始详细的讲:

//1.接口初始化
    void listInit(list* lst);
    //2.创建空间
    listNode* creatNode(LDataType val);
    //3.尾插
    void listPushBack(list* lst,LDataType val);
    //4.尾删
    void listPopBack(list* lst);
    //5.头插
    void listPushFront(list* lst,LDataType val);
    //6.头删
    void listPopFront(list* lst);
    //7.中间插入
    void listInsertAfter(listNode* cur, LDataType val);
    //8.删除节点
    void listEraseAfter(listNode* cur);
    //9.查找
    listNode* listFind(list* lst, LDataType val);
    //10.销毁
    void listDestory(list* lst);

## 接口实现 ##

##### 1.接口初始化 #####

对于这里的接口初始化没有太多要说的,就是将头结点创建出来,等于空就可以了

void listInit(list* lst){ 
    	 
    	if (lst == NULL)	//如果为空指针,直接返回
    		return;
    	//初始化为空的链表
    	lst->_head = NULL;	
    }

##### 2.创建空间 #####

因为单链表这个东西,我们需要一个一个的进行创建比较麻烦,所以我们直接把他封装成一个接口,每次需要的时候直接调用就可以了,比较方便,也容易操作.

listNode* creatNode(LDataType val){ 
    	
    	listNode* node = (listNode*)malloc(sizeof(listNode));	//动态开辟一块空间
    
    	node->_data = val;	//将开辟的值进行赋予
    	node->_next = NULL;	//next为空,表示为最后一个元素
    
    	return node;		//返回
    }

##### 3.尾插 #####

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

void listPushBack(list* lst,LDataType val){ 
    	
    	if (lst == NULL)		//为空判断
    		return; 
    
    	
    	if (lst->_head == NULL){ 	//如果为空
    		lst->_head=creatNode(val);		//直接将这个元素创建在头结点后面
    	}
    	
    	else{ 									//不为空
    		listNode* tail = lst->_head;		//创建一个tail指向头结点
    		while (tail->_next != NULL){ 		//从头进行遍历,直到找到为NULL的最后一个元素
    			tail = tail->_next;				//遍历
    		}
    		
    		tail->_next = creatNode(val);		//寻找到最后一个后,将其进行元素插入,这里是调用了2的操作
    	}
    }

##### 4.尾删 #####

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

void listPopBack(list* lst){ 
    	
    	if (lst== NULL||lst->_head==NULL)		//判断是否为空
    		return;
    
    	struct listNode* tail = lst->_head;		//让tail指向头结点
    	struct listNode* prev = NULL;			
    
    	
    	while (tail->_next != NULL){ 			//进行遍历
    		
    		prev = tail;						//tail值赋予,也就是找到了倒数第二的位置
    		tail = tail->_next;					//循环
    	}
    	
    	free(tail);			//释放空间
    
    	if (prev == NULL)		//如果为空,就说明只存在一个数据,将数据删除,就只剩下头结点
    		lst->_head = NULL;	//只能让存在的头结点为空
    	else					//如果不为空,则存在元素倒数第二的next指向NULL即可
    		prev->_next = NULL; 
    }

##### 5.头插 #####

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

void listPushFront(list* lst,LDataType val){ 
    	
    	if (lst == NULL)		//判空
    		return;
    		
    	if (lst->_head == NULL)		//如果只有一个头节点
    		lst->_head = creatNode(val);	//则直接创建一个新的即可
    
    	else{ 						//如果有其他元素
    		listNode* node = creatNode(val);	//先创建
    		listNode* next = lst->_head;		//让next指向头结点,也就是原来第一个元素的头
    
    		lst->_head = node;		//头结点指向新创建的元素
    		node->_next = next;		//新创建元素的next指向原来第一个元素的头
    	}
    }

### 要点:!!! ###

**这里主要理解的是你要理解,最开始头结点和指向了原来的第一个元素,这两个地址可以理解成是一样的,所以最后一句node->\_next = next;这里的后面的next就是红色三角形这里的地址!!!**

##### 6.头删 #####

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

void listPopFront(list* lst){ 
    	
    	if (lst == NULL||lst->_head==NULL)		//判空
    		return;
    
    	struct listNode* next = lst->_head->_next;  //创建一个next指向原来头结点指向的第一个元素
    	                                            //的next,也就是第二个元素的首地址,连线的地址可以类似于一样
    	
    	free(lst->_head);	//释放头结点
    	lst->_head = next;	//头结点指向我们上面整理好的第二个元素的头
    }

多理解我的话,多画图思考

##### 7.中间插入 #####

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

void listInsertAfter(listNode* cur, LDataType val){ 
    	
    	listNode* node = creatNode(val);	//创建新元素
    	listNode* next = cur->_next;		//创建next指向原来位置的next也就是下一个元素的头(连线地址相等)
    
    	cur->_next = node;					//上一个元素的next指向新创建的元素
    	node->_next = next;					//创建元素的next指向下一个元素
    }

##### 8.删除节点(删除要删除的下一个元素) #####

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

void listEraseAfter(listNode* cur){ 
    	
    	listNode* next = cur->_next;	//创建next指向要cur的next
    	if (next == NULL)				//判空
    		return;
    
    	struct listNode* nextnext = next->_next;	//创建cur的下一个元素的next,也就是最后一个元素的头
    	free(next);			//释放空间
    	cur->_next = nextnext;		//连接
    }

##### 9.查找 #####

listNode* listFind(list* lst, LDataType val){ 
    	
    	if (lst == NULL||lst->_head==NULL)		//判空
    		return NULL;
    
    	//从头开始遍历
    	struct listNode* cur = lst->_head;	//cur指向头结点
    	while (cur){ 		//循环
    		if (cur->_data == val)		//当寻找到相等的,直接返回其位置
    			return cur;
    
    		cur = cur->_next;		//循环进行
    	}
    	return NULL;		//找不到返回空
    }

简单,理解就可以

##### 10.销毁 #####

因为释放单链表需要地址,先将下一个地址找到,再将这个进行释放,循环进行.

void listDestory(list* lst){ 
    	
    	if (lst->_head == NULL||lst==NULL)	//判空
    		return;
    		
    	else{ 									//不为空向下执行
    		listNode* cur = lst->_head;			//cur指向头结点
    		while (cur){ 						//循环
    			listNode* next = cur->_next;	//指向下一个头结点
    			free(cur);						//释放这个空间
    			cur = next;						//向后移一个,继续释放
    		}
    	}
    	lst->_head = NULL;		//最后将头结点为空操作
    }

对于这一部分的代码主要是理解,看起来很难是你没有理解到位,我总结出来的(**连线两端的地址可以看成是相等的**)剩下的就好考虑多了,多敲代码,细心一点,一起加油!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/7d3b8ac70b11495aa5e0a574dd0e2ef4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/6f78fc3f268a4cad9274098a67551173.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20221024/c07c7d22a52f47a2acf20a95dc3c5bf1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]: /images/20221024/9751dc85cfaa40baa845aa0c5c7acabd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 4]: /images/20221024/d33d2b79385d4d9b92f59f5b7054820f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 5]: /images/20221024/b59dac9c60c749b581e7ff33ed2e5739.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 6]: /images/20221024/50c52e2a33e64c6e93c9530266ab7346.png