第1回はリストと呼ばれるものです

リストというのは
ノードとよばれるものにデータを格納して
そのノード同士を直列にポインタでつないだものです
イメージ的には乾電池の直列つなぎです

リストの利点はデータの挿入や（先頭末尾以外の）削除などが高速です
なぜなら、つなぎなおしの際にポインタを繋ぎなおす箇所が
最大でも（双方向の場合）4箇所で済むからです
それに反してデータへのアクセスは
ノードをたどって調べていかなければならないので
配列などに比べて低速です

ノードを並列繋ぎをすると木（ツリー）構造になります
（実際には木はもっと複雑ですが）

もっとも簡単なノードの書き方は次のようになります

struct node
{
 node* next;
 int   data;
};

nodeという構造体の中に自分自身のポインタ(node*)を持っています
気持ち悪いですが、これは慣れです。
ポインターはあくまでもアドレス格納用変数であるので
循環した定義になってないのがポイントです。
（nextがポインタでないならばエラーです）

int data;としていますが
一般的には格納するデータの構造体などをノードに持たせます

struct Data
{
 char name[256];
 int index;
 float something;
};

struct node
{
 node* next;
 Data data;
 
 // ノード生成時(newされたとき)初期化
 node():next(NULL)
 {
   memset(data,0,sizeof(Data));
 }
};

ノードを追加するときはnewします

node* head = NULL; // 全ノードの先頭ノード
Data somedata;
// 先頭ノードがなければ作成
if(head == NULL)
 head = new node;

// 追加したい場合nextにnewする
head->next = new node;
// 追加したノードにデータを格納
head->next->data = somedata;
// さらに追加したい場合、さらにたどってnewします
head->next->next = new node;

リストの強みは途中に追加したい場合です
(あと削除をしたい場合)

node* newnode = newnode;

node* tmpnode;
// つなぎなおすところを一時保存
tmpnode = head->next->next;  

// 挿入
head->next = newnode;
// つなぎなおし
newnode->next = tmpnode;

終了処理はめんどくさいです
たどりつつ削除しなければなりません

node* tmpnode = head;
node* del = tmpnode;
while(tmpnode != NULL)
{
 del = tmpnode;
 tmpnode = tmpnode->next;
 delete del;
}

これだけ見ると使いづらいだけに見えますが・・・
配列などの中間要素に挿入、削除などをする場合
最後方に追加してソートするという手間がかかります
（さらにいうと自由に配列の長さは変えることが基本的にはできません）
これに比べてリストは
ノードのポインタをつなぎなおすだけで済みます
配列と比べて新しいノードを追加するだけでいいので
固定長ではないところも強みです
つまり、データを頻繁に入れ替える場合に重宝する
データ構造なのです

以下に双方向リストをテンプレートクラス化したものを載せておきます
わかる人だけ専用ですが・・・（ぉぃ

//list.h
#ifndef LIST_H
#define LIST_H


#include <assert.h>

template <class T>
class CList
{

public:
	
	// 双方向ノード
	struct Node
	{
		Node *next;	// 次
		Node *prev;	// 前
		T	 data;	// データ

		Node():next(NULL),prev(NULL)
		{
		}

	};

	// コンストラクタ
	CList();

	// ノードが存在するか確かめる
	bool CheckNode(Node* node);

	// 先頭ノード追加
	void AddHead(T setdata);
	// 末尾ノード追加
	void AddTail(T setdata);
	// インデックス番号にノード追加
	void AddNode(int index,T setdata);

	
	// インデックス番号によるノード取得
	Node* GetNode(int index);
	// インデックス番号のノードデータ取得
	T GetNodeData(int index);
	// ノードポインタによるノードデータ取得
	T GetNodeData(Node* getnode);
	// インデックス番号のノードデータへのポインタ取得
	T* GetNodeDataPtr(int index);
	// ノードポインタによるノードデータへのポインタ取得
	T* GetNodeDataPtr(Node* getnode);

	// 先頭削除
	void DelHead();
	// 末尾削除
	void DelTail();
	// インデックス番号のノード削除
	void DelNode(int index);
	// ノードポインタのノード削除
	void DelNode(Node* delnode);
	// 全ノード削除
	void DelAllNode();

	// デストラクタ
	~CList();
	// リスト長取得
	int GetLength();

	

private:

