C++ 单向链表手动实现（课后作业版）
2024-10-21 18:52:04
单向链表，并实现增删查改等功能
首先定义节点类，类成员包含当前节点的值和下一个节点的地址
/node definition
template <typename T>
class Node {
public:
T value;
Node<T>* next;
Node() {}
Node(const T& value) {
this->value = value;
next = nullptr;
}
Node(const T& value, const Node<T>& next) {
this->value = value;
this->next = next;
}
};然后是链表类的定义，主要包含了增删查改等功能
//linklist definition
template <typename T>
class LinkList {
public:
Node<T>* headnode;
LinkList();
LinkList(const T* arr, int len); //array initial
LinkList(const LinkList<T>& link);
~LinkList();
LinkList<T>& push_back(T n);
LinkList<T>& push_front(T n);
LinkList<T>& insert(int pos, int n, T* arr);
LinkList<T>& pop_front();
LinkList<T>& pop_back();
LinkList<T>& remove(int pos, int num);
LinkList<T>& reverse();
T& operator[](int n);
T& at(int n);
LinkList<T>& replace(int pos, int n, T* arr);
int getLen() {return len;}
void clear() {this->~LinkList();}
void display();
private:
int len = 0;
Node<T>* getNode(int n);
};各个函数解释：
LinkList(); 默认构造函数
LinkList(const T* arr, int len); 一般构造函数
LinkList(const LinkList<T>& link) 拷贝构造函数
~LinkList(); 析构函数
LinkList<T>& push_back(T n); 在尾部添加一个元素
LinkList<T>& push_front(T n); 在头部添加一个元素
LinkList<T>& insert(int pos, int n, T* arr); 在pos处插入n个元素
LinkList<T>& pop_front(); 删除第一个节点
LinkList<T>& pop_back(); 删除最后一个节点
LinkList<T>& remove(int pos, int num); 删除pos开始的num个元素
LinkList<T>& reverse(); 反转链表
T& operator[](int n); 重载[ ]运算符，返回第n个节点的值
T& at(int n); 与[ ]一样，只不过会检查索引是否越界
LinkList<T>& replace(int pos, int n, T* arr); 替换n个节点
int getLen() {return len;} 返回长度，因为len是private
void clear() {this->~LinkList();} 清除链表
void display(); 显示链表所有元素
Node<T>* getNode(int n); 返回第n个节点的指针，是private函数，在其他函数中经常用到
最后是各个成员函数的定义：
#include <iostream>
using namespace std;
//node definition
template <typename T>
class Node {
public:
T value;
Node<T>* next;
Node() {}
Node(const T& value) {
this->value = value;
next = nullptr;
}
Node(const T& value, const Node<T>& next) {
this->value = value;
this->next = next;
}
};
//linklist definition
template <typename T>
class LinkList {
public:
Node<T>* headnode;
LinkList();
LinkList(const T* arr, int len); //array initial
LinkList(const LinkList<T>& link);
~LinkList();
LinkList<T>& push_back(T n);
LinkList<T>& push_front(T n);
LinkList<T>& insert(int pos, int n, T* arr);
LinkList<T>& pop_front();
LinkList<T>& pop_back();
LinkList<T>& remove(int pos, int num);
LinkList<T>& reverse();
T& operator[](int n);
T& at(int n);
LinkList<T>& replace(int pos, int n, T* arr);
int getLen() {return len;}
void clear() {this->~LinkList();}
void display();
private:
int len = 0;
Node<T>* getNode(int n);
};
//default constructor
template <typename T>
LinkList<T>::LinkList() {
headnode = nullptr;
len = 0;
}
//normal constructor
template <typename T>
LinkList<T>::LinkList(const T* arr, int len) {
Node<T>* temp = nullptr;
Node<T>* node = nullptr;
if ( len < 0 ) {
cout << "[error]: illegal length of LinkList" << endl;
exit(0);
}
for ( int i = len-1; i >= 0; i-- ) {
node = new Node<T>(i);
node->value = *(arr+i);
node->next = temp;
temp = node;
node = nullptr;
}
headnode = temp;
this->len = len;
}
//copy constructor
template <typename T>
LinkList<T>::LinkList(const LinkList<T>& link) {
this->len = link.getLen();
this->headnode = link.headnode;
link.headnode = nullptr;
}
//deconstructor
template <typename T>
LinkList<T>::~LinkList() {
this->len = 0;
Node<T>* temp = headnode;
while ( headnode ) {
temp = headnode;
headnode = headnode->next;
delete temp;
temp = nullptr;
}
}
//display all elements in Linklist<T>
template <typename T>
void LinkList<T>::display() {
if ( len == 0 ) {
cout << "[warning]: can not disply empty linkedlist" << endl;
return;
}
Node<T> *node = headnode;
for ( int i = 0; i < len; i++ ) {
cout << node->value << " ";
node = node->next;
}
cout << endl;
}
//add one node at the last position
template <typename T>
LinkList<T>& LinkList<T>::push_back(T n) {
Node<T> *node = this->getNode(len-1);
if ( node->next == nullptr ) {
Node<T> *temp = new Node<T>(n);
node->next = temp;
this->len++;
}
return *this;
}
//add one node at the first position
template <typename T>
LinkList<T>& LinkList<T>::push_front(T n) {
Node<T>* node_new = new Node<T>(n);
node_new->next = headnode;
headnode = node_new;
this->len++;
return *this;
}
//insert elements to LinkList
template <typename T>
LinkList<T>& LinkList<T>::insert(int pos, int n, T* arr) {
if ( pos > len-1 || len < 0 ) {
cout << "[error]: illegal insert position, please check again" << endl;
exit(0);
}
if ( pos == 0 ) {
for ( int i = 0; i < n; i++ )
this->push_front(arr[n-1-i]);
return *this;
}
Node<T>* node_N = getNode(pos-1); //前半部分
Node<T>* temp = node_N->next; //后半部分
Node<T>* node_new = nullptr; //新增加的
for ( int i = 0; i < n; i++ ) {
node_new = new Node<T> (arr[n-1-i]);
node_new->next = temp;
temp = node_new;
node_new = nullptr;
}
node_N->next = temp;
this->len += n;
return *this;
}
//delete the first element
template <typename T>
LinkList<T>& LinkList<T>::pop_front() {
if ( this->len == 0 ) {
cout << "[error]: LinkList don't has any element" << endl;
exit(0);
}
Node<T>* temp = headnode;
headnode = getNode(1);
delete temp;
this->len--;
return *this;
}
//delete the last element
template <typename T>
LinkList<T>& LinkList<T>::pop_back() {
if ( this->len == 0 ) {
cout << "[error]: LinkList don't has any element" << endl;
exit(0);
}
Node<T>* temp = getNode(len-2);
delete temp->next;
temp->next = nullptr;
this->len--;
return *this;
}
//get the last node pointer
template <typename T>
Node<T>* LinkList<T>::getNode(int n) {
if ( n > len-1 || n < 0) {
cout << "[error]: index out of range" <<endl;
}
Node<T> *node = headnode;
for( int i = 0; i < n; i++ ) {
node = node->next;
}
return node;
}
//remove n elements
template <typename T>
LinkList<T>& LinkList<T>::remove(int pos, int num) {
if ( pos > len-1 || len < 0 ) {
cout << "[error]: illegal remove position, please check again" << endl;
exit(0);
} else if ( pos + num > len) {
cout << "[error]: remove index out of range" << endl;
exit(0);
}
if ( pos == 0 ) {
for ( int i = 0; i < num; i++ )
this->pop_front();
return *this;
}
Node<T>* node_N = getNode(pos-1);
Node<T>* node_N_num = getNode(pos+num);
Node<T>* temp = getNode(pos);
while ( 1 ) {
Node<T>* node = temp;
temp = temp->next;
delete node;
if ( temp == node_N_num ) {
break;
}
}
node_N->next = node_N_num;
this->len -= num;
return *this;
}
//reverse linklist
template <typename T>
LinkList<T>& LinkList<T>::reverse() {
Node<T>* front = nullptr;
Node<T>* mid = headnode;
Node<T>* back = headnode->next;
while ( back ) {
mid->next = front;
front = mid;
mid = back;
back = back->next;
}
mid->next = front;
front = nullptr;
headnode = mid;
return *this;
}
template <typename T>
T& LinkList<T>::operator[](int n) {
if ( n > len-1 || n < 0 ) {
cout << "[error]: index out of range" << endl;
exit(0);
}
return this->getNode(n)->value;
}
template <typename T>
LinkList<T>& LinkList<T>::replace(int pos, int n, T* arr) {
if ( pos > len-1 || len < 0 ) {
cout << "[error]: illegal remove position, please check again" << endl;
exit(0);
} else if ( pos + n > len) {
cout << "[error]: remove index out of range" << endl;
exit(0);
}
Node<T>* temp = nullptr;
if ( pos == 0 )
temp = headnode;
else
temp = this->getNode(pos-1);
for ( int i = 0; i < n; i++ ) {
temp->value = arr[i];
temp = temp->next;
}
return *this;
}
int main(){
int arr[]{1,2,4,5,0};
LinkList<int> link(arr, sizeof(arr)/sizeof(int));
cout << "LinkLint init with arr: " <<endl;
link.display();
cout << "push_back:" << endl;
link.push_back(34);
link.display();
cout << "push_front:" << endl;
link.push_front(10);
link.display();
cout << "insert:" << endl;
link.insert(0,4,arr);
link.display();
cout << "pop_front:" << endl;
link.pop_front();
link.display();
cout << "pop_back:" << endl;
link.pop_back();
link.display();
cout << "remove:" << endl;
link.remove(2,3);
link.display();
cout << "[] operator:" << endl;
cout << link[2] << endl;
cout << "replace:" << endl;
int a[] = {6,5,2};
link.replace(2, sizeof(a)/sizeof(int), a);
link.display();
cout << "linklist reserve:" << endl;
link.reverse();
link.display();
cout << "clear:" << endl;
link.clear();
cout << "len=" << link.getLen() << endl;
link.display();
}
最新文章
- RandHelper
- Hibernate组件映射
- O2O营销模式(Online To Offline)
- Adele的生活
- 【学习笔记】【C语言】scanf函数
- C语言使用中的细节问题总结
- NOIP2001 一元三次方程求解
- pre标签 首行会自动换行解决方案
- ActiveMQ (一) 初识ActiveMQ
- 浅析深度学习mini_batch的BP反传算法
- openstack快速安装之packstack
- 从零开始学习PYTHON3讲义（六）for循环跟斐波那契数列
- Redux的工作流程
- Codeforces 837 简要题解
- Jenkins构建部署Maven项目
- python函数式编程——偏函数
- shell 脚本部分变量含义
- flask的安装
- verilog语法实例学习(5)
- Sword redis配置