逆転を狙う工大生の日々

絶賛留年中の落ちこぼれがなんとか頑張ろうとしている日記です

Javaで深さ優先探索と幅優先探索

とうとうやってまいりました。深さ優先探索幅優先探索。実装につきましては、以下のサイトを参考にさせていただきました。ありがとうございます。参考というかまんま・・・

http://d.hatena.ne.jp/lettas0726/20110418/1303097692

 今回は2分木で各探索を実現しましたが、2分木についての概要を簡単に

木構造の一種

・そもそも木構造とは?

→ 階層関係を実現するためのデータ構造。データを「節(ノード)」にもたせて、それを「枝(エッジ)」で繋ぐことで、各データの関係を階層的に表現することが出来る。一番上のノードを「」、あるノードAから見て、エッジで結ばれていて、かつ根に近いノードBのことを「BはAの親ノード」といい、逆に「AはBの子ノード」という。

・K分木とは、各ノードについて、その子ノードが最大でK個である木のこと

・つまり2分木は、各ノードの子ノードが最大2つである木

 

ふむふむ。度々習ってきたことなので概要だけならわかるぞ。いよいよ実装です。

2分木構造の表現


	BinaryTree left; //2分木の左の子ノード
	BinaryTree right; //右の子ノード
	Object data; //このノードのデータ
	
	//新たなノードを生成する
	public BinaryTree(Object data, BinaryTree left, BinaryTree right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}    

2分木はこれで良さそうですね。これはリスト構造のnextと考え方はにてますね。

 

続いて、深さ優先探索についての概要を

・DFS(Depth First Search)

・始点からの距離には関係なく、訪問できる節を出来るだけ深く訪問していく探索法

・始点からどんどん深い階層にたどっていき、子ノードがないノードに到達したら、ひとつ前のノードに戻って再びそこからたどっていくという方法。

・スタックを用いて実現

 2分木だと、ずっと左の子ノードをたどっていき、子ノードが無くなったら、一つ前のノードの右の子ノードを訪れて同様にたどっていくという感じですね。バックトラックがこういう辿り方をするはずです。・・・ですよね?

DFSの実装

	//状況に合った子ノードを返す(DFS用)
	public BinaryTree[] getChildrenDfs(){
		if(left != null && right != null){
			BinaryTree[] o = {right,left};
			return o;
		}else if(left != null && right == null){
			BinaryTree[] o = {left};
			return o;
		}else if(left == null && right != null){
			BinaryTree[] o = {right};
			return o;
		}
		BinaryTree[] o = {};
		return o;
	}
	
	public void dfs(BinaryTree t,Object goal){
		ArrayDeque stack = new ArrayDeque();
		stack.push(t);
		while(!stack.isEmpty()){
			BinaryTree t1 = stack.pop();
			System.out.println(t1.data + "を訪れました");
			if(t1.data == goal){
				System.out.println("目標" + goal + "に到達しました");
				break;
			}
			for(BinaryTree t2 : t1.getChildrenDfs()){
				stack.push(t2);
			}
		}
	}

まずは、現在訪れているノードの子ノードを返す関数getChildrenDfs()について。まあ子ノードを返すだけです。左右ノードが存在するときに{right,left}とするのは、配列の先頭からスタックにプッシュするとき、この順番じゃないと右ノードから深くたどっていってしまうからです。深さ優先探索は、

1,スタックから要素をポップ

2,要素で何かする

3,子ノードをプッシュ

4,終了条件まで繰り返す

という思ったより簡単なアルゴリズムでした。多分覚えました。

 

続いて、幅優先探索の概要を

・BFS(Breath First Search)

・同じ階層の要素を左ノードからすべて探索した後、一つ下の階層にうつって同様にすべて探索する。これを繰り返す。

・キューを用いて実現する

こちらのほうが言葉で説明しやすいですねw 絶対に左ノードから辿る必要はないのかな?

