データ構造とアルゴリズムシリーズ課程(02)---線形表とヘビを貪る
リニア構造は、次のような特徴を持つ構造です.には、「第1」と呼ばれる唯一のデータ要素 が存在する.には、「最後の」と呼ばれる唯一のデータ要素 が存在する.は、第1の要素を除いて、集合内の各要素に1つの前駆体 しかない.最後の要素を除いて、集合内の各要素はいずれも後続の しかない.
では、線形テーブル、スタック、キュー、配列、文字列はいずれも線形構造と見なすことができる.
線形表はN個のデータ要素の有限なシーケンスで、この部分の内容について私のデータ構造の授業を参考することができて、以下はダウンロードアドレスです:
http://download.csdn.net/detail/jackfrued/6200903
インタフェース向けプログラミングの考え方に従って,まず1つのインタフェースを介して線形テーブルに対応する方法を立案し,次いで配列ベースとチェーン構造ベースの2つの実装方式を与えた.
シーケンステーブルとチェーンテーブルの共通インプリメンテーションを抽象的な親クラスに配置
リニア・テーブルの配列実装バージョン-シーケンス・テーブル
チェーン実装方式-チェーンテーブル
はい、ここまでチェーン時計で蛇を貪るゲームを実現することができます.その鍵は蛇が卵を食べてからどのように長くなるかです.ヘビの各ノードをチェーンテーブルで格納する場合、ヘビの成長は、ヘッドまたはテールにノードを追加することによって実現することができる.同様に、ヘビを移動させるには、テールノードを削除したり、ヘッドノードを追加したりすることで実現することもできます.つまり、チェーンテーブルで提供される操作を利用して、ヘビを貪るゲームを簡単に実現することができます.コードは以下のようになります.
ヘビの各ノードを定義します.
次は最も重要な蛇です.
蛇の方向を表す列挙:
ゲームのメインフォーム:
もちろん、このゲームには壁と卵が欠かせません.コードは以下の通りです.
はい、ここまでヘビを食いしん坊にするゲームができました.このゲームの衝突検出はとても簡単です.ヘビと卵と壁は格子の中にあるので(描かれていませんが)、横縦座標の比較で完成します.
では、線形テーブル、スタック、キュー、配列、文字列はいずれも線形構造と見なすことができる.
線形表はN個のデータ要素の有限なシーケンスで、この部分の内容について私のデータ構造の授業を参考することができて、以下はダウンロードアドレスです:
http://download.csdn.net/detail/jackfrued/6200903
インタフェース向けプログラミングの考え方に従って,まず1つのインタフェースを介して線形テーブルに対応する方法を立案し,次いで配列ベースとチェーン構造ベースの2つの実装方式を与えた.
/**
*
* @author
*
* @param -
*/
public interface MyList {
/**
*
* @param index
* @return
*/
public T get(int index);
/**
*
* @param t
* @param index
*/
public void set(T t, int index);
/**
*
* @param t
*/
public void add(T t) ;
/**
*
* @param t
* @param index
*/
public void add(T t, int index);
/**
*
* @param index
* @return
*/
public T remove(int index);
/**
*
* @param t
* @return true false
*/
public boolean remove(T t);
/**
*
* @param t
* @return , -1
*/
public int indexOf(T t);
/**
*
* @return
*/
public int size();
/**
*
*/
public void clear();
/**
*
* @return true false
*/
public boolean isEmpty();
}
シーケンステーブルとチェーンテーブルの共通インプリメンテーションを抽象的な親クラスに配置
public abstract class MyAbstractList implements MyList {
protected int size;
@Override
public void add(T t) {
add(t, size);
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public synchronized boolean remove(T t) {
int index = indexOf(t);
if(index >= 0) {
remove(index);
return true;
}
return false;
}
} リニア・テーブルの配列実装バージョン-シーケンス・テーブル
import java.util.Arrays;
/**
* ( )
* @author Hao
*
* @param ( )
*/
public class MyArrayList extends MyAbstractList {
private T[] content = null;
private int capacity; //
private int size; //
private double factor; // (0~1)
public MyArrayList() {
this(50, 0.5);
}
public MyArrayList(double factor) {
this(50, factor);
}
public MyArrayList(int capacity) {
this(capacity, 0.5);
}
@SuppressWarnings("unchecked")
public MyArrayList(int capacity, double factor) {
content = (T[]) new Object[capacity];
this.capacity = capacity;
this.factor = factor;
this.size = 0;
}
public T get(int index) {
if(index >= 0 && index < size) {
return content[index];
}
else {
throw new RuntimeException(" : " + index);
}
}
public synchronized void add(T t, int index) {
if(index >= 0 && index <= size) {
if(size >= capacity) {
ensureCapacity();
}
for(int i = size - 1; i >= index; i--) {
content[i + 1] = content[i];
}
content[index] = t;
size++;
}
else {
throw new RuntimeException(" : " + index);
}
}
private void ensureCapacity() {
capacity += (int)(capacity * factor);
content = Arrays.copyOf(content, capacity);
}
public synchronized T remove(int index) {
if(index >= size || index < 0) {
throw new IndexOutOfBoundsException(" : " + index);
}
T temp = content[index];
for(int i = index; i < size; i++) {
content[i] = content[i + 1];
}
size--;
return temp;
}
public void clear() {
size = 0;
}
@Override
public synchronized void set(T t, int index) {
if(index >= size || index < 0) {
throw new IndexOutOfBoundsException(" : " + index);
}
content[index] = t;
}
@Override
public int indexOf(T t) {
for(int i = 0; i < size; i++) {
if(content[i].equals(t)) {
return i;
}
}
return -1;
}
} チェーン実装方式-チェーンテーブル
public class MyLinkedList extends MyAbstractList {
private ListNode head, tail;
private class ListNode {
public T element;
public ListNode next;
public ListNode(T element) {
this.element = element;
}
}
public synchronized T get(int index) {
if (index < 0 || index >= size) {
throw new RuntimeException(" : " + index);
}
ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.element;
}
public synchronized void addFirst(T t) {
ListNode newNode = new ListNode(t);
newNode.next = head;
head = newNode;
size++;
if (tail == null) {
tail = head;
}
}
public synchronized void addLast(T t) {
if (tail == null) {
head = tail = new ListNode(t);
} else {
tail.next = new ListNode(t);
tail = tail.next;
}
size++;
}
public synchronized void add(T t, int index) {
if (index < 0 || index > size) {
throw new RuntimeException(" : " + index);
} else {
if (index == 0) {
addFirst(t);
} else if (index == size) {
addLast(t);
} else {
ListNode curr = head;
for (int i = 1; i < index; i++) {
curr = curr.next;
}
ListNode temp = curr.next;
curr.next = new ListNode(t);
curr.next.next = temp;
size++;
}
}
}
public synchronized T remove(int index) {
if (index < 0 || index >= size) {
throw new RuntimeException(" : " + index);
} else if (index == 0) {
return removeFirst();
} else if (index == size - 1) {
return removeLast();
} else {
ListNode prev = head;
for (int i = 1; i < index; i++) {
prev = prev.next;
}
ListNode curr = prev.next;
prev.next = curr.next;
size--;
return curr.element;
}
}
public synchronized T removeFirst() {
T temp = null;
if (head != null) {
temp = head.element;
head = head.next;
size--;
if(head == null) {
tail = null;
}
}
return temp;
}
public synchronized T removeLast() {
T temp = null;
if (tail != null) {
ListNode prev = head;
if(prev == tail) {
temp = prev.element;
head = tail = null;
}
else {
while(prev.next != tail) {
prev = prev.next;
}
temp = prev.next.element;
prev.next = null;
tail = prev;
}
size--;
}
return temp;
}
public void clear() {
head = tail = null;
}
@Override
public void set(T t, int index) {
if (index < 0 || index >= size) {
throw new RuntimeException(" : " + index);
}
ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
curr.element = t;
}
@Override
public int indexOf(T t) {
if(head != null) {
ListNode curr = head;
for (int i = 0; i < size; i++) {
if(curr.element.equals(t)) {
return i;
}
curr = curr.next;
}
}
return -1;
}
}
はい、ここまでチェーン時計で蛇を貪るゲームを実現することができます.その鍵は蛇が卵を食べてからどのように長くなるかです.ヘビの各ノードをチェーンテーブルで格納する場合、ヘビの成長は、ヘッドまたはテールにノードを追加することによって実現することができる.同様に、ヘビを移動させるには、テールノードを削除したり、ヘッドノードを追加したりすることで実現することもできます.つまり、チェーンテーブルで提供される操作を利用して、ヘビを貪るゲームを簡単に実現することができます.コードは以下のようになります.
ヘビの各ノードを定義します.
import java.awt.Color;
import java.awt.Graphics;
public class SnakeNode {
private int size = 10;
private int row, col;
public SnakeNode(int row, int col) {
this.row = row;
this.col = col;
}
public int getRow() {
return row;
}
public void setRow(int row) {
this.row = row;
}
public int getCol() {
return col;
}
public void setCol(int col) {
this.col = col;
}
public void draw(Graphics g) {
g.setColor(Color.GREEN);
g.fillRect(col * size, row * size, size, size);
}
}
次は最も重要な蛇です.
import java.awt.Graphics;
import java.awt.Rectangle;
import com.accp.util.MyLinkedList;
import com.accp.util.MyList;
public class Snake {
private MyLinkedList list = new MyLinkedList();
private Direction dir = Direction.LEFT;
private boolean alive = true;
public Snake() {
list.addLast(new SnakeNode(30, 30));
list.addLast(new SnakeNode(30, 31));
list.addLast(new SnakeNode(30, 32));
list.addLast(new SnakeNode(30, 33));
list.addLast(new SnakeNode(30, 34));
}
public Direction getDir() {
return dir;
}
public MyList getBody() {
return list;
}
public boolean isAlive() {
return alive;
}
public void setAlive(boolean alive) {
this.alive = alive;
}
public SnakeNode getHead() {
return list.get(0);
}
public void move() {
increaseLength();
list.removeLast();
}
public void changeDirection(char ch) {
switch (ch) {
case 'w':
case 'W':
if (dir != Direction.DOWN) {
dir = Direction.UP;
}
break;
case 's':
case 'S':
if (dir != Direction.UP) {
dir = Direction.DOWN;
}
break;
case 'a':
case 'A':
if (dir != Direction.RIGHT) {
dir = Direction.LEFT;
}
break;
case 'd':
case 'D':
if (dir != Direction.LEFT) {
dir = Direction.RIGHT;
}
break;
}
}
public void draw(Graphics g) {
for (int i = 0; i < list.size(); i++) {
list.get(i).draw(g);
}
}
public Rectangle getRectangle() {
SnakeNode head = list.get(0);
return new Rectangle(head.getCol() * 10, head.getRow() * 10, 10, 10);
}
public void eatEgg() {
increaseLength();
increaseLength();
}
private void increaseLength() {
SnakeNode snakeHead = list.get(0);
int row = snakeHead.getRow();
int col = snakeHead.getCol();
switch (dir) {
case UP:
row = row - 1;
break;
case DOWN:
row = row + 1;
break;
case LEFT:
col = col - 1;
break;
case RIGHT:
col = col + 1;
break;
}
SnakeNode newHead = new SnakeNode(row, col);
list.addFirst(newHead);
}
}
蛇の方向を表す列挙:
public enum Direction {
LEFT, RIGHT, UP, DOWN;
}
ゲームのメインフォーム:
import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.KeyAdapter;
import java.awt.event.KeyEvent;
import java.awt.image.BufferedImage;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import com.accp.util.MyList;
@SuppressWarnings("serial")
public class GameFrame extends JFrame {
private Snake s = new Snake();
private Wall w = new Wall();
private Egg e = null;
private char oldKey = '#';
private BufferedImage image =
new BufferedImage(600, 600, BufferedImage.TYPE_INT_RGB);
private Egg makeAnEgg() {
int row = (int) (Math.random() * 40 + 10);
int col = (int) (Math.random() * 40 + 10);
return new Egg(row, col);
}
public GameFrame() {
e = makeAnEgg();
this.setSize(600, 600);
this.setResizable(false);
this.setLocationRelativeTo(null);
this.setDefaultCloseOperation(EXIT_ON_CLOSE);
this.addKeyListener(new KeyAdapter() {
@Override
public void keyPressed(KeyEvent e) {
char ch = e.getKeyChar();
if(ch != oldKey) { // �������
oldKey = ch;
s.changeDirection(ch);
}
}
});
new Thread(new Runnable() {
@Override
public void run() {
while(true) {
if(s.isAlive()) {
s.move();
if(e != null) {
if(e.getRow() == s.getHead().getRow() && e.getCol() ==
s.getHead().getCol()) {
s.eatEgg();
e = makeAnEgg();
}
}
SnakeNode snakeHead = s.getHead();
int row = snakeHead.getRow();
int col = snakeHead.getCol();
if(row <= 5 || row >= 55 || col <= 5 || col >= 55) {
s.setAlive(false);
}
MyList snakeBody = s.getBody();
for(int i = 1; i < snakeBody.size(); i++) {
SnakeNode node = snakeBody.get(i);
if(node.getRow() == row && node.getCol() == col) {
s.setAlive(false);
break;
}
}
if(!s.isAlive()) {
JOptionPane.showMessageDialog(null, "Game Over!!!");
}
try {
Thread.sleep(200);
}
catch (InterruptedException e) {
}
repaint();
}
}
}
}).start();
}
@Override
public void paint(Graphics g) {
//super.paint(g);
Graphics offG = image.getGraphics();
offG.setColor(new Color(0xffff80));
offG.fillRect(0, 0, 600, 600);
w.draw(offG);
s.draw(offG);
if(e != null) {
e.draw(offG);
}
g.drawImage(image, 0, 0, null);
}
public static void main(String[] args) {
new GameFrame().setVisible(true);
}
}
もちろん、このゲームには壁と卵が欠かせません.コードは以下の通りです.
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Rectangle;
/**
*
* @author
*
*/
public class Brick {
private int row, col;
private int size = 10;
public Brick(int row, int col) {
this.row = row;
this.col = col;
}
public void draw(Graphics g) {
g.setColor(new Color(64, 0, 0));
g.fillRect(col * size, row * size, size, size);
}
public Rectangle getRectangle() {
return new Rectangle(col * size, row * size, size, size);
}
}import java.awt.Graphics;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author
*
*/
public class Wall {
private List list = new ArrayList();
public Wall() {
for(int i = 5; i <= 55; i++) {
list.add(new Brick(5, i)); // -
list.add(new Brick(i, 5)); // |
list.add(new Brick(55, i)); // -
list.add(new Brick(i, 55)); // |
}
}
public List getAllBricks() {
return list;
}
public void draw(Graphics g) {
for(Brick b : list) {
b.draw(g);
}
}
} import java.awt.Color;
import java.awt.Graphics;
/**
*
* @author
*
*/
public class Egg {
private int col, row;
private int size = 10;
public Egg(int col, int row) {
this.row = row;
this.col = col;
}
public int getCol() {
return col;
}
public void setCol(int col) {
this.col = col;
}
public int getRow() {
return row;
}
public void setRow(int row) {
this.row = row;
}
public void draw(Graphics g) {
g.setColor(Color.RED);
g.fillOval(col * size, row * size, size, size);
}
}
はい、ここまでヘビを食いしん坊にするゲームができました.このゲームの衝突検出はとても簡単です.ヘビと卵と壁は格子の中にあるので(描かれていませんが)、横縦座標の比較で完成します.