- 1线性表的增加
- 1.1 线性表的尾部插入指定元素value
- 1.2 线性表的头部插入指定元素value
- 1.3 线性表中间位置插入指定元素value
- 2.线性表的查找
- 2.1查看当前数组是否存在值为value的元素，存在返回true,否则返回false
- 2.2 根据数组索引查找对应元素
- 2.3 查找当前数组中值为value的元素下标
- 3.线性表修改
- 4 线性表的删除
- 4.1 根据数组索引删除元素
- 4.1.1删除index指定位置元素
- 4.1.1删除头部元素
- 4.1.3删除尾部元素
- 4.2 根据元素值删除线性表
- 4.2.1 删除数组中第一个值为value的元素
- 4.2.2 删除数组中所有值为value的元素
- 5.完整代码
- 6.顺序表增删改查测试
线性表增删改查代码在Package里面写，在Package下建两个文件，MyArray用于写顺序表的增删改查代码，Test用于测试
1线性表的增加
线性表增加的时候，一定要先判断数组是否已满，如果数组已满，要先扩容
1.1 线性表的尾部插入指定元素valuepublic void addLast(int value){
// 先判断当前数组是否已满
if (size==data.length){
// 如果满了 则需要扩容。利用 grow进行扩容
grow();
}
data[size]=value;
// 插入新元素 数组长度++
size++;
}
1.2 线性表的头部插入指定元素value
在数组头部插入元素时，我们首先要将头部首元素先空出来，这时候，一定要从数组尾部依次挪动。
// 数组头部插入value
public void addFirst(int value){
// 先判断当前数组是否已满
if (size==data.length){
// 如果满了 则需要扩容。利用 grow进行扩容
grow();
}
for (int i = size-1; i >=0; i--) {
data[i+1]=data[i];
}
data[0]=value;
size++;
}
1.3 线性表中间位置插入指定元素value
在中间指定位置插入元素时，一定要先判断插入的位置是否合法，此时插入的位置index不能与data.length比较，因为data.length是数组长度，但数组不一定放满，应与数组实际长度size比较
// 在index位置插入value值
public void addindex(int index,int value){
if (size==data.length){
// 如果满了 则需要扩容。利用 grow进行扩容
grow();
}
if (index<0||index>size){
System.out.println("error!");
}
if (index==0){
addFirst(value);
// 此处一定要记得return
return;
}
if (index==size){
addLast(value);
}
else {
for (int i = size-1; i >=index; i--) {
data[i+1]=data[i];
}
data[index]=value;
size++;
}
}
2.线性表的查找
2.1查看当前数组是否存在值为value的元素，存在返回true,否则返回false
//查看线性表中是否存在value值
public boolean contains(int value){
for (int i = 0; i < size; i++) {
if ( data[i]==value){
return true;
}
}
return false;
}
2.2 根据数组索引查找对应元素
一定要先判断索引的合法性，因为用户的输入具有不确定性
// 根据数组索引查找对应元素
public int get(int index){
if (index<0||index>=size){
System.out.println("error");
}
return data[index];
}
2.3 查找当前数组中值为value的元素下标
// 获取值为value的下标
public int getByvalue(int value){
for (int i = 0; i < size; i++) {
if (data[i]==value){
return i;
}
}
return -1;
}
3.线性表修改
根据索引修改对应位置的元素，并返回该索引对应的原始元素
// 修改数组index位置的元素为newvalue,返回值为修改前的元素值
public int set(int index,int newvalue){
if (index<0||index>=size){
System.out.println("error");
return -1;
}
int oldervalue=data[index];
data[index]=newvalue;
return oldervalue;
}
4 线性表的删除
4.1 根据数组索引删除元素
4.1.1删除index指定位置元素
加粗样式
//删除指定索引index位置的元素
public void removeindex(int index){
if (index<0||index>=size){
System.out.println("error");
return;
}
if (index==0){
removeFirst();
return;
}
if (index==size-1){
removeLast();
}
else{
for (int i = index; i <= size-1; i++) {
data[i]=data[i+1];
}
// 指定索引index元素的删除，实际上是将index后面的元素依次向前复制，
// 这时候最后一个元素data[size-1]会出现两次，因此我们需要将最后一个元素赋0
data[size-1]=0;
size--;
}
}
4.1.1删除头部元素
删除头部元素有两种方式，第一种依次向前覆盖
// 删头元素
public void removeFirst(){
for (int i = 0; i < size; i++) {
data[i]=data[i+1];
}
data[size-1]=0;
size--;
}
第二种调用删除指定索引的方法removeindex
public void removeFirst() {
removeIndex(0);
}
4.1.3删除尾部元素
同样是两种方法，第一种直接删除
// 删除尾元素
public void removeLast(){
data[size-1]=0;
size--;
}
调用删除指定索引的方法
public void removeLast() {
removeIndex(size - 1);
}
4.2 根据元素值删除线性表
4.2.1 删除数组中第一个值为value的元素
先找到这个该元素，即获得了指定索引，再按照删除指定索引的方法删除
// 删除数组中第一个值为value的元素
public void removevalueOnce(int value){
// 先找value值
for (int i = 0; i < size; i++) {
if (data[i]==value){
removeindex(i);
return;
}
}
System.out.println(value+"不在");
}
4.2.2 删除数组中所有值为value的元素
// 删除数组中所有值为value的元素
public void removevalueall(int value){
for (int i = 0; i < size; i++) {
// 存在连续的值为value的元素，所以使用while循环，
// 若数组为 2 2 3 2 4时，当data[0]删除之后，新数组为2 3 2 4
// data[0]又为0，所以要使用while循环
while (i!=size&&data[i]==value){
removeindex(i);
}
}
}
5.完整代码
package seqllist;
import java.util.Arrays;
// 基于数组的顺序表
// MyArray类，包装数组，Test使用MyArray类，不需要知道MyArray类里面的方法如何实现，只需要知道怎样使用就行
public class MyArray {
//
private int[] data;
//当前动态数组实际存放的元素个数,默认值为0
private int size;
// 无参构造方法，初始化数组
public MyArray(){
data=new int[10];
}
// 有参构造方法 capacity传入的数组大小
public MyArray(int capacity){
data =new int[capacity];
}
//数组尾部插入，value待插入的元素值
public void addLast(int value){
// 先判断当前数组是否已满
if (size==data.length){
// 如果满了 则需要扩容。利用 grow进行扩容
grow();
}
data[size]=value;
// 插入新元素 数组长度++
size++;
}
// 数组头部插入value
public void addFirst(int value){
// 先判断当前数组是否已满
if (size==data.length){
// 如果满了 则需要扩容。利用 grow进行扩容
grow();
}
for (int i = size-1; i >=0; i--) {
data[i+1]=data[i];
}
data[0]=value;
size++;
}
// 在index位置插入value值
public void addindex(int index,int value){
if (size==data.length){
// 如果满了 则需要扩容。利用 grow进行扩容
grow();
}
if (index<0||index>size){
System.out.println("error!");
}
if (index==0){
addFirst(value);
return;
}
if (index==size){
addLast(value);
}
else {
for (int i = size-1; i >=index; i--) {
data[i+1]=data[i];
}
data[index]=value;
size++;
}
}
//查看线性表中是否存在value值
public boolean contains(int value){
for (int i = 0; i < size; i++) {
if ( data[i]==value){
return true;
}
}
return false;
}
// 根据数组索引查找对应元素
public int get(int index){
if (index<0||index>=size){
System.out.println("error");
}
return data[index];
}
// 获取值为value的下标
public int getByvalue(int value){
for (int i = 0; i < size; i++) {
if (data[i]==value){
return i;
}
}
return -1;
}
// 修改数组index位置的元素为newvalue,返回值为修改前的元素值data[index]
public int set(int index,int newvalue){
if (index<0||index>=size){
System.out.println("error");
return -1;
}
int oldervalue=data[index];
data[index]=newvalue;
return oldervalue;
}
//删除指定索引index位置的元素
public void removeindex(int index){
if (index<0||index>=size){
System.out.println("error");
return;
}
if (index==0){
removeFirst();
return;
}
if (index==size-1){
removeLast();
}
else{
for (int i = index; i <= size-1; i++) {
data[i]=data[i+1];
}
// 指定索引index元素的删除，实际上是将index后面的元素依次向前复制，
// 这时候最后一个元素data[size-1]会出现两次，因此我们需要将最后一个元素赋0
data[size-1]=0;
size--;
}
}
// 删头元素
public void removeFirst(){
for (int i = 0; i < size; i++) {
data[i]=data[i+1];
}
data[size-1]=0;
size--;
}
// 删除尾元素
public void removeLast(){
data[size-1]=0;
size--;
}
// 删除数组中第一个值为value的元素
public void removevalueOnce(int value){
for (int i = 0; i < size; i++) {
if (data[i]==value){
removeindex(i);
return;
}
}
System.out.println(value+"不在");
}
// 删除数组中所有值为value的元素
public void removevalueall(int value){
for (int i = 0; i < size; i++) {
// 存在连续的值为value的元素
while (i!=size&&data[i]==value){
removeindex(i);
}
}
}
// 写一个toString方法打印数组内容
public String toString(){
String ret="[";
for (int i = 0; i < size; i++) {
ret+=data[i];
if (i!=size-1){
ret+=", ";
}
}
ret+="]";
return ret;
}
private void grow() {
// 扩容为原来数组长度的1倍
int[] newData = Arrays.copyOf(data,data.length<<1);
this.data=newData;
}
}
6.顺序表增删改查测试
package seqllist;
public class Test {
public static void main(String[] args) {
MyArray myArray=new MyArray(3);
myArray.addLast(1);
myArray.addLast(3);
myArray.addLast(5);
myArray.addLast(7);
//1 3 5 7
System.out.println(myArray);
myArray.addFirst(0);
// 0 1 3 5 7
System.out.println(myArray);
// 0 1 2 3 5 7
myArray.addindex(2,2);
System.out.println(myArray);
myArray.addindex(0,-1);
//-1 0 1 2 3 5 7
System.out.println(myArray);
myArray.addindex(7,8);
//-1 0 1 2 3 5 7 8
System.out.println(myArray);
//true
System.out.println( myArray.contains(7));
//false
System.out.println(myArray.contains(10));
//3
System.out.println(myArray.get(4));
// 3
System.out.println(myArray.getByvalue(2));
System.out.println(myArray);
//[-1, 0, 11, 2, 3, 5, 7, 8]
myArray.set(2,11);
//[-1, 0, 11, 2, 3, 5, 7, 8]
System.out.println(myArray);
myArray.removeindex(2);
//[-1, 0, 2, 3, 5, 7, 8]
System.out.println(myArray);
myArray.removeFirst();
//[0, 2, 3, 5, 7, 8]
System.out.println(myArray);
myArray.removeLast();
//[0, 2, 3, 5, 7]
System.out.println(myArray);
myArray.addLast(3);
myArray.addFirst(3);
//[3,0, 2, 3, 5, 7,3]
System.out.println(myArray);
myArray.removevalueOnce(3);
//[0, 2, 3, 5, 7,3]
System.out.println(myArray);
myArray.removevalueall(3);
//[0, 2, 5, 7]
System.out.println(myArray);
myArray.removeFirst();
System.out.println(myArray);
// myArray.removeindex(1);
// System.out.println(myArray);
}
}
