实现一个顺序表
接口实现
定义一个MyArrayList类，在类中实现以下函数
|
1 2 3 |
public class MyArrayList {
} |
数组的定义
|
1 2 3 4 5 |
public int [] elem; //定义一个整形数组 public int usize; //usize表示数组的长度 public MyArrayList(){ this .elem = new int [ 5 ]; } |
打印顺序表
for循环打印顺序表的每一位
|
1 2 3 4 5 6 |
public void display(){ for ( int i = 0 ; i < this .usize; i++) { System.out.print( this .elem[i]+ " " ); } System.out.println(); } |
在pos位置新增元素
先定义一个isFull函数判断顺序表是否满了，满了返回true，没满则返回false
|
1 2 3 4 5 6 |
public boolean isFull(){ if ( this .usize == this .elem.length){ return true ; } return false ; } |
将pos位置后的元素后移，顺序表顺序表长度增加一位
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public void add( int pos, int data){ //判断顺序表是否满了 if (isFull()){ System.out.println( "顺序表已满" ); //扩容 this .elem = Arrays.copyOf( this .elem, 2 * this .usize); } //判断pos的合法性 if (pos < 0 || pos > this .usize){ System.out.println( "pos位置不合法" ); return ; } //将pos位置后的数字后移 for ( int i = this .usize- 1 ; i >= pos; i--) { this .elem[i+ 1 ] = this .elem[i]; } this .elem[pos] = data; this .usize++; } |
判定是否包含某个元素
|
1 2 3 4 5 6 7 8 |
public boolean contains( int key){ for ( int i = 0 ; i < this .usize; i++) { if ( this .elem[i] == key){ return true ; } } return false ; } |
查找某个对应元素的位置
返回它的位置
|
1 2 3 4 5 6 7 8 |
public int search( int key){ for ( int i = 0 ; i < this .usize; i++) { if ( this .elem[i] == key){ return i; } } return - 1 ; } |
获取pos位置的元素
定义一个isEmpty函数判断顺序表是否为空
|
1 2 3 |
public boolean isEmpty(){ return this .usize == 0 ; } |
|
1 2 3 4 5 6 7 8 9 10 11 |
public int getPos( int pos){ //判断顺序表是否为空 if (isEmpty()){ return - 1 ; } //判断pos 位置是否合法 if (pos < 0 || pos >= this .usize){ return - 1 ; } return this .elem[pos]; } |
给pos位置的元素设为value 更新为新的数字
|
1 2 3 4 5 6 7 8 9 10 11 |
public void setPos( int pos, int value){ //判断顺序表是否为空 if (isEmpty()){ return ; } //判断pos位置是否合法 if (pos < 0 || pos >= this .usize){ return ; } this .elem[pos] = value; } |
删除第一次出现的关键字key
查找到关键字，从关键字所在的位置开始到顺序表结束每一项前移，覆盖掉关键字，长度减少一位
|
1 2 3 4 5 6 7 8 9 10 11 |
public void remove( int key){ int index= search(key); if (key == - 1 ){ System.out.println( "关键字不存在" ); return ; } for ( int i = key; i < this .usize- 1 ; i++) { this .elem[i] = this .elem[i+ 1 ]; } this .usize--; } |
获取顺序表长度
|
1 2 3 |
public int size(){ return this .usize; } |
清空顺序表
顺序表长度直接为0
|
1 2 3 |
public void clear(){ this .usize = 0 ; } |
实现这个顺序表
定义一个测试类，测试这些函数的输出
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public class TestDemo { public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(); //给这个顺序表写入1,2，3,4，5 myArrayList.add( 0 , 1 ); myArrayList.add( 1 , 2 ); myArrayList.add( 2 , 3 ); myArrayList.add( 3 , 4 ); myArrayList.add( 4 , 5 ); //打印这个顺序表 myArrayList.display(); //判定5这个元素是否在该顺序表中 System.out.println(myArrayList.contains( 5 )); //查找5这个元素 返回它的位置 System.out.println(myArrayList.search( 5 )); //获取3位置的元素 System.out.println(myArrayList.getPos( 3 )); //将4位置的元素重新赋值为9 myArrayList.setPos( 4 , 9 ); //打印新的顺序表 myArrayList.display(); //删除第一次出现的元素4 myArrayList.remove( 4 ); //打印新的顺序表 myArrayList.display(); //获取顺序表的长度 System.out.println(myArrayList.size()); System.out.println( "清空" ); //清空顺序表 myArrayList.clear(); //打印新的顺序表 myArrayList.display(); } } |
得到结果：
顺序表的优缺点
优点：顺序表查找方便，知道这个元素的位置就可以直接找到这个元素。
缺点：扩容一般成2倍增长，会有一定的空间浪费。
原文链接：https://blog.csdn.net/weixin_46494806/article/details/115678332
查看更多关于Java实现一个顺序表的完整代码的详细内容...