アルゴリズムとデータ構造1

アルゴリズムとデータ構造1
2007年6月22日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2007/index.html
講義計画
1.
2.
アルゴリズムとデータ構造入門（６月８日２時限）
アルゴリズムとデータ構造基礎（６月１２日２時限）
3.
メモリとデータ構造（６月１４日４時限）
4.
プログラムとアルゴリズム（６月１５日２時限）
5.
配列（６月１９日２時限）
6.
連結リスト（６月２２日２時限）
7.
スタック（６月２５日４時限）
8.
待ち行列（６月２６日２時限）
•
第１章の演習（６月２９日２時限）
9.
二分木（７月３日２時限）
10. 探索（７月５日４時限）
11.
ハッシュ（７月６日２時限）
•
第２章の演習（７月１０日２時限）
12. ソート（７月１３日２時限）
13. 再帰的アルゴリズム（７月１７日２時限）
14. くり返し処理と再帰的処理（７月１９日４時限）
•
第３章の演習（７月２０日２時限）
15. ［クォータ末試験］（７月２７日２時限Ｋ１０１）
Ｊａｖａのデストラクタ
• デストラクタは、delete によりインスタンスが
消滅するときに呼ばれる(C++の場合…)。
• Java には delete もデストラクタもない。
– 似たものに Object.finalize() というメソッドがある。
• gcにより、インスタンスが消滅するときに呼ばれる。
– もちろん、オーバーライドできる。
– いつ呼ばれるかわからない。
– System.gc()と同期して処理される、とは限らない。
連結リスト（２９ページ）
• データをそれぞれの要素に格納
• 要素どおし、つながってリストを形成
先頭
データ
データ
データ
次
次
次
データを動かすことなく、要素の挿入・削除ができる
// リストを形成するためのデータ構造
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; /* 構造体型の自己参照 */
};
連結リスト操作（挿入）
先頭
データ
データ
データ
次
次
次
データ
次
図1.3.5 教科書31ページ
単純な連結リスト（線形リスト）データ挿入
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){
System.err.println("その場所には挿入はできません: " + aPosition);
return false;
}
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){
System.err.println
("その場所は削除できません: " + aPosition);
return false;
}
Element previousElement = this.getElement(aPosition - 1);
previousElement.setNextElement(targetElement.getNextElement());
targetElement.setNextElement(null);
return true;
}
例：メモリ割り当て（３７ページ）
最も簡単なメモリ割り当てアルゴリズム
・リストで管理
・データ領域を分断し、あらたなリスト要素として、挿入
・リストのヘッダには空きか使用中かのフラグがある
・割当てるデータ領域はリストのヘッダとヘッダの間
使用状況を示すフラグ
次のヘッダを指すポインタ
空き
空き使用中
ヘッダは左のような構造
要素としては、フラグとポインタしかない
空きの領域
使用中
空き
空き使用中
空き
空き
空き空き
使用中
メモリの割り付け・開放を繰り返していくとメモリが分断するようになる
・フラグメンテーションといい、大きな領域を割り当てできなくなる
・そこで、ときおり、空き領域にはさまれたヘッダを削除する
メモリ割付け技法
•連続割付け
•単一連続割付け
•分割割付け(ゾーン割り付け)
•固定区画割付け
•可変区画割付け
•非連続割付け
•ページング
•セグメンテーション
管理手法
•線形リスト
•ハッシュ表
双方向連結リスト（３９ページ）
• 連結リストを双方にリンクしたもの
データ
データ
データ
先頭
次
次
次
最後
前
前
前
両方向から探索できる
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();
}
public Object get(int aPosition)
return length;
{
}
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){
return null;
}
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){
System.err.println
("その場所には挿入はできません: " + aPosition);
return false;
}
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){
System.err.println
("その場所は削除できません: " + aPosition);
return false;
}
DoublyElement previousElement = this.getElement(aPosition - 1);
previousElement.setNextElement(targetElement.getNextElement());
targetElement.getNextElement().setPreviousElement(previousElement);
targetElement.setNextElement(null);
targetElement.setPreviousElement(null);
return true;
}

Download Report