BFSの実装

	//状況に合った子ノードを返す(BFS用)
	public BinaryTree[] getChildrenBfs(){
		if(left != null && right != null){
			BinaryTree[] o = {left,right};
			return o;
		}else if(left != null && right == null){
			BinaryTree[] o = {left};
			return o;
		}else if(left == null && right != null){
			BinaryTree[] o = {right};
			return o;
		}
		BinaryTree[] o = {};
		return o;
	}
	public void bfs(BinaryTree t,Object goal){
		ArrayDeque queue = new ArrayDeque();
		queue.offer(t);
		while(!queue.isEmpty()){
			BinaryTree t1 = queue.poll();
			System.out.println(t1.data + "を訪れました");
			if(t1.data == goal){
				System.out.println("目標" + goal + "に到達しました");
				break;
			}
			for(BinaryTree t2 : t1.getChildrenBfs()){
				queue.offer(t2);
			}
		}
	}

こちらでは子ノードを{left,right}の順番にしています。キューはFIFOなのでこうしないと右ノードからたどってしまいます。右ノードからでも良いとは思いますがね。DFSにおけるスタックがキューに変わっただけでこうなるとはなんか凄いですね。スタックもキューも使い方次第でこうも違うのかと。

実行結果

public class Main {
	public static void main(String[] args) {
		BinaryTree t = 
		new BinaryTree("S",new BinaryTree("a",new BinaryTree("c",null,null),
				new BinaryTree("d",null,null)),new BinaryTree("b",new BinaryTree(
				"e",null,null),new BinaryTree("f",null,null)));
				
		System.out.println("DFSの結果");
		t.dfs(t,"e");
		System.out.println("----------------------------------------");
		System.out.println("BFSの結果");
		t.bfs(t,"e");
	}
}

f:id:ikuth:20140514214232p:plain

この図のような木を生成します。そして各探索の結果を出力します。

f:id:ikuth:20140514214556p:plain

出来ました!!ちゃんとスタックやキューの中身も出力させたほうが良かったかなーと思いながら、紙とペンでその辺はしっかり手を動かしたので動きもつかめました。

 

なんとか更新間に合いました。疲れてて日中ずっとボケっとしてたツケが・・・。

 今期中はとりあえずJavaで色々やってこうと思います。CとかC++は暇になる来期にみっちりやってこうと・・・。

 

内容がしょっぱすぎて、プログラミングタグつけるの怖くなってきたけど許して。

アセンブリで挿入ソート〜完成版〜

いろいろ調べてようやくできたので貼り付けておきます。ソート部分以外はほとんどいろんなサイトを参考にしながらの構成となってしまった。英語読めるようになれば調べるのも楽になるのかな。


         .data
array_elem_num: .asciiz"array_elem_num : "
bracket_1: .asciiz "["
bracket_2: .asciiz "]"
input:  .asciiz"input"
output: .asciiz"output"
equal:  .asciiz"="
line:   .asciiz"--------result--------"
eol:    .asciiz"\n"

        .text
        .globl main

main:
        jal     read
        li      $v0,    4
        la      $a0,    line
        syscall
	li	$v0,	4
	la	$a0,	eol
	syscall
        jal     sort
        jal     print
        j       main

read:   # 「$s0 = 配列の先頭アドレス」「$s1 = 配列のサイズ」
        # 配列の大きさを読み込むためのメッセージ
        li      $v0,    4
        la      $a0,    array_elem_num
        syscall

        # 配列の大きさの入力を受け付ける
        li      $v0,    5
        syscall

        # 配列のサイズを$1に取り込む
        move    $s1,    $v0

        # 配列を生成して先頭アドレスを受け取る
        sll     $a0,    $v0,    2
        li      $v0,    9
        syscall

        # 生成した配列の先頭アドレスを$s0に保存
        move    $s0,    $v0

        # 配列のオフセット用のレジスタとして$t0を初期化する
        move    $t0,    $zero

        loop:

        # "input[0]="~"input[array_elem_num]="と表示する
        li      $v0,    4
        la      $a0,    input
        syscall
        la      $a0,    bracket_1
        syscall
        li      $v0,    1
        move    $a0,    $t0
        syscall
        li      $v0,    4
        la      $a0,    bracket_2
        syscall
	li	$v0,	4
	la	$a0,	equal
	syscall

        # 設定する配列要素の値を受け取る
        li      $v0,    5
        syscall

        # 取り込んだ値を保存する
        sll     $t1,    $t0,    2
        add     $t1,    $t1,    $s0
        sw      $v0,    0($t1)

        # オフセットをインクリメントする
        addi    $t0,    $t0,    1

        # 入力し終えたかチェック
        bne     $t0,    $s1,    loop

        # 改行する
        li      $v0,    4
        la      $a0,    eol
        syscall

        jr      $ra

