学步园

A Beta Version with much room for improvement.

package orderlink;<br /> /**有序链表。不允许有重复数据。<br /> * @author Sodino<br /> * @version 1.0 beta*/<br /> public class OrderLink {<br /> /**标识本链表中没有此元素。*/<br /> public static final int NO_ELEMENT = -1;<br /> /** 默认的空间增量值。 */<br /> public static final int DEFAULT_INCREMENT = 7;<br /> /**升序标识符。当为升序时为true，降序时为false。只可在构造函数中进行赋值。*/<br /> private final boolean ascent;<br /> /** 当前链表已存储的整形数据元素个数。 */<br /> private int size;<br /> /** 当前链表可以存储的整形数据的最多个数。 */<br /> private int capability;<br /> /** 链表新增空间增量值。当array的长度不足时要新开辟的空间增量。 */<br /> private int increment;<br /> /** 用于存储数据的数组。 */<br /> private int[] array;<br /> /**新元素可插入的索引序号。默认值为NO_ELEMENT*/<br /> private int insertIndex = NO_ELEMENT;<br /> /**构造一个有序链表并指定排序顺序。初始容量为DEFAULT_INCREMENT。<br /> * @param ascent - 指定排序顺序。ascent为true表示升序，为false表示降序。*/<br /> public OrderLink(boolean ascent) {<br /> this.ascent = ascent;<br /> this.capability = DEFAULT_INCREMENT;<br /> this.increment = DEFAULT_INCREMENT;<br /> this.size = 0;<br /> array = new int[this.capability];<br /> }<br /> /**构造一个有序链表。<br /> * @param capability - 指定本链表的初始容量 。<br /> * @param increment - 指定本链表的增量值。<br /> * @param ascent - 指定本链表的排序顺序。<br /> * */<br /> public OrderLink(int capability, int increment, boolean ascent) {<br /> this.capability = Math.max(DEFAULT_INCREMENT, capability);<br /> this.increment = Math.max(DEFAULT_INCREMENT, increment);<br /> this.ascent = ascent;<br /> size = 0;<br /> array = new int[this.capability];<br /> }<br /> /**构造一个有序链表并将指定的数组数据添加进链表中。排序顺序为指定的升降序。<br /> * @param arr - 指定的数组。<br /> * @param ascent - 指定的排序顺序。*/<br /> public OrderLink(int[] arr, boolean ascent) {<br /> this.ascent = ascent;<br /> this.capability = Math.max(arr.length, DEFAULT_INCREMENT);<br /> this.increment = DEFAULT_INCREMENT;<br /> this.size = 0;<br /> array = new int[this.capability];<br /> add(arr);<br /> }<br /> /**<br /> * 获取指定的序号的数据。<br /> * @param index - 指定的序号。<br /> * @return 当index小于等于size时，返回指定的序号的数据值；如果大于index值，返回0。<br /> */<br /> public int get(int index) {<br /> if (index > size() - 1 || index < 0) {<br /> return 0;<br /> }<br /> return array[index];<br /> }<br /> /**将指定的数组添加进本链表中。*/<br /> public void add(int[] arr) {<br /> for (int i = 0; i < arr.length; i++) {<br /> add(arr[i]);<br /> }<br /> }<br /> /**往链表中添加进一个新数据。<br /> * @param num - 将要添加进链表的数据。<br /> * @return 如果添加成功，返回true，失败，即要添加的数据已经在本链表中存在了，则返回false。*/<br /> public boolean add(int num) {<br /> int index = indexOf(num);<br /> if (index == NO_ELEMENT) {<br /> System.out.println("num = " + num + " insertIndex = "<br /> + insertIndex);<br /> insert(num, insertIndex);<br /> return true;<br /> }<br /> return false;<br /> }<br /> /**将指定的数据插入到指定序号的位置中。<br /> * @param num - 指定要插入的数据。<br /> * @param index - 指定的序号。*/<br /> private void insert(int num, int index) {<br /> confirmCapability(size() + 1);<br /> System.arraycopy(array, insertIndex, array, insertIndex + 1, size()<br /> - insertIndex);<br /> array[insertIndex] = num;<br /> setSize(size() + 1);<br /> }<br /> /**查找指定的数在本链表中的序号。起始值为0。<br /> * @param num - 指定的要查找的数。<br /> * @return 如果查找到了，则返回在本链表中的序号。如果没找到则返回NO_ELEMENT。*/<br /> public int indexOf(int num) {<br /> return binSearch(array, num);<br /> }<br /> /**删除指定序号的数。<br /> * @param index - 指定要删除的序号。<br /> * @return 删除成功返回true，否则返回false。*/<br /> public boolean remove(int index) {<br /> if (index < 0 || index >= size()) {<br /> return false;<br /> }<br /> System.arraycopy(array, index + 1, array, index, size() - 1 - index);<br /> setSize(size() - 1);<br /> return true;<br /> }<br /> /**<br /> * 设置空间增量值。增量最小值默认为DEFAULT_INCREMENT。<br /> */<br /> public void setIncrement(int increment) {<br /> this.increment = Math.max(increment, DEFAULT_INCREMENT);<br /> }<br /> /**<br /> * 获取当前链表可以存储的整形数据的最多个数。<br /> *<br /> * @return 当前链表可以存储的整形数据的最多个数。<br /> */<br /> public int getCapability() {<br /> return capability;<br /> }<br /> /**<br /> * 获取空间增量值。<br /> *<br /> * @return 空间增量值。<br /> */<br /> public int getIncrement() {<br /> return increment;<br /> }<br /> /**<br /> * 删除所有的数据。<br /> */<br /> public void clear() {<br /> setSize(0);<br /> }<br /> /**<br /> * 设置新的size值。<br /> * @param size - 新的size值。<br /> */<br /> private void setSize(int size) {<br /> this.size = size;<br /> }<br /> /**<br /> * 返回当前链表忆存储的整形数据个数。<br /> * @return 当前链表忆存储的整形数据个数。<br /> */<br /> public int size() {<br /> return size;<br /> }<br /> /**获取排序信息。<br /> * @return 升序返回true，降序返回false。*/<br /> public boolean isAscent() {<br /> return ascent;<br /> }<br /> /**二分查找。<br /> * @param array - 要查找的数组。<br /> * @param num - 指定的要查找的数据。<br /> * @return 如果查找到了，则返回在本链表中的序号。如果没找到则返回NO_ELEMENT。*/<br /> private int binSearch(int[] array, int num) {<br /> // 初始工作。<br /> insertIndex = NO_ELEMENT;<br /> int index = NO_ELEMENT;<br /> if (size() == 0) {<br /> insertIndex = 0;<br /> return index;<br /> }<br /> int lowIndex = 0, highIndex = size() - 1, midIndex = 0;<br /> while (lowIndex <= highIndex) {<br /> midIndex = (lowIndex + highIndex) >> 1;<br /> if (array[midIndex] == num) {<br /> index = midIndex;<br /> break;<br /> }<br /> // 确定insertIndex 的位置<br /> if (lowIndex == highIndex) {<br /> // 都找完了，没找到<br /> // 默认情况为：<br /> insertIndex = lowIndex;<br /> // 考虑特殊情况：<br /> if (isAscent()) {<br /> if (array[lowIndex] < num) {<br /> insertIndex = lowIndex + 1;<br /> }<br /> // 默认情况不作修改。<br /> // else{<br /> // insertIndex = lowIndex;<br /> // }<br /> } else {<br /> if (array[lowIndex] > num) {<br /> insertIndex = lowIndex + 1;<br /> }<br /> // 默认情况不作修改。<br /> // else{<br /> // insertIndex = lowIndex;<br /> // }<br /> }<br /> break;<br /> }<br /> // 二分查找<br /> if (array[midIndex] > num) {<br /> if (isAscent()) {<br /> // highIndex = midIndex - 1;//用下面的句子代替本句是因为((low +<br /> // high)>>1)会有个向下取整。取整后若mid = low时且执行mid = high<br /> // -1,则出现high反而比low小的情况，异常。<br /> highIndex = Math.max(lowIndex, midIndex - 1);<br /> } else {<br /> lowIndex = midIndex + 1;<br /> }<br /> } else {<br /> if (!isAscent()) {<br /> highIndex = Math.max(lowIndex, midIndex - 1);<br /> } else {<br /> lowIndex = midIndex + 1;<br /> }<br /> }<br /> }<br /> return index;<br /> }<br /> /**<br /> * <p><br /> * 确认当前的OrderLink是否可以存储size大小的数据量。</p><br /> * <p><br /> * 如果不足以存储size大小的数据量，OrderLink将自动增加increment大小的空间。</p><br /> *<br /> * @param size - 待验证的容量。<br /> */<br /> private void confirmCapability(int size) {<br /> int sub = size - getCapability();<br /> if (sub > 0) {<br /> // 空间不足<br /> // System.out.println("Capability is Inadequate!");<br /> int incre = Math.max(increment, sub);<br /> addCapability(incre);<br /> }<br /> }<br /> /**<br /> * 一次性增加本链表的容量。<br /> *<br /> * @param increment - 新增加的容量值。<br /> * @return 容量增加成功返回true，失败返回false。<br /> */<br /> public boolean addCapability(int increment) {<br /> if (increment <= 0) {<br /> return false;<br /> }<br /> int newCapability = this.getCapability() + increment;<br /> int[] newArr = new int[newCapability];<br /> this.capability = newCapability;<br /> System.arraycopy(array, 0, newArr, 0, array.length);<br /> array = null;<br /> array = newArr;<br /> // System.out.println("addCapabilityValue:" + increment);<br /> return true;<br /> }<br /> /**<br /> * 减少OrderLink的容量值。无论减少值为多少，OrderLink都保留至少DEFAULT_INCREMENT大小的最小容量。减少容量值过大可能会影响已存储了的数据。<br /> *<br /> * @param decrement - 容量值的减少量。<br /> * @return 容量减少成功返回true，失败返回false。<br /> */<br /> public boolean reduceCapability(int decrement) {<br /> if (decrement <= 0) {<br /> return false;<br /> }<br /> int maxDecrement = getCapability() - DEFAULT_INCREMENT;<br /> if (decrement > maxDecrement) {<br /> decrement = maxDecrement;<br /> }<br /> int newCapability = getCapability() - decrement;<br /> int[] newArr = new int[newCapability];<br /> this.capability = newCapability;<br /> setSize(Math.min(size(), newCapability));<br /> int copyLength = size();<br /> System.arraycopy(array, 0, newArr, 0, copyLength);<br /> // System.out.println("newCap: " + this.getCapability() +<br /> // "copyLength: "<br /> // + copyLength);<br /> array = null;<br /> array = newArr;<br /> return true;<br /> }<br /> }<br />