鏈表模板、隊列模板、順序表模板、棧模板、-創(chuàng)新互聯(lián)
//利用容器適配器實現(xiàn)棧和隊列
#pragma once
#include<iostream>
#include<string>
#include<cassert>
using namespace std;
template<typename T>
struct Node
{
public:
Node(const T& d)
:_next(NULL)
, _prev(NULL)
,_data(d){}
T _data;
Node<T> *_next;
Node<T> *_prev;
};
template<typename T>
class LinkList
{
public:
LinkList()
:_head(NULL)
, _tail(NULL){}
LinkList(const LinkList<T>& list);
LinkList<T>& operator=(LinkList<T> list);
~LinkList();
void PushBack(const T& d);
void PushFront(const T& d);
void PopBack();
void PopFront();
void Insert(Node<T> *addr, const T& d); //在當(dāng)前結(jié)點后面插入元素
Node<T>* Search(const T& d);
void Remove(const T& d);
void RemoveAll(const T& d);
void Sort();
void Display();
size_t Size();
T& GetFront()
{
assert(_head);
return _head->_data;
}
T& GetBack()
{
assert(_tail);
return _tail->_data;
}
private:
Node<T> *_head;
Node<T> *_tail;
};
template<typename T>
size_t LinkList<T>::Size()
{
Node<T> *cur = _head;
size_t count = 0;
while (cur)
{
count++;
cur = cur->_next;
}
return count;
}
template<typename T>
LinkList<T>::LinkList(const LinkList<T>& list)
:_head(NULL)
, _tail(NULL)
{
Node<T> *cur = list._head;
while (cur)
{
PushBack(cur->_data);
cur = cur->_next;
}
}
template<typename T>
LinkList<T>& LinkList<T>::operator=(LinkList<T> list)
{
std::swap(_head,list._head);
std::swap(_tail,list._tail);
return *this;
}
template<typename T>
LinkList<T>::~LinkList()
{
Node<T> *cur = _head;
while (cur)
{
_head = _head->_next;
delete cur;
cur = _head;
}
_tail = NULL;
}
template<typename T>
void LinkList<T>::PushBack(const T& d)
{
Node<T> *NewHead = new Node<T>(d);
if (NULL == _head)
{
_head = NewHead;
_tail = NewHead;
}
else
{
_tail->_next = NewHead;
NewHead->_prev = _tail;
_tail = _tail->_next;
}
}
template<typename T>
void LinkList<T>::PushFront(const T& d)
{
Node<T> *NewHead = new Node<T>(d);
if (NULL == _head)
{
_head = NewHead;
_tail = NewHead;
}
else
{
NewHead->_next = _head;
_head->_prev = NewHead;
_head = NewHead;
}
}
template<typename T>
void LinkList<T>::PopBack()
{
if (NULL == _head)
{
return;
}
else if (NULL==_head->_next)
{
delete _tail;
_head = NULL;
_tail = NULL;
}
else
{
Node<T> *cur = _tail;
_tail = _tail->_prev;
_tail->_next = NULL;
delete cur;
}
}
template<typename T>
void LinkList<T>::PopFront()
{
if (NULL == _head)
{
return;
}
else if (NULL == _head->_next)
{
delete _tail;
_head = NULL;
_tail = NULL;
}
else
{
Node<T> *cur = _head;
_head = _head->_next;
_head->_prev = NULL;
delete cur;
}
}
template<typename T>
void LinkList<T>::Insert(Node<T> *addr, const T& d) //在當(dāng)前結(jié)點后面插入元素
{
Node<T> *NewNode = new Node<T>(d);
if (_head == addr)
{
NewNode->_next = _head;
_head->_prev = NewNode;
_head = NewNode;
}
else if (_tail == addr)
{
PushBack(d);
}
else
{
NewNode->_next = addr->_next;
addr->_next->_prev = NewNode;
addr->_next = NewNode;
NewNode->_prev = addr;
}
}
template<typename T>
Node<T>* LinkList<T>::Search(const T& d)
{
Node<T> *cur = _head;
while (cur)
{
if (cur->_data == d)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
template<typename T>
void LinkList<T>::Remove(const T& d)
{
Node<T> *cur =Search(d);
if (cur == _head)
{
PopFront();
}
else if (cur == _tail)
{
PopBack();
}
else
{
cur->_prev->_next = cur->_next;
cur->_next->_prev = cur->_prev;
delete cur;
}
}
template<typename T>
void LinkList<T>::RemoveAll(const T& d)
{
while (Search(d) != NULL)
{
Remove(d);
}
}
template<typename T>
void LinkList<T>::Sort()
{
Node<T> *end = _tail;
while (_head != end)
{
Node<T> *cur = _head;
int flag = 1;
while (cur!=end)
{
if (cur->_data > cur->_next->_data)
{
T tmp = cur->_data;
cur->_data = cur->_next->_data;
cur->_next->_data=tmp;
flag = 0;
}
cur = cur->_next;
}
if (flag)
{
return;
}
end = end->_prev;
}
}
template<typename T>
void LinkList<T>::Display()
{
Node<T> *cur = _head;
while (cur)
{
cout << cur->_data << " ";
cur = cur->_next;
}
cout << endl;
}
#include"LinkList.h"
template<typename T,template<class> class Container>
class Queue
{
public:
void Push(const T& d);
void Pop();
T& Front();
T& Back();
size_t Size();
bool Empty();
void Display()
{
while (!Empty())
{
cout << Front() << " ";
Pop();
}
cout << endl;
}
private:
Container<T> _con;
};
template<typename T,template<class> class Container>
void Queue<T,Container>::Push(const T& d)
{
_con.PushBack(d);
}
template<typename T,template<class> class Container>
void Queue<T,Container>::Pop()
{
_con.PopFront();
}
template<typename T,template<class> class Container>
T& Queue<T,Container>::Front()
{
return _con.GetFront();
}
template<typename T,template<class> class Container>
T& Queue<T,Container>::Back()
{
return _con.GetBack();
}
template<typename T,template<class> class Container>
size_t Queue<T,Container>::Size()
{
return _con.Size();
}
template<typename T,template<class> class Container>
bool Queue<T,Container>::Empty()
{
return _con.Size()== 0;
}#pragma once
#include<iostream>
#include<cstring>
#include<string>
#include<cassert>
using namespace std;
template<typename T>
class Seqlist
{
public:
Seqlist();
Seqlist(const Seqlist<T>& seq);
Seqlist & operator=(Seqlist<T> seq);
~Seqlist();
void PushBack(const T& d);
void PushFront(const T& d);
void PopBack();
void PopFront();
void Insert(int index,const T& d);
int Search(const T& d);
void Remove(const T& d);
void RemoveAll(const T& d);
void Sort();
void Reserve(int n);
void Display();
int GetSize();
T& operator[](int index);
private:
void CheckCapacity(int n=0);
private:
T *_pdata;
int _sz;
int _capacity;
};
template<typename T>
T& Seqlist<T>::operator[](int index)
{
assert(index >= 0);
assert(index < _sz);
return _pdata[index];
}
template<typename T>
int Seqlist<T>::GetSize()
{
return _sz;
}
template<typename T>
Seqlist<T>::Seqlist()
:_sz(0)
, _capacity(0)
, _pdata(NULL){}
template<typename T>
Seqlist<T>::Seqlist(const Seqlist<T>& seq)
{
_pdata = new T[seq._capacity];
for (int i = 0; i < seq._sz; i++)
{
_pdata[i] = seq._pdata[i];
}
_sz = seq._sz;
_capacity = seq._capacity;
}
template<typename T>
Seqlist<T>& Seqlist<T>::operator=(Seqlist<T> seq)
{
swap(_pdata,seq._pdata);
_sz = seq._sz;
_capacity = seq._capacity;
return *this;
}
template<typename T>
Seqlist<T>::~Seqlist()
{
if (_pdata != NULL)
{
delete[] _pdata;
_pdata = NULL;
_sz = 0;
_capacity = 0;
}
}
template<typename T>
void Seqlist<T>::CheckCapacity(int n=0)
{
if (_sz == _capacity||n>_capacity)
{
int NewCapacity =2*_capacity+1;
if (n > _capacity)
{
NewCapacity = n;
}
T* tmp = new T[NewCapacity];
for (int i = 0; i < _sz; i++)
{
tmp[i] =_pdata[i];
}
delete[] _pdata;
_pdata = tmp;
_capacity = NewCapacity;
}
}
template<typename T>
void Seqlist<T>::PushBack(const T& d)
{
CheckCapacity();
_pdata[_sz++] = d;
}
template<typename T>
void Seqlist<T>::PushFront(const T& d)
{
CheckCapacity();
//memmove(_pdata + 1,_pdata,sizeof(T)*_sz);
for (int i =_sz;i>0; i--)
{
_pdata[i] = _pdata[i-1];
}
_pdata[0] = d;
_sz++;
}
template<typename T>
void Seqlist<T>::PopBack()
{
_sz--;
}
template<typename T>
void Seqlist<T>::PopFront()
{
//memmove(_pdata,_pdata+1,sizeof(T)*(--_sz));
for (int i = 0; i<_sz-1; i++)
{
_pdata[i] = _pdata[i+1];
}
_sz--;
}
template<typename T>
void Seqlist<T>::Insert(int index, const T& d)
{
assert(index >= 0);
assert(index<_sz);
CheckCapacity();
//memmove(_pdata+index+1,_pdata+index,sizeof(T)*(_sz-index));
for (int i = _sz; i>index; i--)
{
_pdata[i] = _pdata[i - 1];
}
_sz++;
_pdata[index] = d;
}
template<typename T>
int Seqlist<T>::Search(const T& d)
{
int i = 0;
for (i = 0; i < _sz; i++)
{
if (_pdata[i] == d)
{
return i;
}
}
return -1; //沒找到返回-1
}
template<typename T>
void Seqlist<T>::Remove(const T& d)
{
int index = Search(d);
if (index == -1)
{
return;
}
else
{
//memmove(_pdata+index,_pdata+index+1,sizeof(T)*(_sz-index-1));
for (int i =index; i<_sz-1; i++)
{
_pdata[i] = _pdata[i+1];
}
_sz--;
}
}
template<typename T>
void Seqlist<T>::RemoveAll(const T& d)
{
while (Search(d) != -1)
{
Remove(d);
}
}
template<typename T>
void Seqlist<T>::Reserve(int n)
{
CheckCapacity(n);
}
template<typename T>
void Seqlist<T>::Sort()
{
int end = _sz - 1;
for (int i = 0; i < _sz - 1; i++)
{
int flag = 1;
int k = end;
for (int j = 0; j <end;j++)
{
if (_pdata[j]>_pdata[j+1])
{
T tmp = _pdata[j];
_pdata[j] = _pdata[j + 1];
_pdata[j + 1] = tmp;
flag = 0;
k= j;
}
}
if (flag == 1)
{
return;
}
end = k;
}
}
template<typename T>
void Seqlist<T>::Display()
{
for (int i = 0; i < _sz; i++)
{
cout << _pdata[i] << " ";
}
cout << endl;
}#include"Seqlist.h"
template<typename T,template<class> class Container>
class Stack
{
public:
bool Empty();
void Push(const T& d);
void Pop();
T& Top();
int Size();
void Display()
{
while (!Empty())
{
cout << Top() << " ";
Pop();
}
cout << endl;
}
private:
Container<T> _con;
};
template<typename T, template<class> class Container>
bool Stack<T,Container>::Empty()
{
return _con.GetSize()==0;
}
template<typename T, template<class> class Container>
void Stack<T, Container>::Pop()
{
_con.PopBack();
}
template<typename T, template<class> class Container>
void Stack<T,Container>::Push(const T& d)
{
_con.PushBack(d);
}
template<typename T, template<class> class Container>
int Stack<T,Container>::Size()
{
return _con.GetSize();
}
template<typename T, template<class> class Container>
T& Stack<T, Container>::Top()
{
int sz=_con.GetSize()-1;
return _con[sz];
}另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
標(biāo)題名稱：鏈表模板、隊列模板、順序表模板、棧模板、-創(chuàng)新互聯(lián)
文章網(wǎng)址：http://muchs.cn/article10/dppddo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、定制開發(fā)、營銷型網(wǎng)站建設(shè)、網(wǎng)站設(shè)計公司、面包屑導(dǎo)航、關(guān)鍵詞優(yōu)化
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容
- 在flask中開啟debug調(diào)試模式的方法-創(chuàng)新互聯(lián)
- gRPC如何在ASP.NETCore3.0項目中使用-創(chuàng)新互聯(lián)
- [C#基礎(chǔ)知識系列]全面解析C#中靜態(tài)與非靜態(tài)-創(chuàng)新互聯(lián)
- faced：基于深度學(xué)習(xí)的CPU實時人臉檢測-創(chuàng)新互聯(lián)
- 如何使用Django內(nèi)置的緩存API-創(chuàng)新互聯(lián)
- 深入淺析ArrayList和LinkedList的執(zhí)行效率比較-創(chuàng)新互聯(lián)
- 如何在python中使用Pandas讀取txt表格-創(chuàng)新互聯(lián)
- 成都網(wǎng)站建設(shè)：響應(yīng)式網(wǎng)站常見的設(shè)計錯誤。 2022-08-04
- 自適應(yīng)網(wǎng)站建設(shè)的發(fā)展趨勢 2016-10-05
- 泰州響應(yīng)式網(wǎng)站制作：制作響應(yīng)式網(wǎng)站有哪些困難？ 2021-10-01
- 新網(wǎng)站設(shè)計和網(wǎng)站改版選擇響應(yīng)式網(wǎng)站設(shè)計的原因 2021-12-06
- 網(wǎng)頁設(shè)計老司機(jī)，不要再被響應(yīng)式網(wǎng)站建設(shè)牽著鼻子走了，坑你跳不起! 2022-06-28
- 響應(yīng)式網(wǎng)站哪幾方面會直接影響價格？ 2020-11-14
- 自適應(yīng)網(wǎng)頁設(shè)計與響應(yīng)式網(wǎng)站的區(qū)別 2022-11-29
- 所有的行業(yè)都適合進(jìn)行響應(yīng)式網(wǎng)站制作嗎？ 2016-10-18
- 日照競價托管：為什么響應(yīng)式網(wǎng)站建樹有利于SEO呢？ 2023-01-13
- 為什么選擇響應(yīng)式網(wǎng)站定制，帶來哪些優(yōu)勢 2022-07-10
- 成都網(wǎng)站建設(shè)制作公司：制作響應(yīng)式網(wǎng)站的“四不要” 2023-02-17
- 從源頭把控四點響應(yīng)式網(wǎng)站建設(shè)品質(zhì)即可得到有效保障 2022-05-15