frostar@wiki
リスト構造
最終更新:
frostar
-
view
リスト構造はデータと次のデータへのアドレスを1つの塊(ノード)として持っていて、それを連ねたデータ構造である。
- 利点
- データの挿入、削除がしやすい
- データをどんどん追加できる
- 欠点
- 目的のデータへのアクセスが面倒
まずはノードを作ってみる。
Data型という型のデータを格納するリストについて考える。
Data型という型のデータを格納するリストについて考える。
class Node{ Data data; Node* next; }
次のデータへのポインタは自分の型のポインタになる。
ちなみに、とりあえず各データへアクセスするためのメソッドについては置いておく。
ちなみに、とりあえず各データへアクセスするためのメソッドについては置いておく。
リストの本体は次のようになる
class List{ Node* rootP;//先頭ノードのポインタ void addData(Data& d);//データ追加 void insertData(int n,Data& d);//データ挿入 Data getData(int n);//データ取得 void remove(int n);//データ削除 }
各メソッド
void addData(Data& d){ Node* node = new Node(d); if(rootP == NULL){ rootP = data; }else{ Node* p; for(p=rootP;p->getNext()!=NULL;p=p->getNext()); p->setNext(node); } }
getNext、setNextはそれぞれNode型のnextにアドレスを格納するためのメソッド。
まず、nodeというNode型のデータをnewで作る。
rootPがNULLの時(データがない時)はrootPにnodeを格納。
それ以外なら、先頭から順次ノードを見て、nextがNULL(次のデータがない→最後のデータ)のデータの次にnodeを追加する。
まず、nodeというNode型のデータをnewで作る。
rootPがNULLの時(データがない時)はrootPにnodeを格納。
それ以外なら、先頭から順次ノードを見て、nextがNULL(次のデータがない→最後のデータ)のデータの次にnodeを追加する。
void insertData(int n,T& d){ Node* node = new Node(d); if(n==0){ node->setNext(rootP); rootP=node; }else{ Node* p = rootP; for(int i=1;i<n;i++){ if(p==NULL)break; p=p->getNext(); } node->setNext(p->getNext()); p->setNext(data); } }
n番目にデータを挿入する。
基本的にはaddとあまり変わらない。
nが0ならnodeの次のデータとして、現在の先頭ノードを入れ、rootPにnodeのアドレスを入れることで、nodeを先頭ノードとしている。
それ以外なら、データをn回たどって、その次のノードにnodeを挿入する。
挿入場所の1つ前のノードのnextに挿入ノードのアドレスを入れ、挿入ノードのnextに1つ前のノードの次のノードを格納することで実現できる。
基本的にはaddとあまり変わらない。
nが0ならnodeの次のデータとして、現在の先頭ノードを入れ、rootPにnodeのアドレスを入れることで、nodeを先頭ノードとしている。
それ以外なら、データをn回たどって、その次のノードにnodeを挿入する。
挿入場所の1つ前のノードのnextに挿入ノードのアドレスを入れ、挿入ノードのnextに1つ前のノードの次のノードを格納することで実現できる。
Data getData(int n){ Node* p = rootP; for(int i=0;i<n;i++){ if(p==NULL)break; p=p->getNext(); } if(p==NULL)return NULL; return p->getData(); }
データの取得も、n回たどって、そのデータを返してるだけである。
void remove(int n){ if(0<=n && rootP!=NULL){ Node *p = rootP; Node *bp = NULL; for(int i=0;i<n;i++){ bp=p; p=p->getNext(); } if(p==NULL)break; if(bp==NULL)rootP=p->getNext(); else bp->setNext(p->getNext()); delete p; } }
削除するときは、削除対象ノードの前のノードのnextを削除対象ノードの次のノードにして、データを削除することで実現できる。
今回は単方向リストを作成したが、ひとつ後ろのノードのアドレスを持つ双方向リストも存在する。
双方向リストでは、データの検索性が上がるが、処理が増えるし、それほど大きくないデータなら単方向リストで十分だと思う。
また、最大数や検索ポインタなどの処理を追加してもいいだろう。
あくまで今回のは最低限レベルである。
実際、何のデータをリストに格納するかはわからないので、C++だとtemplateを使うといい。
双方向リストでは、データの検索性が上がるが、処理が増えるし、それほど大きくないデータなら単方向リストで十分だと思う。
また、最大数や検索ポインタなどの処理を追加してもいいだろう。
あくまで今回のは最低限レベルである。
実際、何のデータをリストに格納するかはわからないので、C++だとtemplateを使うといい。