【数据结构从青铜到王者】第二篇:数据结构之单向不带头不循环链表

左手的ㄟ右手 2022-11-18 02:29 134阅读 0赞

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

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、链表的概念及结构
 *   *   *   *  1.链表的概念
             *  2.链表的结构
 *  二、链表的种类
 *  三、链表的实现
 *   *   *   *  1.自定义链表结点struct SListNode
             *  2.链表打印数据SListPrint
             *  3.链表创建结点BuyListNode
             *  4.链表尾部插入数据SListPushBack
             *  5.链表头部插入数据SListPushFront
             *  6.链表尾部删除数据SListPopBack
             *  7.链表头部删除数据SListPopFront
             *  8.链表查找数据SListFindKey
             *  9.链表在pos位置之后插入数据SListInsertAfter
             *  10.链表在pos位置之前插入数据SListInsertBefore
             *  11.链表在pos位置之后删除数据SListEarseAfter
 *  总结

--------------------

![在这里插入图片描述][20210412115354283.png]

# 前言 #

顺序表的问题及思考  
问题：

1.  中间/头部的插入删除，时间复杂度为O(N)
2.  增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3.  增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：  
如何解决以上问题呢？下面给出了链表的结构来看看

--------------------

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

#### 1.链表的概念 ####

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

#### 2.链表的结构 ####

链表包括数据域和指针域：  
![在这里插入图片描述][20210412114909119.png]  
数据结构中：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]

# 二、链表的种类 #

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.  单向、双向
2.  带头、不带头
3.  循环、非循环

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]  
4. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结  
构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。  
5. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

# 三、链表的实现 #

#### 1.自定义链表结点struct SListNode ####

代码如下：

#pragma once
    #include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    typedef int SLTDateType;
    
    typedef struct SListNode
    { 
    	SLTDateType data;          //数据域
    	struct SListNode* next;   //指针域
    }SLTNode;

#### 2.链表打印数据SListPrint ####

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

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

代码如下：

void SListPrint(SLTNode* plist)
    { 
    	assert(plist);
    	SLTNode* cur = plist;
    	while (cur !=NULL)
    	{ 
    		printf("%d--> ", cur->data);
    		cur = cur->next;
    	}
    	printf("NULL\n");
    }

#### 3.链表创建结点BuyListNode ####

代码如下：

SLTNode* BuyListNode(SLTDateType num)                     //创建一个结点
    { 
    	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    	assert(node);
    	node->data = num;
    	node->next = NULL;
    	return node;
    }

#### 4.链表尾部插入数据SListPushBack ####

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

代码如下：

void SListPushBack(SLTNode** pplist, SLTDateType num)     //尾部插入数据,会改变第一个结点，所以传二级指针
    { 
    	assert(pplist);
    	SLTNode* newnode = BuyListNode(num);                  //创建一个新结点
    	if (*pplist == NULL)                                 //考虑当前一个结点都没有情况
    	{ 
    		*pplist = newnode;
    	}
    	else
    	{ 
    		SLTNode* tail = *pplist;
    		while (tail->next != NULL)  //遍历找到尾结点
    		{ 
    			tail = tail->next;
    		}
    		tail->next = newnode;  //把新结点的地址给前一个结点的指针
    	}
    }

#### 5.链表头部插入数据SListPushFront ####

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

代码如下：

void SListPushFront(SLTNode** pplist, SLTDateType num)
    { 
    	assert(pplist);
    	SLTNode* newnode = BuyListNode(num);
    	newnode->next = *pplist;
    	*pplist = newnode;
    }

#### 6.链表尾部删除数据SListPopBack ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 9]  
代码如下：

