酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2005年7月5日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2005/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; /* 構造体型の自己参照 */ };

連結リスト操作（挿入） リストを使ったスタック（push） 先頭 次 データ 次 データ データをそれぞれの要素に格納 要素どおし、つながってリストを形成 単純な連結リスト（線形リスト）データ挿入

連結リストの宣言 リストへの挿入 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();

連結リスト操作（削除） リストを使ったスタック（pop） 先頭 次 データ 単純な連結リスト（線形リスト）データ削除

リストへの挿入・削除を先頭に限定すれば スタック構造が実現できる 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; // public String toString() は省略… private Object data; private DoublyElement next; private DoublyElement 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;

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

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