模板實現棧隊列以及鏈表

模板實現鏈表

//test.h
#include <iostream>
#include <cstdio>
#include <assert.h>
using namespace std;template <class T>
struct ListNode
{ListNode* _prev;ListNode* _next;T _data;ListNode(const T& x):_prev(NULL),_next(NULL),_data(x){}
};template <class T>
class List
{typedef ListNode<T> Node;
public:List();~List();//l(l1)//l.List(this, l1)List(const List<T>& l);List<T>& operator = (const List<int>& l);void Clean();void Insert(Node* pos, const T& x);void Erase(Node* pos);void PushFront(T x);void PushBack(T x);void PopBack();void PopFront();void Print();
protected:Node* _head;
};//test.cc
#include "test.h"
template <class T>
List <T>::List()
{_head = new Node(T());_head -> _next = _head;_head -> _prev = _head;
}template <class T>
List <T>::~List()
{Clean();delete _head;
}//l(l1)
//l.List(this, l1)
template <class T>
List<T>::List(const List<T>& l)
{_head = new Node(T());_head -> _next = _head -> _prev = _head;Node* cur = l._head -> _next;while(cur != l._head){PushBack(cur -> _data);cur = cur -> _next;}
}template <class T>
List <T>& List <T>::operator = (const List<int>& l)
{_head = l._head;return *this;
}template <class T>
void List <T>::Clean()
{Node* cur = _head -> _next;while(cur != _head){Node* next = cur -> _next;delete cur;cur = next;}
}template <class T>
void List <T>::Insert(Node* pos, const T& x)
{assert(pos);Node* new_node = new Node(x);Node* prev = pos -> _prev;Node* next = pos;new_node -> _next = next;next -> _prev = new_node;prev -> _next = new_node;new_node -> _prev = prev;
}template <class T>
void List <T>::Erase(Node* pos)
{assert(pos != _head);Node* prev = pos -> _prev;Node* next = pos -> _next;prev -> _next = next;next -> _prev = prev;delete [] pos;
}template <class T>
void List <T>::PushFront(T x)
{Insert(_head -> _next, x);
}template <class T>
void List <T>::PushBack(T x)
{Insert(_head -> _prev -> _next, x);
}template <class T>
void List <T>::PopBack()
{Erase(_head -> _prev);
}template <class T>
void List <T>::PopFront()
{Erase(_head -> _next);
}template <class T>
void List <T>::Print()
{Node* cur = _head -> _next;while(cur != _head){cout << cur -> _data << " ";cur = cur -> _next;}cout << endl;
}

模板實現隊列

