酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2006年6月23日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2006/index.html

データを動かすことなく、要素の挿入・削除ができる 連結リスト（２９ページ） データをそれぞれの要素に格納 要素どおし、つながってリストを形成 先頭 次 データ データを動かすことなく、要素の挿入・削除ができる

クラスの自己参照 宣言は未完了だが特別な記述は不要 インスタンスの自己参照 this による参照 // リストを形成するためのデータ構造 public class Element { private Element() } public Element(Object aData) this.data = aData; public Object getData() return this.data; クラス宣言の中における クラスの自己参照 　　宣言は未完了だが特別な記述は不要 インスタンスの自己参照 　　this による参照 public Element getNextElement() { return this.next; } public void setNextElement(Element anNextElement) this.next = anNextElement; public String toString() if(null != this.next){ return (this.data.toString() + " → "); }else{ return this.data.toString(); private Object data; private Element next; // クラスの自己参照

自己参照 宣言の中で自分自身を参照すること 一見すると奇妙な点がある Java言語では自分の中に自分を含むように見える 宣言が完了する前に自分自身を参照していること 宣言が未完了では、当然、インスタンスは定義できないはず C言語で書くと、ポインタを置いている 参照ということは、型が未定義でも大きさは計算可能 /* リストを形成するためのデータ構造 in C language */ struct Element { void *data; struct Element *next; /* 構造体型の自己参照 */ };

連結リスト操作（挿入） 先頭 次 データ 次 データ 図2.4.1・2.4.2 教科書41・42ページ 図2.4.1・2.4.2　教科書41・42ページ 単純な連結リスト（線形リスト）データ挿入