	unsigned int length;	// リスト長
	Node *head,*tail;		// ヘッド、テイル

	// ノードを探す
	Node* SearchNode(int index);

	// 先頭からたどる
	Node*  SearchFromHead(int index);

	// 最後からたどる
	Node*  SearchFromTail(int index);
};

// コンストラクタ
template <class T>
CList<T>::CList():head(NULL),tail(NULL),length(0)
{
}

// ノードが存在するか確かめる
template <class T>
typename bool CList<T>::CheckNode(Node* node)
{
	// NULLなら調べるまでもない
	if(node == NULL)
		return false;

	Node* tmp = head;
	while(tmp != NULL)
	{
		if(tmp == node)
			return true;	// 存在確認

		tmp = tmp->next;
	}

	// ない！！
	return false;
}


// ノードを探す
template <class T>
typename CList<T>::Node* CList<T>::SearchNode(int index)
{
	// そもそもにノードがない
	if(length == 0)
		return NULL;

	// 0未満のインデックスはない
	if(index < 0)
		index = 0;

	// リスト長以上のインデックスはない
	if(index >= static_cast<int>(length))
		index = length - 1;

	// リスト長の半分未満なら先頭から探す
	if(index < static_cast<int>(length/2))
		return this->SearchFromHead(index);
	// 半分以上なら末尾から探す
	else
		return this->SearchFromTail(length - (index + 1));
}


// 先頭からたどる
template <class T>
typename CList<T>::Node*  CList<T>::SearchFromHead(int index)
{
	Node* node = head;
	for(int i = 0;i < index;++i)
		node = node->next;

#if _DEBUG
	assert(this->CheckNode(node));
#endif

	return node;
}

// 末尾からたどる
template <class T>
typename CList<T>::Node*  CList<T>::SearchFromTail(int index)
{
	Node* node = tail;
	for(int i = 0;i < index;++i)
		node = node->prev;

#if _DEBUG
	assert(this->CheckNode(node));
#endif

	return node;
}


// 先頭ノード追加
template <class T>
void CList<T>::AddHead(T setdata)
{
	// ヘッドがない
	if(head == NULL)
	{	
		length++;
		head = new Node;
		tail = head;
		head->data = setdata;
		return;
	}
	else
	{	
		length++;
		head->prev = new Node;
		head->prev->prev = NULL;
		head->prev->next = head;

		head = head->prev;	// ヘッドの移動
		head->data = setdata;
		return;
	}

}

// 末尾ノード追加
template <class T>
void CList<T>::AddTail(T setdata)
{
	// テイルがない
	if(tail == NULL)
	{	
		length++;
		tail = new Node;
		head = tail;
		tail->data = setdata;
		return;
	}
	else
	{	
		length++;
		tail->next = new Node;
		tail->next->next = NULL;
		tail->next->prev = tail;

		tail = tail->next;	// テイル移動
		tail->data = setdata;
		return;
	}

}


// インデックス番号にノード追加
template <class T>
void CList<T>::AddNode(int index,T setdata)
{	
	// ノードを探す
	Node* node = this->SearchNode(index);

	// ノードがない場合
	if(node == NULL)
	{	
		length++;
		head = new Node;
		tail = head;
		head->data = setdata;
		return;
	}
	else
	{
		if(node->next == NULL)
		{	
			length++;
			node->next = new Node;
			node->next->prev = node;
			node->next->next = NULL;
			node->next->data = setdata;
			tail = node->next;

			return;
		}
		else
		{	
			length++;
			Node* tmp = new Node;
			tmp->data = setdata;
			tmp->prev = node;
			tmp->next = node->next;
			node->next->prev = tmp;
			node->next = tmp;
			return;
		}

	}

	
}


// インデックス番号によるノード取得
template <class T>
typename CList<T>::Node* CList<T>::GetNode(int index)
{
	return this->SearchNode(index);
}

// インデックス番号のノードデータ取得
template <class T>
T CList<T>::GetNodeData(int index)
{
	return this->SearchNode(index)->data;
}

// ノードポインタによるノードデータ取得
template <class T>
T CList<T>::GetNodeData(Node* getnode)
{
#if _DEBUG
	assert(this->CheckNode(getnode));
#endif

	return getnode->data;
}

// インデックス番号のノードデータへのポインタ取得
template <class T>
T* CList<T>::GetNodeDataPtr(int index)
{
	return &this->SearchNode(index)->data;
}

