天天看点

线性表线性表概述顺序表单向循环链表双向循环链表测试线性表

线性表概述

线性表是最基本、最简单、也是最常用的一种数据结构。在线性表中数据元素之间的关系是线性,数据元素可以看成是排列在一条线上或一个环上。

线性表分为静态线性表和动态线性表,常见的有顺序表(静态的)、单向链表(动态的)和双向链表(动态的)。

线性表的操作主要包括:

(1)计算表的长度n。

(2)线性表是否为空

(3)将元素添加到线性表的末尾

(4)获取第i个元素,0≤i < n。

(5)清除线性表

(6)返回列表中首次出现指定元素的索引,如果列表不包含此元素,则返回 -1。

(7)返回列表中最后一次出现指定元素的索引,如果列表不包含此元素,则返回 -1。

(8)将新元素插入第i个位置,0≤i < n,使原来的第i,i+1,…,n–1个元素变为第i+1,i+2,…,n个元素。

(9)更改第i个元素

(10)删除第i个元素,0≤i < n,使原来的第i+1,i+2,…,n–1个元素变为第i,i+1,…,n–2个元素

由此,对线性表抽象数据类型定义List接口如下:

List接口

package list;

public interface List {
	/**
	 * 将元素添加到线性表的末尾
	 */
	public void add(Object e);
	
	/**
	 * 清除线性表
	 */
	public void clear();
	/**
	 * 获取i位置的元素
	 * @param i
	 * @return
	 */
	public Object get(int i);
	/**
	 * 返回列表中首次出现指定元素的索引,如果列表不包含此元素,则返回 -1。
	 * @param e
	 * @return
	 */
	public int indexOf(Object e);
	/**
	 * 在i后面插入一个元素e
	 * @param i
	 * @param e
	 */
	public void insert(int i, Object e);
	/**
	 * 判断线性表是否为空
	 * @return
	 */
	public boolean isEmpty();
	/**
	 * 回列表中最后出现指定元素的索引,如果列表不包含此元素,则返回 -1。
	 * @param e
	 * @return
	 */
	public int lastIndexOf(Object e);
	/**
	 *  移除列表中指定位置的元素
	 * @param i
	 */
	public void remove(int i);
	/**
	 * 用指定元素替换列表中指定位置的元素(可选操作)。
	 * @param i
	 * @param e
	 */
	public void set(int i, Object e);
	/**
	 * 返回线性表的大小
	 * @return
	 */
	public int size();
}
           

顺序表

结构模型

线性表线性表概述顺序表单向循环链表双向循环链表测试线性表

图顺序存储结构内存结构示意图 

源代码

package list;

public class ArrayList implements List{
	/**
	 * 顺序表默认的初始大小
	 */
	public static final int defLen = 10;
	private int maxLen;
	private Object[] array;
	private int size;
	
	public ArrayList() {
		size = 0;
		maxLen = defLen;
		array = new Object[defLen];
	}
	
	@Override
	public void clear() {
		size = 0;
	}

	@Override
	public Object get(int i) {
		if(i>=0 && i<size)
			return array[i];
		else
			return null;
	}

	@Override
	public int indexOf(Object e) {
		int i =0; 
		while(i<size && !array[i].equals(e)) {
			i++;
		}
		if(i < size)
			return i;
		else
			return -1;
	}

	@Override
	public void insert(int i, Object e) {
		if(i >= size) {
			i = size;
			if((size) >= maxLen)//如果插入数的位置大于顺序表的最大容量,则扩大容量
				expand();
		}
		for(int j = size; j>i+1; j--) {
			array[j] = array[j-1];
		}
		array[i+1] = e;
		size ++;
	}

	@Override
	public boolean isEmpty() {
		if(size == 0)
			return true;
		else 
			return false;
	}

	@Override
	public int lastIndexOf(Object e) {
		int i = size-1;
		while(i>=0 && !array[i].equals(e)) {
			i--;
		}
		if(i>=0)
			return i;
		else
			return -1;
	}

