数据结构和算法系列课程（02） --- 线性表和贪吃蛇

线性结构是一种具有以下特点的结构：

• 存在唯一一个被称为“第一个”的数据元素
• 存在唯一一个被称为“最后一个”的数据元素
• 除第一个元素之外，集合中的每个元素均有且仅有一个前驱
• 除最后一个元素之外，集合中的每个元素均有且仅有一个后继

那么，线性表、栈、队列、数组、字符串都可以视为线性结构。

线性表是N个数据元素的有限序列，关于这部分的内容可以参考我的数据结构的课件

按照面向接口编程的思想，我们先通过一个接口为线性表拟定相应的方法，然后给出基于数组和基于链式结构的两种实现方式。

/**
 * 线性表接口
 * @author 骆昊
 *
 * @param <T> 泛型参数 - 线性表存储的元素类型
 */
public interface MyList<T> {

	/**
	 * 获取指定位置的元素
	 * @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<T> implements MyList<T> {
	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 <T> 泛型参数(线性表存储元素的类型)
 */
public class MyArrayList<T> extends MyAbstractList<T> {
	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<T> extends MyAbstractList<T> {
	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<SnakeNode> list = new MyLinkedList<SnakeNode>();
	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<SnakeNode> 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<SnakeNode> 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<Brick> list = new ArrayList<Brick>();
	
	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<Brick> 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);
	}
}

好了，到这里一个贪吃蛇游戏就做好了，这个游戏的碰撞检测非常简单，因为蛇和蛋还有墙都在格子里（虽然没有绘制出来），通过横纵坐标的比较就可以完成了。