// ノードポインタによるノードデータへのポインタ取得
template <class T>
T* CList<T>::GetNodeDataPtr(Node* getnode)
{
#if _DEBUG
	assert(this->CheckNode(getnode));
#endif

	return &getnode->data;
}


// 先頭削除
template <class T>
void CList<T>::DelHead()
{
	// ヘッドがない（削除失敗）
	if(head == NULL)
		return;
	else
	{
		// ヘッドしかない
		if(head->next == NULL)
		{
			assert(head == tail); // 確認用

			length--;
			delete head;
			head = NULL;
			tail = NULL;	// このときテイルも同じアドレス
			return;
		}
		else
		{
			length--;
			head = head->next;	// ヘッドを移行
			delete head->prev;	// 先頭を削除
			head->prev = NULL;
			return;
		}

	}

}

// 末尾削除
template <class T>
void CList<T>::DelTail()
{
	// テイルがない（削除失敗）
	if(tail == NULL)
		return;
	else
	{
		
		// テイルしかない
		if(tail->prev == NULL)
		{
			assert(head == tail); // 確認用
			
			length--;
			delete tail;
			tail = NULL;
			head = NULL;	// このときヘッドも同じアドレス
			return;

		}
		else
		{
			length--;
			tail = tail->prev;	// テイルを移行
			delete tail->next;	// 末尾を削除
			tail->next = NULL;
			return;
		}		

	}
}


// インデックス番号のノード削除
template <class T>
void CList<T>::DelNode(int index)
{
	// ノードを探す
	Node* delnode = this->SearchNode(index);

#if _DEBUG
	assert(delnode);
#endif

	// ノードがない場合
	if(delnode == NULL)
		return;

	// ヘッド＝テイルである場合
	if(delnode == head && delnode == tail)
	{
		length--;
		delete delnode;
		head = NULL;
		tail = NULL;
		return;
	}
	// ヘッドである場合
	else if(delnode == head)
	{
		this->DelHead();
		return;
	}
	// テイルである場合
	else if(delnode == tail)
	{	
		this->DelTail();
		return;
	}
	else
	{
		// 前後のノードがあれば
		if(delnode->next != NULL && delnode->prev != NULL)
		{
			// つなぎなおし
			delnode->prev->next = delnode->next;
			delnode->next->prev = delnode->prev;

			length--;
			delete delnode;
			return;
		}
	}
}

// ノードポインタのノード削除
template <class T>
void CList<T>::DelNode(Node* delnode)
{
	// 存在しているノードなのか確認
	if(!this->CheckNode(delnode))
	{
		return;
	}

	// ヘッド＝テイルである場合
	if(delnode == head && delnode == tail)
	{
		length--;
		delete delnode;
		head = NULL;
		tail = NULL;
		return;
	}
	// ヘッドである場合
	else if(delnode == head)
	{
		this->DelHead();
		return;
	}
	// テイルである場合
	else if(delnode == tail)
	{	
		this->DelTail();
		return;
	}
	else
	{
		// 前後のノードがあれば
		if(delnode->next != NULL && delnode->prev != NULL)
		{
			// つなぎなおし
			delnode->prev->next = delnode->next;
			delnode->next->prev = delnode->prev;

			length--;
			delete delnode;
			return;
		}
	}

}

// 全ノード削除
template <class T>
void CList<T>::DelAllNode()
{
	Node* tmp = head;

	// ヘッドからすべてのノードをたどり消す
	while(tmp != NULL)
	{
		Node* del = tmp;
		tmp = tmp->next;
		delete del;
	}

	head = NULL;
	tail = NULL;
	length = 0;
}


// デストラクタ
template <class T>
CList<T>::~CList()
{
	Node* tmp = head;

	// ヘッドからすべてのノードをたどり消す
	while(tmp != NULL)
	{
		Node* del = tmp;
		tmp = tmp->next;
		delete del;
		
	}

	head = NULL;
	tail = NULL;
	length = 0;

}


// リスト長取得
template <class T>
int CList<T>::GetLength()
{
	return static_cast<int>(length);
}


#endif
選択肢 投票
（＾ω＾）余裕だおっおっお 5  
特になんもねぇよ 0  
。（`ω´#）。ちょっと出直してくる 0  
トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-09-16 (木) 00:49:17