数据结构之线性表

 

    线性结构是最简单，也是最常用的数据结构之一。线性结构的特点是：在数据元素的有限集中，除第一个元素无直接前驱，最后一个元素无直接后续以外，每个数据元素有且仅有一个直接前驱元素和一个直接后续元素。

    在线性表的具体实现中，表中相邻的元素不一定存储在连续的内存空间中，除非表是用数组来实现的。对于数组，可以利用其下标在一个操作内随机存取任意位置上的元素；对于线性表，只能根据当前元素找到其前驱或后继，因此要存取序号为i的元素，一般不能在一个操作内实现，除非表是用数组实现的。

 

public interface List {
	//返回线性表的大小，即数据元素的个数。
	public int getSize();
	//如果线性表为空返回true，否则返回false。
	public boolean isEmpty();
	//判断线性表是否包含数据元素e
	public boolean contains(Object e);
	//返回数据元素e 在线性表中的序号
	public int indexOf(Object e);
	//将数据元素e 插入到线性表中i 号位置
	public void insert(int i, Object e) throws OutOfBoundaryException;
	//将数据元素e 插入到元素obj 之前
	public boolean insertBefore(Object obj, Object e);
	//将数据元素e 插入到元素obj 之后
	public boolean insertAfter(Object obj, Object e);
	//删除线性表中序号为i 的元素,并返回之
	public Object remove(int i) throws OutOfBoundaryException;
	//删除线性表中第一个与e 相同的元素
	public boolean remove(Object e);
	//替换线性表中序号为i 的数据元素为e，返回原数据元素
	public Object replace(int i, Object e) throws OutOfBoundaryException;
	//返回线性表中序号为i 的数据元素
	public Object get(int i) throws OutOfBoundaryException;
}
public interface Strategy {
	//判断两个数据元素是否相等
	public boolean equal(Object obj1, Object obj2);
	/**
	* 比较两个数据元素的大小
	* 如果obj1 < obj2 返回-1
	* 如果obj1 = obj2 返回0
	* 如果obj1 > obj2 返回1
	*/
	public int compare(Object obj1, Object obj2);
}
public class OutOfBoundaryException extends RuntimeException{
	public OutOfBoundaryException(String err){
		super(err);
	}
}

 

    线性表的顺序存储与实现：线性表的顺序存储是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的这种机内表示称作线性表的顺序存储。它的特点是，以数据元素在机内存储地址相邻来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储地址都和线性表的起始地址相差一个与数据元素在线性表中的序号成正比的常数。由此，只要确定了线性表的起始地址，线性表中的任何一个数据元素都可以随机存取，因此线性表的顺序存储结构是一种随机的存储结构。

    由于高级语言中的数组具也有随机存储的特性，因此在抽象数据类型的实现中都是使用数组来描述数据结构的顺序存储结构。

     如果线性表中的数据元素是对象时，数组存放的是对象的引用，即线性表中所有数据元素的对象引用是存放在一组连续的地址空间中。

     线性表的数组实现：

public class ListArray implements List {
	private final int LEN = 8; //数组的默认大小
	private Strategy strategy; //数据元素比较策略
	private int size; //线性表中数据元素的个数
	private Object[] elements; //数据元素数组
	//构造方法
	public ListArray () {
		this(new DefaultStrategy());
	}
	public ListArray (Strategy strategy){
		this.strategy = strategy;
		size = 0;
		elements = new Object[LEN];
	}
	//返回线性表的大小，即数据元素的个数。
	public int getSize() {
		return size;
	}
	//如果线性表为空返回true，否则返回false。
	public boolean isEmpty() {
		return size == 0;
	}
	//判断线性表是否包含数据元素e
	public boolean contains(Object e) {
		for (int i = 0; i < size; i++)
			if (strategy.equal(e,elements[i]))
				return true;
		return false;
	}
	//返回数据元素e 在线性表中的序号
	public int indexOf(Object e) {
		for (int i = 0; i < size; i++)
			if (strategy.equal(e,elements[i]))
				return i;
		return -1;
	}
	//将数据元素e 插入到线性表中i 号位置
	public void insert(int i, Object e) throws OutOfBoundaryException {
		if (i < 0 || i > size)
			throw new OutOfBoundaryException("插入序号越界");
		if (size >= elements.length)
			expandSpace();
		for (int j = size; j > i; j--)
			elements[j] = elements[j-1];
		elements[i] = e;
		size++;
		return;
	}
	private void expandSpace(){
		Object[] a = new Object[elements.length * 2];
		for (int i = 0; i < elements.length; i++)
			a[i] = elements[i];
		elements = a;
	}
	//将数据元素e 插入到元素obj 之前
	public boolean insertBefore(Object obj, Object e) {
		int i = indexOf(obj);
		if (i < 0)
			return false;
		insert(i, e);
		return true;
	}
	//将数据元素e 插入到元素obj 之后
	public boolean insertAfter(Object obj, Object e) {
		int i = indexOf(obj);
		if (i < 0)
			return false;
		insert(i + 1, e);
		return true;
	}
	//删除线性表中序号为i 的元素,并返回之
	public Object remove(int i) throws OutOfBoundaryException {
		if (i<0||i>=size)
			throw new OutOfBoundaryException("删除序号越界");
		Object obj = elements[i];
		for (int j = i; j < size - 1; j++)
			elements[j] = elements[j + 1];
		elements[--size] = null;
		return obj;
	}
	//删除线性表中第一个与e 相同的元素
	public boolean remove(Object e) {
		int i = indexOf(e);
		if (i < 0)
			return false;
		remove(i);
		return true;
	}
	//替换线性表中序号为i 的数据元素为e，返回原数据元素
	public Object replace(int i, Object e) 
				throws OutOfBoundaryException {
		if (i < 0 || i >= size)
			throw new OutOfBoundaryException("序号越界");
		Object obj = elements[i];
		elements[i] = e;
		return obj;
	}
	//返回线性表中序号为i 的数据元素
	public Object get(int i) throws OutOfBoundaryException {
		if (i < 0 || i >= size)
			throw new OutOfBoundaryException("序号越界");
		return elements[i];
	}
}

 
    线性表的链式存储与实现：实现线性表的另一种方法是链式存储，即用指针将存储线性表中数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销。
     节点接口：

