自制链表容器
1
#include <iostream>
#include <stdexcept>
using namespace std;
template <class T>class list {
private:
//节点类
class node {
public:
node(node* prev, T const& data, node* next) :m_prev(prev), m_data(data), m_next(next) {}
node* m_prev;//前指针
T m_data;//数据
node* m_next;//后指针
};
node* m_hade, * m_tail;//链表头和链表尾
public:
//缺省构造
list() :m_hade(NULL), m_tail(NULL) {}
//拷贝构造
list(list const& that) :m_hade(NULL), m_tail(NULL) {
}
//析构
~list() {
}
//判空
bool empty() {
return (m_hade == NULL && m_tail == NULL);
}
//压栈:头结点
void push_front(T const& data) {
m_hade = new node(NULL, data, m_hade);
if (m_hade->m_next) {
m_hade->m_next->m_prev = m_hade;
}
else {
m_tail = m_hade;
}
}
//弹栈:头结点
void pop_front() {
if (empty())
return;
node* pnode = m_hade->m_next;
delete m_hade;
m_hade = pnode;
if (m_hade) {
m_hade->m_prev = NULL;
}
else {
m_tail = NULL;
}
}
//获取头结点数据
T& front() {
if (empty()) {
throw underflow_error("nul node");
}
return m_hade->m_data;
}
T const& front()const {
return const_cast<list*>(this)->front;
}
//压栈:尾结点
void push_back(T const& data) {
m_tail = new node(m_tail, data, NULL);
if (m_tail->m_prev) {
m_tail->m_prev->m_next = m_tail;
}
else {
m_hade = m_tail;
}
}
//弹栈:尾结点
void pop_back() {
if (empty()) {
return;
}
node* pnode = m_tail->m_prev;
delete m_tail;
m_tail = pnode;
if (m_tail) {
m_tail->m_next = NULL;
}
else {
m_hade = NULL;
}
}
//获取尾结点数据
T& back() {
if (empty()) {
throw underflow_error("nul node");
}
return m_tail->m_data;
}
T const& back() const {
return const_cast<list*>(this)->back();
}
//清空链表
void clear() {
while (!empty()) {
pop_front();
}
}
//获取链表大小
size_t size() {
if (empty()) {
return 0;
}
size_t count = 0;
for (node* pnode = m_hade; pnode; pnode = pnode->m_next) {
++count;
}
return count;
}
friend ostream& operator<<(ostream& os, const list<int>& l);
//重载输出流操作符
};
ostream& operator<<(ostream& os, const list<int>& r) {
for (list<int>::node* pnode = r.m_hade; pnode; pnode = pnode->m_next) {
os << pnode->m_data << ' ';
}
return os;
}
int main()
{
list<int> myList;
for (int i = 0; i < 5; i++) {
myList.push_back(10 + i);
}
cout << myList.size() << endl;;
cout << myList << endl;
myList.pop_back();
cout << myList.back() << endl;
return 0;
}
2
#include <iostream>
#include <stdexcept>
using namespace std;
template <class T>class list {
private:
//节点类
class node {
public:
node(node* prev, T const& data, node* next) :m_prev(prev), m_data(data), m_next(next) {}
node* m_prev;//前指针
T m_data;//数据
node* m_next;//后指针
};
public:
node* m_heda, * m_tail;//链表头和链表尾
//迭代类
class iterator {
public:
iterator(node* start,node* cur,node* end):m_start(start),m_cur(cur),m_end(end){}
T& operator*() {
if (!m_cur) {
throw underflow_error("nul node");
}
return m_cur->m_data;
}
iterator& operator++() {
if (!m_cur) {
this->m_cur = this->m_start;
}
else
{
this->m_cur = m_cur->m_next;
}
return *this;
}
iterator& operator--() {
if (!m_cur) {
m_cur = m_end;
}
else
{
m_cur = m_cur->m_prev;
}
return *this;
}
bool operator==(const iterator& that) const{
return m_start == that.m_start&&
m_cur == that.m_cur&&
m_end == that.m_end;
}
bool operator!=(const iterator& that) const {
return !(*this == that);
}
private:
node* m_start;//开始指向
node* m_cur;//当前指向
node* m_end;//终止指向
friend class list;
};
//常迭代类
class const_iterator {
public:
const_iterator(iterator const& it) :m_it(it) {}
T const& operator*() {
return *m_it;
}
const_iterator & operator++() {
++m_it;
return *this;
}
const_iterator& operator--() {
--m_it;
return *this;
}
bool operator==(const_iterator& that)const {
return m_it == that.m_it;
}
bool operator!=(const_iterator& that)const {
return !(*this == that);
}
private:
iterator m_it;
};
//缺省构造
list() :m_heda(NULL), m_tail(NULL) {}
//拷贝构造
list(list const& that) :m_heda(NULL), m_tail(NULL) {
for (node* pnode = that.m_heda; pnode; pnode = pnode->m_next) {
push_back(pnode->m_data);
}
//that = const_cast<list>(that);
//for (list<T>::iterator it = that.begin(), ite = that.end(); it != ite; it++) {
// push_back(it.m_cur->m_data);
//}
/*for (auto a : that) {
push_back(a.node.m_data);
}
*/
}
//在迭代器指向的位置前添加节点
void insert(iterator const& it, T const& data) {
if (it == end())//如果当前没有节点
{
push_back(data);
}
else
{
node* pnode = new node(it.m_cur->m_prev,data, it.m_cur);
if (pnode->m_prev)//如果没有前一个节点,即在第一个节点前添加节点
{
pnode->m_prev->m_next = pnode;
}
else
{
m_heda = pnode;//在第一个节点之前添加节点
}
pnode->m_next->m_prev = pnode;
}
}
void erase(iterator const& it) {
if (it==end())
{
return;
}
if (it.m_cur->m_prev)//判断是否有前一个节点
{
it.m_cur->m_prev->m_next = it.m_cur->m_next;
}
else
{
m_heda = it.m_cur->m_next;
}
if (it.m_cur->m_prev)//判断是否有后一个节点
{
it.m_cur->m_next->m_prev = it.m_cur->m_prev;
}
else
{
m_tail = it.m_cur->m_prev;
}
delete it.m_cur;
}
//析构
~list() {
clear();
}
//获取遍历迭代器
iterator begin() {
return iterator(m_heda, m_heda, m_tail);
}
//获取标记迭代器
iterator end() {
return iterator(m_heda, NULL ,m_tail);
}
//获取常遍历迭代器
const_iterator begin()const {
return iterator(m_heda, m_heda, m_tail);
}
//获取常结束标记迭代器
const_iterator end()const {
return iterator(m_heda, NULL, m_tail);
}
//判空
bool empty() {
return (m_heda == NULL && m_tail == NULL);
}
//压栈:头结点
void push_front(T const& data) {
m_heda = new node(NULL, data, m_heda);
if (m_heda->m_next) {
m_heda->m_next->m_prev = m_heda;
}
else {
m_tail = m_heda;
}
}
//弹栈:头结点
void pop_front() {
if (empty())
return;
node* pnode = m_heda->m_next;
delete m_heda;
m_heda = pnode;
if (m_heda) {
m_heda->m_prev = NULL;
}
else {
m_tail = NULL;
}
}
//获取头结点数据
T& front() {
if (empty()) {
throw underflow_error("nul node");
}
return m_heda->m_data;
}
T const& front()const {
return const_cast<list*>(this)->front;
}
//压栈:尾结点
void push_back(T const& data) {
m_tail = new node(m_tail, data, NULL);
if (m_tail->m_prev) {
m_tail->m_prev->m_next = m_tail;
}
else {
m_heda = m_tail;
}
}
//弹栈:尾结点
void pop_back() {
if (empty()) {
return;
}
node* pnode = m_tail->m_prev;
delete m_tail;
m_tail = pnode;
if (m_tail) {
m_tail->m_next = NULL;
}
else {
m_heda = NULL;
}
}
//获取尾结点数据
T& back() {
if (empty()) {
throw underflow_error("nul node");
}
return m_tail->m_data;
}
T const& back() const {
return const_cast<list*>(this)->back();
}
//清空链表
void clear() {
while (!empty()) {
pop_front();
}
}
//获取链表大小
size_t size() {
if (empty()) {
return 0;
}
size_t count = 0;
//for (node* pnode = m_heda; pnode; pnode = pnode->m_next) {
// ++count;
//}
for (auto it = begin(), ite = end(); it != ite; ++it) {
++count;
}
return count;
}
};
template<class IT, class T>
IT find(IT begin,IT end, T const& data) {
for(IT it=begin;it!=end;++it){
if (*it == data) {
return it;
}
}
return end;
}
/*
* 5 8 9 3 4 7 6
* p
* i
* j
*
* i++;j--
* p 和谁相同谁不能动,另一个做自增或自减
* p 和谁交换数据,p 就和谁相同
* 4 3 5 9 8 7 6
* p
* i
* j
* p,i,j,都相同时在进行左右递归
*/
template<class IT>
void sort(IT begin, IT end) {
IT p = begin;
IT last = end;//尾结点的下一个位置
--last;//尾结点
for (IT i = begin, j = last; i != j;)
{
while (i!=p && *i<*p)
{
++i;
}
if (i!=p)
{
swap(*i, *p);
p = i;
}
while (j!=p&&*p<*j)
{
--j;
}
if (j!=p)
{
swap(*j, *p);
p = j;
}
}
IT it = begin;
++it;
if (p != begin && p != it) {
sort(begin, p);
}
it = p;
++it;
if (it != end && it != last) {
sort(it, end);
}
}
template<class IT,class CMP>
void sort(IT begin, IT end,CMP cmp) {
IT p = begin;
IT last = end;//尾结点的下一个位置
--last;//尾结点
for (IT i = begin, j = last; i != j;)
{
while (i != p && cmp(*i, *p))
{
++i;
}
if (i != p)
{
swap(*i, *p);
p = i;
}
while (j != p && cmp(*p , *j))
{
--j;
}
if (j != p)
{
swap(*j, *p);
p = j;
}
}
IT it = begin;
++it;
if (p != begin && p != it) {
sort(begin, p,cmp);
}
it = p;
++it;
if (it != end && it != last) {
sort(it, end,cmp);
}
}
//比较类 提供给比较器使用
class CMP
{
public:
bool operator()(int const& i, int const& j) {
return i < j; //比较器升序和降序由此行决定
}
};
void print(const list<int>& ls) {
typedef list<int>::const_iterator IT;
for (IT it = ls.begin(),ite = ls.end();it!=ite; ++it)
//for(auto a:ls)
{
cout << *it<<" ";
//cout << a << endl;
}
cout << endl;
}
int main()
{
list<int> myList;
for (int i = 0; i < 5; i++) {
myList.push_back(10 - i);
}
for (auto it = myList.begin(), ite = myList.end(); it != ite; ++it) {
if (*it==13)
{
myList.insert(it, 111);
myList.erase(it);
}
}
list<int> myList2(myList);
print(myList);
const list<int> cls=myList;
auto i = ::find(myList.begin(), myList.end(), 111);
if (i!=myList.end())
{
myList.erase(i);
}
else
{
cout << "没有找到" << endl;
}
CMP cmp;
sort(myList.begin(), myList.end(),cmp);
print(myList);
return 0;
}