sort:   # 挿入ソート「$s2 = i」「$s3 = j」とする
        # i = 1
        li    $s2,    1
       
        # for(i=1;「i < array_elem_num」; i++)
        loop1:
	beq	$s2,	$s1,	loop1_end

	# j = i
	move	$s3,	$s2
	
        # for(j=i; 「j >= 1」; j-- )
        loop2:
        beq     $s3,    $zero,	loop2_end                      

        # $t1 = a[j]
        sll     $t0,    $s3,    2
        add     $t0,    $t0,    $s0
        lw      $t2,    0($t0)

        # $t2 = a[j-1]
        addi    $t1,    $s3,    -1
        sll     $t1,    $t1,    2
        add     $t1,    $t1,    $s0
        lw      $t3,    0($t1)

        # a[j-1] > a[j]ならswapする
        # swap 
	ble	$t3,	$t2,	swap_end
        sw      $t2     0($t1)
        sw      $t3     0($t0)
        swap_end:
       
        # j--してjループの先頭に
        addi    $s3,    $s3,    -1
        j       loop2

	# i++してiループの先頭に
        loop2_end:
        addi    $s2,    $s2,    1
        j       loop1

        loop1_end:
        jr      $ra

print:
        # 配列のオフセットとして$t0を初期化
        move    $t0,    $zero

        # output[0]~output[array_elem_num]をread部分同様プリントする
        loop_p:
        li      $v0,    4
        la      $a0,    output
        syscall
        li      $v0,    4
        la      $a0,    bracket_1
        syscall
        li      $v0,    1
        move    $a0,    $t0
        syscall
        li      $v0,    4
        la      $a0,    bracket_2
        syscall
        li      $v0,    4
        la      $a0,    equal
        syscall

        # 配列の値を読み込んで出力
        sll     $t1,    $t0,    2
        add     $t1,    $t1,    $s0
        li      $v0,    1
        lw      $a0,    0($t1)
        syscall
       
        # 改行
        li      $v0,    4
        la      $a0,    eol
        syscall

        # オフセットをインクリメント
        addi    $t0,    $t0,    1
       
        # すべて出力して無ければ戻る
        bne     $t0,    $s1,    loop_p

        # 改行
        li      $v0,    4
        la      $a0,    eol
        syscall

        jr      $ra
 

こんな感じです。未完成のほうの記事は消すつもりだったのですが、あとで比較するのも面白いかなと思ったので残しときます。こちらは実行結果。ずっと繰り返します。提出前には0を入力すると終了するようにしときます。

f:id:ikuth:20140513111017p:plain

 

 

アセンブリちょっとだけ学校でやったけど

大分ミスがあったうえに、修正中大学の計算機室が調子悪くて途中離脱。新年度になってシステム変わった影響で度々フリーズするのですが、なんとかしてほしい。システム自体は使いやすくやってるんだから。

 

とりあえずちょこちょこいじった結果読み込みとプリントはできましたが、肝心のソート部分が出来てないというw

 

どっかでアドレスの受け渡しか、分岐ミスってるのかな。また戦ってきます。

アセンブリで挿入ソート~未完成ver~

ひだまりスケッチ一挙放送に時間を取られました。よかったです。