public interface Node {
	//获取结点数据域
	public Object getData();
	//设置结点数据域
	public void setData(Object obj);
}

 
     单链表结点定义：

public class SLNode implements Node {
	private Object element;
	private SLNode next;
	public SLNode() {
		this(null,null);
	}
	public SLNode(Object ele, SLNode next){
		this.element = ele;
		this.next = next;
	}
	public SLNode getNext(){
		return next;
	}
	public void setNext(SLNode next){
		this.next = next;
	}
	/**************** Methods of Node Interface **************/
	public Object getData() {
		return element;
	}
	public void setData(Object obj) {
		element = obj;
	}
}

 

 
     双向链表结点定义：

public class DLNode implements Node {
	private Object element;
	private DLNode pre;
	private DLNode next;
	public DLNode() {
		this(null,null,null);
	}
	public DLNode(Object ele, DLNode pre, DLNode next){
		this.element = ele;
		this.pre = pre;
		this.next = next;
	}
	public DLNode getNext(){
		return next;
	}
	public void setNext(DLNode next){
		this.next = next;
	}
	public DLNode getPre(){
		return pre;
	}
	public void setPre(DLNode pre){
		this.pre = pre;
	}
	/****************Node Interface Method**************/
	public Object getData() {
		return element;
	}
	public void setData(Object obj) {
		element = obj;
	}
}

 

     线性表的单链表实现：

