数据结构--链表篇一

小灰灰 2023-01-01 07:54 195阅读 0赞

![20210101094953784.png][] 单链表

如上图即为单链表的示意图。将结点按照一定的次序进行串联起来的，即为单链表。因为如果要访问链表中的任何一个结点的话，都需要从head处开始遍历，故称其为单链表。

> 单链表的每个结点存储地址并不连续（可能某两个之间是连续的，只不过几率很小），在访问的时候，只能从头指针开始沿着结点的link域进行。
> 
> 使用带头结点的单链表有两个好处：
> 
> ① 对带头结点的单链表，在表的任何结点之前插入节点或者删除表中的任何结点，所要做的都是修改前一结点的指针域。若单链表没有头结点，则首节点没有前驱结点，在其前插入及结点或者删除该及结点要做特殊情况处理。
> 
> ② 对带头结点的单链表，表头指针是指向头及结点的非空指针，因此空链表与非空链表的处理是一样的。

其中每个节点的数据结构代码如下：

template<class T>
    class LinkNode
    {
    public:
    	T m_Data; // 数据域
    	LinkNode<T>* pLink; // 指针域，指向下一个后继结点
    
    	// 构造函数
    	LinkNode(const T& data, LinkNode<T>* ptr = 0)
    	{
    		m_Data = data;
    		pLink = ptr;
    	}
    };

m\_Data 即是用来存储数据的成员变量。pLink 是用来指向当前节点的后继结点，如果没有则为null/0。

以下演示如何构建链表：

#include <iostream>
    #include "Link.h"
    using namespace std;
    
    int main()
    {
    	
    	LinkNode<int>* head = new LinkNode<int>(-1, 0); // 创建首个结点
    	LinkNode<int>* current = head;
    	const int length = 10;
    
    	for (int i = 0; i < length; i++)
    	{
    		LinkNode<int>* point = new LinkNode<int>(i, current); // 创建新结点
    		current->pLink = point;                               // 将当前结点的后继结点指针指向新结点
    		current = current->pLink;
    	}
    
        current = head;
    	for (int i = 0; i < length; i++)
    	{
    		if (current != 0)
    		{
    			cout << current ->m_Data << " ";
    			current = current ->pLink;
    		}
    	}
        
    	system("pause");
    }

实际开发过程中肯定不能像上述代码一样，构造链表需要做各种循环工作，应该封装起来，合理管理。

下面定义一个单链表的类。

#pragma once
    #include "Link.h"
    
    template<class T>
    class LinkList
    {
    private :
    	LinkNode<T> *pHead, *pTail;
    	LinkNode<T> *pPre, *pCur;
    	int position; // 当前元素在表中的位置序号
    
    private :
    	LinkNode<T>* GetPos(int pos); // 返回指定位置pos的指针
    
    public:
    	LinkList();
    	~LinkList();
    	int GetSize()const;
    	bool IsEmpty()const;
    	void Reset(int pos = 0);  // 初始化指针的位置
    	void Next(); // 使用指针移动到一个结点
    	bool EndOfList()const; // 指针是否到了链尾
    	int CurrentPosition(void); // 返回当前指针的位置
    	void InsertHead(const T& item); // 在表头插入结点
    	void InsertTail(const T& item); // 在表尾插入结点
    	void InsertAt(const T& item); // 在当前结点之前插入结点
    	void InsertAfter(const T& item); // 在当前结点之后插入结点
    	T DeleteCurrent(); // 删除当前结点
    	T& Data(); // 返回对当前结点成员数据的引用
    	const T& Data()const; // 返回对当前结点数据成员的常引用
    	void Clear();  // 清空链表：释放所有结点的内存空间	
    	bool InsertPos(const int pos, const T value); // 在指定位置pos插入结点
    	bool DeletePos(const int pos); // 删除指定位置的结点
    };

构造函数和析构函数：

template<class T>
    LinkList<T>::LinkList()
    {
    	position = 0;
    	pHead = nullptr;
    	pTail = pHead;
    	pPre = pHead;
    	pCur = pHead;
    }
    
    template<class T>
    LinkList<T>::~LinkList()
    {
    	LinkNode<T> *pLast, *pCurrent;
    	pCurrent = pHead;
    
    	while (pCurrent != nullptr)
    	{
    		pLast = pCurrent->pLink;
    		delete pCurrent;
    		pCurrent = pLast;
    	}
    }

返回指定位置 pos 的指针。

