酒居敬一(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.

Slides:



Advertisements
Similar presentations
アルゴリズムとプログラミン グ (Algorithms and Programming) 第6回:クラスとインスタンス クラスの宣言 アクセス修飾子 インスタンスの生成 (new キーワード) this キーワード フィールドとメソッドの実際の定義と使い 方 クラスの宣言 アクセス修飾子 インスタンスの生成.
Advertisements

アルゴリズムとデータ構造 2012年6月27日
5.データ構造入門 5-1.連結リスト(Linked List) 5-2.スタック(Stack) 5-3.キュー(Queue)
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
データ構造とアルゴリズム 第10回 mallocとfree
アルゴリズムとデータ構造1 2007年6月12日
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
情報工学概論 (アルゴリズムとデータ構造)
オペレーティングシステムJ/K 2004年11月4日
アルゴリズムとデータ構造 第3回基本的なデータ構造(リスト) 2015/10/28 アルゴリズムとデータ構造 2015.
アルゴリズムとデータ構造 2011年6月13日
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
アルゴリズムとデータ構造 2011年6月9日
アルゴリズムとデータ構造1 2009年6月25日
アルゴリズムとデータ構造 第2回 線形リスト(復習その2).
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
第13回 ハッシュテーブルを使ったプログラム ~高速に検索するには?~.
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
アルゴリズムとデータ構造 2013年6月17日
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
暗黙的に型付けされる構造体の Java言語への導入
アルゴリズムとデータ構造 2013年7月16日
アルゴリズムとデータ構造1 2006年7月4日
プログラミング 4 記憶の割り付け.
アルゴリズムとデータ構造1 2005年7月15日
コンパイラ 2012年11月15日
アルゴリズムとデータ構造勉強会 第6回 スレッド木
アルゴリズムとデータ構造 2010年6月28日
オペレーティングシステムJ/K (仮想記憶管理)
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
データ構造と アルゴリズム 第五回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
簡易データベース 情報画像工学実験 I : 実験2 担当:関屋大雄(工学部1号棟515室)
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
6.データ構造入門 6-1.連結リスト(Linked List) 6-2.スタック(Stack) 6-3.キュー(Queue)
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
オペレーティングシステムJ/K (管理のためのデータ構造)
サブゼミ第7回 実装編① オブジェクト型とキャスト.
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造1 2009年6月15日
ネットワーク・プログラミング Cプログラミングの基礎.
アルゴリズムとデータ構造 2012年6月25日
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造 2010年6月17日
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
TList リスト構造とは? 複数のデータを扱うために、 データの内容と、次のデータへのポインタを持つ構造体を使う。
Presentation transcript:

酒居敬一(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;

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

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