データ構造テンプレートの実装(1):双方向チェーンテーブル

date:2018-09-27 12:42:30+00:00元タイトル:自分でデータ構造テンプレートを実現(1):双方向チェーンテーブル元リンク:https://www.dreamoftime0.com/2018/09/27/%e8%87%aa%e5%b7%b1%e5%8a%a8%e6%89%8b%e5%ae%9e%e7%8e%b0%e5%8f%8c%e5%90%91%e9%93%be%e8%a1%a8/
今日急に気まぐれになって、自分で1つの簡単な双方向のチェーン時計と基本的な機能を実現して、大体以下の機能を実現しました
dtsListNodeは、値value、順方向ポインタpre、および後方向ポインタnextを含むノードクラスである.
dtsListは双方向チェーンテーブルであり、beginとend関数によりヘッダアドレスポインタと最後の要素の後を指すテールポインタを得ることができ、empty関数を用いて空か否かを判断し、sizeはデータノード数、printとprint_を返すrevは、現在のすべてのノードを出力し、add 2 Head、add 2 End、deleteFromHead、deleteFromEndを使用してヘッダからノードを追加または削除し、ノードまたはプロファイルを削除するときに使用するメモリをタイムリーに解放します.
ソースコードは次のとおりです.

#ifndef DTS_LIST_HPP
#define DTS_LIST_HPP
#include
using namespace std;

template
class dtsListNode{
public:
	T value;
	dtsListNode* next;
	dtsListNode* pre;
	dtsListNode(T v,dtsListNode* nextPointer=NULL,dtsListNode* prePointer=NULL)
		:value(v),next(nextPointer),pre(prePointer){}
	dtsListNode():next(NULL),pre(NULL){}
};

template
class dtsList{
protected:
	dtsListNode* pHead;//     
	dtsListNode* pBegin;//         
	dtsListNode* pTail;//          
	dtsListNode* pEnd;//     
	inline dtsListNode* insertAfter(dtsListNode* first,T val){
		dtsListNode* second = new dtsListNode(val);
		dtsListNode* third = first->next;

		if(first==pHead)
			pBegin=second;
		if(first==pTail)
			pTail=second;

		first->next=second;
		second->pre=first;
		second->next=third;
		third->pre=second;

		return second;
	}
	inline T deleteAfter(dtsListNode* first){
		T ret;
		if(!first || !first->next || !first->next->next)
			return ret;
		dtsListNode* second=first->next;
		dtsListNode* third=second->next;
		ret=second->value;

		if(first==pHead){//     pBegin 
			pBegin=third;
		}
		if(second==pTail){//     pTail 
			if(first!=pHead){
			pTail=first;
			}
			else {//         
			pBegin=NULL;
			pTail=NULL;
			}
		}


		delete second;
		first->next=third;
		third->pre=first;

		return ret;
	}

public:
	dtsList(){
		pHead = new dtsListNode();
		pEnd = new dtsListNode();
		pBegin = NULL;
		pTail = NULL;

		pHead->next=pEnd;
		pEnd->pre=pHead;
	}
	inline bool empty(){
		return pBegin==NULL;
	}
	int size(){
		if(empty())
			return 0;
		int ret=0;
		for(dtsListNode* it=pBegin;it!=pEnd;it=it->next){
			++ret;
		}
		return ret;
	}
	dtsListNode* begin(){
		return pBegin;
	}
	dtsListNode* end(){
		return pEnd();
	}
	dtsList& add2End(T val){
		if(!pTail || !pBegin){//      
			pBegin=insertAfter(pHead,val);
			pTail=pBegin;
			//print();
		} else {//          ，      
			insertAfter(pTail,val);
			//print();
		}
		//cout<pre);
		}
		T ret;
		return ret;
	}
	T deleteFromHead(){
		return deleteAfter(pHead);
	}
	void print(const char* separator="->",const char* null_str="   "){
		if(pHead->next==pEnd){
			cout<next ){
				coutpre)
					cout<next==pEnd){
			cout<pre ){
				coutnext)
					cout<next;
			//cout<

以下はテストメイン関数

#include
#include
#include"dtsList.hpp"
using namespace std;

int main(){
    dtsList l;
    l.add2Head("one");
    l.add2End("two");
    l.add2End("three");
    l.add2Head("zero");

    l.print("->");
    l.print_rev();
    cout<");
    cout<");
    cout<");
    cout<");
    cout<

出力:

zero->one->two->three
threeone->two
size:3
zero    
one->two
size:2
one    
two
size:1
two    
   
size:0