//test.cc
#include "test.h"template <class T>
Vector<T>::Vector():_start(NULL),_finish(NULL),_endofstorage(NULL)
{
}template <class T>
//v1(v)
Vector <T>::Vector(const Vector <T>& v)
{size_t size = v.Size();T* start = new T[size];delete [] _start;_start = start;_finish = _start + size;_endofstorage = _start + v.Capacity;
}template <class T>
Vector <T>& Vector <T>::operator = (const Vector <T>& v)
{swap(_start, v._start);swap(_finish, v._start);swap(_endofstorage, v._endofstorage);return *this;
}template <class T>
void Vector <T>::Expand(size_t new_capacity)
{if(new_capacity > Capacity()){size_t size = Size();T* tmp = new  T[new_capacity];if(_start){for(int i = 0; i < (int)size; i++){tmp[i] = _start[i]; }delete [] _start;}_start = tmp;_finish = _start + size;_endofstorage = _start + new_capacity;}
}template <class T>
void Vector <T>::Reserve(size_t size)
{Expand(size);
}template <class T>
const T& Vector <T>::operator [] (size_t pos)const
{return _start[pos];
}
template <class T>
size_t Vector <T>:: Size()
{return _finish - _start;
}template <class T>
void Vector <T>::Insert(size_t pos, const T& x)
{assert(pos <= Size());if(_finish == _endofstorage){size_t new_capacity = Capacity() == 0 ? 3 : Capacity() * 2;Expand(new_capacity);}T* end = _finish - 1;while(end >= _start + pos){*(end + 1) = *end; --end;}*end = x;++_finish;
}template <class T>
void Vector <T>::PushFront(const T& x)
{if(Size() == Capacity()){size_t new_capacity = Capacity() == 0 ? 3 : 2 * Capacity();Expand(new_capacity);}T* end = _finish;for(; end >= _start; --end){*(end + 1) = *(end);}*_start = x;++_finish;
}
template <class T>
void Vector <T>::PushBack(const T& x)
{if(_finish == _endofstorage){size_t new_capacity = Capacity() == 0 ? 3 : 2 * Capacity();Expand(new_capacity);}*_finish = x;++_finish;
}template <class T>
void Vector <T>::Erase(size_t pos)
{assert(pos < Size());T* start = _start + pos;while(start < _finish)// TODO{*start = *(start + 1);start++;}--_finish;
}template <class T>
void Vector <T>::ReSize(size_t size, const T& value)
{Expand(size);memset(_start, value, sizeof(T) * size);
}template <class T>
size_t Vector <T>::Capacity()
{return _endofstorage - _start;
}template <class T>
Vector <T> ::~Vector()
{if(_start){delete [] _start;}
}template <class T>
bool Vector <T> ::Empty()
{return _start == _finish;
}template <class T>
void Vector<T>::PopBack()
{Erase(Size() - 1);
}template <class T>
void Vector <T>::PopFront()
{Erase(0);
}template <class T, class Container>
void Queue <T, Container>::Push(const T& x)
{_con.PushBack(x);
}template <class T, class Container>
void Queue<T, Container>::Pop()
{_con.PopFront();
}template <class T>
T& Vector<T>::Front()
{if(_start != NULL){return *_start;}
}template <class T, class Container>
T& Queue <T, Container>::Front()
{return _con.Front();
}template <class T, class Container>
bool Queue <T, Container>::Empty()
{return _con.Empty();
}
//test.h
#include <iostream>
#include <cstdio>
#include <assert.h>
#include <string.h>
using namespace std;#define TESTHEADER printf("\n==============%s===========\n", __FUNCTION__)template <class T>
class Vector
{
public:Vector();~Vector();Vector(const Vector <T>& v);Vector& operator = (const Vector <T>& v);void Reserve(size_t size);void ReSize(size_t size, const T& value = T());const T& operator [] (size_t pos) const;void Insert(size_t pos, const T& x);void PushFront(const T& x);void PushBack(const T& x);void Erase(size_t pos);size_t Capacity();bool Empty();size_t Size();void PopBack();void PopFront();T& Front();
protected:void Expand(size_t size);
protected:T* _start;T* _finish;T* _endofstorage;
};template <class T, class Container>
class Queue
{
public:void Push(const T& x);void Pop();T& Front();bool Empty();
protected:Container _con;
};

模板實現棧

