- 导语
线性结构又分为多种类型：顺序线性表、链式线性表、栈、队列、堆等等
今天我们来复习一下如何使用数组来实现线性表
- 设计抽象数据类型ADT
package com.zhanwj.datastructure;
public interface ListInterface {
/**
* @return the size of the list
*/
public int getSize();
/**
* @return
* if null then return true,else return false
*/
public boolean isEmpty();
/**
* @param mObject the object that wanted to be
*confirm whether it is contained in the list
* @return if the list contains the object then return true
*/
public boolean contains(Object mObject);
/**
* return the index of object in the list
* @param mObject
* @returnthe index
*/
public int indexOf(Object mObject);
/**
* insert element into the list
* @param ithe place to insert
* @param mObject the element to insert
*/
public void insert(int i,Object mObject) throws OutOfBoundaryException;
/**
* insert the element before the mObject
* @param mObject
* @param element
*/
public boolean insertBefore(Object mObject,Object element);
/**
* insert the element after the mObject
* @param mObject
* @param element
*/
public boolean insertAfter(Object mObject,Object element);
/**
* remove the element whose index is i
* @param i
* @return object
*/
public Object remove(int i) throws OutOfBoundaryException;
/**
* remove the object that same as mObject at the first time
* @param mObject
* @return
*/
public boolean remove(Object mObject);
/**
* replace the element whose index is i with mObject
* @param i
* @param mObject
* @return
*/
public Object replace(int i,Object mObject) throws OutOfBoundaryException;
/**
* return the element whose index is i
* @param i
* @return
*/
public Object get(int i) throws OutOfBoundaryException;
}
分析：在此接口中，声明了常用的线性表操作函数，最主要的就是插入数据、删除数据、替换数据等等
- 设计顺序线性表类
package com.zhanwj.datastructure;
/**
* use array to implement the list
* @author wenjerzhan
*
*/
public class ListArray implements ListInterface {
/**
* the default length of the array
*/
private final int LENGTH = 8;
/**
* the size of the list
*/
private int size;
/**
* the array definition
*/
private Object[] elements;
private CompareInterface mCompareInterface;
public ListArray(CompareInterface compareInterface){
this.mCompareInterface = compareInterface;
this.size = 0;
this.elements = new Object[LENGTH];
}
@Override
public int getSize() {
return size;
} @Override
public boolean isEmpty() {
return size==0;
} @Override
public boolean contains(Object mObject) {
for (int i = 0;
i < size;
i++) {
if (this.mCompareInterface.equal(mObject, (Object)elements[i]))
return true;
}
return false;
}
@Override
public int indexOf(Object mObject) {
for (int i = 0;
i < size;
i++) {
if (this.mCompareInterface.equal(mObject, elements[i]))
return i;
}
return -1;
} @Override
public void insert(int i, Object mObject) throws OutOfBoundaryException {
if (i < 0||i > size )
throw new OutOfBoundaryException("error,out of the list boundary");
if (size >= elements.length)
addArrayLength();
for (int j = size;
j >i;
j--)
elements[j] = elements[j-1];
elements[i] = mObject;
size++;
}
private void addArrayLength(){
Object[] temp = new Object[elements.length*2];
for (int i = 0;
i < elements.length;
i++) {
temp[i] = elements[i];
}
elements = temp;
} @Override
public boolean insertBefore(Object mObject, Object element) {
int index = indexOf(mObject);
if (index < 0 )
return false;
insert(index, element);
return true;
} @Override
public boolean insertAfter(Object mObject, Object element) {
int index = indexOf(mObject);
if (index < 0)
return false;
insert(index+1, element);
return true;
} @Override
public Object remove(int i) throws OutOfBoundaryException {
if (i <0 ||i>= size)
throw new OutOfBoundaryException("error,out of the boundary");
Object mObject = elements[i];
for (int j = i;
j < size-1;
j++) {
elements[j] = elements[j+1];
}
elements[--size] = null;
return mObject;
} @Override
public boolean remove(Object mObject) {
int index = indexOf(mObject);
if (index < 0 )
return false;
remove(index);
return true;
} @Override
public Object replace(int i, Object mObject) throws OutOfBoundaryException {
if (i <0 ||i>= size)
throw new OutOfBoundaryException("error,out of the boundary");
Object temp = elements[i];
elements[i] = mObject;
return temp;
} @Override
public Object get(int i) throws OutOfBoundaryException {
if (i <0 ||i>= size)
throw new OutOfBoundaryException("error,out of the boundary");
return elements[i];
}}
备注：注意各操作方法实现的顺序，有些方法的实现需要调用其他方法
- 类文件UML视图
文章图片
- 测试代码
package com.zhanwj.datastructure;
public class ListArrayTest {
public static void main(String[] args) throws Exception{
CompareInterface compareInterface = new CompareInterface() {@Override
public boolean equal(Object mObject1, Object mObject2) {
if (mObject1.equals(mObject2))
return true;
return false;
}@Override
public int compare(Object mObject1, Object mObject2) {
return mObject1.toString().compareTo(mObject2.toString());
}
};
ListArray mListArray = new ListArray(compareInterface);
final int LENGTH = 8;
int num = 11;
/**
* test the getSize() function
*/
System.out.println("====before insert operation,the size of the list is "+mListArray.getSize());
/**
* test the isEmpty() function
*/
String isEmptyTest = mListArray.isEmpty()?"empty":"not empty";
System.out.println("====before insert operation ,the list is "+isEmptyTest);
/**
* test the insert(i,object) function
*/
for (int i = 0;
i < LENGTH;
i++) {
mListArray.insert(i, ++num);
System.out.println("insert into position "+(i+1)+" with value of "+num);
}
System.out.println("after insert operation,the size of the list is "+mListArray.getSize());
/**
* test the contains(object) function
*/
String contains = mListArray.contains((Object)14)?"contain":"not contain";
String notContains = mListArray.contains((Object)11)?"contain":"not contain";
System.out.println("====the value 14 "+contains+" in the list");
System.out.println("the value 11 "+notContains+" in the list");
/**
* test the indexOf(Object) function
*/
System.out.println("====the index of 13 is "+ (mListArray.indexOf((Object)13)+1));
/**
* test the insertBefore(object1,object2) function
*/
mListArray.insertBefore(14, 44);
System.out.println("====insert 44 before 14!");
System.out.print("the list is:");
for (int i = 0;
i < mListArray.getSize();
i++) {
System.out.print(mListArray.get(i)+"\t");
}
System.out.println();
/**
* test the insertAfter(object1,object2) function
*/
mListArray.insertAfter(14, 45);
System.out.println("====insert 45 after 14!");
System.out.print("the list is:");
for (int i = 0;
i < mListArray.getSize();
i++) {
System.out.print(mListArray.get(i)+"\t");
}
System.out.println();
/**
* test the remove(i) function
*/
mListArray.remove(7);
System.out.print("====after remove,the list is:");
for (int i = 0;
i < mListArray.getSize();
i++) {
System.out.print(mListArray.get(i)+"\t");
}
System.out.println();
/**
* test the replace(i,object) function
*/
mListArray.replace(7, 23);
System.out.print("====after replace,the list is:");
for (int i = 0;
i < mListArray.getSize();
i++) {
System.out.print(mListArray.get(i)+"\t");
} }
}
测试代码运行结果：
| ====before insert operation,the size of the list is 0 ====before insert operation ,the list is empty insert into position 1 with value of 12 insert into position 2 with value of 13 insert into position 3 with value of 14 insert into position 4 with value of 15 insert into position 5 with value of 16 insert into position 6 with value of 17 insert into position 7 with value of 18 insert into position 8 with value of 19 after insert operation,the size of the list is 8 ====the value 14 contain in the list the value 11 not contain in the list ====the index of 13 is 2 ====insert 44 before 14! the list is:12 1344141516171819 ====insert 45 after 14! the list is:12 134414451516171819 ====after remove,the list is:121344144515161819 ====after replace,the list is:121344144515162319 |
【java数据结构（线性表之数组实现）】
