线性表顺序存储结构--(Java)

---

线性表概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组基础上完成数据的增删查改。

线性表接口实现

public interface SequenceTable {
	//打印顺序表
    public void display();

    //添加元素
    public void add(int index , int date );

    //判断是否含有
    public boolean contains(int data);

    //查找元素下标
    public int getIndex(int data);

    //获取元素
    public Integer get(int index);

    //更新元素
    public void update(int index , int data);

    //删除元素
    public void remove(int index);

    // 获取顺序表长度
    public int length();

    // 清空顺序表
    public void clear();
}    
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

线性表具体实现

	public class SeqList implements SequenceTable {
	
	    private int SEQUENCE_TABLE_BASIC_CAPACITY=4;   		  //顺序表基础容量
	    private double SEQUENCE_TABLE_EXPANSION_FACTOR=0.75;  //顺序表扩容因子
	    private double SEQUENCE_TABLE_EXPANSION_MULTIPLE=1.5; //顺序表扩容倍数
	    private int[] seqTable;								  //顺序表存储元素数组
	    private int count;									  //顺序表实际长度
    
    	public SeqList(){									  //初始化线性表
        	this.seqTable=new int[SEQUENCE_TABLE_BASIC_CAPACITY];
    	}

	   /**
		*	线性表具体忌口方法实现
		*/
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

初始化线性表，

打印顺序表

	@Override
    public void display() {
        if (count==0){
            System.out.println("当前顺序表为空");
            return;
        }
        System.out.print("当前顺序表内容为： " );
        for (int index=0 ; index<count ; index++){
            System.out.print(seqTable[index]+"\t");
        }
        System.out.println();
    }
1
2
3
4
5
6
7
8
9
10
11
12

当前顺序表不为空时，打印顺序表内容

添加元素

	@Override
    public void add(int index , int data ) {
        if ( index < 0 || index > count ){      //判断合法性
            System.out.println("输入不合法");
        }
        if (count==(int)(SEQUENCE_TABLE_BASIC_CAPACITY*SEQUENCE_TABLE_EXPANSION_FACTOR)){  //判断顺序表是否满了，满了就扩容
            SEQUENCE_TABLE_BASIC_CAPACITY= (int)(SEQUENCE_TABLE_EXPANSION_MULTIPLE*SEQUENCE_TABLE_BASIC_CAPACITY);
            System.out.println("扩容成功，当前顺序表最大容量为 "+SEQUENCE_TABLE_BASIC_CAPACITY);
            this.seqTable = Arrays.copyOf(this.seqTable,SEQUENCE_TABLE_BASIC_CAPACITY);
        }
        if (count!=0){
            for (int i = SEQUENCE_TABLE_BASIC_CAPACITY-1; i > index ; i-- ){       //先将待插入位置及其后面的数组元素后移一个位置，给信插入的元素让位置
                seqTable[i]=seqTable[i-1];
            }
        }
        seqTable[index]=data;                   //插入新元素
        count++;
        System.out.println("元素"+data+"插入顺序表成功");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第一个if : 判断当前添加元素的位置是否合法

第二个if : 判断添加当前元素时是否达到顺序表数组扩容阈值，如果达到阈值，数组进行扩容后在进行添加元素操作

第三个if : 当顺序表不为空时，将需要插入位置及其后面的数组元素全部后移一位，为新插入的元素让位置

判断是否含有

    @Override
    public boolean contains(int data) {
        for (int index =0 ; index < count ; index++ ){
            if (seqTable[index]==data){
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9

查找元素下标

    @Override
    public int getIndex(int data) {
        for (int index =0 ; index < count ; index++ ){
            if (seqTable[index]==data){
                return index;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9

当查找不到原素时，返回下标-1，

获取元素下标

    @Override
    public int getIndex(int data) {
        for (int index =0 ; index < count ; index++ ){
            if (seqTable[index]==data){
                return index;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9

根据下标获取元素

    @Override
    public Integer  get(int index) {
        if ( index < 0 || index >= count ){
            System.out.print("下标不合法!");
            return null;
        }
        if (count==0){
            System.out.print("当前顺序表为空");
        }
        return seqTable[index];
    }
1
2
3
4
5
6
7
8
9
10
11

根据下标更新元素

    @Override
    public void update(int index , int data) {
        if ( index < 0 || index >= count ){
            System.out.print("下标不合法!");
        }
        if (count==0){
            System.out.println("当前顺序表为空");
        }
        seqTable[index]=data;
    }
1
2
3
4
5
6
7
8
9
10

根据下标删除元素

    @Override
    public void remove(int index) {
        if ( index < 0 || index >= count ){
            System.out.print("下标不合法!");
        }
        if (count==0){
            System.out.println("当前顺序表为空");
        }
        for (int i=index;i<count;i++){
            seqTable[i]=seqTable[i+1];
        }
        count--;
        System.out.println("下标"+index+"处元素删除成功");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

获取顺序表长度

    @Override
    public int length() {
        return count;
    }
1
2
3
4

清理线性表

    @Override
    public void clear() {
        this.count=0;
    }
1
2
3
4

Demo演示

/**
 * @Author chen_jiapin
 * @Date 2022/9/5 10:03
 * @Version 1.0
 */
public class Demo {

    public static void main(String[] args){
        SeqList seqList = new SeqList();
        System.out.println(seqList.get(0));
        seqList.display();
        System.out.println("长度为："+seqList.length());
        seqList.add(0,0);
        seqList.add(1,1);
        seqList.add(2,2);
        seqList.display();
        System.out.println("长度为："+seqList.length());
        seqList.add(3,3);
        seqList.add(4,4);
        seqList.display();
        System.out.println("长度为："+seqList.length());
        seqList.add(2,99);
        seqList.display();
        System.out.println("长度为："+seqList.length());
        System.out.println("99在顺序表中-->"+seqList.contains(99)+",其下标是-->"+seqList.getIndex(99));
        System.out.println("0在顺序表中-->"+seqList.contains(0)+",其下标是-->"+seqList.getIndex(0));
        System.out.println("4在顺序表中-->"+seqList.contains(4)+",其下标是-->"+seqList.getIndex(4));
        System.out.println("5在顺序表中-->"+seqList.contains(5)+",其下标是-->"+seqList.getIndex(5));
        System.out.println("index=4的元素为-->"+seqList.get(4));
        System.out.println("index=0的元素为-->"+seqList.get(0));
        System.out.println("index=8的元素为-->"+seqList.get(8));
        seqList.update(4,44);
        seqList.display();
        System.out.println("长度为："+seqList.length());
        seqList.remove(2);
        seqList.display();
        System.out.println("长度为："+seqList.length());
        seqList.clear();
        seqList.display();
        System.out.println("长度为："+seqList.length());
    }
}

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
35
36
37
38
39
40
41
42
43

结果

下标不合法!null
当前顺序表为空
长度为：0
元素0插入顺序表成功
元素1插入顺序表成功
元素2插入顺序表成功
当前顺序表内容为： 0	1	2	
长度为：3
扩容成功，当前顺序表最大容量为 6
元素3插入顺序表成功
扩容成功，当前顺序表最大容量为 9
元素4插入顺序表成功
当前顺序表内容为： 0	1	2	3	4	
长度为：5
元素99插入顺序表成功
当前顺序表内容为： 0	1	99	2	3	4	
长度为：6
99在顺序表中-->true,其下标是--> 2
0在顺序表中-->true,其下标是--> 0
4在顺序表中-->true,其下标是--> 5
5在顺序表中-->false,其下标是--> -1
index=4的元素为--> 3
index=0的元素为--> 0
下标不合法!index=8的元素为--> null
当前顺序表内容为： 0	1	99	2	44	4	
长度为：6
下标2处元素删除成功
当前顺序表内容为： 0	1	2	44	4	
长度为：5
当前顺序表为空
长度为：0

Process finished with exit code 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