	@Override
	public void remove(int i) {
		for(int j=i; j<size-1; j++) {
			array[j] = array[j+1];
		}
		size --;
	}

	@Override
	public void set(int i, Object e) {
		array[i] = e;
	}

	@Override
	public int size() {
		return size;
	}
	/**
	 * 当顺序表的大小不够时,扩充顺序表的大小
	 */
	private void expand() {
		maxLen = 2*maxLen;
		Object newArray[] = new Object[maxLen];
		for(int i=0; i<size; i++) {
			newArray[i] = array[i];
		}
		array = newArray;
	}

	@Override
	public void add(Object e) {
		if(size >=maxLen)
			expand();
		array[size] = e;
		size ++;
	}
}
           

单向循环链表

结构模型

线性表线性表概述顺序表单向循环链表双向循环链表测试线性表

带头结点的单链结构

  (a)空链;  (b)非空链 

源代码

package list;
/**
 * 链表的结点
 * @author luoweifu
 *
 */
class Node{
	Object data;	//数据元素
	Node next;		//后驱结点
	public Node() {
		this(null);
	}
	public Node(Object data) {
		this.data = data;
		this.next = null;
	}
}
/**
 * 带头结点的链式链表,下标从0开始; 
 * @author Administrator
 *
 */
public class LinkList implements List {
	Node head;	//头结点
	int size;	//链表的大小
	public LinkList() {
		head = new Node();
		size = 0;
	}
	public LinkList(Object[] datas) {
		int n = datas.length;
		head = new Node();
		Node p = head;
		for(int i=0; i<n; i++) {
			p.next = new Node(datas[i]);
			p = p.next;
		}
		size = n;
	}
	@Override
	public void add(Object e) {
		Node p;
		if(0 == size) {
			p = head;
		} else {
			p = index(size-1);
		}
		p.next = new Node(e);
		size ++;
	}

	@Override
	public void clear() {
		head.next = null;
		size = 0;
	}

	@Override
	public Object get(int i) {
		Node p = index(i);
		return p.data;
	}
	
	private Node index(int i) {
		Node p = null;
		if(i>=0 && i<size){
			p = head;
			for(int j=0; j<=i; j++) {
				p = p.next;
			}
		} 
		return p;
	}

	@Override
	public int indexOf(Object e) {
		Node p = head.next;
		int i = 0;
		while(!p.data.equals(e)) {
			p = p.next;
			i++;
		}
		if(i<size)
			return i;
		else 
			return -1;
	}

	@Override
	public void insert(int i, Object e) {
		Node p = index(i);
		Node p2 = new Node(e);
		p2.next = p.next;
		p.next = p2;
		size ++;
	}

	@Override
	public boolean isEmpty() {
		if(size ==0)
			return true;
		else
			return false;
	}

	@Override
	public int lastIndexOf(Object e) {
		int i = size-1;
		while(!get(i).equals(e)) {
			i--;
		}
		if(i>=0)
			return i;
		else 
			return -1;
	}

	@Override
	public void remove(int i) {
		if(i>=0 && i<size) {
			Node p = null;
			if(i == 0)
				p = head;
			else {
				p = index(i-1);
			}
			p.next = index(i).next;
		}
		size --;
	}

	@Override
	public void set(int i, Object e) {
		Node p = index(i);
		p.data = e;
	}

	@Override
	public int size() {
		return size; 
	}
	
}
           

双向循环链表

结构模型

线性表线性表概述顺序表单向循环链表双向循环链表测试线性表

带头结点的双循环链结构

 (a)空链;  (b)非空链 

源代码

package list;
/**
 * 链表的结点
 * @author luoweifu
 *
 */
class DlNode{
	Object data;
	DlNode prior, next;
	public DlNode() {
		this(null);
	}
	public DlNode(Object data) {
		this.data = data;	//数据元素
		this.prior = null;	//前驱结点
		this.next = null;	//后驱结点
	}
}
/**
 * 带头结点的双向循环链表,下标从0开始; 
 * @author Administrator
 *
 */
