[数据结构与算法] 22.数据结构-单链表的具体实现

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

-> 数据结构与算法 -> 22.数据结构-单链表的具体实现 -> 正文阅读

[数据结构与算法]22.数据结构-单链表的具体实现

文章目录

下面实现上一节单链表的插入和删除操作

LinkList.h(未优化)

#ifndef  __LINK_LIST_
#define  __LINK_LIST_


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

		mutable Node m_header;
		int m_length;
	public:
		LinkList();
		~LinkList();
		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;
}

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 = &m_header;

			for (int pos = 0; pos < i; pos++)
			{
				pre = pre->next;
			}

			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 = &m_header;
		for (int pos = 0; pos < i; pos++)
		{
			pre = pre->next;
		}

		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 = &m_header;
		for (int pos = 0; pos < i; pos++)
		{
			pre = pre->next;
		}

		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 = &m_header;
		for (int pos = 0; pos < i; pos++)
		{
			pre = pre->next;
		}

		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 (int i = 0; i < l.length(); i++)
	{
		cout << l.get(i) << endl;
	}


	return 0;
}

单链表的优化

1.头结点的优化

单链表在构建时必须先创建头结点，头结点在创建时必须调用具体类型的构造函数，如果具体类型的构造函数抛出异常，则单链表对象将构建失败，并会传递具体类型构造函数的异常

class Test
{
public:
  Test()
  {
    throw 0;
  }
};

int main()
{
  LinkedList<Test> l;
  return 0;
}

创建一个内存布局与链表相同的头结点，在创建头结点的时候不会调用构造函数,

mutable struct:public Object
 {
   char reserved[sizeof(T)];//占位空间，与T类型的大小一样
   Node* next;
 }m_header;

2、目标位置定位的代码优化

单链表的操作中经常需要找到目标位置，可以将此部分代码独立出来。

Node* position(int index)const
 {
   //类型转换
   Node* ret = reinterpret_cast<Node*>(&m_header);
 
   for(int i = 0; i < index; i++)
   {
       ret = ret->next;
   }
   return ret;
}

3.增加查找操作

增加一个find操作，查找第一个出现查找值的地方
virtual int find(const T& value)const = 0;

int find(const T& value)const
    {
        int ret = -1;
        Node* node = m_header.next;
        int i = 0;
        while(node)
        {
            if(node->value == value)
            {
                ret = i;
                break;
            }
            else
            {
                node = node->next;
                 i++;
            }
        }
        return ret;
    }

4.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;
		
		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();
		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

5.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;
}

/*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>
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 (int i = 0; i < l.length(); i++)
	{
		cout << l.get(i) << endl;
	}


	return 0;
}