再履修の科目で、MIPSアセンブリでプログラム作成という課題がそのうち出ます。二つあって、去年のその片方はソートアルゴリズムを一つ実装してくださいという内容でした。去年は途中で投げ出しましたが、心を入れ替えた僕は強いのであらかじめやっておこうと。挿入ソートを選択した理由は、ソートする配列の要素はコンソール上の手入力という指定なので、そこまで大きなデータは取り扱わないと思い、実装の容易さと計算量的には妥当な落としどころだと思ったからです。

 

クイックソートが出来る気がしないというのはナイショで

 

それでいざ書き終えたのは良かったのですが、自宅のPCspimだとなんかうまくいかないので明日大学のでやってみます。英語読めないから分かんないです。コンパイルは通ったのでソースだけ貼っつけときますが、結果はどうなるのでしょうか。


	.data
array_elem_num:	.asciiz"array_elem_num : "
bracket_1: .asciiz "["
bracket_2: .asciiz "]"
input:	.asciiz"input"
output:	.asciiz"output"
equal:	.asciiz"="
line:	.asciiz"--------result--------"
eol:	.asciiz"\n"

	.text
	.globl main

main:
	jal	read
	li	$v0,	4
	la	$a0,	line
	syscall
	jal	sort
	jal	print
	j	main

read:	# 「$s0 = 配列の先頭アドレス」「$s1 = 配列のサイズ」
	# 配列の大きさを読み込むためのメッセージ
	li	$v0,	4
	la	$a0,	array_elem_num
	syscall
	
	# 配列の大きさの入力を受け付ける
	li	$v0,	5
	syscall

	# 配列のサイズを$1に取り込む
	move	$s1,	$v0

	# 配列を生成して先頭アドレスを受け取る
	sll	$a0,	$v0,	2
	li	$v0,	9
	syscall

	# 生成した配列の先頭アドレスを$s0に保存
	move	$s0,	$v0

	# 配列のオフセット用のレジスタとして$t0を初期化する
	move	$t0,	$zero

	loop:

	# "input[0]="~"input[array_elem_num]="と表示する
	li	$v0,	4
	la	$a0,	input
	syscall
	la	$a0,	bracket_1
	syscall
	li	$v0,	1
	move	$a0,	$t0
	syscall
	li	$v0,	4
	la	$a0,	bracket_2
	syscall

	# 設定する配列要素の値を受け取る
	li	$v0,	5
	syscall

	# 取り込んだ値を保存する
	sll	$t1,	$t0,	2
	add	$t1,	$t1,	$s0
	sw	$v0,	0($t1)

	# オフセットをインクリメントする
	addi	$t1,	$t1,	1

	# 入力し終えたかチェック
	bne	$t0,	$s1,	loop

	# 改行する
	li	$v0,	4
	la	$a0,	eol
	syscall

	jr	$ra

sort:	# 挿入ソート「$s2 = i」「$s3 = j」とする
	# i = 0
	move	$s2,	$zero
	
	# for(i=0;「i < array_elem_num」; i++)
	loop1:
	slt	$t5,	$s2,	$s1
	bne	$t5,	$zero,	loop1_end

	# for(「j=i」; j >= 1; j-- )
	loop2:
	sltu	$t3,	$s3,	1
	bne	$t3,	$zero,	loop2_end			
	move	$s3,	$s2

	# $t1 = a[j]
	sll	$t0,	$s3,	2
	add	$t0,	$t0,	$s0
	lw	$t1,	0($t0)

	# $t2 = a[j-1]
	addi	$t0,	$s3,	-1
	sll	$t0,	$t0,	2
	add	$t0,	$t0,	$s0
	lw	$t2,	0($t0)

	# a[j-1] > a[j]ならswapする
	ble	$t2,	$t1	swap_end	

	# swap 
	lw	$t3	0($t1)
	lw	$t4	0($t2)
	sw	$t3	0($t2)
	sw	$t4	0($t1)
	swap_end:
	
	# j--してループの先頭に
	addi	$s3,	$s3,	-1
	j	loop2
	
	loop2_end:
	addi	$s2,	$s2,	1
	j	loop1

	loop1_end:
	jr	$ra

