[数据结构与算法] 24.数据结构-单链表的遍历与优化

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 24.数据结构-单链表的遍历与优化 -> 正文阅读

[数据结构与算法]24.数据结构-单链表的遍历与优化

文章目录

1.当前单链表的遍历方法

LinkList<int> l;
for(int i = 0;i < 5;i++)
{
	l.insert(0,i);
}
for(int i = 0;i < l.length();i++)
{
	l.get(i);
}

在头部插入元素时，时间复杂度是O(n)。获取元素时，时间复杂度是O(n*n)，内层定位位置时有一个O(n)复杂度,那么该怎么优化单链表，使得其在线性的时间内进行遍历操作

2.O(n)操作遍历单链表

解决思路：
在单链表的内部定义一个游标，开始时指向位置为0的数据元素，游标每一次移动获取一下链表的数据元素，这里提供一组遍历函数分别为：
在这里插入图片描述
其中各个函数的定义为：
move函数的i参数为目标位置，step参数为每次移动的节点数。
end用来判断当前的游标是否到达了单链表的尾部。
current返回当前游标指向的数据元素。
next移动游标，移动的次数根据move中的step的值来决定。

3.改进后的单链表

LinkList.h

#ifndef  __LINK_LIST_
#define  __LINK_LIST_

namespace DTlib
{
	template<class T>
	class LinkList
	{
	public:
		struct Node
		{
			T	  value;
			Node* next;
		};

		mutable struct
		{
			char reverse[sizeof(T)];
			Node* next;
		} m_header;

		int m_length;
		int m_step;
		Node* m_current;

		Node* position(int i)const
		{
			Node* pre = reinterpret_cast<Node*>(&m_header);
			for (int pos = 0; pos < i; pos++)
			{
				pre = pre->next;
			}

			return pre;
		}
	public:
		LinkList();
		~LinkList();
		int find(const T& e)const;
		bool end();
		bool next();
		T current();
		bool move(int i, int step = 1);
		bool insert(int i, T& e);
		bool remove(int i);
		bool set(int i, T& e);
		T get(int i) const;
		int length() const;
		void clear();
	};
}


#endif

LinkList.cpp

#include "LinkList.h"
#include <iostream>

using namespace DTlib;
using namespace std;

template<class T>
LinkList<T>::LinkList()
{
	m_header.next = NULL;
	m_length = 0;
	m_step = 0;
	m_current = NULL;
}

/*template<class T>
Node* LinkList<T>::position(int i)const
{
	Node*  pre =  reinterpret_cast<Node*>(&m_header);
	for (int pos = 0; pos < i; pos++)
	{
		pre = pre->next;
	}

	return pre;
}*/

template<class T>
int LinkList<T>::find(const T& e)const
{
	Node* pre = reinterpret_cast<Node*>(&m_header);
	int i = 0;

	while (e != pre->next->value)
	{
		pre = pre->next;
		i++;
	}

	return i;
}

template<class T>
bool LinkList<T>::end()
{
	return m_current == NULL;
}


template<class T>
bool LinkList<T>::move(int i, int step)
{
	bool ret = (i >= 0) && (i <= m_length);
	if (ret)
	{
		m_current = position(i)->next;
		m_step = step;
	}

	return ret;
}


template<class T>
T LinkList<T>::current()
{
	
	if (!end())
	{
		return m_current->value;
	}
	else
	{
		cout << "current end()" << endl;
		return -1;//不知道写啥值
	}
}

template<class T>
bool LinkList<T>::next()
{
	int i = 0;
	while (!end() && i < m_step)
	{
		m_current = m_current->next;
		i++;
	}

	return i == m_step;
}


template<class T>
bool LinkList<T>::insert(int i, T& e)
{
	bool ret = (i >= 0) && (i <= m_length);
	if (ret)
	{
		Node* node = new Node();

		if (node != NULL)
		{
			Node* pre = reinterpret_cast<Node*>(&m_header);

			pre = position(i);

			node->value = e;
			node->next = pre->next;
			pre->next = node;
		}
		else
		{
			cout << "no memery to malloc" << endl;
		}
	}

	m_length++;
	return ret;
}


template<class T>
bool LinkList<T>::remove(int i)
{
	bool ret = (i >= 0) && (i <= m_length);

	if (ret)
	{
		Node* pre = reinterpret_cast<Node*>(&m_header);

		pre = position(i);

		Node* toDel = pre->next;
		pre->next = toDel->next;
		delete toDel;
		m_length--;
	}

	return ret;
}

template<class T>
bool LinkList<T>::set(int i, T& e)
{
	bool ret = (i >= 0) && (i <= m_length);

	if (ret)
	{
		Node* pre = reinterpret_cast<Node*>(&m_header);

		pre = position(i);

		pre->next->value = e;
	}

	return ret;
}

template<class T>
T LinkList<T>::get(int i) const
{
	bool ret = (i >= 0) && (i <= m_length);
	T e;

	if (ret)
	{
		Node* pre = reinterpret_cast<Node*>(&m_header);

		pre = position(i);

		e = pre->next->value;
	}

	return e;
}


template<class T>
int  LinkList<T>::length() const
{
	return m_length;
}

template<class T>
void LinkList<T>::clear()
{

	while (m_header.next != NULL)
	{
		Node* toDel = m_header.next;
		m_header.next = toDel->next;
		delete toDel;
	}

	m_length = 0;
}

