双向循环链表的C++ OOP实现
// 2020/02/16 Tealer.Guo
// 双向链表
# include
template
struct Node {
T elements;
Node* left; // 左节点
Node* right; // 右节点
Node() {}
Node(const T& this_elem, Node* this_left, Node* this_right) {
elements = this_elem;
left = this_left;
right = this_right;
}
Node(const T& this_elem) {
elements = this_elem;
}
};
template
class linkerList {
public:
linkerList(); // 构造方法
linkerList(linkerList& this_node); // 复制构造方法
int indexOf(const T& this_elem) const;
T& get(int this_index) const;
void insert(int this_index, const T& this_elem);
void erase(int this_index);
int size() const { return list_size; }
bool empty() const { return list_size == 0; }
void output(std::ostream& out) const;
protected:
void checkIndex(int this_index) const;
Node* first_node;
Node* last_node;
int list_size;
};
template
linkerList::linkerList() {
// 构造方法
first_node = last_node =nullptr;
list_size = 0;
}
template
linkerList::linkerList(linkerList& this_node) {
// 复制构造函数
first_node = this_node.first_node;
last_node = this_node.last_node;
list_size = this_node.list_size;
}
template
void linkerList::checkIndex(int this_index) const {
// 检查索引
if(this_index list_size) {
std::cerr << "Out of Index!";
exit(1);
}
}
template
int linkerList::indexOf(const T& this_elem) const {
// 返回索引
Node* this_node = first_node;
int this_index = 0;
while(this_node -> elements != this_elem) {
this_node = this_node -> right;
this_index ++;
}
return this_index;
}
template
T& linkerList::get(int this_index) const {
// 取得元素
checkIndex(this_index);
if(this_index == 0) {
return first_node -> elements;
} else {
// 左 -> 右
Node* this_node = first_node;
for(int i = 0; i right;
}
return this_node -> elements;
}
}
template
void linkerList::insert(int this_index, const T& this_elem) {
// 插入元素
checkIndex(this_index);
if(this_index == 0) {
first_node = new Node(this_elem, last_node, first_node);
last_node = first_node;
} else {
// 左 -> 右
Node* this_node = first_node;
for(int i = 0; i right;
}
this_node -> right = new Node(this_elem, this_node, this_node -> right);
if(this_node -> right -> right != nullptr)
this_node -> right -> right -> left = this_node -> right;
else
last_node = this_node -> right;
}
list_size ++;
}
template
void linkerList::erase(int this_index) {
// 删除元素
checkIndex(this_index);
Node* this_node = first_node;
if(this_index == 0) {
this_node = this_node -> right;
} else {
// 从左向右
for(int i = 0; i right;
}
this_node -> right = this_node -> right -> right;
}
list_size--;
}
template
void linkerList::output(std::ostream& out) const {
// 输出
Node* this_node = first_node;
for(int i = 0; i < list_size; i ++) {
out < elements < right;
}
}
template
std::ostream& operator<<(std::ostream& out, linkerList& this_linker) {
// 重载
this_linker.output(out);
return out;
}
作者:追风_