void SListPopBack(SLTNode** pplist)
    { 
    	//1.没有结点
    	//2.1个结点
    	//3.多个结点
    	if (pplist == NULL)
    	{ 
    		return;
    	}
    	else if ((*pplist)->next == NULL)
    	{ 
    		free(pplist);
    		*pplist = NULL;
    	}
    	else
    	{ 
    		SLTNode* prev = NULL;
    		SLTNode* tail = *pplist;
    		while (tail->next != NULL)
    		{ 
    			prev = tail;
    			tail = tail->next;
    		}
    		free(tail);
    		tail = NULL;
    		prev->next = NULL;
    	}
    }

#### 7.链表头部删除数据SListPopFront ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 10]  
代码如下：

void SListPopFront(SLTNode** pplist)
    { 
    	if (*pplist == NULL)
    	{ 
    		return;
    	}
    	else
    	{ 
    		SLTNode* next = (*pplist)->next;
    		free(*pplist);
    		*pplist = next;
    	}
    }

#### 8.链表查找数据SListFindKey ####

代码如下：

SLTNode* SListFindKey(SLTNode* plist, SLTDateType num)
    { 
    	SLTNode* cur = plist;
    	while (cur != NULL)
    	{ 
    		if (cur->data == num)
    		{ 
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }

#### 9.链表在pos位置之后插入数据SListInsertAfter ####

代码如下：

void SListInsertAfter(SLTNode* pos, SLTDateType num)
    { 
    	assert(pos);
    	SLTNode* newnode = BuyListNode(num);
    	newnode->next = pos->next;
    	pos->next = newnode;
    }

#### 10.链表在pos位置之前插入数据SListInsertBefore ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 11]  
代码如下：

void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDateType num)
    { 
    	assert(pos&&pplist);	
    	SLTNode* newnode = BuyListNode(num);
    	if (pos == *pplist)
    	{ 
    		newnode->next = pos;
    		*pplist = newnode;
    	}
    	SLTNode* prev = NULL;
    	SLTNode* cur = pplist;
    	while (cur != pos)
    	{ 
    		prev = cur;
    		cur = cur->next;
    	}
    	prev->next = newnode;
    	newnode->next = pos;
    }

#### 11.链表在pos位置之后删除数据SListEarseAfter ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 12]  
代码如下：

void SListEarseAfter(SLTNode* pos)
    { 
    	assert(pos);
    	if (pos->next == NULL)
    	{ 
    		return;
    	}
    	else
    	{ 
    		SLTNode* cur = pos->next;
    		pos->next = cur->next;
    	}
    }

--------------------

# 总结 #

以上就是今天要讲的内容，本文仅仅简单介绍了链表的各种方法的实现，而链表提供了方法能使我们快速便捷地处理数据的函数和方法，我们务必掌握。另外，如果有需要源码的私信我即可。还有，，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。  
![在这里插入图片描述][20210412122356460.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/6ca610d3e8294ea7a9990c1d4b470b24.png
[20210412115354283.png]: /images/20221022/8cc17a16eff948a797fe310471985963.png
[20210412114909119.png]: /images/20221022/abd0450a65844be0be769dea1b1ace1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221022/0f7a8fb8fc4c4730a37591d97fe946d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221022/b43b392dd4d94568b293608466863fac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221022/c09cfb43988543d3a80cc9e6abf826ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221022/b2035848559d483488e5ecf1e558548d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]: /images/20221022/9d82148d9d5b4cb7acc558da99ec7be5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]: /images/20221022/e7bcf38ad9054272b2f073d1d952d415.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]: /images/20221022/1cb51dd85f344193bf671864c397e13b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]: /images/20221022/45cacee975404e67b77261a48a1dd236.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 8]: /images/20221022/11550858a46048fbaaacad0d556780d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 9]: /images/20221022/747b7f034f99412abf0d419f31b3d9dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 10]: /images/20221022/b3022cb53a4a40d3b7d86b9d1237363f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 11]: /images/20221022/9ea35d02932e44c88f895328c41d565b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 12]: /images/20221022/ad60110966a24b30a05c92c8f85f87d5.png
[20210412122356460.png_pic_center]: /images/20221022/a85f4777b64a41aeacb85b52b29e95ab.png