顺序表
定义：
用一段物理地址连续的存储单元依次存储数据元素的线性结构（逻辑上连续，物理上也连续）
（1）静态顺序表：使用定长数组存储。
（2）动态顺序表：使用动态开辟的数组存储
【注意】静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，所以相比之下，动态数组更为灵活，可根据需要动态分配空间大小
实现方法：
增、删、改、查
增加操作：从头部插入、从尾部插入、在任意索引位置处插入
删除操作：根据索引删除元素、根据元素值删除第一个出现的该元素、根据元素值删除所有该值元素
查找操作：根据元素值查找是否存在某元素、根据索引下标返回该处元素值、根据元素值返回索引下标
修改操作：根据索引下标修改该处元素
代码实现：
public class MyArray {
private int[]data;
private int size;
// 无参构造
public MyArray（）{
this.data=new int[5];
}
// 有参构造
public MyArray（int n）{
this.data=new int[n];
}
// grow方法用于扩充内存
private void grow（） {
int[] newdata= Arrays.copyOf（data,size*2）;
this.data=newdata;
}
// toString方法输出顺序表内容
public String toString（）{
String str="[";
for （int i = 0; i <size ; i++） {
str+=data[i];
if（i!=size-1）{
str+=",";
}
}
str+="]";
return str;
}
// 尾插法：
public void addLast（int value）{
if（size== data.length）{
grow（）;
}
data[size]=value;
size++;
}
// 头插法：
public void addFirst（int value）{
if（size==data.length）{
grow（）;
}
for （int i = size-1; i >=0; i--） {
data[i+1]=data[i];
}
data[0]=value;
size++;
}
// 中间任意位置插入：
public void addIndex（int index,int value）{
if（size==data.length）
grow（）;
if（index<0||index>size）{
System.err.println（"插入位置不合理！"）;
return;
}
else {
for （int i = size - 1; i >= index; i--） {
data[i + 1] = data[i];
}
data[index] = value;
size++;
}
}
// 查看当前数组中是否存在该元素
public boolean contains（int value）{
for （int i = 0; i < size; i++） {
if（data[i]==value）
return true;
}
return false;
}
// 查找当前数组元素对应的下标
public int getIndex（int value）{
for （int i = 0; i < size; i++） {
if（data[i]==value）{
return i;
}
}
return -1;
}
// 查找数组下标为index的元素
public int getValue（int index） {
if （index < 0 || index > size - 1） {
System.out.println（"输入下标不合理"）;
return -1;
}
return data[index];
}
// 根据索引删除元素，注意将最后一个元素置为0
public void removeIndex（int index）{
if（index<0||index>=size）{
System.err.println（"输入不合法！"）;
}
for （int i = index; i <size-1; i++） {
data[i]=data[i+1];
}
size--;
data[size]=0;
}
// 删除第一个元素值为value的元素
public void removeValueOnce（int value）{
int a=getIndex（value）;
removeIndex（a）;
}
// 删除所有元素值为value的元素
public void removeValueAll（int value）{
for （int i = 0; i < size; i++） {
while（i!=size||data[i]==value）
removeIndex（i）;
}
}
// 根据索引修改元素
public void recompose（int index,int newValue）{
if（index<0||index>=size）{
System.err.println（"输入不合法！"）;
}
data[index]=newValue;
}
}
|
