Learning Notes - data structure

Linear Table

1, ADT

/**
 *
 *  Linear table  ADT
 * @author sxw
 *
 */
public interface List {

        /**
         *  Get the number of data elements  .
         * @return  Returns the size of the linear table
         */
        public int getSize();

        /**
         *  Judge linear table is empty
         * @return  If linear table is NULL returns true, otherwise it returns  false.
         */
        public boolean isEmpty();

        /**
         *  Determine whether there is data in the linear table elements  e
         * @param e  Data elements
         * @return  If linear table contains e returns  true, Otherwise it returns  false.
         */
        public boolean contains(Object e);

        /**
         *  Locate the data element e online of the position in the table
         * @param e
         * @return  Returns a data element e online ordinal of a table  , If you do not find returns  -1.
         */
        public int indexOf(Object e);

        /**
         *  The data element e is inserted into the linear table  index Location
         * @param index
         * @param e
         * @throws OutOfBoundaryException  If index is out of the capacity of the linear table  , This exception is thrown
         */
        public void insert(int index, Object e) throws OutOfBoundaryException;

        /**
         *  The data element e is inserted into the element  obj Before
         * @param obj
         * @param e
         * @return  If the insert was successful
         */
        public boolean insertBefore(Object obj, Object e);

        /**
         *  The data element e is inserted into the element  obj After
         * @param obj
         * @param e
         * @return  If the insert was successful
         */
        public boolean insertAfter(Object obj, Object e);

        /**
         *  Delete linear table element sequence number I  , And return of
         * @param index
         * @return  Returns the deleted data elements
         * @throws OutOfBoundaryException  If index out  , This exception is thrown  .
         */
        public Object remove(int index) throws OutOfBoundaryException;

        /**
         *  Delete linear table first and e the same elements
         * @param e
         * @return  Are you sure you want to delete was successful
         */
        public boolean remove(Object e);

        /**
         *  Replace linear table ordinal data element-I  e
         * @param index
         * @param e
         * @return  Returns the original data elements
         * @throws OutOfBoundaryException  If index out  , This exception is thrown  .
         */
        public Object replace(int index, Object e) throws OutOfBoundaryException;

        /**
         *  Get the ordinal index of the data elements
         * @param index
         * @return  Returns the serial number is linear table index of the data elements
         * @throws OutOfBoundaryException  If index out  , This exception is thrown  .
         */
        public Object get(int index) throws OutOfBoundaryException;
}

2, the linear form of the order of image

Image sequence using an array to achieve

Linear order of the table structure is a random access memory storage structure.

/**
 *  Linear table order image using array implementation
 * @author sxw
 *
 */
public class ListArray implements List
{
        private static final int LEN = 10; //  The default size of the array
        private Strategy strategy; //  Data elements compare policy
        private int size; //  Linear data from the table, the number of elements
        private Object[] elements; //  A data element array  

        public ListArray()
        {
                this(new DefaultStrategy());
        }

        public ListArray(Strategy strategy)
        {
                this.strategy = strategy;
                size = 0;
                elements = new Object[LEN];
        }

        //  Returns the size of the linear table, that is, the number of data elements  .
        public int getSize()
        {
                return size;
        }

        //  If linear table is NULL returns true, otherwise it returns  false.
        public boolean isEmpty()
        {
                return size == 0;
        }

        //  Determine whether there is data in the linear table elements  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;
        }

        //  Returns a data element e online ordinal of a table
        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;
        }

        //  The data element e is inserted into the linear table  i Number location
        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();
                //  Array expansion
                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);
                }
        }

        //  The data element e is inserted into the element  obj Before
        public boolean insertBefore(Object obj, Object e)
        {
                int i = indexOf(obj);
                if (i < 0) return false;
                insert(i, e);
                return true;
        }

        //  The data element e is inserted into the element  obj After
        public boolean insertAfter(Object obj, Object e)
        {
                int i = indexOf(obj);
                if (i < 0) return false;
                insert(i + 1, e);
                return true;
        }

        //  Delete linear table element sequence number I  , And return of
        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;
        }

        //  Delete linear table first and e the same elements
        public boolean remove(Object e)
        {
                int i = indexOf(e);
                if (i < 0) return false;
                remove(i);
                return true;
        }

        //  Replace linear table ordinal data element-I  e, Returns the original data elements
        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;
        }

        //  Returns the serial number is linear in table I of data elements
        public Object get(int index) throws OutOfBoundaryException
        {
                if (index < 0 || index >= size) throw new OutOfBoundaryException("Index: "+index+", Size: "+size);
                return elements[index];
        }
}

3, analysis

i. Insert

First filter exception, if the incoming parameter super-sector, an exception

Array expansion, call ensureCapacity function

Elements after the index moved back, the index position of assignment into

Array length by 1

ii. delete

First of all, to increase process robustness, exception filter

Remove the index position of the specified element after element move forward,

After setting the last element of the array is null, so that gc to recovery, and size by 1

Remove the element to return

4, test cases

/**
 * @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));
        }

}
分类:Java 时间:2010-03-28 人气:220
分享到:
blog comments powered by Disqus

相关文章

iOS 开发

Android 开发

Python 开发

JAVA 开发

开发语言

PHP 开发

Ruby 开发

搜索

前端开发

数据库

开发工具

开放平台

Javascript 开发

.NET 开发

云计算

服务器

Copyright (C) codeweblog.com, All Rights Reserved.

CodeWeblog.com 版权所有 黔ICP备15002463号-1

processed in 0.230 (s). 14 q(s)