template<class T>
    LinkNode<T>* LinkList<T>::GetPos(int pos)
    {
    	if (pos == -1 || pos == 0)
    	{
    		return pHead;
    	}
    
    	int count = 0; 
    	LinkNode<T>* p = pHead;
    	while (p != nullptr && count < pos)
    	{
    		p = p->pLink;
    		count++;
    	}
    	return p;
    }

在链表头部插入结点：

template<class T>
    void LinkList<T>::InsertHead(const T& item)
    {
    	if (pHead == nullptr)
    	{
    		pHead = new LinkNode<T>(item);
    		pTail = pHead;
    	}
    	else
    	{
    		LinkNode<T>* temp = pHead;
    		pHead = new LinkNode<T>(item);
    		pHead->pLink = temp;
    	}
    }

在尾部插入结点：

template<class T>
    void LinkList<T>::InsertTail(const T& item)
    {
    	if (pTail == nullptr)
    	{
    		pTail = new LinkNode<T>(item);
    		pHead = pTail;
    	}
    	else
    	{
    		LinkNode<T>* temp = pTail;
    		pTail = new LinkNode<T>(item);
    		temp->pLink = pTail;
    	}
    }

**如果要对当前的链表插入一个新的结点，需要怎么做呢？**

1. 创建新的结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NMT0NLX1pIT05HX1pIRU4_size_16_color_FFFFFF_t_70][]

2. 将新建结点q的指针域link指向要插入链表中的后继结点的位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NMT0NLX1pIT05HX1pIRU4_size_16_color_FFFFFF_t_70 1][]

3. 将p结点的linkl指针域指向q。即可完成新增结点功能。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NMT0NLX1pIT05HX1pIRU4_size_16_color_FFFFFF_t_70 2][]  
代码实现：

template<class T>
    bool LinkList<T>::InsertPos(const int pos, const T value)
    {
    	if (pos < 0)
    		return false;
    
    	LinkNode<T> *p, *q;
    	p = GetPos(pos - 1);
    
    	// 首次插入，GetPos 返回空，则应插入成功
    	if (p == pHead)
    	{
    		if (p == nullptr && pos == 0)
    		{
    			InsertHead(value);
    			return true;
    		}
    	}
    
    	// 如果pos前一个位置为null，则不允许插入
    	if (p == nullptr)
    	{
    		return false;
    	}
    
    	q = new LinkNode<T>(value);
    	q->pLink = p->pLink;
    	p->pLink = q;
    	if (p == pTail) //如果 p是表尾，则pTail 指向新结点 q;
    	{
    		pTail = q;
    	}
    
    	return true;
    }

**删除指定位置pos的结点。**

![2021010120013982.png][]

将q结点的前驱结点p结点的link域指向q的后继结点，q的link域指向null，同时要清理delete q结点，否则，会引起内存泄漏。

![20210101200625101.png][]

实现代码：

template<class T>
    bool LinkList<T>::DeletePos(const int pos)
    {
    	LinkNode<T> *p, *q;
    	p = GetPos(pos - 1);  // 待删除结点的前驱结点
    
    	// p结点不存在，则pos位置的结点不存在，删除失败
    	if (p == nullptr)
    	{
    		return false;
    	}
        
    	// q 是待删除结点
    	if (pos == 0)
    	{
    		q = pHead;
    	}
    	else
    	{
    		q = p->pLink; 
    	}
    
    	if (q != nullptr)
    	{
    		p->pLink = q->pLink;
    	}
    	else
    	{
    		return false;
    	}
    
    	// 首部和尾部指向同一个内存块，即链表中只有0个或者1个结点
    	if (pHead == pTail)
    	{
    		pHead = pTail = nullptr;
    	}
    	else if (q == pTail) // 如果待删除结点q是链表尾部，删除后，前驱结点p变成尾部结点
    	{
    		pTail = p;
    	}
    	else if (q == pHead)// 如果待删除结点q是链表首部，删除后，q的后继结点变成首部结点
    	{
    		pHead = q->pLink;
    	}
    
    	if(q != nullptr)
    		delete q;
    
    	return true;
    }

[20210101094953784.png]: /images/20221120/b61ab173dc294f32923714d94d400e6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NMT0NLX1pIT05HX1pIRU4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210101193553531.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NMT0NLX1pIT05HX1pIRU4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NMT0NLX1pIT05HX1pIRU4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210101193353510.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NMT0NLX1pIT05HX1pIRU4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NMT0NLX1pIT05HX1pIRU4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210101193839460.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NMT0NLX1pIT05HX1pIRU4=,size_16,color_FFFFFF,t_70
[2021010120013982.png]: https://img-blog.csdnimg.cn/2021010120013982.png
[20210101200625101.png]: https://img-blog.csdnimg.cn/20210101200625101.png