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

灰太狼 2021-09-21 12:56 191阅读 0赞

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

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

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

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

[http://download.csdn.net/detail/jackfrued/6200903][http_download.csdn.net_detail_jackfrued_6200903]

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

/**
     * 线性表接口
     * @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);
    	}
    }

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

[http_download.csdn.net_detail_jackfrued_6200903]: http://download.csdn.net/detail/jackfrued/6200903