1 Star 0 Fork 0

郑玉强/dataStructure

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
circular_singly_linked_list.hpp 5.35 KB
一键复制 编辑 原始数据 按行查看 历史
郑玉强 提交于 2024-10-06 16:23 +08:00 . 临时提交
#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
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/zheng-yuqiang_lyg_cn/data-structure.git
git@gitee.com:zheng-yuqiang_lyg_cn/data-structure.git
zheng-yuqiang_lyg_cn
data-structure
dataStructure
dev01

搜索帮助