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

相关文章

  • Java ArrayList in the remove (Object obj) method of 2010-09-27

    Today, having a bug, discovered that the original programmer to write the equals method is a little problem, it is a lot of problems. By the way looked ArrayList of remove (Object obj) method, it may look, is remove the following methods: public bool

  • Java proxy mode (through public interface) 2010-06-16

    Java proxy mode (through public interface) Proxy pattern implementation of a common scheme is to define an interface or abstract class, and derive the target subclass (RealClass), and proxy subclass (ProxyClass). We have to operate in the target sub-

  • Public key certificate - a public key encryption 2010-05-28

    Reprinted from: http://www.hoposoft.com/secuinfo/104.html Public key certificate - a public key encryption Public key certificate, usually referred to as the certificate is a digital signature of the declaration, it will bind public key values to the

  • Data encryption and public key private key public key certification 2011-01-25

    I have previously written an article entitled " Web login authentication security design "may be clear enough about, one reader questioned the message that" public disclosure of the name suggests is the matter, as long as you like, no one w

  • Hibernate.initialize (Object obj) 2009-09-24

    On lazy (lazy) and forced to load (Hibernate.initialize (Object proxy)), etc. Sustained in the use of hibernate when it is sometimes necessary to change the dynamic loading of objects, such as in the editorial pages inside lazy = true, the page in th

  • Understanding of Java Object Serialization - Serializable interface 2010-03-20

    Overview: When a class implements the Serializable interface (the interface only marker interface does not contain any method definition), indicating that the class can be serialized. The purpose is to serialize an object that implements Serializable

  • Change: Focus on Queue: Java 1.5 add a new data structure interface (SynchronousQueue) 2008-10-22

    Reprinted: http://blog.csdn.net/Victor_Jan/archive/2004/09/27/117695.aspx Java 1.5 versions will ultimately be provided for programming, one of the most basic data structure of the inner-Queue to support. This article will explore the newly added to

  • 有关int 和 Object 转换问题(oracle 10 默认JDK 1.4.2) 2013-05-29

    前天使用rhino 和js做了一个oracle的function,由于客户使用的是oracle 10,所以只支持jdk1.4.2的,其实很简单的,就是让oracle的函数支持使用javascript编写,实现过程较为简单,就是在传递参数时要求使用Object[] args , 可当我写如下代码时报错: Object [] args = {3,29}; 很明确地说不能将int 转换为Object ,以前好象没有这样的情况,查了好半天才想起原来在jdk1.4的时候,是不能把一个int 赋值给 Obj

  • ASP.NET Handler call ibatis appear in the Object reference not set to an instance of an object. 2010-08-27

    Project encountered a verification problem, call the method in the handler, always appear Object reference not set to an instance of an object.'s Wrong. Debugging mapper found for the session on a problem, the project is loaded sqlmapper used HttpCon

  • According to id, or to return the object obj 2010-01-10

    /** According to the id or the object returns an object or array of objects */ function $(){ var argLen = arguments.length; var eleArr = new Array; if(argLen == 0) return null; else if(argLen == 1){ if(typeof arguments[0] == "object") return arg

iOS 开发

Android 开发

Python 开发

JAVA 开发

开发语言

PHP 开发

Ruby 开发

搜索

前端开发

数据库

开发工具

开放平台

Javascript 开发

.NET 开发

云计算

服务器

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

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

processed in 0.459 (s). 12 q(s)