首页 > > 程序设计 > C/C++ >

线性表

2018-06-17 22:48:08来源：未知 阅读 ()

新老客户大回馈,云服务器低至5折

下面说的线性表主要是线性链表，这里主要将双向链表，单向链表循环链表等是类似的，不再累述。如果发现错误，还望不吝指正。

定义

线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。
在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。
线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。
线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。（来自百度百科）

实现

采用的C++实现整个链表的操作过程，对于节点的内存的管理使用了C++11中提供的智能指针shared_ptr，以确保不会发生内存泄露的情况。

对链表操作的实现中采用了两层封装，将涉及到指针的操作封装成了私有方法，避免泄露指针，导致无法控制对象析构的时刻，并且整个链表是非线程安全的。

节点数据结构：

template <typename T>
class Node {
public:
	Node() { _prev = nullptr, _next = nullptr; }
	Node(T data) : Node() { _data = data; }
	void set_data(T data) { _data = data; }
	void set_prev(std::shared_ptr<Node<T>> prev) { _prev = prev; }
	void set_next(std::shared_ptr<Node<T>> next) { _next = next; }
	std::shared_ptr<Node<T>> prev() { return _prev; }
	std::shared_ptr<Node<T>> next() { return _next; }
	T data() { return _data; }

private:
	T _data;
	std::shared_ptr<Node<T>> _prev;
	std::shared_ptr<Node<T>> _next;
};

整个表结构：

整个表包含一个指向头结点的指针和一个指向尾节点的指针，以及表的长度和表的大小的变量。

template <typename T>
class LinearList
{
public:
	LinearList();
	~LinearList();
	void insert_node(T data, int64_t index);
	void delete_node(int64_t index, T& data);
	T get_element(int64_t index);
	int64_t size();
	int64_t length();

private:
	std::shared_ptr<Node<T>> get_ptr(int64_t index);
	std::shared_ptr<Node<T>> get_element_ptr(int64_t index);
	void insert_node_ptr(std::shared_ptr<Node<T>> &data, int64_t index);
	void delete_node_ptr(int64_t index, std::shared_ptr<Node<T>> &data);

private:
	std::shared_ptr<Node<T>> _current;
	std::shared_ptr<Node<T>> _head;
	std::shared_ptr<Node<T>> _tail;
	int64_t _current_index;
	int64_t _size;
	int64_t _length;
};

 

插入新节点：　　

整个链表是一个带空头结点的链表：

1. 寻找插入点

2. 将待插入节点的next指针指向插入点指向的下一节点

3. 将待插入节点的prev指针指向插入点

4. 如果插入点的next指针不为空（不是头结点），将插入点的下一节点的prev指针指向带插入节点

5. 将插入点的next指针指向待插入点

 

 图画的比较丑，简单的表示下程序的执行过程 

template<typename T>
inline void LinearList<T>::insert_node(T data, int64_t index)
{
	if (index < 0 || index > _length)
	{
		index = _length;
	}
	std::shared_ptr<Node<T>> data_ptr = std::make_shared<Node<T>>(data);
	this->insert_node_ptr(data_ptr, index);
}

inline void LinearList<T>::insert_node_ptr(std::shared_ptr<Node<T>> &data, int64_t index)
{
	_ASSERTE(!(index < 0 || index > _length));
	std::shared_ptr<Node<T>> tmp_ptr(_head);
	// 查找插入位置
	for (int64_t i = 0; i < index; ++i)
	{
		tmp_ptr = tmp_ptr->next();
	}
	// 将data插入到tmp_ptr的后面
	data->set_next(tmp_ptr->next());
	data->set_prev(tmp_ptr);
	tmp_ptr->next() == nullptr ? tmp_ptr : tmp_ptr->next()->set_prev(data);
	tmp_ptr->set_next(data);
	_tail = index == _length ? data : _tail;
	++_length;
	_size += sizeof(Node<T>);
}

删除节点：

1.  查找待删除节点

2. 断开其prev和next指针

然后delete掉tmp_ptr指针，此处用的智能指针，当离开该作用域后，2号节点的引用计数为0，会自动释放2号节点的空间

template<typename T>
inline void LinearList<T>::delete_node(int64_t index, T & data)
{
	if (index < 0 || index > _length)
	{
		index = _length;
	}

	std::shared_ptr<Node<T>> tmp_ptr;
	delete_node_ptr(index, tmp_ptr);
	data = tmp_ptr->data();
}