public class ListSLinked implements List {
	private Strategy strategy; //数据元素比较策略
	private SLNode head; //单链表首结点引用
	private int size; //线性表中数据元素的个数
	public ListSLinked () {
		this(new DefaultStrategy());
	}
	public ListSLinked (Strategy strategy) {
		this.strategy = strategy;
		head = new SLNode();
		size = 0;
	}
	//辅助方法：获取数据元素e 所在结点的前驱结点
	private SLNode getPreNode(Object e){
		SLNode p = head;
		while (p.getNext() != null)
			if (strategy.equal(p.getNext().getData(), e))
				return p;
			else
				p = p.getNext();
		return null;
	}
	//辅助方法：获取序号为0<=i<size 的元素所在结点的前驱结点
	private SLNode getPreNode(int i){
		SLNode p = head;
		for ( ; i > 0; i--)
			p = p.getNext();
		return p;
	}
	//获取序号为0<=i<size 的元素所在结点
	private SLNode getNode(int i){
		SLNode p = head.getNext();
		for ( ; i > 0; i--)
			p = p.getNext();
		return p;
	}
	//返回线性表的大小，即数据元素的个数。
	public int getSize() {
		return size;
	}
	//如果线性表为空返回true，否则返回false。
	public boolean isEmpty() {
		return size == 0;
	}
	//判断线性表是否包含数据元素e
	public boolean contains(Object e) {
		SLNode p = head.getNext();
		while (p != null)
		if (strategy.equal(p.getData(), e))
			return true;
		else
			p = p.getNext();
		return false;
	}
	//返回数据元素e 在线性表中的序号
	public int indexOf(Object e) {
		SLNode p = head.getNext();
		int index = 0;
		while (p != null)
			if (strategy.equal(p.getData(), e))
				return index;
			else {
				index++;
				p = p.getNext();
			}
		return -1;
	}
	//将数据元素e 插入到线性表中i 号位置
	public void insert(int i, Object e) throws OutOfBoundaryException {
		if (i < 0 || i > size)
			throw new OutOfBoundaryException("插入序号越界");
		SLNode p = getPreNode(i);
		SLNode q = new SLNode(e, p.getNext());
		p.setNext(q);
		size++;
		return;
	}
	//将数据元素e 插入到元素obj 之前
	public boolean insertBefore(Object obj, Object e) {
		SLNode p = getPreNode(obj);
		if (p != null) {
			SLNode q = new SLNode(e, p.getNext());
			p.setNext(q);
			size++;
			return true;
		}
		return false;
	}
	//将数据元素e 插入到元素obj 之后
	public boolean insertAfter(Object obj, Object e) {
		SLNode p = head.getNext();
		while (p != null)
			if (strategy.equal(p.getData(), obj)){
				SLNode q = new SLNode(e, p.getNext());
				p.setNext(q);
				size++;
				return true;
			} else {
				p = p.getNext();
			}
		return false;
	}
	//删除线性表中序号为i 的元素,并返回之
	public Object remove(int i) throws OutOfBoundaryException {
		if (i < 0 || i >= size)
			throw new OutOfBoundaryException("删除序号越界");
		SLNode p = getPreNode(i);
		Object obj = p.getNext().getData();
		p.setNext(p.getNext().getNext());
		size--;
		return obj;
	}
	//删除线性表中第一个与e 相同的元素
	public boolean remove(Object e) {
		SLNode p = getPreNode(e);
		if (p != null){
			p.setNext(p.getNext().getNext());
			size--;
			return true;
		}
		return false;
	}
	//替换线性表中序号为i 的数据元素为e，返回原数据元素
	public Object replace(int i, Object e)
			throws OutOfBoundaryException {
		if (i < 0 || i >= size)
			throw new OutOfBoundaryException("序号越界");
		SLNode p = getNode(i);
		Object obj = p.getData();
		p.setData(e);
		return obj;
	}
	//返回线性表中序号为i 的数据元素
	public Object get(int i) throws OutOfBoundaryException {
		if (i < 0 || i >= size)
			throw new OutOfBoundaryException("序号越界");
		SLNode p = getNode(i);
		return p.getData();
	}
}

 

     链接表可以看成是一组结点序列以及基于结点进行操作的线性结构的抽象，或者说是对链表的抽象。

 

     链接表接口：

public interface LinkedList {
	//查询链接表当前的规模
	public int getSize();
	//判断列表是否为空
	public boolean isEmpty();
	//返回第一个结点
	public Node first() throws OutOfBoundaryException;
	//返回最后一结点
	public Node last() throws OutOfBoundaryException;
	//返回p 之后的结点
	public Node getNext(Node p)  
		throws InvalidNodeException, OutOfBoundaryException;
	//返回p 之前的结点
	public Node getPre(Node p) 
		throws InvalidNodeException, OutOfBoundaryException;
	//将e 作为第一个元素插入链接表,并返回e 所在结点
	public Node insertFirst(Object e);
	//将e 作为最后一个元素插入列表,并返回e 所在结点
	public Node insertLast(Object e);
	//将e 插入至p 之后的位置,并返回e 所在结点
	public Node insertAfter(Node p, Object e) 
		throws InvalidNodeException;
	//将e 插入至p 之前的位置,并返回e 所在结点
	public Node insertBefore(Node p, Object e) 
		throws InvalidNodeException;
	//删除给定位置处的元素，并返回之
	public Object remove(Node p) throws InvalidNodeException;
	//删除首元素，并返回之
	public Object removeFirst() throws OutOfBoundaryException;
	//删除末元素，并返回之
	public Object removeLast() throws OutOfBoundaryException;
	//将处于给定位置的元素替换为新元素，并返回被替换的元素
	public Object replace(Node p, Object e) throws InvalidNodeException;
	//元素迭代器
	public Iterator elements();
}

public class InvalidNodeException extends RuntimeException {
	public InvalidNodeException(String err) {
		super(err);
	}
}

 

     基于双向链表实现的链接表：