public class DoubleLinkList implements List {
	DlNode head;	//头结点
	int size;	//链表的大小
	public DoubleLinkList() {
		head = new DlNode();
		head.prior = head;
		head.next = head;
		size = 0;
	}
	public DoubleLinkList(Object[] datas) {
		int n = datas.length;
		head = new DlNode();
		DlNode p = head;
		DlNode p2 = null;
		for(int i=0; i<n; i++) {
			p2 = new DlNode(datas[i]);
			p.next = p2;
			p2.prior = p;
			p = p.next;
		}
		p2.next = head;
		head.prior = p2; 
		size = n;
	}
	@Override
	public void add(Object e) {
		DlNode p, p2;
		if(0 == size) {
			p = head;
		} else {
			p = index(size-1);
		}
		p2 = new DlNode(e);
		p.next = p2;
		p2.prior = p;
		p2.next = head;
		head.prior = p2;
		size ++;
	}

	@Override
	public void clear() {
		head.prior = head;
		head.next = head;
		size = 0;
	}

	@Override
	public Object get(int i) {
		DlNode p = index(i);
		return p.data;
	}
	
	private DlNode index(int i) {
		DlNode p = null;
		if(i>=0 && i<size){
			p = head;
			for(int j=0; j<=i; j++) {
				p = p.next;
			}
		} 
		return p;
	}

	@Override
	public int indexOf(Object e) {
		DlNode p = head.next;
		int i = 0;
		while(!p.data.equals(e)) {
			p = p.next;
			i++;
		}
		if(i<size)
			return i;
		else 
			return -1;
	}

	@Override
	public void insert(int i, Object e) {
		DlNode p = index(i);
		DlNode p2 = new DlNode(e);
		p2.next = p.next;
		p2.prior = p;
		p.next = p2;
		size ++;
	}

	@Override
	public boolean isEmpty() {
		if(size ==0)
			return true;
		else
			return false;
	}

	@Override
	public int lastIndexOf(Object e) {
		DlNode p = head.prior;
		int i = size-1;
		while(!p.data.equals(e)) {
			p = p.prior;
			i--;
		}
		if(i>=0)
			return i;
		else 
			return -1;
	}

	@Override
	public void remove(int i) {
		if(i>=0 && i<size) {
			DlNode p = null;
			if(i == 0)
				p = head;
			else {
				p = index(i-1);
			}
			DlNode p2 = index(i).next;
			p.next = p2.next;
			p2.next.prior = p;
		}
		size --;
	}

	@Override
	public void set(int i, Object e) {
		DlNode p = index(i);
		p.data = e;
	}

	@Override
	public int size() {
		return size; 
	}
	
}
           

测试线性表

package list;

public class Test {

	/**
	 * 测试线性表
	 * @param args
	 */
	public static void main(String args[]) {
		List list = new ArrayList();
		//List list = new LinkList();
		//List list = new DoubleLinkList();
		for(int i=0; i<10; i++) {
			list.add(new Integer(i));
		}
		list.remove(9);
		System.out.print("size;" + list.size() + "\n");
		System.out.println("isEmpty:" + list.isEmpty());
		System.out.print("第7个位置的元素:" + list.get(7) + "\n");	
		for(int i=0; i<list.size(); i++) {
			System.out.print(list.get(i) + "    ");
		}
		
		list.add(21);
		list.add(22);
		list.insert(3, new Integer(5));
		System.out.print("size:" + list.size() + "\n");
		System.out.print("第一次出现5的索引:" + list.indexOf(5) + "\n");
		System.out.print("最后一次出现5的索引:" + list.lastIndexOf(5) + "\n");
		list.set(0, new Integer(30));
		for(int i=0; i<list.size(); i++) {
			System.out.print(list.get(i) + "    ");
		}
	}
}
           

结果

size;9

isEmpty:false

第7个位置的元素:7

0    1    2    3    4    5    6    7    8    size:12

第一次出现5的索引:4

最后一次出现5的索引:6

30    1    2    3    5    4    5    6    7    8    21    22    

继续阅读