連結リストの宣言 リストへの挿入 public class MyLinkedList { public MyLinkedList() this.firstElement = new Element(null); } public boolean insert(Object aData) return this.insert(1, aData); private Element firstElement; 連結リストの宣言 リストへの挿入 public boolean insert(int aPosition, Object aData) { if(1 > aPosition){ System.err.println("その場所には挿入はできません: " + aPosition); return false; } Element previousElement = this.getElement(aPosition - 1); if(null == previousElement){ Element element = new Element(aData); element.setNextElement(previousElement.getNextElement()); previousElement.setNextElement(element); return true;

public Element getElement(int aPosition) { Element currentElement = this.firstElement; for(int count = 0; count < aPosition; count++){ if(null == currentElement){ return null; } currentElement = currentElement.getNextElement(); return currentElement; public int search(Object aData) { int count = 1; Element currentElement = this.firstElement.getNextElement(); while(null != currentElement){ if(currentElement.getData().equals(aData)){ return count; } ++count; currentElement = currentElement.getNextElement(); return -1;

public Object get(int aPosition) { Element element = this.getElement(aPosition); if(null == element){ System.err.println("指定した場所には要素がありません"); return null; } return element.getData(); public int size() { int length = 0; Element currentElement = this.firstElement.getNextElement(); while(null != currentElement){ ++length; currentElement = currentElement.getNextElement(); } return length; public void printAll() { Element currentElement = this.firstElement.getNextElement(); while(null != currentElement){ System.out.print(currentElement); currentElement = currentElement.getNextElement(); } System.out.println();

連結リスト操作（削除） 先頭 次 データ 図2.4.3　教科書43ページ 単純な連結リスト（線形リスト）データ削除

リストへの挿入・削除を先頭に限定すれば スタック構造が実現できる public boolean remove(Object aData) { int position = this.search(aData); return this.remove(position); } リストへの挿入・削除を先頭に限定すれば スタック構造が実現できる public boolean remove(int aPosition) { if(1 > aPosition){ System.err.println ("その場所は削除できません: " + aPosition); return false; } Element targetElement = this.getElement(aPosition); if(null == targetElement){ Element previousElement = this.getElement(aPosition - 1); previousElement.setNextElement(targetElement.getNextElement()); targetElement.setNextElement(null); return true;

例：メモリ割り当て（３７ページ） 最も簡単なメモリ割り当てアルゴリズム ・リストで管理 ・データ領域を分断し、あらたなリスト要素として、挿入 ・リストのヘッダには空きか使用中かのフラグがある ・割当てるデータ領域はリストのヘッダとヘッダの間 使用状況を示すフラグ 次のヘッダを指すポインタ ヘッダは左のような構造 要素としては、フラグとポインタしかない 空きの領域 使用中 空き 空き 使用中

メモリの割り付け・開放を繰り返していくとメモリが分断するようになる ・フラグメンテーションといい、大きな領域を割り当てできなくなる 空き 使用中 空き 空き 空き 空き 使用中 メモリの割り付け・開放を繰り返していくとメモリが分断するようになる ・フラグメンテーションといい、大きな領域を割り当てできなくなる ・そこで、ときおり、空き領域にはさまれたヘッダを削除する メモリ割付け技法 連続割付け 単一連続割付け 分割割付け(ゾーン割り付け) 固定区画割付け 可変区画割付け 非連続割付け ページング セグメンテーション 管理手法 線形リスト ハッシュ表

双方向連結リスト（３９ページ） 連結リストを双方にリンクしたもの 先頭 次 データ 最後 前 両方向から探索できる

リストを形成する要素として nextとpreviousが定義されて リストを双方向にたどれるようにしている public class DoublyElement { public DoublyElement(Object aData) this.data = aData; } public Object getData() return this.data; public DoublyElement getNextElement() return this.next; public DoublyElement getPreviousElement() return this.previous; リストを形成する要素として nextとpreviousが定義されて リストを双方向にたどれるようにしている public void setNextElement (DoublyElement anNextElement) { this.next = anNextElement; } public void setPreviousElement (DoublyElement anPreviousElement) this.previous = anPreviousElement; private Object data; private DoublyElement next, previous;

public class DoublyLinkedList { public DoublyLinkedList() this.firstElement = new DoublyElement(null); this.lastElement = new DoublyElement(null); this.firstElement.setNextElement(this.lastElement); this.lastElement.setPreviousElement(this.firstElement); } private DoublyElement firstElement; private DoublyElement lastElement; public int search(Object aData) { int count = 1; DoublyElement currentElement = this.firstElement.getNextElement(); while(currentElement != this.lastElement){ if(currentElement.getData().equals(aData)){ return count; } ++count; currentElement = currentElement.getNextElement(); return -1;

public int size() { int length = 0; DoublyElement currentElement = this.firstElement.getNextElement(); while(currentElement != this.lastElement){ ++length; currentElement = currentElement.getNextElement(); } return length; public Object get(int aPosition) { DoublyElement element = this.getElement(aPosition); if(null == element){ System.err.println("指定した場所には要素がありません"); return null; } return element.getData(); public DoublyElement getElement(int aPosition) DoublyElement currentElement = this.firstElement; for(int count = 0; count < aPosition; count++){ if(currentElement == this.lastElement){ currentElement = currentElement.getNextElement(); return currentElement;

双方向連結リスト（挿入） キューへのデータの挿入 先頭 次 データ 最後 前 次 データ 前 双方向連結リスト　データ挿入 連結リストを双方にリンクしたもの

public boolean insert(Object aData) { return this.insert(1, aData); } public boolean insert(int aPosition, Object aData) if(1 > aPosition){ System.err.println ("その場所には挿入はできません: " + aPosition); return false; DoublyElement previousElement = this.getElement(aPosition - 1); if(null == previousElement){ DoublyElement element = new DoublyElement(aData); element.setNextElement(previousElement.getNextElement()); previousElement.getNextElement().setPreviousElement(element); previousElement.setNextElement(element); element.setPreviousElement(previousElement); return true;

双方向連結リスト操作（削除） キューからのデータの取り出し 先頭 次 データ 最後 前 双方向連結リスト　データ削除

public boolean remove(Object aData) { int position = this.search(aData); return this.remove(position); } public boolean remove(int aPosition) if(1 > aPosition){ System.err.println ("その場所は削除できません: " + aPosition); return false; DoublyElement targetElement = this.getElement(aPosition); if(null == targetElement){ DoublyElement previousElement = this.getElement(aPosition - 1); previousElement.setNextElement(targetElement.getNextElement()); targetElement.getNextElement().setPreviousElement(previousElement); targetElement.setNextElement(null); targetElement.setPreviousElement(null); return true;