print:
	# 配列のオフセットとして$t0を初期化
	move	$t0,	$zero

	# output[0]~output[array_elem_num]をread部分同様プリントする
	loop_p:
	li	$v0,	4
	la	$a0,	output
	syscall
	li	$v0,	4
	la	$a0,	bracket_1
	syscall
	li	$v0,	1
	move	$a0,	$t0
	syscall
	li	$v0,	4
	la	$a0,	bracket_2
	syscall
	li	$v0,	4
	la	$a0,	equal
	syscall

	# 配列の値を読み込んで出力
	sll	$t1,	$t0,	2
	add	$t1,	$t1,	$s0
	li	$v0,	1
	lw	$a0,	0($t1)
	syscall
	
	# 改行
	li	$v0,	4
	la	$a0,	eol
	syscall

	# オフセットをインクリメント
	addi	$t0,	$t0,	1
	
	# すべて出力して無ければ戻る
	bne	$s0,	$s1,	loop_p

	# 改行
	li	$v0,	4
	la	$a0,	eol
	syscall

	jr	$ra

ポインタとか参照とかもそうだけど、やっぱり逐一図にしないと整理できないです。命令自体はシンプルだけどやっぱ引数の名前がまぎらわしい。このソースだと多分うまく動かないです。動かなくても、というか動かないこと前提で明日からデバッグ作業します!それではまた明日!

Javaで連結リストの実装

さて週末やることのノルマの一つ目です。今回は

「連結リスト」

の実装をやりました。参考書をガン見しながらやったのでいつもより綺麗なプログラムになりましたw

 

まず連結リストの基礎知識をおさらいしてみます

・リストを実現するデータには、この「連結リスト」と「配列」がある

・連結リストとは、リストに含まれる各要素をリンクによってつなぎあわせたもの

・セルの一つ一つに、前後のセルへのリンクを持たせるため、リンク1つ分のメモリが必要になるため、配列よりメモリをくう

・しかし、要素の挿入や削除が簡単に行える

 

実装した感想ですが、ポインタを思い出してしんどかったですw

コード自体は確かに簡潔な記述になっていると思います。じゃあ貼っていきます。

 

ー次の要素だけのリンクだけをもつ連結リスト / LinkedList.java

	
public class Cell{
    Cell next; //次のセルへのリンク
	Object data; //このセルのデータ
	int num; //このセルの順番
	
	Cell(Object data){
		next = null;
		this.data = data;
	}
}   

まずリストのひな形をつくります。これを操作してリストを表現していきます。


/*
 *今回は昇順にint型のデータを並べたリスト構造を実装
 **/
public class LinkedList{
	final Cell header;
	
	public LinkedList(){
		header = new Cell("List Head");
	}

	//リストへの挿入
	public void insert(int num){
		Cell p = header.next;
		Cell q = header;
		while(p != null && num > (Integer)p.data){
			q = p;
			p = p.next;
		}
		
		Cell newCell = new Cell(num);
		newCell.next = p;
		q.next = newCell;
	}
	
	//リストからの削除(dataがnumであるリストを削除する)
	public void delete(int num){
		Cell p = header.next;
		Cell q = header;
		
		if(q == null){
			throw new IllegalStateException("リストが空なので削除できません");
		}
		
		while(num != (Integer)p.data){
			q = p;
			p = p.next;
			if(p == null){
				throw new IllegalStateException("指定したデータは存在しません");
			}
		}
		q.next = p.next;
	}
	
	public String toString(){
		StringBuilder st = new StringBuilder();
		st.append("[ ");
		for(Cell p = header.next; p!=null; p=p.next){
			st.append(p.data + " ");
		}
		st.append("]");
		return st.toString();
	}
	
}

ポインタ操作みたいでしんどい。図を書きながら何とか理解。