public class LinkedListDLNode implements LinkedList {
	private int size; //规模
	private DLNode head;//头结点,哑元结点
	private DLNode tail;//尾结点,哑元结点
	public LinkedListDLNode() {
		size = 0;
		head = new DLNode();//构建只有头尾结点的链表
		tail = new DLNode();
		head.setNext(tail);
		tail.setPre(head);
	}
	//辅助方法，判断结点p 是否合法，如合法转换为DLNode
	protected DLNode checkPosition(Node p) throws InvalidNodeException {
		if (p == null)
			throw new InvalidNodeException("错误：p 为空。");
		if (p == head)
			throw new InvalidNodeException("错误：p 指向头节点，非法。");
		if (p == tail)
			throw new InvalidNodeException("错误：p 指向尾结点，非法。");
		DLNode node = (DLNode) p;
		return node;
	}
	//查询链接表当前的规模
	public int getSize() {
		return size;
	}
	//判断链接表是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	//返回第一个结点
	public Node first() throws OutOfBoundaryException{
		if (isEmpty())
			throw new OutOfBoundaryException("错误：链接表为空。");
		return head.getNext();
	}
	//返回最后一结点
	public Node last() throws OutOfBoundaryException{
		if (isEmpty())
			throw new OutOfBoundaryException("错误：链接表为空。");
		return tail.getPre();
	}
	//返回p 之后的结点
	public Node getNext(Node p) 
			throws InvalidNodeException,OutOfBoundaryException {
		DLNode node = checkPosition(p);
		node = node.getNext();
		if (node == tail)
			throw new OutOfBoundaryException("错误：已经是链接表尾端。");
		return node;
	}
	//返回p 之前的结点
	public Node getPre(Node p) 
			throws InvalidNodeException, OutOfBoundaryException {
		DLNode node = checkPosition(p);
		node = node.getPre();
		if (node == head)
			throw new OutOfBoundaryException("错误：已经是链接表前端。");
		return node;
	}
	//将e 作为第一个元素插入链接表
	public Node insertFirst(Object e) {
		DLNode node = new DLNode(e,head,head.getNext());
		head.getNext().setPre(node);
		head.setNext(node);
		size++;
		return node;
	}
	//将e 作为最后一个元素插入列表,并返回e 所在结点
	public Node insertLast(Object e) {
		DLNode node = new DLNode(e,tail.getPre(), tail);
		tail.getPre().setNext(node);
		tail.setPre(node);
		size++;
		return node;
	}
	//将e 插入至p 之后的位置,并返回e 所在结点
	public Node insertAfter(Node p, Object e) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		DLNode newNode = new DLNode(e,node, node.getNext());
		node.getNext().setPre(newNode);
		node.setNext(newNode);
		size++;
		return newNode;
	}
	//将e 插入至p 之前的位置,并返回e 所在结点
	public Node insertBefore(Node p, Object e) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		DLNode newNode = new DLNode(e, node.getPre(),node);
		node.getPre().setNext(newNode);
		node.setPre(newNode);
		size++;
		return newNode;
	}
	//删除给定位置处的元素，并返回之
	public Object remove(Node p) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		Object obj = node.getData();
		node.getPre().setNext(node.getNext());
		node.getNext().setPre(node.getPre());
		size--;
		return obj;
	}
	//删除首元素，并返回之
	public Object removeFirst() throws OutOfBoundaryException{
		return remove(head.getNext());
	}
	//删除末元素，并返回之
	public Object removeLast() throws OutOfBoundaryException{
		return remove(tail.getPre());
	}
	//将处于给定位置的元素替换为新元素，并返回被替换的元素
	public Object replace(Node p, Object e) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		Object obj = node.getData();
		node.setData(e);
		return obj;
	}
	//元素迭代器
	public Iterator elements() {
		return new LinkedListIterator(this);
	}
}

 

    迭代器（Iterator）是程序设计的一种模式，它属于设计模式中的行为模式，它的功能是提供一种方法顺序访问一个聚集对象中各个元素，而又不需暴露该对象的内部表示。

    LinkedListIterator，基于LinkedList 聚集对象的迭代器实现：

public interface Iterator {
	//移动到第一个元素
	public void first();
	//移动到下一个元素
	public void next();
	//检查迭代器中是否还有剩余的元素
	public boolean isDone();
	//返回当前元素
	public Object currentItem();
}
public class LinkedListIterator implements Iterator {
	private LinkedList list;//链接表
	private Node current;//当前结点
	//构造方法
	public LinkedListIterator(LinkedList list) {
		this.list = list;
		if (list.isEmpty()) //若列表为空
			current = null; //则当前元素置空
		else
			current = list.first();//否则从第一个元素开始
	}
	//移动到第一个元素
	public void first() {
		if (list.isEmpty()) //若列表为空
			current = null; //则当前元素置空
		else
			current = list.first();//否则从第一个元素开始
	}
	//移动到下一个元素
	public void next() throws OutOfBoundaryException{
		if (isDone())
			throw new OutOfBoundaryException("错误：已经没有元素。");
		if (current == list.last()) 
			current = null; //当前元素后面没有更多元素
		else 
			current = list.getNext(current);
	}
	//检查迭代器中是否还有剩余的元素
	public boolean isDone() { return current==null; }
	//返回当前元素
	public Object currentItem() throws OutOfBoundaryException{
		if (isDone())
			throw new OutOfBoundaryException("错误：已经没有元素。");
		return current.getData();
	}
}