- 追加された行はこの色です。
- 削除された行はこの色です。
第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;
}
これだけ見ると使いづらいだけに見えますが・・・
配列などの中間要素に挿入、削除などをする場合
最後方に追加してソートするという手間がかかります
(さらにいうと自由に配列の長さは変えることが基本的にはできません)
これに比べてリストは
ノードのポインタをつなぎなおすだけで済みます
配列と比べて新しいノードを追加するだけでいいので
固定長ではないところも強みです
つまり、データを頻繁に入れ替える場合に重宝する
データ構造なのです
以下に双方向リストをテンプレートクラス化したものを載せておきます
わかる人だけ専用ですが・・・(ぉぃ
//list.h
#pragma once
// 双方向リスト改
#include <iostream>
using namespace std;
#include <iostream>
#include <assert.h>
template <class T>
class list
{
private:
int length;
list *head,*tail,*prev,*next;
T data;
public:
list(void);
virtual ~list(void);
void addlisthead(T setdata);
void addlist(int addnum,T setdata);
void addlisttail(T setdata);
void dellist(int delnum);
void dellisthead();
void dellisttail();
T get(int getnum);
void set(int setnum,T setdata);
int getlength();
};
template <class T>
class CList
{
private:
unsigned int length; // リスト長
//コンストラクタ
template <class T>
list<T>::list(void):length(0),head(NULL),tail(NULL),prev(NULL),next(NULL)
{
}
// 双方向ノード
struct Node
{
Node *next; // 次
Node *prev; // 前
T data; // データ
Node():next(NULL),prev(NULL)
{
}
//デストラクタ(全てのリストを解放)
template <class T>
list<T>::~list(void)
{
list* tmplist = head;
list* del = NULL;
while(tmplist != NULL)
{
del = tmplist;
tmplist = tmplist->next;
};
Node *head,*tail; // ヘッド、テイル
delete del;
}
// ノードを探す
Node* SearchNode(int index);
}
// 先頭からたどる
Node* SearchFromHead(int index);
// 先頭追加(指定番号)
template <class T>
void list<T>::addlisthead(T setdata)
{
if(head == NULL)
{
head = new list<T>;
tail = head;
head->data = setdata;
return;
}
// 最後からたどる
Node* SearchFromTail(int index);
public:
// コンストラクタ
CList();
// リスト長を増やす
length++;
// ノードが存在するか確かめる
bool CheckNode(Node* node);
list* tmplist = head;
// 先頭ノード追加
void AddHead(T setdata);
// 末尾ノード追加
void AddTail(T setdata);
// インデックス番号にノード追加
void AddNode(int index,T setdata);
// リスト追加
tmplist->prev = new list<T>;
tmplist->prev->next = tmplist;
tmplist->prev->prev = NULL;
tmplist->prev->data = setdata;
// インデックス番号によるノード取得
Node* GetNode(int index);
// インデックス番号のノードデータ取得
T GetNodeData(int index);
// ノードポインタによるノードデータ取得
T GetNodeData(Node* getnode);
// インデックス番号のノードデータへのポインタ取得
T* GetNodeDataPtr(int index);
// ノードポインタによるノードデータへのポインタ取得
T* GetNodeDataPtr(Node* getnode);
// ヘッドを移行
head = tmplist->prev;
// 先頭削除
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>
void list<T>::addlist(int addnum,T setdata)
{
// 最小以下
if(addnum < 0)
addnum = 0;
// ノードが存在するか確かめる
template <class T>
typename bool CList<T>::CheckNode(Node* node)
{
// NULLなら調べるまでもない
if(node == NULL)
return false;
// 最大以上
if(addnum > length)
addnum = length;
Node* tmp = head;
while(tmp != NULL)
{
if(tmp == node)
return true; // 存在確認
tmp = tmp->next;
}
if(head == NULL)
{
head = new list<T>;
tail = head;
head->data = setdata;
return;
}
// ない!!
return false;
}
// リスト長を増やす
length++;
list* tmplist = head;
// ノードを探す
template <class T>
typename CList<T>::Node* CList<T>::SearchNode(int index)
{
// そもそもにノードがない
if(length == 0)
return NULL;
for(int i = 0;i < addnum;++i)
tmplist = tmplist->next;
// 0未満のインデックスはない
if(index < 0)
index = 0;
// 末尾だったら
if(tmplist->next == NULL)
{
tmplist->next = new list<T>;
tmplist->next->next = NULL;
tmplist->next->prev = tmplist;
tmplist->next->data = setdata;
// リスト長以上のインデックスはない
if(index >= static_cast<int>(length))
index = length - 1;
// テイルを移行
tail = tmplist->next;
}
// 先頭だったら
else if(tmplist->prev == NULL)
{
// リスト追加
tmplist->prev = new list<T>;
tmplist->prev->next = tmplist;
tmplist->prev->prev = NULL;
tmplist->prev->data = setdata;
// リスト長の半分未満なら先頭から探す
if(index < static_cast<int>(length/2))
return this->SearchFromHead(index);
// 半分以上なら末尾から探す
else
return this->SearchFromTail(length - (index + 1));
}
// ヘッドを移行
head = tmplist->prev;
}
// 中間だったら
else
{
//つなぎなおし
tmplist->prev->next = new list<T>;
tmplist->prev->next->prev = tmplist->prev;
tmplist->prev->next->next = tmplist;
tmplist->prev = tmplist->prev->next;
tmplist->prev->data = setdata;
}
}
// 先頭からたどる
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
// 末尾追加(指定番号)
template <class T>
void list<T>::addlisttail(T setdata)
{
if(head == NULL)
{
head = new list<T>;
tail = head;
head->data = setdata;
return;
}
return node;
}
// リスト長を増やす
length++;
// 末尾からたどる
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;
list* tmplist = head;
// リストを辿って末端のノードに接続
while(tmplist->next != NULL)
{
tmplist = tmplist->next;
}
#if _DEBUG
assert(this->CheckNode(node));
#endif
// リストの生成
tmplist->next = new list<T>;
tmplist->next->next = NULL;
tmplist->next->prev = tmplist;
tmplist->next->data = setdata;
return node;
}
// テイルを移行
tail = tmplist->next;
}
// 先頭ノード追加
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;
// 先頭削除
template <class T>
void list<T>::dellisthead()
{
//削除不能
if(length < 0)
return;
head = head->prev; // ヘッドの移動
head->data = setdata;
return;
}
list* del = head;
head = head->next;
head->prev = NULL;
}
delete del;
// 末尾ノード追加
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
{
length--;
}
// テイルしかない
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 list<T>::dellist(int delnum)
{
//削除不能
if(length < 0)
return;
}
}
// 最小以下
if(delnum < 0)
delnum = 0;
// 最大以上
if(delnum > length)
delnum = length;
// インデックス番号のノード削除
template <class T>
void CList<T>::DelNode(int index)
{
// ノードを探す
Node* delnode = this->SearchNode(index);
list* tmplist = head;
list* del;
#if _DEBUG
assert(delnode);
#endif
for(int i = 0;i < delnum;++i)
tmplist = tmplist->next;
// ノードがない場合
if(delnode == NULL)
return;
del = tmplist;
// ヘッド=テイルである場合
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;
// 末尾
if(tmplist->next == NULL)
{
tail = tail->prev;
tail->next = NULL;
}
// 先頭
else if(tmplist->prev == NULL)
{
head = head->next;
head->prev = NULL;
}
// 中間
else
{
tmplist->prev->next = tmplist->next;
tmplist->next->prev = tmplist->prev;
}
length--;
delete delnode;
return;
}
}
}
delete del;
// ノードポインタのノード削除
template <class T>
void CList<T>::DelNode(Node* delnode)
{
// 存在しているノードなのか確認
#if _DEBUG
assert(delnode = this->SearchNode(delnode));
#endif
length--;
}
if(delnode == NULL)
return;
// 末尾削除
template <class T>
void list<T>::dellisttail()
{
//削除不能
if(length < 0)
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;
list* del = tail;
tail = tail->prev;
tail->next = NULL;
length--;
delete delnode;
return;
}
}
delete del;
}
length--;
}
// 全ノード削除
template <class T>
void CList<T>::DelAllNode()
{
Node* tmp = head;
// ヘッドからすべてのノードをたどり消す
while(tmp != NULL)
{
Node* del = tmp;
tmp = tmp->next;
delete del;
}
// 指定番号のリストデータを取り出す
template <class T>
T list<T>::get(int getnum)
{
// 最小以下
if(getnum < 0)
getnum = 0;
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;
// 最大以上
if(getnum > length)
getnum = length;
list* tmplist = head;
}
for(int i = 0;i < getnum;++i)
tmplist = tmplist->next;
head = NULL;
tail = NULL;
length = 0;
return tmplist->data;
}
// 指定番号のリストデータにデータを追加する
template <class T>
void list<T>::set(int setnum,T setdata)
{
// 最小以下
if(setnum < 0)
setnum = 0;
// 最大以上
if(setnum > length)
setnum = length;
}
list* tmplist = head;
for(int i = 0;i < setnum;++i)
tmplist = tmplist->next;
// リスト長取得
template <class T>
int CList<T>::GetLength()
{
return static_cast<int>(length);
}
tmplist->data = setdata;
}
int main()
{
// メモリリーク検出用
#ifdef _DEBUG
_CrtSetDbgFlag(_CrtSetDbgFlag(_CRTDBG_REPORT_FLAG) | _CRTDBG_LEAK_CHECK_DF);
_CrtSetBreakAlloc(58); // リーク箇所チェック
#endif
// リスト長を返す
template <class T>
int list<T>::getlength()
{
return length + 1;
}
return 0;
}
#vote((^ω^)余裕だおっおっお[5],-[0],。(`ω´#)。ちょっと出直してくる[0])