public class Main {
	public static void main(String[] args) {
		LinkedList list = new LinkedList();
		list.insert(2);
		list.insert(5);
		list.insert(4);
		
		System.out.println(list.toString());
		list.delete(4);
		System.out.println(list.toString());
		
		LinkedList list2 = new LinkedList();
		list2.insert(2);
		list2.insert(5);
		list2.insert(4);
		
		list2.delete(2);
		System.out.println(list2.toString());
		list.delete(10);
	}
}

 f:id:ikuth:20140510210256p:plain

実行結果はこんな感じ。まあ参考書をほとんど真似たので。。。

ー双方向のリンクをもつ双方向リスト / DLinkedLink.java


public class DCell {
	DCell prev; //前のセルへのリンク
	DCell next; //次のセルへのリンク
	Object data; //セルのデータ
	
	public DCell(Object data){
		this.data = data;
		prev = null;
		next = null;
	}
}

前の要素を参照するためのprevを用意します。


import java.util.NoSuchElementException;

public class DLinkedList {
	final DCell head;
	
	public DLinkedList(){
		head = new DCell("List head");
		head.prev = head.next = head;
	}
	
	//セルpの直後にdataを挿入
	private void insertAfter(DCell p,Object data){
		DCell x = new DCell(data);
		x.prev = p;
		x.next = p.next;
		p.next.prev = x;
		p.next = x;
	}
	
	//先頭にdataを挿入
	public void insertFirst(Object data){
		insertAfter(head,data);
	}
	
	public void insertLast(Object data){
		insertAfter(head.prev,data);
	}
	
	//指定したセルを削除する
	private void remove(DCell p){
		p.prev.next = p.next;
		p.next.prev = p.prev;
	}
	
	public Object removeFirst(){
		if(isEmpty()){
			throw new NoSuchElementException("リストが空です");
		}
		
		DCell cell = head.next;
		remove(cell);
		return cell.data;
	}
	
	public Object removeLast(){
		if(isEmpty()){
			throw new NoSuchElementException("リストが空です");
		}
		
		DCell cell = head.prev;
		remove(cell);
		return cell.data;
	}
	
	public boolean isEmpty(){
		return head.next == head;
	}
	
	public String toString(){
		StringBuilder st = new StringBuilder();
		st.append("[ ");
		for(DCell p=head.next; p != head; p = p.next){
			st.append(p.data + " ");
		}
		st.append("]");
		return st.toString();
	}
}   

双方向であると同時に循環させているので、コンストラクタでhead.prevもheadを指すようにしています。


public class Main {
	public static void main(String[] args) {
		DLinkedList list = new DLinkedList();		
		list.insertFirst("a");
		list.insertLast("b");
		list.insertLast("c");
		System.out.println(list.toString());
		
		list.removeFirst();
		System.out.println(list.toString());
		
		list.removeLast();
		System.out.println(list.toString());
		
		list.removeFirst();
		System.out.println(list.toString());
		list.removeFirst();
	}
}

 f:id:ikuth:20140510210722p:plain

実行結果はこのようになりました。ちゃんと出来てますね。

今後リスト構造をうまく使いこなせるようにしないとね。

既にArrayList様やHashMap様には度々お世話になっておりますけど。

今週末にやること

主に自分宛て

~最低限~

Javaで連結リストを実装

Java各種ソートを実装

MIPSアセンブリでなんかのソートアルゴリズムを実装(再履修科目用)

~順調に行けば~

JavaGUIのお勉強

JavaでDOMのお勉強

・ニューラル情報処理、暗号とセキュリティの復習(今期履修科目では特に理解不足なので・・・)

 

まあこれだけやりたいことがあるということでね。意欲はあるのであとはそれに実力が追いつけるかですね。はい。計画では、ソートやったらようやく探索です。探索を使いこなせるようになったら色々とやりたいことが出来るようになったり、AOJの問題も解けるようになるでしょう楽しみ。

 

中間試験「だが俺を忘れてもらっちゃ困るぜ!!」

ぼく「あぅぅ・・・」

 

~追記~

参考書見た感じ、ソートより先にリスト表現と木構造をやったほうが良さそうなのでそうすることにします。鋭意勉強中

 

 

Prologのお勉強1~スタックを実装~