//test.h
#include <iostream>
#include <cstdio>
#include <assert.h>
#include <string.h>
using namespace std;#define TESTHEADER printf("\n==================%s==================\n", __FUNCTION__)
template <class T>
class Vector
{
public:Vector();~Vector();Vector(const Vector <T>& v);Vector& operator = (const Vector <T>& v);void Reserve(size_t size);void ReSize(size_t size, const T& value = T());const T& operator [] (size_t pos) const;void Insert(size_t pos, const T& x);void PushFront(const T& x);void PushBack(const T& x);void Erase(size_t pos);size_t Capacity();bool Empty();size_t Size();void PopBack();void PopFront();const T& Back();
protected:void Expand(size_t size);
protected:T* _start;T* _finish;T* _endofstorage;
};template<class T, class Container>
class Stack
{
public:void Push(const T& x);void Pop();const T& Top();bool Empty();
protected:Container _con;
};
//test.cc
#include "test.h" 
template <class T>
Vector<T>::Vector():_start(NULL),_finish(NULL),_endofstorage(NULL)
{
}template <class T>
//v1(v)
Vector <T>::Vector(const Vector <T>& v)
{size_t size = v.Size();T* start = new T[size];delete [] _start;_start = start;_finish = _start + size;_endofstorage = _start + v.Capacity;
}template <class T>
Vector <T>& Vector <T>::operator = (const Vector <T>& v)
{swap(_start, v._start);swap(_finish, v._start);swap(_endofstorage, v._endofstorage);return *this;
}template <class T>
void Vector <T>::Expand(size_t new_capacity)
{if(new_capacity > Capacity()){size_t size = Size();T* tmp = new  T[new_capacity];if(_start){for(int i = 0; i < (int)size; i++){tmp[i] = _start[i]; }delete [] _start;}_start = tmp;_finish = _start + size;_endofstorage = _start + new_capacity;}
}template <class T>
void Vector <T>::Reserve(size_t size)
{Expand(size);
}template <class T>
const T& Vector <T>::operator [] (size_t pos)const
{return _start[pos];
}
template <class T>
size_t Vector <T>:: Size()
{return _finish - _start;
}template <class T>
void Vector <T>::Insert(size_t pos, const T& x)
{assert(pos <= Size());if(_finish == _endofstorage){size_t new_capacity = Capacity() == 0 ? 3 : Capacity() * 2;Expand(new_capacity);}T* end = _finish - 1;while(end >= _start + pos){*(end + 1) = *end; --end;}*end = x;++_finish;
}template <class T>
void Vector <T>::PushFront(const T& x)
{if(Size() == Capacity()){size_t new_capacity = Capacity() == 0 ? 3 : 2 * Capacity();Expand(new_capacity);}T* end = _finish;for(; end >= _start; --end){*(end + 1) = *(end);}*_start = x;++_finish;
}
template <class T>
void Vector <T>::PushBack(const T& x)
{if(_finish == _endofstorage){size_t new_capacity = Capacity() == 0 ? 3 : 2 * Capacity();Expand(new_capacity);}*_finish = x;++_finish;
}template <class T>
const T& Vector<T>::Back()
{return _start[Size() - 1];
}template <class T>
void Vector <T>::Erase(size_t pos)
{assert(pos < Size());T* start = _start + pos;while(start < _finish)// TODO{*start = *(start + 1);start++;}--_finish;
}template <class T>
void Vector <T>::ReSize(size_t size, const T& value)
{Expand(size);memset(_start, value, sizeof(T) * size);
}template <class T>
size_t Vector <T>::Capacity()
{return _endofstorage - _start;
}template <class T>
Vector <T> ::~Vector()
{if(_start){delete [] _start;}
}template <class T>
bool Vector <T> ::Empty()
{return _start == _finish;
}template <class T>
void Vector<T>::PopBack()
{Erase(Size() - 1);
}template <class T>
void Vector <T>::PopFront()
{Erase(0);
}///////////////////////////////////////////////////////////////////////////////////////////////
//模板參數實現容器適配器
///////////////////////////////////////////////////////////////////////////////////////////////template<class T, class Container>
void Stack<T, Container>::Push(const T& x)
{_con.PushFront(x);
}template<class T, class Container>
void Stack<T, Container>::Pop()
{_con.PopBack();
}template<class T, class Container>
bool Stack<T, Container>::Empty()
{_con.Empty();
}template<class T, class Container>
const T& Stack<T, Container>::Top()
{return _con.Back();
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/383891.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/383891.shtml
英文地址，請注明出處：http://en.pswp.cn/news/383891.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

基于Visual C++2013拆解世界五百強面試題--題5-自己實現strstr

基于Visual C++2013拆解世界五百強面試題--題5-自己實現strstr

http://blog.csdn.net/itcastcpp/article/details/12907371 請用C語言實現字符串的查找函數strstr&#xff0c; 找到則返回子字符串的地址&#xff0c;沒有找到返回為空&#xff0c;請用數組操作與指針操作實現 看到題目想到最簡單的方法就是母字符串和子字符串比較&#xff0c…
閱讀更多...
卡特蘭數

卡特蘭數

卡特蘭數的引入與n邊形分成三角形的個數有關&#xff1a; 我們令f[n]表示n邊形可以分成的三角形的個數&#xff0c;特殊的&#xff0c;令f[2]1 我們考慮以頂點1頂點的一個三角形&#xff0c;假設用的是n邊形的k-k1邊&#xff0c;那么這種情況的方案數就是f[k]?f[n?k1]f[k]*…
閱讀更多...
軟件測試相關概念

軟件測試相關概念

什么叫軟件測試 軟件測試就是測試產品沒有錯誤,同時又證明軟件是可以正確運行的 測試和調試的區別 調試一般都在開發期間 ,測試是伴隨著整個軟件的生命周期, 調試是發現程序中問題并且解決問題, 測試是發現程序中的缺陷 軟件測試的目的和原則 目的:驗證軟件有沒有問題 原…
閱讀更多...
Linux 線程信號量同步

Linux 線程信號量同步

https://www.cnblogs.com/jiqingwu/p/linux_semaphore_example.html 信號量和互斥鎖(mutex)的區別&#xff1a;互斥鎖只允許一個線程進入臨界區&#xff0c;而信號量允許多個線程同時進入臨界區。 不多做解釋&#xff0c;要使用信號量同步&#xff0c;需要包含頭文件semaphore.…
閱讀更多...
本原勾股數組

本原勾股數組

勾股數我們都很熟悉&#xff0c;a2b2c2&#xff0c;可是如何快速找到所有的勾股數組呢&#xff1f; 本原勾股數組a2b2c2性質&#xff1a; 1. a,b奇偶不同&#xff0c;c一定是奇數 2. 若b為偶數&#xff0c;c-b和cb一定是完全平方數 3. 設t>s>1,且均為奇數&#xff0c;則…
閱讀更多...
C++靜態成員函數訪問非靜態成員的幾種方法

C++靜態成員函數訪問非靜態成員的幾種方法

https://www.cnblogs.com/rickyk/p/4238380.html 大家都知道C中類的成員函數默認都提供了this指針&#xff0c;在非靜態成員函數中當你調用函數的時候&#xff0c;編譯器都會“自動”幫你把這個this指針加到函數形參里去。當然在C靈活性下面&#xff0c;類還具備了靜態成員和靜…
閱讀更多...
費馬大定理

費馬大定理

當n>3時方程 xnynzn沒有正整數解 結論很簡潔&#xff0c;剛才看了一下證明的歷史&#xff0c;我勒個去。。。。
閱讀更多...
類中的靜態成員函數訪問非靜態成員變量

類中的靜態成員函數訪問非靜態成員變量

http://blog.csdn.net/u011857683/article/details/52294353 1.思路&#xff1a; 靜態成員函數屬于類(通過類訪問&#xff0c;調用函數時沒有提供this指針)&#xff0c; 非靜態成員函數屬于實例&#xff08;通過對象訪問&#xff09;&#xff08;默認都提供了this指針&#xf…
閱讀更多...
Pollar Rho算法

Pollar Rho算法

原本是想把這個算法搞懂的&#xff0c;然后在網上看了又看&#xff0c;覺得&#xff0c;還是有時間再來看吧&#xff0c;我錯了。 看到了一個大佬的博客&#xff0c;順帶收集一下板子 這個板子可以求大數的最大的因子。 #define LL long long bool IsPrime(LL);//返回素性測…
閱讀更多...
小知識點總結

小知識點總結

用戶輸入一個url之后到整個頁面返回給客戶這個過程都經歷了一些什么 首先url是為了讓人記憶方便的,計算機在進行網絡傳輸的過程中只能通過ip地址找到對應的主機,所以當輸入一個ip地址的時候,此時就需要找對應的url,首先從瀏覽器中取查找ip地址,再到系統中去查找,再到域名解析服…
閱讀更多...
C++學習之普通函數指針與成員函數指針

C++學習之普通函數指針與成員函數指針

http://blog.csdn.net/lisonglisonglisong/article/details/38353863 函數指針&#xff08;function pointer&#xff09;是通過指向函數的指針間接調用函數。相信很多人對指向一般函數的函數指針使用的比較多&#xff0c;而對指向類成員函數的函數指針則比較陌生。我最近也被問…
閱讀更多...
HDU2683——歐拉完全數

HDU2683——歐拉完全數

題目要求符合等式的數&#xff0c;我們首先要做的就是分析這個數&#xff1a; 對于這個等式&#xff0c;我們可能什么都看不出來&#xff0c;左邊很難化簡的樣子&#xff0c;所以我們就要想到通過變化怎么樣把右邊化成和左邊形式差不多的樣子。結合組合數我們想到二項式定理&am…
閱讀更多...
BZOJ-2005能量采集-數論函數

BZOJ-2005能量采集-數論函數

很入門的數論函數題目。我還是wa了一發&#xff08;爆long long 了&#xff09; 對于每個位置x,y&#xff0c;在他們和能量采集器中間的植物為gcd(x,y)-1&#xff0c;【在他們之間說明斜率相同&#xff0c;而和他們斜率相同的就是所有gcd(x/gcd(x,y),y/gcd(x,y))1的并且比他們小…
閱讀更多...
網絡五層模型

網絡五層模型

TCP/IP五層模型 應用層: HTTP,HTTPS協議,其中HTTP沒有對數據進行加密操作,但是HTTPS對數據進行了加密操作 其中HTTP端口號一般是80/8080等等,HTTPS端口號是443,SSH端口號一般是22,ftp是21 HTTP協議報頭: 首行:請求方法,url,協議版本 請求報頭: HOST:主機 Connection:長連接…
閱讀更多...
C++的靜態成員函數指針

C++的靜態成員函數指針

http://blog.csdn.net/sky453589103/article/details/47276789 先簡單的說說非靜態的成員函數。非靜態成員函數指針的類型&#xff1a;類的非靜態成員是和類的對象相關的。也就是說&#xff0c;要通過類的對象來訪問變量。成員函數的類型定義為&#xff1a;typedef void (A::*p…
閱讀更多...
從一個字符串中刪除另一個字符串中出現過的字符

從一個字符串中刪除另一個字符串中出現過的字符

http://blog.csdn.net/walkerkalr/article/details/39001155 定義一個函數&#xff0c;輸入兩個字符串&#xff0c;從第一個字符串中刪除在第二個中出現過的所偶字符串。例如從第一個字符串"We are students."中刪除第二個字符中“auiou”中出現過的字符得到的結果是…
閱讀更多...
SPOJ-VLATTICE Visible Lattice Points-莫比烏斯反演

SPOJ-VLATTICE Visible Lattice Points-莫比烏斯反演

需要將問題分解一下。 我們需要求的是這個立方體從(0,0,0)能看到的點的個數。可是在三個含有(0,0,0)的面上我們沒有辦法和其他的一起進行分析&#xff08;因為含有坐標是0&#xff0c;而我們的數論工具都是從1開始的&#xff09;&#xff0c;所以我們可以將那三個面分開考慮&a…
閱讀更多...
進程的通信

進程的通信

管道 什么是管道 由于進程之間是相互獨立的,因此在進程與進程之間進行相互聯系的時候,此時就需要采用一種機制,通過管道的方式將進程一個進程的執行數據交給另外一個進程,此時就可以以通過管道來實現 匿名管道和命名管道 匿名管道 創建一個匿名管道的方式是pipe(int pipe[…
閱讀更多...
獲取網絡接口信息——ioctl()函數與結構體struct ifreq、 struct ifconf

獲取網絡接口信息——ioctl()函數與結構體struct ifreq、 struct ifconf

http://blog.csdn.net/windeal3203/article/details/39320605 Linux 下 可以使用ioctl()函數 以及 結構體 struct ifreq 結構體struct ifconf來獲取網絡接口的各種信息。 ioctl 首先看ioctl()用法ioctl()原型如下&#xff1a;#include <sys/ioctl.h>int ioctl(int fd, i…
閱讀更多...
歐拉降冪

歐拉降冪

我們記f(n)為n的歐拉函數值&#xff0c;則 當B>f©時&#xff0c;AB%CAB%f©f©%C&#xff0c;這里A,C可能不互質。 很好用&#xff0c;證明很復雜&#xff0c;等有時間回來學習一下。
閱讀更多...
最新文章

Copyright @ 2022~2023