template<typename T>
inline void LinearList<T>::delete_node_ptr(int64_t index, std::shared_ptr<Node<T>>& data)
{
	_ASSERTE(!(index < 0 || index > _length));
	std::shared_ptr<Node<T>> tmp_ptr(_head->next());
	// 查找待删除节点
	for (int64_t i = 0; i < index; ++i) 
	{
		tmp_ptr = tmp_ptr->next();
	}
	tmp_ptr->prev() == nullptr ? nullptr : tmp_ptr->prev()->set_next(tmp_ptr->next());
	tmp_ptr->next() == nullptr ? nullptr : tmp_ptr->next()->set_prev(tmp_ptr->prev());
	data = tmp_ptr;
	--_length;
	_size -= sizeof(Node<T>);
	_current = _head;
	_current_index = 0;
}

查看某个节点：

此处为了降低遍历时的时间复杂度，故添加了一个游标指针以及游标下标，用于指向刚访问过的节点，故在遍历时不用每次都从头结点遍历到尾节点。

inline T LinearList<T>::get_element(int64_t index)
{
	std::shared_ptr<Node<T>> result_ptr = get_ptr(index);
	if (!result_ptr)
	{
		throw new std::exception("could not found.");
	}
	return result_ptr->data();
}

template<typename T>
inline std::shared_ptr<Node<T>> LinearList<T>::get_ptr(int64_t index)
{
	_ASSERTE(!(index < 0 || index > _length - 1));
	int64_t max_index = _length - 1;
	int64_t min_index = 0;
	int64_t low_index = 0;
	int64_t high_index = max_index;
	low_index = index >= _current_index ? _current_index : min_index;
	high_index = index >= _current_index ? max_index : _current_index;
	if ((index - low_index) <= (high_index - index))	// 正向遍历
	{
		_current = low_index == min_index ? _head->next() : _current;
		_current_index = low_index == min_index ? min_index : _current_index;
		while (_current && index != _current_index)
		{
			_current = _current->next();
			++_current_index;
		}
	}
	else  // 逆向遍历
	{
		_current = high_index == max_index ? _tail : _current;
		_current_index = high_index == max_index ? max_index : _current_index;
		while (_current && index != _current_index)
		{
			_current = _current->prev();
			--_current_index;
		}
	}
	return _current;
}

主函数：

int main() {

	LinearList<int> linear_list;
	for (int64_t i = 0; i < 10; i++)
	{
		linear_list.insert_node(i, i);
	}

	std::cout << "逆向遍历节点：" << std::endl;
	for (int64_t i = linear_list.length() - 1; i >= 0; --i)
	{
		std::cout << linear_list.get_element(i) << " ";
	}
	std::cout << std::endl << std::endl;

	std::cout << "正向遍历节点：" << std::endl;
	for (int64_t i = 0; i < linear_list.length(); ++i) {
		std::cout << linear_list.get_element(i) << " ";
	}
	std::cout << std::endl << std::endl;

	std::cout << "删除第2个节点： " << std::endl;
	int data;
	linear_list.delete_node(2, data);
	std::cout << data << std::endl << std::endl;

	std::cout << "逆向遍历节点：" << std::endl;
	for (int64_t i = linear_list.length() - 1; i >= 0; --i)
	{
		std::cout << linear_list.get_element(i) << " ";
	}
	std::cout << std::endl << std::endl;

	std::cout << "第2个节点已删除，再次遍历结果为：" << std::endl;
	for (int64_t i = 0; i < linear_list.length(); ++i) {
		std::cout << linear_list.get_element(i) << " ";
	}
	std::cout << std::endl << std::endl;

	std::cout << "删除第2个节点： " << std::endl;
	linear_list.delete_node(2, data);
	std::cout << data << std::endl << std::endl;

	std::cout << "逆向遍历节点：" << std::endl;
	for (int64_t i = linear_list.length() - 1; i >= 0; --i)
	{
		std::cout << linear_list.get_element(i) << " ";
	}
	std::cout << std::endl << std::endl;

	std::cout << "第2个节点已删除，再次遍历结果为：" << std::endl;
	for (int64_t i = 0; i < linear_list.length(); ++i) {
		std::cout << linear_list.get_element(i) << " ";
	}
	std::cout << std::endl << std::endl;

	return 0;
}

　　

运行结果为：

 

 代码下载地址：https://github.com/wuhui2356/data_structure/tree/master/LinearList

　　

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：【zzulioj 2135】 这里是天堂！

下一篇：1365 浴火银河星际跳跃

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签