小小的链表其实并不简单

叁歲伎倆 2022-02-19 18:54 199阅读 0赞

## 链表 ##

*  概念：链表也是我们最常使用的一种数据结构，它是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链  
    接次序实现的 。
 *  分类  
    单向链表、双向链表  
    带头的链表、不带头链表  
    循环链表、非循环链表等
 *  让我们来看看链表到底是什么样子的

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]  
上图就是我们最常用的单向链表及双选购链表的示意图。很明显链表这种数据结构它是通过一种手段将我们的数据串起来，所以在数据在存储的时候它并不一定要是连续的，我们只需要将当前数据的下一个数据的位置信息保存起来即可，那么链表就是通过指针来保存数据的位置信息的。

*  话不多说还是上代码，下面我以单链表为例，让我们看看链表到底是如何实现的。

#include<iostream>
    
    using namespace std;
    
    //用Elemtype代替int  好处就是当int改变时，只需要改变一个int即可
    typedef int Elemtype;
    //链表节点的定义
    typedef struct Node
    {
    	int value;
    	struct Node* next;
    }Node;
    
    //初始化链表，没有一个节点的链表，即为空链表。
    void LinkListInit(Node** p)
    {
    	*p = NULL;
    }
    
    //链表的销毁
    void DestoryLinkList(Node** p)
    {
    	//销毁链表则要找一个临时变量保存当前的位置，这才能保证后面的节点位置信息不丢失
    	Node* ptr;
    	for (Node* cur = *p; cur != NULL; cur = ptr)
    	{
    		ptr = cur->next;
    		free(cur);
    	}
    }
    //打印节点值
    void PrintLinkList(Node* p)
    {
    	if (p == NULL)
    	{
    		cout << "该链表为空链表。" << endl;
    		return ;
    	}
    	while (p != NULL)
    	{
    		cout << p->value << " " << endl;
    		p = p->next;
    	}
    
    }
    //链表的头插法
    void LinkListInsertFront(Node** p,int value)
    {
    	//构造节点
    	Node* node = (Node*)malloc(sizeof(Node));
    	node->value = value;
    	node->next = *p;
    	*p = node;
    }
    
    //链表的尾插法
    void LinkListInsertBack(Node** p, Elemtype value)
    {
    	//构造节点
    	Node* node = (Node*)malloc(sizeof(Node));
    	node->value = value;
    
    	if (*p == NULL) {
    		// 链表中一个结点都没有
    		*p = node;
    		return;
    	}
    
    
    	//既然要尾插那么就要找到尾节点
    	Node* cur = *p;
    	for (; cur->next != NULL; cur = cur->next);
    	//此时cur为尾节点
    	cur->next = node;
    	node->next = NULL;
    }
    
    //链表的中间插入，即插入到某个节点的后面
    void LinkListInsertMid(Elemtype value,Node* pos)
    {
    	//构造节点
    	Node* node = (Node*)malloc(sizeof(Node));
    	node->value = value;
    	//先找到当前的节点位置
    	node->next = pos->next;
    	pos->next = node;
    }
    
    //链表的查找，返回当前节点的地址
    Node* LinkListFind(Node* p, Elemtype value)
    {
    	//参数的合法性检验
    	if (p == NULL)
    	{
    		return NULL;
    	}
    	Node* cur = p;
    	for (; cur != NULL; cur = cur->next)
    	{
    		if (cur->value = value)
    		{
    			//此时cur为当前value的地址
    			return cur;
    		}
    	}
    	return NULL;
    
    }
    
    //头删
    void LinkListDelFront(Node** p)
    {
    	if (*p == NULL)
    	{
    		return;
    	}
    	else
    	{
    		Node *next = (*p)->next;
    		free(*p);
    		*p = next;
    	}
    }
    
    //尾删
    void LinkListPopBack(Node** p)
    {
    	if (*p == NULL)
    	{
    		return;
    	}
    	if ((*p)->next == NULL) 
    	{
    		free(*p);
    		*p = NULL;
    		return;
    	}
    
    	// 找到倒数第二个结点
    	// cur->next->next == NULL 停下来
    	Node *cur = *p;
    	while (cur->next->next != NULL) 
    	{
    		cur = cur->next;
    	}
    
    	// 释放最后一个结点
    	free(cur->next);
    	cur->next = NULL;
    }
    
    //中间删除(某个节点之后删除)
    void LinkListDel(Node* p)
    {
    	Node *next = p->next;
    	p->next = p->next->next;
    	free(next);
    }
    
    int main()
    {
    	Node* node;
    	cout << "链表已经初始化成功" << endl;;
    	LinkListInit(&node);  //初始化
    	PrintLinkList(node);
    
    	cout << "请输入头插入的节点值：";
    	Elemtype value;
    	cin >> value;
    	LinkListInsertFront(&node,value);//头插
    	PrintLinkList(node);
    
    
    	cout << "请输入尾插入的节点值：";
    	Elemtype value1;
    	cin >> value1;
    	LinkListInsertBack(&node, value1);//尾插
    	PrintLinkList(node);
    
    	cout << "请输入您想要查找的节点值：";
    	Elemtype value2;
    	cin >> value2;
    	Node* p = LinkListFind(node,value2);
    	if (p == NULL)
    	{
    		cout << "没有找到该节点" << endl;
    	}
    	else
    	{
    		cout << "找到该节点" << endl;
    	}
    
    	cout << "请输入中间插入的节点值：";
    	Elemtype value3;
    	cin >> value3;
    	cout << "请输入您想要插入的位置节点的值：";
    	Elemtype value4;
    	cin >> value4;
    	Node* pp = LinkListFind(node, value4);
    	LinkListInsertMid(value3,pp);//中间插入
    	PrintLinkList(node);
    	
    	cout << "请输入您要删除节点的值：";
    	int value5;
    	cin >> value5;
    	Node* ppp = LinkListFind(node, value5);
    	cout << "删除" << value5 << "节点";
    	LinkListDel(ppp);
    	PrintLinkList(node);
    	cout << "删除头节点" << endl;
    	LinkListDelFront(&node);
    	PrintLinkList(node);
    	cout << "删除尾节点" << endl;
    	LinkListPopBack(&node);
    	PrintLinkList(node);
    	
    	system("pause");
    	return 0;
    }

自我感觉啊，面对链表的相关问题时还是得画图，有了图，我们的思路才会更加清晰，对于链表而言，它没有随机访问能力，如果要查找某个数，只能遍历一遍，时间相对而言没有顺序表好，但是链表的增删很快，不需要像顺序表一样挪动数据。

**注注注**：重要的事说三遍，其实看起来小小的链表没有多难操作，但就是通过这小小链表引申了很多问题，有许多问题值得我们去思考，当你真正理解了链表之后，你会发现链表真的还挺有意思的。后续我会继续与大家分享我遇到的关于链表的一些有意思的问题，我们可以与链表进一步的增进感情嘛！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]: /images/20220219/397ed17913ba47598452a7b5ae079c7c.png