- 追加された行はこの色です。
- 削除された行はこの色です。
第1回はリストと呼ばれるものです
リストというのは
ノードとよばれるものにデータを格納して
そのノード同士を直列にポインタでつないだものです
イメージ的には乾電池の直列つなぎです
リストの利点はデータの挿入や（先頭末尾以外の）削除などが高速です
なぜなら、つなぎなおしの際にポインタを繋ぎなおす箇所が
最大でも（双方向の場合）4箇所で済むからです
それに反してデータへのアクセスは
ノードをたどって調べていかなければならないので
配列などに比べて低速です
ノードを並列繋ぎをすると木（ツリー）構造になります
（実際には木はもっと複雑ですが）
もっとも簡単なノードの書き方は次のようになります
struct node
{
node* next;
int data;
};
nodeという構造体の中に自分自身のポインタ(node*)を持っています
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;
}
これだけ見ると使いづらいだけに見えますが・・・
配列などの中間要素に挿入、削除などをする場合
最後方に追加してソートするという手間がかかります
（さらにいうと自由に配列の長さは変えることが基本的にはできません）
これに比べてリストは
ノードのポインタをつなぎなおすだけで済みます
配列と比べて新しいノードを追加するだけでいいので
固定長ではないところも強みです
つまり、データを頻繁に入れ替える場合に重宝する
データ構造なのです
以下に双方向リストをテンプレートクラス化したものを載せておきます
わかる人だけ専用ですが・・・（ぉぃ
// 双方向リスト改
#include <iostream>
#include <assert.h>
template <class T>
class CList
{
private:
unsigned int length; // リスト長
// 双方向ノード
struct Node
{
Node *next; // 次
Node *prev; // 前
T data; // データ
Node():next(NULL),prev(NULL)
{
}
};
Node *head,*tail; // ヘッド、テイル
// ノードを探す
Node* SearchNode(int index);
// 先頭からたどる
Node* SearchFromHead(int index);
// 最後からたどる
Node* SearchFromTail(int index);
public:
// コンストラクタ
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();
};
// コンストラクタ
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 _DEBUG
assert(delnode = this->SearchNode(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(delanode == 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);
}
int main()
{
// メモリリーク検出用
#ifdef _DEBUG
_CrtSetDbgFlag(_CrtSetDbgFlag(_CRTDBG_REPORT_FLAG) | _CRTDBG_LEAK_CHECK_DF);
_CrtSetBreakAlloc(58); // リーク箇所チェック
#endif
return 0;
}
#vote(（＾ω＾）余裕だおっおっお[5],-[0],。（`ω´#）。ちょっと出直してくる[0])
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
