学习笔记--数据结构

线性表

1、ADT

/**
 * 
 * 线性表ADT
 * @author sxw
 *
 */
public interface List {
	
	/**
	 * 得到数据元素的个数。
	 * @return 返回线性表的大小
	 */
	public int getSize();
	
	/**
	 * 判断线性表是否为空
	 * @return 如果线性表为空返回true，否则返回false。
	 */
	public boolean isEmpty();
	
	/**
	 * 判断线性表是否包含数据元素e
	 * @param e 数据元素
	 * @return 如果线性表包含e返回true，否则返回false。
	 */
	public boolean contains(Object e);
	
	/**
	 * 定位数据元素e在线性表中的位置
	 * @param e
	 * @return 返回数据元素e在线性表中的序号，如果找不到返回-1。
	 */
	public int indexOf(Object e);
	
	/**
	 * 将数据元素e插入到线性表中index位置
	 * @param index
	 * @param e
	 * @throws OutOfBoundaryException 如果index超出线性表的容量，抛出此异常
	 */
	public void insert(int index, Object e) throws OutOfBoundaryException;
	
	/**
	 * 将数据元素e插入到元素obj之前
	 * @param obj
	 * @param e
	 * @return 是否插入成功
	 */
	public boolean insertBefore(Object obj, Object e);
	
	/**
	 * 将数据元素e插入到元素obj之后
	 * @param obj
	 * @param e
	 * @return 是否插入成功
	 */
	public boolean insertAfter(Object obj, Object e);
	
	/**
	 * 删除线性表中序号为i的元素,并返回之
	 * @param index
	 * @return 返回删除的数据元素
	 * @throws OutOfBoundaryException 如果index超界，则抛出此异常。
	 */
	public Object remove(int index) throws OutOfBoundaryException;
	
	/**
	 * 删除线性表中第一个与e相同的元素
	 * @param e
	 * @return 是否删除成功
	 */
	public boolean remove(Object e);
	
	/**
	 * 替换线性表中序号为i的数据元素为e
	 * @param index
	 * @param e
	 * @return 返回原数据元素
	 * @throws OutOfBoundaryException 如果index超界，则抛出此异常。
	 */
	public Object replace(int index, Object e) throws OutOfBoundaryException;
	
	/**
	 * 取得序号index的数据元素
	 * @param index
	 * @return 返回线性表中序号为index的数据元素
	 * @throws OutOfBoundaryException 如果index超界，则抛出此异常。
	 */
	public Object get(int index) throws OutOfBoundaryException;
}

 2、线性表的顺序映像

顺序映像采用数组实现

线性表的顺序存储结构是一种随机存取的存储结构。

/**
 * 线性表顺序映像采用数组实现
 * @author sxw
 *
 */
public class ListArray implements List
{
	private static final int LEN = 10; // 数组的默认大小
	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;
		return indexOf(e) > 0;
	}

	// 返回数据元素e在线性表中的序号
	public int indexOf(Object e)
	{
		if (e == null)
		{
			for (int i = 0; i < size; i++)
			{
				if (elements[i] == null) return i;
			}
		}
		for (int i = 0; i < size; i++)
			if (strategy.equal(e, elements[i])) return i;
		return -1;
	}

	// 将数据元素e插入到线性表中i号位置
	public void insert(int index, Object e) throws OutOfBoundaryException
	{
		if (index < 0 || index > size) throw new OutOfBoundaryException("Index: "+index+", Size: "+size);
		
//		if (size >= elements.length) ensureCapacity();
		// 数组扩容
		ensureCapacity(size + 1);
		
		
		for (int j = size; j > index; j--)
		{
			elements[j] = elements[j - 1];
		}
		// 	System.arraycopy(elementData, index, elementData, index + 1, size - index);
		
		elements[index] = e;
		size++;
		return;
	}

	private void ensureCapacity(int minCapacity)
	{
//		Object[] a = new Object[elements.length * 2];
//		for (int i = 0; i < elements.length; i++)
//			a[i] = elements[i];
//		elements = a;
		
		int oldCapacity = elements.length;
		if (minCapacity > oldCapacity)
		{
			// increase strategy
			int newCapacity = (oldCapacity * 3) / 2 + 1;
			if (newCapacity < minCapacity) 
			{
				newCapacity = minCapacity;
			}
			// minCapacity is usually close to size, so this is a win:
			elements = Arrays.copyOf(elements, newCapacity);
		}
	}

	// 将数据元素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 index) throws OutOfBoundaryException
	{
		if (index < 0 || index >= size) throw new OutOfBoundaryException("Index: "+index+", Size: "+size);
		Object obj = elements[index];
		for (int j = index; 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 index, Object e) throws OutOfBoundaryException
	{
		if (index < 0 || index >= size) throw new OutOfBoundaryException("Index: "+index+", Size: "+size);
		Object obj = elements[index];
		elements[index] = e;
		return obj;
	}

	// 返回线性表中序号为i的数据元素
	public Object get(int index) throws OutOfBoundaryException
	{
		if (index < 0 || index >= size) throw new OutOfBoundaryException("Index: "+index+", Size: "+size);
		return elements[index];
	}
}

 3、分析

      i.插入

         首先过滤异常，如果传入参数超界，抛出异常

         数组扩容，调用ensureCapacity函数

         将index后的元素向后移动，将index位置赋值插入

         数组长度增1

     ii.删除

       首先增加程序健壮性，过滤异常

       指定删除的index位置元素后的元素前移，

      之后设置数组最后一个元素为null，让gc去回收，并size减1

      返回删除的元素

 

