数据结构——Doubly_Linked_List的代码实现

65 阅读 0 评论 43 点赞

我是靠谱客的博主缥缈大雁，最近开发中收集的这篇文章主要介绍数据结构——Doubly_Linked_List的代码实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Reference Book: 《Data Structure and Program Design in C++》

------------------------------------------------------------------------------------------------------------------------------------------------

1. (1) Node.h文件

#ifndef NODE_H_INCLUDED
#define NODE_H_INCLUDED
template <class Node_entry>
struct Node
{
// data members
Node_entry entry;
Node<Node_entry> *next;
Node<Node_entry> *back;
// constructors
Node();
Node(Node_entry item, Node<Node_entry> *link_back = nullptr,
Node<Node_entry> *link_next = nullptr);
// The parameter add_on is set an default value null.
};
#endif // NODE_H_INCLUDED

1. (2) Node.cpp文件

#include "Node.h"
template <class Node_entry>
Node<Node_entry>::Node()
/*Pre:None.
Post:Initialize the next links to Null.
*/
{
back = nullptr;
next = nullptr;
}
template <class Node_entry>
Node<Node_entry>::Node(Node_entry item, Node<Node_entry> *link_back,
Node<Node_entry> *link_next)
/*Pre:None.
Post:Add a first node to Node structure.
*/
{
entry = item;
back = link_back;
next = link_next;
}

2. (1) Doubly_Linked_List.h文件

/**********************************
Doubly_Ordered_List
**********************************/
#ifndef DOUBLY_LINKED_LIST_H
#define DOUBLY_LINKED_LIST_H
#include "Node.h"
namespace
{
enum Error_code{success, range_error, underflow, overflow, fail, not_present};
}
template <class List_entry>
class Doubly_Linked_List
{
public:
Doubly_Linked_List();
int size()const;
bool full()const;
bool empty()const;
void clear();
void traverse(void(*visit)(List_entry &));
Error_code retrieve(int position, List_entry &x)const;
Error_code replace(int position, const List_entry &x);
Error_code remove(int position, List_entry &x);
Error_code insert(int position, const List_entry &x);
~Doubly_Linked_List();
Doubly_Linked_List(const Doubly_Linked_List<List_entry> &copy);
void operator = (const Doubly_Linked_List<List_entry> &copy);
protected:
Node<List_entry> *head;
int count;
mutable int current_position;
// 在const函数中需要修改用mutable
mutable Node<List_entry> *current;
void set_position(int position)const;
private:
};
/*
Implementation of the Class
*/
template <class List_entry>
Doubly_Linked_List<List_entry>::Doubly_Linked_List()
// 构造函数
{
count = 0;
head = current = nullptr;
current_position = -1;
}
template <class List_entry>
Doubly_Linked_List<List_entry>::~Doubly_Linked_List()
// 析构函数
{
clear();
}
template <class List_entry>
Doubly_Linked_List<List_entry>::Doubly_Linked_List(const Doubly_Linked_List<List_entry> &copy)
// 拷贝构造函数
{
count = copy.count;
current_position = copy.current_position;
Node<List_entry> *new_node, *old_node = copy.head;
if(old_node==nullptr)head = current = nullptr;
else
{
new_node = head = new Node<List_entry>(old_node->entry);
while(old_node->next != nullptr)
{
old_node = old_node->next;
new_node->next = new Node<List_entry>(old_node->entry);
new_node->next->back = new_node;
new_node = new_node->next;
}
set_position(current_position);
}
}
template <class List_entry>
void Doubly_Linked_List<List_entry>::operator = (const Doubly_Linked_List<List_entry> &copy)
// 操作符=重载
{
if(this==&copy)return;
// 判断是否进行了自己赋值给自己的操作
//Doubly_Linked_List new_copy(copy);
// 调用拷贝构造函数
clear();
Node<List_entry> *p = copy.head;
int pos = 0;
insert(pos, p->entry);
// 插入第一个元素并设置head指针
head = current;
if(p->next)p->next->back = p;
p = p->next;
pos++;
while(p)
{
insert(pos, p->entry);
if(p->next)p->next->back = p;
// p->next不为空时其back指针指向p所指的结点
p = p->next;
pos++;
}
count = copy.count;
current_position = copy.current_position;

// 不能直接用current = copy.current, 因为copy将被析构

set_position(current_position);
}
template <class List_entry>
int Doubly_Linked_List<List_entry>::size()const
{
return count;
}
template <class List_entry>
bool Doubly_Linked_List<List_entry>::full()const
{
return false;
}
template <class List_entry>
bool Doubly_Linked_List<List_entry>::empty()const
{
return (count<=0);
}
template <class List_entry>
void Doubly_Linked_List<List_entry>::clear()
{
Node<List_entry> *p = head;
for(; p!=nullptr; p = head)
{
head = head->next;
delete p;
}
count = 0;
head = current = nullptr;
current_position = -1;
}
template <class List_entry>
void Doubly_Linked_List<List_entry>::set_position(int position)const
{
// 向后搜索
if(current_position <= position)
for(; current_position != position; current_position++)
current = current->next;
// 向前搜索
else
for(; current_position != position; current_position--)
current = current->back;
}
template <class List_entry>
Error_code Doubly_Linked_List<List_entry>::replace(int position, const List_entry &x)
{
if(position<0 || position>=count)return range_error;
set_position(position);
current->entry = x;
return success;
}
template <class List_entry>
Error_code Doubly_Linked_List<List_entry>::retrieve(int position, List_entry &x)const
{
if(position<0 || position>=count)return range_error;
set_position(position);
x = current->entry;
return success;
}
template <class List_entry>
Error_code Doubly_Linked_List<List_entry>::remove(int position, List_entry &x)
{
Node<List_entry> *previous, *following;
//if(count==0)return fail;
if(position<0 || position>=count)return range_error;
if(position==0)
{
following = head;
current = head = head->next;
// 重设current和head指针
current_position = 0;
if(head)head->back = nullptr;
// 若还有结点将其back置为nullptr
}
else
// 包括了pos在count-1的情况
{
set_position(position-1);
previous = current;
following = current->next;
previous->next = following->next;
if(following->next)following->next->back = previous;
}
x = following->entry;
delete following;
count--;
return success;
}
template <class List_entry>
Error_code Doubly_Linked_List<List_entry>::insert(int position, const List_entry &x)
{
Node<List_entry> *new_node, *following, *preceding;
if(position<0 || position>count)return range_error;
// 在pos==0处进行插入
if(position==0)
{
if(count==0)following = nullptr;
else
{
set_position(0);
following = current;
}
preceding = nullptr;
}
else
{
set_position(position-1);
preceding = current;
following = current->next;
}
new_node = new Node<List_entry>(x, preceding, following);
// 申请新结点
if(new_node==nullptr)return overflow;
// 申请失败
if(preceding!=nullptr)preceding->next = new_node;

if(!preceding)head = new_node;
// 若在pos==0的位置插入重设head指针

if(following!=nullptr)following->back = new_node;
current = new_node;
current_position = position;
count++;
return success;
}
template <class List_entry>
void Doubly_Linked_List<List_entry>::traverse(void (*visit)(List_entry &))
{
Node<List_entry> *to_visit = head;
for(; to_visit; to_visit = to_visit->next)
// 遍历列表中所有元素并执行visit函数
(*visit)(to_visit->entry);
}
#endif // DOUBLY_LINKED_LIST_H