代码拉取完成,页面将自动刷新
#ifndef CIRCULAR_SINGLY_LINKED_LIST_HPP
#define CIRCULAR_SINGLY_LINKED_LIST_HPP
#include <cstddef>
#include <iostream>
#include <exception>
#include "linear_list.h"
using namespace std;
template <class TData>
struct CircularSinglyLinkedNode
{
TData data;
CircularSinglyLinkedNode<TData>* next;
explicit CircularSinglyLinkedNode(CircularSinglyLinkedNode<TData>* next = NULL) :
next(next) {}
explicit CircularSinglyLinkedNode(const TData& data, CircularSinglyLinkedNode<TData>* next = NULL) :
data(data), next(next) {}
};
template <class TData>
class CircularSinglyLinkedList :public LinearList<TData>
{
private:
CircularSinglyLinkedNode<TData>* first_;
CircularSinglyLinkedNode<TData>* last_;
int length_;
public:
CircularSinglyLinkedList() :
first_(NULL), last_(NULL), length_(0) {}
~CircularSinglyLinkedList();
// 获取容器长度
virtual int length() const override { return this->length_; };
virtual bool getData(int pos, TData& data) const override;
// const TData& data ==> const TData * const data
virtual bool setData(int pos, const TData& data) override;
virtual bool insert(int prev_pos, const TData& data) override;
virtual bool remove(int deletion_pos, TData& data) override;
virtual bool isEmpty() const override { return this->first_ == NULL; };
virtual void print() const override;
CircularSinglyLinkedNode<TData>* search(const TData& data) const;
CircularSinglyLinkedNode<TData>* getNode(int pos) const;
void clear();
};
template<class TData>
inline CircularSinglyLinkedList<TData>::~CircularSinglyLinkedList()
{
this->clear();
}
template<class TData>
inline bool CircularSinglyLinkedList<TData>::getData(int pos, TData& data) const
{
if (pos < 1 || pos > this->length_ || this->length_ == 0)
return false;
CircularSinglyLinkedNode<TData>* cur = this->first_;
for (int i = 1; i < pos; i++)
cur = cur->next;
data = cur->data;
return true;
}
template<class TData>
inline bool CircularSinglyLinkedList<TData>::setData(int pos, const TData& data)
{
if (pos < 1 || pos > this->length_)
return false;
CircularSinglyLinkedNode<TData>* cur = this->first_;
for (int i = 1; i < pos; i++)
cur = cur->next;
cur->data = data;
return true;
}
template<class TData>
inline bool CircularSinglyLinkedList<TData>::insert(int prev_pos, const TData& data)
{
if (prev_pos > this->length_ || prev_pos < 0)
return false;
CircularSinglyLinkedNode<TData>* new_node = new CircularSinglyLinkedNode<TData>(data);
if (new_node == NULL)
throw bad_alloc();
if (this->length_ == 0)
{
this->first_ = new_node;
this->first_->next = this->first_;
this->last_ = this->first_;
this->length_ = 1;
return true;
}
CircularSinglyLinkedNode<TData>* prev_node = this->getNode(prev_pos);
new_node->next = prev_node->next;
prev_node->next = new_node;
if (prev_node == 0)
this->first_ = new_node;
if (new_node->next == this->first_)
this->last_ = new_node;
this->length_++;
return true;
}
template<class TData>
inline bool CircularSinglyLinkedList<TData>::remove(int deletion_pos, TData& data)
{
if (deletion_pos < 1 || deletion_pos > this->length_)
return false;
if (this->length_ == 1)
{
data = this->first_->data;
delete this->first_;
this->first_ = NULL;
this->last_ = NULL;
this->length_ = 0;
return true;
}
if (deletion_pos == 1)
{
data = this->first_->data;
CircularSinglyLinkedNode<TData>* deletion_node = this->first_;
this->last_->next = this->first_->next;
this->first_ = this->first_->next;
delete deletion_node;
deletion_node = NULL;
this->length_--;
return true;
}
// 其他情况
CircularSinglyLinkedNode<TData>* prev_node = this->getNode(deletion_pos - 1);
CircularSinglyLinkedNode<TData>* deletion_node = prev_node->next;
if (deletion_node == this->last_)
this->last_ = prev_node;
data = deletion_node->data;
prev_node->next = deletion_node->next;
delete deletion_node;
// 防止出现悬空指针
deletion_node = NULL;
this->length_--;
return true;
}
template<class TData>
inline void CircularSinglyLinkedList<TData>::print() const
{
if (!this->first_)
{
cout << "Empty list" << endl;
return;
}
cout << "打印循环单链表:{ ";
CircularSinglyLinkedNode<TData>* cur = this->first_;
for (int pos = 1; pos <= this->length_; pos++)
{
cout << cur->data;
if (pos != this->length_)
cout << ",";
cur = cur->next;
}
cout << " }" << endl;
}
template<class TData>
inline CircularSinglyLinkedNode<TData>* CircularSinglyLinkedList<TData>::search(const TData& data) const
{
CircularSinglyLinkedNode<TData>* cur = this->first_;
for (int i = 1; i <= this->length_; i++)
{
if (cur->data == data)
return cur;
cur = cur->next;
}
return nullptr;
}
template<class TData>
inline CircularSinglyLinkedNode<TData>* CircularSinglyLinkedList<TData>::getNode(int pos) const
{
if (pos < 0 || pos > this->length_)
return NULL;
if (pos == 0)
return this->last_;
CircularSinglyLinkedNode<TData>* cur = this->first_;
for (int i = 1; i < pos; i++)
cur = cur->next;
return cur;
}
template<class TData>
inline void CircularSinglyLinkedList<TData>::clear()
{
if (this->first_ == NULL)
return;
for (int i = 1; i <= this->length_; i++)
{
CircularSinglyLinkedNode<TData>* target_node = this->first_;
this->first_ = target_node->next;
delete target_node;
target_node = NULL;
}
this->first_ = NULL;
this->last_ = NULL;
this->length_ = 0;
}
#endif // !CIRCULAR_SINGLY_LINKED_LIST_HPP
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。