4、测试用例

/**
 * @author sxw
 * 
 */
public class ListArrayTest
{

	private static People people;
	private List list;

	/**
	 * @throws java.lang.Exception
	 */
	@Before
	public void setUp() throws Exception
	{
		list = new ListArray();
		people = new People();
		insertToList(list);
	}

	private static void insertToList(List l)
	{
		for (int j = 0; j < 9; j++)
		{
			l.insert(j, new People("People" + " " + j, String.valueOf(j)));
		}
		l.insert(9, people);
	}

	/**
	 * @throws java.lang.Exception
	 */
	@After
	public void tearDown() throws Exception
	{
	}

	/**
	 * Test method for {@link dsa.adt.ListArray#getSize()}.
	 */
	@Test
	public final void testGetSize()
	{
		Assert.isTrue(list.getSize() == 10);
		System.out.println(list.getSize());
//		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link dsa.adt.ListArray#isEmpty()}.
	 */
	@Test
	public final void testIsEmpty()
	{
		Assert.isTrue(list.isEmpty() == false);
//		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link dsa.adt.ListArray#contains(java.lang.Object)}.
	 */
	@Test
	public final void testContains()
	{
		Assert.isTrue(list.contains(people));
//		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link dsa.adt.ListArray#indexOf(java.lang.Object)}.
	 */
	@Test
	public final void testIndexOf()
	{
		Assert.isTrue(list.indexOf(people) > 0);
//		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link dsa.adt.ListArray#insert(int, java.lang.Object)}.
	 */
	@Test
	public final void testInsert()
	{
		int size = list.getSize();
		list.insert(list.getSize(), people);
		Assert.isNotNull(list.get(size));
//		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for
	 * {@link dsa.adt.ListArray#insertBefore(java.lang.Object, java.lang.Object)}
	 * .
	 */
	@Test
	public final void testInsertBefore()
	{
		int size = list.getSize();
		Object obj = new Object();
		list.insertBefore(people, obj);
		Assert.isTrue(list.get(size - 1) == obj);
//		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for
	 * {@link dsa.adt.ListArray#insertAfter(java.lang.Object, java.lang.Object)}
	 * .
	 */
	@Test
	public final void testInsertAfter()
	{
		int size = list.getSize();
		Object obj = new Object();
		list.insertAfter(people, obj);
		Assert.isTrue(list.get(size) == obj);
//		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link dsa.adt.ListArray#remove(int)}.
	 */
	@Test
	public final void testRemoveInt()
	{
		int size = list.getSize();
		list.remove(size - 1);
		Assert.isTrue(list.getSize() == size - 1);
//		fail("Not yet implemented"); // TODO
	}

	/**
	 * Test method for {@link dsa.adt.ListArray#remove(java.lang.Object)}.
	 */
	@Test
	public final void testRemoveObject()
	{
		int size = list.getSize();
		list.remove(people);
		Assert.isTrue(list.getSize() == size - 1);
	}

	/**
	 * Test method for {@link dsa.adt.ListArray#replace(int, java.lang.Object)}.
	 */
	@Test
	public final void testReplace()
	{
		list.replace(0, people);
		Assert.isTrue(list.get(0) == people);
	}

	/**
	 * Test method for {@link dsa.adt.ListArray#get(int)}.
	 */
	@Test
	public final void testGet()
	{
		Assert.isNotNull(list.get(0));
	}

}