演習でPrologという論理型言語を学んでおります。ちなみに去年軽く落単しましたので再履修です。今より遥かにプログラミング出来なかったので(今も出来ているとはいいがたいですが)、CやJavaと全く異なるPrologなんて出来っこなかったわけで。

 

というわけで、SWI-Prologを導入して教科書の演習問題を細々と解いていました。少し慣れてきたので、昨日やったスタックをPrologで実装することに挑戦してみました。

 

使用している教科書は、

Prologへの入門/I.Bratko 著,安部憲広 訳」

です。今後のPrologはすべてこれです。

  http://www.geocities.jp/m_hiroi/prolog/prolog01.html

たまにこのサイトを使うかもしれません。とても細かくまとめられてます。

実装したい機能

・スタック(リスト)を与えると、そのスタックポインタを返す(機能1)

・ポップ(機能2)

・プッシュ(機能3)

 

これらの機能を実現するためにまずいくつかの関数を別に定義します。しなくてもいいのでしょうが、別に定義しておくことで、見栄えとあとから追加する場合などに便利だと思ったからです。今回は、

・「二つのリストをくっつけたリストを返すconc/3」

・「リストの要素数を求めるlist_elem_num/2」

を定義します。

-conc/3-

conc([],L,L).
conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3).

conc([a,b,c],[d,e],L3)のとき、L3=[a,b,c,d,e]となります。この関数は今後も度々でると思います。教授が興奮してこの関数の発明は革命的ですとか言ってました。確かに最初に考えた人は凄いですね。

 -list_elem_num/2-


list_elem_num([],0).
list_elem_num([X|Tail],Num) :-
    list_elem_num(Tail,Num1),
    Num is Num1 + 1.

「リストが空の時は要素数が0」を終了条件として、再帰処理でリストの要素数Numを求めてます。

さて、これで準備がととのったので、一気にまとめて貼ります。



% スタック(Spはスタックポインタ)
stack([],0).
stack(List,Sp) :- list_elem_num(List,Sp).

% ポップ(先頭から要素を取り出す)
% 第二項は取り出した要素、第三項はポップ後のスタック
pop([],X,[],0) :- false.
pop([X|Tail],X,Tail,Sp) :-
     stack(Tail,Sp).

% プッシュ(先頭に要素を追加する)
% 第一項は追加したい要素、第三項はプッシュ後のスタック
push(X,[],[X],1).
push(X,List,Newlist,Sp) :-
     conc(X,List,Newlist),
     stack(Newlist,Sp).

まずstackを定義したstack/2についてですが、現在の要素の先頭のインデックスをn-1とすると、そこから一つ足したnをスタックポインタのインデックスとしていました。配列のインデックスは0から始まるので、リストの要素数がそのままスタックポインタのインデックス数と一致します。それ故にシンプルな構造です。

続いてpop/4についてです。

pop(_対象リスト,_ポップした要素,_ポップ後のリスト,ポップ後のスタックポインタ)

を入力します。ポップはスタックの一番上の要素を取り出すので、先頭を取り出したあとのTailをstack/2に渡せばポップ後のスタックポインタが求められます。またTailはポップ後のリストそのものであるため、こちらもシンプルな構造となります。

最後にpush/4

push(_プッシュする要素,_対象リスト,_プッシュ後のリスト,プッシュ後のスタックポインタ)

を入力すると、まずプッシュする要素と対象リストを結合した、プッシュ後のリストを生成し、その生成したリストのスタックポインタを求めるという手順です。

 

実行結果は

f:id:ikuth:20140507233701p:plain

ひたすら見にくいですね。申し訳ないです。

List = [0,1,2,3,4,5]

を2回ポップした後、10をプッシュするという問い合わせです。それぞれの操作後のスタックポインタ値も出しています。List4の下にSp4=5と出力されるのではなく、Sp2 = Sp4, Sp4 = 5とされる理由はよくわかんないです。一応プッシュとポップ操作はできていることがわかります。よかったよかった。

 

自由課題のテーマ考えないとなあ。それでは。