#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdlib.h>
#include <iostream>
using namespace std;
template<class T>
struct ListNode
{
? ? ListNode(const T& data = T())
? ? : _pPre(0)
? ? , _pNext(0)
? ? , _data(data)
? ? {}
? ? ListNode<T>* _pPre;
? ? ListNode<T>* _pNext;
? ? T _data;
};
//迭代器
template<class T,class Ref,class Ptr>
class ListIterator
{
? ? typedef ListIterator<T, Ref, Ptr> Self;
public:
? ? ListIterator()
? ? ? ? :_pCur(0)
? ? {}
? ? ListIterator(ListNode<T>* pCur)
? ? ? ? : _pCur(pCur)
? ? {}
? ? ListIterator(const Self& s)
? ? ? ? : _pCur(s._pCur)
? ? {}
? ? Ref operator*()
? ? {
? ? ? ? return _pCur->_data;
? ? }
? ? Ptr operator->()
? ? {
? ? ? ? return &(operator*());
? ? ? ? //return &(_pCur->_data);
? ? }
? ? Self& operator++()
? ? {
? ? ? ? _pCur = _pCur->_pNext;
? ? ? ? return*this;
? ? }
? ? Self operator++(int)
? ? {
? ? ? ? Self temp(*this);
? ? ? ? _pCur = _pCur->_pNext;
? ? ? ? return temp;
? ? }
? ? Self& operator--()
? ? {
? ? ? ? _pCur = _pCur->_pPre;
? ? ? ? return*this;
? ? }
? ? Self operator--(int)
? ? {
? ? ? ? Self temp(*this);
? ? ? ? _pCur = _pCur->_pPre;
? ? ? ? return temp;
? ? }
? ? bool operator!=(const Self& s)
? ? {
? ? ? ? return _pCur != s._pCur;
? ? }
? ? bool operator==(const Self& s)
? ? {
? ? ? ? return _pCur == s._pCur;
? ? }
? ? ListNode<T>* _pCur;
};
template <class T>
class List
{
public:
? ? typedef ListIterator<T, T&, T*> Iterator;
? ? typedef ListNode<T> Node;
public:
? ? List()//無參構(gòu)造函數(shù)
? ? ? ? : _pHead(new Node)
? ? {
? ? ? ? _pHead->_pNext = _pHead;//帶頭節(jié)點(diǎn)的循環(huán)鏈表
? ? ? ? _pHead->_pPre = _pHead;
? ? }
? ? List(const T* array, size_t size)//有參構(gòu)造函數(shù)
? ? ? ? :_pHead(new Node)
? ? {
? ? ? ? _pHead->_pNext = _pHead;
? ? ? ? _pHead->_pPre = _pHead;
? ? ? ? for (size_t i = 0; i < size; i++)
? ? ? ? {
? ? ? ? ? ? PushBack(array[i]);
? ? ? ? }
? ? }
? ? List(const List<T>& l)//拷貝構(gòu)造函數(shù)
? ? ? ? :_pHead(new Node)
? ? {
? ? ? ? _pHead->_pNext = _pHead;
? ? ? ? _pHead->_pPre = _pHead;
? ? ? ? Node* cur = l._pHead->_pNext;
? ? ? ? for (size_t i = 0; i < l.Size();i++)
? ? ? ? {
? ? ? ? ? ? PushBack(cur->_data);
? ? ? ? ? ? cur = cur->_pNext;
? ? ? ? }
? ? }
? ? List<T>& operator=(const List<T>& l)//賦值運(yùn)算符重載
? ? {
? ? ? ? if (this != &l)
? ? ? ? {
? ? ? ? ? ? Node* pRet = l._pHead->_pNext;
? ? ? ? ? ? for (size_t i = 0; i < l.Size(); i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? PushBack(pRet->_data);
? ? ? ? ? ? ? ? pRet = pRet->_pNext;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return *this;
? ? }
? ? ~List()//析構(gòu)函數(shù)
? ? {
? ? ? ? Clear();
? ? ? ? delete _pHead;
? ? ? ? _pHead = NULL;
? ? }
? ? Iterator Begin()
? ? {
? ? ? ? return Iterator(_pHead->_pNext);
? ? }
? ? Iterator End()
? ? {
? ? ? ? return Iterator(_pHead);
? ? }
? ? void PushBack(const T& data)//尾插
? ? {
? ? ? ? Node* _pNewNode = new Node(data);
? ? ? ? if (Empty())//鏈表為空
? ? ? ? {
? ? ? ? ? ? _pHead->_pNext = _pNewNode;
? ? ? ? ? ? _pHead->_pPre = _pNewNode;
? ? ? ? ? ? _pNewNode->_pNext = _pHead;
? ? ? ? ? ? _pNewNode->_pPre = _pHead;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? Node* pTail = _pHead->_pPre;
? ? ? ? ? ? pTail->_pNext = _pNewNode;
? ? ? ? ? ? _pNewNode->_pNext = _pHead;
? ? ? ? ? ? _pNewNode->_pPre = pTail;
? ? ? ? ? ? _pHead->_pPre = _pNewNode;
? ? ? ? }
? ? }
? ? void PopBack()//尾刪
? ? {
? ? ? ? if (Empty())//鏈表為空
? ? ? ? {
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? Node* del = _pHead->_pPre;//要刪除的節(jié)點(diǎn)
? ? ? ? ? ? Node* tail = del->_pPre;//新的尾節(jié)點(diǎn)
? ? ? ? ? ? delete del;
? ? ? ? ? ? tail->_pNext = _pHead;
? ? ? ? ? ? _pHead->_pPre = tail;
? ? ? ? }
? ? }
? ? void PushFront(const T& data)//頭插
? ? {
? ? ? ? Node* _pNewNode = new Node(data);
? ? ? ? _pHead->_pNext->_pPre = _pNewNode;
? ? ? ? _pNewNode->_pNext = _pHead->_pNext;
? ? ? ? _pNewNode->_pPre = _pHead;
? ? ? ? _pHead->_pNext = _pNewNode;
? ? }
? ? void PopFront()//頭刪
? ? {
? ? ? ? if (Empty())
? ? ? ? {
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? Node* pDel = _pHead->_pNext;
? ? ? ? ? ? _pHead->_pNext = pDel->_pNext;
? ? ? ? ? ? pDel->_pNext->_pPre = _pHead;
? ? ? ? ? ? delete pDel;
? ? ? ? }
? ? }
? ? Iterator Insert(Iterator pos, const T& data)//任意位置插入
? ? {
? ? ? ? Node* _pNewNode = new Node(data);
? ? ? ? pos._pCur->_pPre->_pNext = _pNewNode;
? ? ? ? _pNewNode->_pNext = pos._pCur;
? ? ? ? _pNewNode->_pPre = pos._pCur->_pPre;
? ? ? ? pos._pCur->_pPre = _pNewNode;
? ? ? ? return Iterator(_pNewNode);
? ? }
? ? Iterator Erase(Iterator pos)//任意位置刪除
? ? {
? ? ? ? Node* pCur = pos._pCur->_pNext;
? ? ? ? pos._pCur->_pNext->_pPre = pos._pCur->_pPre;
? ? ? ? pos._pCur->_pPre->_pNext = pos._pCur->_pNext;
? ? ? ? delete pos._pCur;
? ? ? ? return Iterator(pCur);
? ? }
? ? Iterator Find(const T& d)//通過迭代器來查找
? ? {
? ? ? ? Iterator it = Begin();
? ? ? ? while (it != End())
? ? ? ? {
? ? ? ? ? ? if ((*it) == d)
? ? ? ? ? ? ? ? return it;
? ? ? ? ? ? it++;
? ? ? ? }
? ? ? ? return End();
? ? }
? ? bool Empty()const//判斷鏈表是否為空
? ? {
? ? ? ? return _pHead->_pNext == _pHead;
? ? }
? ? size_t Size()const//返回鏈表元素個數(shù)
? ? {
? ? ? ? Node* pCur = _pHead->_pNext;
? ? ? ? size_t count = 0;
? ? ? ? while (pCur != _pHead)
? ? ? ? {
? ? ? ? ? ? ++count;
? ? ? ? ? ? pCur = pCur->_pNext;
? ? ? ? }
? ? ? ? return count;
? ? }
? ? T& Front()//返回第一個節(jié)點(diǎn)
? ? {
? ? ? ? return _pHead->_pNext->_data;
? ? }
? ? const T& Front()const
? ? {
? ? ? ? return _pHead->_pNext->_data;
? ? }
? ? T& Back()//返回尾節(jié)點(diǎn)
? ? {
? ? ? ? return _pHead->_pPre->_data;
? ? }
? ? const T& Back()const
? ? {
? ? ? ? return _pHead->_pPre->_data;
? ? }
? ? void Clear()//清空鏈表
? ? {
? ? ? ? Iterator it = Begin();
? ? ? ? while (it != End())
? ? ? ? {
? ? ? ? ? ? it = Erase(it);
? ? ? ? }
? ? ? ? _pHead->_pNext = _pHead;
? ? ? ? _pHead->_pPre = _pHead;
? ? }
private:
? ? ListNode<T>* _pHead;
};
void PrintList( List<int>& l)//打印鏈表
{
? ? List<int>::Iterator It = l.Begin();
? ? while (It != l.End())
? ? {
? ? ? ? cout << *It << " ";
? ? ? ? ++It;
? ? }
? ? cout << endl;
}
/*------------------------------------------------------------------------------測試代碼----------------------------------------------------------------------------------*/
void FunTest1()
{
? ? //無參構(gòu)造函數(shù)
? ? List<int> l1;
? ? //有參構(gòu)造函數(shù)
? ? int arr[5] = { 1, 2, 3, 4, 5 };
? ? List<int> l2(arr, 5);
? ? PrintList(l2);
? ? //拷貝構(gòu)造函數(shù)
? ? List<int> l3(l2);
? ? //賦值運(yùn)算符重載
? ? l1 = l2;
}
void FunTest2()
{
? ? List<int> l1;
? ? l1.PushBack(1);
? ? l1.PushBack(2);
? ? l1.PushBack(3);
? ? l1.PushBack(4);
? ? l1.PushBack(5);
? ? l1.PushBack(6);
? ? l1.PushFront(7);
? ? PrintList(l1);
? ? cout << l1.Size() << endl;
? ? l1.PopBack();
? ? l1.PopBack();
? ? l1.PopBack();
? ? l1.PopFront();
? ? l1.PopFront();
? ? PrintList(l1);
? ? cout << l1.Size() << endl;
}
void FunTest3()
{
? ? List<int> l1;
? ? l1.PushBack(1);
? ? l1.PushBack(2);
? ? l1.PushBack(3);
? ? l1.PushBack(4);
? ? l1.PushBack(5);
? ? List<int>::Iterator pos = l1.Find(3);
? ? l1.Insert(pos, 0);
? ? PrintList(l1);
? ? l1.Erase(pos);
? ? PrintList(l1);
}
