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));
        }

}
  • del.icio.us
  • StumbleUpon
  • Digg
  • TwitThis
  • Mixx
  • Technorati
  • Facebook
  • NewsVine
  • Reddit
  • Google
  • LinkedIn
  • YahooMyWeb

Related Posts of Learning Notes - data structure

  • hibernate study of the second

    Persistence of three main points: 1, a statement for persistent fields accessors (accessors) and whether the variable signs (mutators) Property statement is not necessarily required for the public's. Hibernate can be default, protected or private ...

  • hibernate (jpa) composite primary key annotation statement Ways

    In the design of the database tables are designed with a composite primary key of the table, that table's record by more than one field joint identification, such as: Table CREATE TABLE TB_HOUR_DATA ( STAT_DATE DATE NOT NULL, PATH_ID NUMBER(20) NOT NULL,

  • jboss ejb3 Message Driven Bean

    Super Medium ejb hate. . . . . . . . . . . . . . . . . . . ================================================ To configure a Message Driven Bean in a different application server parameters are not the same. Currently only passed the test jboss. Message Dri

  • hibernate call stored procedure

    hibernate call stored procedure

  • hibernate generic generic DAO

    package org.lzpeng.dao; import java.io.Serializable; import java.util.List; import org.hibernate.Criteria; import org.hibernate.Query; import org.hibernate.criterion.Criterion; import org.springside.modules.orm.hibernate.Page; /** * * @version 2009-1-10 *

  • First Hibernate Example

    Curd a simple example. Source does not contain the dependent libraries, or playing too much of the package. PO object Note: One must have the default constructor 2 non-final modified. Otherwise useless lazy loading. UserDAOImpl category code, and other co

  • Great collection of java interview topics

    1, object-oriented features of what has 1. Abstract: Abstract is that it has overlooked a subject has nothing to do with the current goal of those aspects in order to more fully with the current objectives of the attention-related aspects. Abstract does n

blog comments powered by Disqus
Recent
Recent Entries
Tag Cloud
Random Entries