template<class T>
LinkList<T>::~LinkList()
{
	clear();
}

int main()
{
	LinkList<int> l;
	for (int i = 0; i < 5; i++)
	{
		l.insert(i, i);
	}

	for (l.move(0,2); !l.end();l.next())
	{
		cout << l.current() << endl;
	}

	for (int i = 0; i < 5; i++)
	{
		cout << l.find(i) << endl;
	}
	

	return 0;
}

结果：
在这里插入图片描述

4.单链表内部封装

将所有生成结点的地方的换成create(),销毁结点的地方换成destory();
在这里插入图片描述
LinkList.h

#ifndef  __LINK_LIST_
#define  __LINK_LIST_

namespace DTlib
{
	template<class T>
	class LinkList
	{
	public:
		struct Node
		{
			T	  value;
			Node* next;
		};

		mutable struct
		{
			char reverse[sizeof(T)];
			Node* next;
		} m_header;

		int m_length;
		int m_step;
		Node* m_current;

		Node* position(int i)const
		{
			Node* pre = reinterpret_cast<Node*>(&m_header);
			for (int pos = 0; pos < i; pos++)
			{
				pre = pre->next;
			}

			return pre;
		}

		Node* create()
		{
			return new Node();
		}

	public:
		LinkList();
		~LinkList();
		void destroy(Node* pn);
		int find(const T& e)const;
		bool end();
		bool next();
		T current();
		bool move(int i, int step = 1);
		bool insert(int i, T& e);
		bool remove(int i);
		bool set(int i, T& e);
		T get(int i) const;
		int length() const;
		void clear();
	};
}


#endif

LinkList.cpp

#include "LinkList.h"
#include <iostream>

using namespace DTlib;
using namespace std;

template<class T>
LinkList<T>::LinkList()
{
	m_header.next = NULL;
	m_length = 0;
	m_step = 0;
	m_current = NULL;
}

/*template<class T>
Node* LinkList<T>::position(int i)const
{
	Node*  pre =  reinterpret_cast<Node*>(&m_header);
	for (int pos = 0; pos < i; pos++)
	{
		pre = pre->next;
	}

	return pre;
}*/


template<class T>
void LinkList<T>::destroy(Node* pn)
{
	delete pn;
}

template<class T>
int LinkList<T>::find(const T& e)const
{
	Node* pre = reinterpret_cast<Node*>(&m_header);
	int i = 0;

	while (e != pre->next->value)
	{
		pre = pre->next;
		i++;
	}

	return i;
}

template<class T>
bool LinkList<T>::end()
{
	return m_current == NULL;
}


template<class T>
bool LinkList<T>::move(int i, int step)
{
	bool ret = (i >= 0) && (i <= m_length);
	if (ret)
	{
		m_current = position(i)->next;
		m_step = step;
	}

	return ret;
}


template<class T>
T LinkList<T>::current()
{
	
	if (!end())
	{
		return m_current->value;
	}
	else
	{
		cout << "current end()" << endl;
		return -1;//不知道写啥值
	}
}

template<class T>
bool LinkList<T>::next()
{
	int i = 0;
	while (!end() && i < m_step)
	{
		m_current = m_current->next;
		i++;
	}

	return i == m_step;
}


template<class T>
bool LinkList<T>::insert(int i, T& e)
{
	bool ret = (i >= 0) && (i <= m_length);
	if (ret)
	{
		Node* node = create();

		if (node != NULL)
		{
			Node* pre = reinterpret_cast<Node*>(&m_header);

			pre = position(i);

			node->value = e;
			node->next = pre->next;
			pre->next = node;
		}
		else
		{
			cout << "no memery to malloc" << endl;
		}
	}

	m_length++;
	return ret;
}


template<class T>
bool LinkList<T>::remove(int i)
{
	bool ret = (i >= 0) && (i <= m_length);

	if (ret)
	{
		Node* pre = reinterpret_cast<Node*>(&m_header);

		pre = position(i);

		Node* toDel = pre->next;
		pre->next = toDel->next;
		delete toDel;
		m_length--;
	}

	return ret;
}

template<class T>
bool LinkList<T>::set(int i, T& e)
{
	bool ret = (i >= 0) && (i <= m_length);

	if (ret)
	{
		Node* pre = reinterpret_cast<Node*>(&m_header);

		pre = position(i);

		pre->next->value = e;
	}

	return ret;
}

template<class T>
T LinkList<T>::get(int i) const
{
	bool ret = (i >= 0) && (i <= m_length);
	T e;

	if (ret)
	{
		Node* pre = reinterpret_cast<Node*>(&m_header);

		pre = position(i);

		e = pre->next->value;
	}

	return e;
}


template<class T>
int  LinkList<T>::length() const
{
	return m_length;
}

template<class T>
void LinkList<T>::clear()
{

	while (m_header.next != NULL)
	{
		Node* toDel = m_header.next;
		m_header.next = toDel->next;
		destroy(toDel);
	}

	m_length = 0;
}

template<class T>
LinkList<T>::~LinkList()
{
	clear();
}

int main()
{
	LinkList<int> l;
	for (int i = 0; i < 5; i++)
	{
		l.insert(i, i);
	}

	for (l.move(0,2); !l.end();l.next())
	{
		cout << l.current() << endl;
	}

	for (int i = 0; i < 5; i++)
	{
		cout << l.find(i) << endl;
	}
	

	return 0;
}