java数据结构实现顺序表示例
import java.util.arrays;
/**
* 顺序线性表的实现
*/
public class linelist<e>{
private int size; //长度
private object[] array; //底层数组
private final int default_length=16; //默认长度
/**
* 无参构造方法
*/
public linelist(){
size = 0;
//使用默认长度构造数组
array = new object[default_length];
}
/**
* 指定长度进行构造
* @param length 指定初始长度
*/
public linelist(int length){
if(length<0){
throw new illegalargumentexception("初始长度不合法:"+length);
}
//使用指定长度构造数组
array = new object[length];
}
/**
* 指定初始化元素和长度进行构造
* @param element 初始化元素
* @param length 初始化长度
*/
public linelist(e element,int length){
if(length<1){
throw new illegalargumentexception("初始长度不合法:"+length);
}
//使用指定长度构造数组
array = new object[length];
//初始化第一个元素
array[0] = element;
size++;
}
/**
* 指定初始化元素进行构造
* @param element 初始化元素
*/
public linelist(e element){
//使用默认长度初始化数组
array = new object[default_length];
//初始化第一个元素
array[0] = element;
}
/**
* 获取元素个数
*/
public int size() {
return size;
}
/**
* 判断是否为空
*/
public boolean isempty() {
return size==0;
}
/**
* 判断是否包含此元素
*/
public boolean contains(e e) {
if(indexof(e) == -1){
return false;
}
return true;
}
/**
* 格式化为数组
*/
public object[] toarray() {
return arrays.copyof(array, size);
}
/**
* 向线性表尾部添加一个元素
* @param e
* @return
*/
public void add(e e) {
extendcapacity(size+1);
array[size]=e;
size++;
}
/**
* 扩容
* @param length 需要的长度
*/
private void extendcapacity(int length){
//当前数组长度和需要的长度取最大
int mincapacity = math.max(array.length, length);
//判断是否需要扩容
if(mincapacity - array.length>0){
//数组长度增加一半
int newlength = array.length + array.length/2;
//如果新的长度还比需求要小,将需求的长度作为数组长度
if(newlength < mincapacity){
newlength=mincapacity;
}
//数组长度不能超过integer.max_value
if(newlength > integer.max_value - 8){
newlength = integer.max_value;
}
//数组扩容
array = arrays.copyof(array, newlength);
}
}
/**
* 从线性表中移除所有此元素
* @param e 需要移除的元素
* @return
*/
public void removeall(e e) {
if(e==null){
for(int i=0;i<size;i++){
if(array[i]==null){
fastremove(i);
}
}
}else{
for(int i=0;i<size;i++){
if(e.equals(array[i])){
fastremove(i);
}
}
}
}
/**
* 删除索引处元素,后面的元素依次前移
* @param index 需要删除的索引
*/
private void fastremove(int index){
if(size-index-1>0){
//数组从index+1开始全部前移
system.arraycopy(array, index+1, array, index, size-1);
}
//最后一个元素请空
array[--size]=null;
}
/**
* 清空线性表
*/
public void clear() {
//将数组全部填充为null
arrays.fill(array, null);
//将元素个数改为0
size=0;
}
/**
* 获得索引处的元素
* @param index
* @return 索引处的元素
*/
@suppresswarnings("unchecked")
public e get(int index) {
checkindex(index);
return (e)array[index];
}
/**
* 验证是否为索引越界
* @param index
*/
private void checkindex(int index){
if(index>=size || index<0){
throw new indexoutofboundsexception("索引越界");
}
}
/**
* 将索引处的元素修改为新的元素
* @param index 索引位置
* @param element 元素
* @return 原索引处的元素
*/
@suppresswarnings("unchecked")
public e set(int index, e element) {
checkindex(index);
e e = (e)array[index];
array[index]=element;
return e;
}
/**
* 在指定的索引处插入指定的元素
* @param index 索引位置
* @param element 元素
*/
public void add(int index, e element) {
//验证索引
checkindex(index);
//是否需要扩容
extendcapacity(size+1);
//复制数组
system.arraycopy(array, index, array, index+1, size-index);
array[index]=element;
}
/**
* 移除索引处的元素
* @param index 索引
* @return 删除了的元素
*/
@suppresswarnings("unchecked")
public e remove(int index) {
checkindex(index);
//取得索引位置的元素
e e = (e)array[index];
fastremove(index);
return e;
}
/**
* 取得元素第一次出现的位置的索引
* @param e 要查找的元素
* @return 如果为-1说明线性表没有这个元素
*/
public int indexof(e e) {
if(e==null){
for(int i=0;i<size;i++){
if(e==array[i]){
return i;
}
}
}
for(int i=0;i<size;i++){
if(e.equals(array[i])){
return i;
}
}
return -1;
}
/**
* 取得元素最后一次出现的位置的索引
* @param e 要查找的元素
* @return 如果为-1说明线性表没有这个元素
*/
public int lastindexof(e e) {
//判断元素是否为null
if(e==null){
for(int i=size-1;i>=0;i--){
if(e==array[i]){
return i;
}
}
}
for(int i=size-1;i>=0;i--){
//如果为null这里会跑出nullpoint异常
//所以前面要加上验证是否为null
if(e.equals(array[i])){
return i;
}
}
return -1;
}
/**
* 截取线性表
* @param fromindex 开始索引
* @param toindex 结束索引
* @return 截取的线性表
*/
@suppresswarnings("unchecked")
public linelist<e> sublist(int fromindex, int toindex) {
//判断开始索引是否越界
if(fromindex<0 || fromindex >=size){
throw new indexoutofboundsexception("开始索引越界:"+fromindex);
}
//判断结束索引是否越界
if(toindex >=size || fromindex <0){
throw new indexoutofboundsexception("结束索引越界:"+toindex);
}
//判断开始索引和结束索引是否正确
if(fromindex > toindex){
throw new illegalargumentexception("参数不正确,开始索引应大于等于结束索引");
}
linelist<e> list = new linelist<e>();
for(int i=fromindex,j=toindex;i<=j;i++){
list.add((e)array[i]);
}
return list;
}
}
上一篇: MySQL的安装以及基本的管理命令和设置
下一篇: JSP迅速入门