weixin_40725706

这个屌丝很懒，什么也没留下！

热门标签

java数据结构，线性表顺序存储（数组）的实现_java实现线性表

作者：weixin_40725706 | 2024-05-05 09:26:07

踩

java实现线性表

java数据结构，线性表顺序存储（数组）的实现

线性表是什么？
线性表的基本操作
线性表基本操作的实现
完整代码
- MyList接口的全部代码
- MyLinearList的全部代码

线性表是什么？

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

线性表的基本操作

1）MakeEmpty(L) 这是一个将L变为空表的方法
2）Length（L）返回表L的长度，即表中元素个数
3）Get（L，i）这是一个函数，函数值为L中位置i处的元素（1≤i≤n）
4）Prior（L，i）取i的前驱元素
5）Next（L，i）取i的后继元素
6）Locate（L，x）这是一个函数，函数值为元素x在L中的位置
7）Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
8）Delete（L，p）从表L中删除位置p处的元素
9）IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false
10）Clear（L）清除所有元素
11）Init（L）同第一个，初始化线性表为空
12）Traverse（L）遍历输出所有元素
13）Find（L，x）查找并返回元素
14）Update（L，x）修改元素
15）Sort（L）对所有元素重新按给定的条件排序
16) strstr(string1,string2)用于字符数组的求string1中出现string2的首地址

这里只实现上述的核心部分功能

线性表基本操作的实现

首先，在java中秉持着面向对象的原则，定义初始的成员变量

public class MyLinearList{
	// 用数组来实现线性表
    // 定义成员变量
    private Object[] elementList;
    private int size=0;//线性表初始长度为0
    private int capacity=10;//默认线性表容量为10
    
    //定义构造方法，初始化线性表容量
    //根据用户指定容量来生成指定长度的线性表
    public MyLinearList(int capacity) {
        this.capacity = capacity;
        elementList =new Object[capacity];
    }
    
    //默认的线性表长度为10
    public MyLinearList() {
        elementList = new Object[capacity];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

然后在接口中定义我们对线性表的基本操作

package day01线性表;

public interface MyList {
    /**
     * 添加元素
     * @param element
     */
    void add(Object element);

    /**
     * 在指定位置插入元素
     * @param target
     * @param element
     */
    void add(int target,Object element);

    /**
     * 根据元素的值来删除
     * @param element
     */
    void delete(Object element);

    /**
     * 根据索引来删除元素
     * @param index
     */
    void delete(int index);

    /**
     * 根据指定的target索引位置来更新元素
     * @param traget
     * @param element
     */
    void update(int traget,Object element);

    /**
     * 返回某一元素第一次在线性表中出现的位置
     * @param element
     * @return
     */
    int indexOf(Object element);

    /**
     * 返回在指定target位置的元素
     * @param target
     * @return
     */
    Object elementAt(int target);

    /**
     * 取指定索引位置元素的前驱元素
     * @param index
     * @return
     */
    Object elementPrior(int index);

    /**
     * 取指定索引位置元素的后继元素
     * @param index
     * @return
     */
    Object elementNext(int index);
}

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

接着用类去实现这一接口，重写其中的全部方法，因为有一些操作，使用静态方法更便捷，所以接口中只是部分的基础操作，线性表的增删改查。

线性表的增加元素–实现代码

	@Override
    public void add(Object element) {
        //如果当前元素长度大于线性表的容量则选择扩容
        if(size>=capacity){
            capacity+=1;
            Object[] newArr = new Object[capacity];
            //将之前的元素复制到新的线性表newArr中
            for (int i = 0; i < size; i++) {
                newArr[i] = elementList[i];
            }
            //用新的扩容以后的newArr来当作新的线性表的地址
            elementList = newArr;
        }
        elementList[size++] = element;
    }

    @Override
    public void add(int target, Object element) {
        //指定位置插入元素，则需要考虑右移元素
        if(size>=capacity){
            capacity+=1;
            Object[] newArr = new Object[capacity];
            //将之前的元素复制到新的线性表newArr中
            for (int i = 0; i < size; i++) {
                newArr[i] = elementList[i];
            }
            //用新的扩容以后的newArr来当作新的线性表的地址
            elementList = newArr;
            //将元素右移
            for (int i = capacity-1; i >target; i--) {
                elementList[i] = elementList[i-1];
            }
            elementList[target] = element;
            size+=1;
        }else{
            for (int i = capacity-1; i >target; i--) {
                elementList[i] = elementList[i-1];
            }
            elementList[target] = element;
            size+=1;
        }
    }
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

线性表的查找元素–实现代码

	@Override
    public int indexOf(Object element) {
        //如果可以在线性表中找到对应的元素的值，则返回索引，否则返回-1表示要找的元素不存在
        for (int i = 0; i < size; i++) {
            if(elementList[i].equals(element)){
                return i;
            }
        }
        return -1;
    }

    @Override
    public Object elementAt(int target) {
        if (target>capacity-1){
            System.out.println("访问的索引已经越界!");
            return null;
        }
        return elementList[target];
    }

    @Override
    public Object elementPrior(int index) {
        if(index>size-1||index-1<0){
            return -1;
        }
        return elementList[index-1];
    }

    @Override
    public Object elementNext(int index) {
        if(index+1>size-1){
            return -1;
        }
        return elementList[index+1];
    }
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

线性表的删除元素–实现代码

	@Override
    public void delete(Object element) {
        int index = indexOf(element);
        if(index>=0){
            delete(index);
        }
    }

    @Override
    public void delete(int index) {
        //线性表删除涉及到删除某一元素，需要将其后面的元素进行左移操作
        elementList[index]=null;
        for (int i = index; i <= size-index; i++) {
            elementList[i] = elementList[i+1];
        }
        size-=1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

线性表的修改元素–实现代码

	 @Override
    public void update(int traget, Object element) {
        elementList[traget] =element;
    }
1
2
3
4

线性表的其他操作-遍历清空，求线性表长度-实现代码

	//清空线性表内容
    public static void clearList(MyLinearList myLinearList) {
        myLinearList.size =0;
    }

    //线性表是否为空
    public static boolean isEmpty(MyLinearList myLinearList) {
        if(myLinearList.size==0){
            return true;
        }
        return false;
    }

    //输出当前线性表容量
    public static void listLength(MyLinearList myLinearList) {
        System.out.println("当前线性表容量为:"+ myLinearList.capacity);
    }
    //输出当前线性表长度
    public static void listSize(MyLinearList myLinearList) {
        System.out.println("当前线性表中不为空的元素个数为:"+ myLinearList.size);
    }

    //重写toString方法
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(elementList[i]+(i==size-1?"":","));
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    //线性表遍历输出
    public static void listPrint(MyLinearList myLinearList){
        System.out.println(myLinearList.toString());
    }
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

main函数测试代码

public static void main(String[] args) {
        //测试，首先生成一个长度为10 的线性表,并且使用add方法顺序插入10个元素
        MyLinearList list = new MyLinearList();
        list.add("one");
        list.add("two");
        list.add("three");
        list.add(".");
        list.add("A");
        list.add("B");
        list.add("D");
        list.add("E");
        list.add("F");
        list.add("G");
        listPrint(list);
        //现在继续增加一个元素到list，看是否会扩容
        list.add(11);
        listPrint(list);
        listLength(list);//长度扩容为20
        System.out.println(list.indexOf("three"));
        list.delete("three");
        listPrint(list);
        list.add("ok");
        listPrint(list);
        list.update(2,"!");
        listPrint(list);
        list.add(2,"?");
        listPrint(list);
        listSize(list);
        System.out.println("index为2的前驱元素为:"+list.elementPrior(2));
        System.out.println("index为5的后继元素为:"+list.elementNext(5));
        clearList(list);
        listPrint(list);
        System.out.println(list.isEmpty(list));
    }
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

完整代码

创建一个包，然后包里面分别创建接口和实现类，
在这里插入图片描述

MyList接口的全部代码

package day01线性表;

public interface MyList {
    /**
     * 添加元素
     * @param element
     */
    void add(Object element);

    /**
     * 在指定位置插入元素
     * @param target
     * @param element
     */
    void add(int target,Object element);

    /**
     * 根据元素的值来删除
     * @param element
     */
    void delete(Object element);

    /**
     * 根据索引来删除元素
     * @param index
     */
    void delete(int index);

    /**
     * 根据指定的target索引位置来更新元素
     * @param traget
     * @param element
     */
    void update(int traget,Object element);

    /**
     * 返回某一元素第一次在线性表中出现的位置
     * @param element
     * @return
     */
    int indexOf(Object element);

    /**
     * 返回在指定target位置的元素
     * @param target
     * @return
     */
    Object elementAt(int target);

    /**
     * 取指定索引位置元素的前驱元素
     * @param index
     * @return
     */
    Object elementPrior(int index);

    /**
     * 取指定索引位置元素的后继元素
     * @param index
     * @return
     */
    Object elementNext(int index);
}

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

MyLinearList的全部代码

package day01线性表;

public class MyLinearList implements MyList{

    // 用数组来实现线性表
    // 定义成员变量
    private Object[] elementList;
    private int size=0;//线性表初始长度为0
    private int capacity=10;//默认线性表容量为10

    //定义构造方法，初始化线性表容量
    //根据用户指定容量来生成指定长度的线性表
    public MyLinearList(int capacity) {
        this.capacity = capacity;
        elementList =new Object[capacity];
    }
    
    //默认的线性表长度为10
    public MyLinearList() {
        elementList = new Object[capacity];
    }

    @Override
    public void add(Object element) {
        //如果当前元素长度大于线性表的容量则选择扩容
        if(size>=capacity){
            capacity+=1;
            Object[] newArr = new Object[capacity];
            //将之前的元素复制到新的线性表newArr中
            for (int i = 0; i < size; i++) {
                newArr[i] = elementList[i];
            }
            //用新的扩容以后的newArr来当作新的线性表的地址
            elementList = newArr;
        }
        elementList[size++] = element;
    }

    @Override
    public void add(int target, Object element) {
        //指定位置插入元素，则需要考虑右移元素
        if(size>=capacity){
            capacity+=1;
            Object[] newArr = new Object[capacity];
            //将之前的元素复制到新的线性表newArr中
            for (int i = 0; i < size; i++) {
                newArr[i] = elementList[i];
            }
            //用新的扩容以后的newArr来当作新的线性表的地址
            elementList = newArr;
            //将元素右移
            for (int i = capacity-1; i >target; i--) {
                elementList[i] = elementList[i-1];
            }
            elementList[target] = element;
            size+=1;
        }else{
            for (int i = capacity-1; i >target; i--) {
                elementList[i] = elementList[i-1];
            }
            elementList[target] = element;
            size+=1;
        }
    }

    @Override
    public void delete(Object element) {
        int index = indexOf(element);
        if(index>=0){
            delete(index);
        }
    }

    @Override
    public void delete(int index) {
        //线性表删除涉及到删除某一元素，需要将其后面的元素进行左移操作
        elementList[index]=null;
        for (int i = index; i <= size-index; i++) {
            elementList[i] = elementList[i+1];
        }
        size-=1;
    }

    @Override
    public void update(int traget, Object element) {
        elementList[traget] =element;
    }

    @Override
    public int indexOf(Object element) {
        //如果可以在线性表中找到对应的元素的值，则返回索引，否则返回-1表示要找的元素不存在
        for (int i = 0; i < size; i++) {
            if(elementList[i].equals(element)){
                return i;
            }
        }
        return -1;
    }

    @Override
    public Object elementAt(int target) {
        if (target>capacity-1){
            System.out.println("访问的索引已经越界!");
            return null;
        }
        return elementList[target];
    }

    @Override
    public Object elementPrior(int index) {
        if(index>size-1||index-1<0){
            return -1;
        }
        return elementList[index-1];
    }

    @Override
    public Object elementNext(int index) {
        if(index+1>size-1){
            return -1;
        }
        return elementList[index+1];
    }

    //清空线性表内容
    public static void clearList(MyLinearList myLinearList) {
        myLinearList.size =0;
    }

    //线性表是否为空
    public static boolean isEmpty(MyLinearList myLinearList) {
        if(myLinearList.size==0){
            return true;
        }
        return false;
    }

    //输出当前线性表容量
    public static void listLength(MyLinearList myLinearList) {
        System.out.println("当前线性表容量为:"+ myLinearList.capacity);
    }
    //输出当前线性表长度
    public static void listSize(MyLinearList myLinearList) {
        System.out.println("当前线性表中不为空的元素个数为:"+ myLinearList.size);
    }

    //重写toString方法
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(elementList[i]+(i==size-1?"":","));
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    //线性表遍历输出
    public static void listPrint(MyLinearList myLinearList){
        System.out.println(myLinearList.toString());
    }

    public static void main(String[] args) {
        //测试，首先生成一个长度为10 的线性表,并且使用add方法顺序插入10个元素
        MyLinearList list = new MyLinearList();
        list.add("one");
        list.add("two");
        list.add("three");
        list.add(".");
        list.add("A");
        list.add("B");
        list.add("D");
        list.add("E");
        list.add("F");
        list.add("G");
        listPrint(list);
        //现在继续增加一个元素到list，看是否会扩容
        list.add(11);
        listPrint(list);
        listLength(list);//长度扩容为20
        System.out.println(list.indexOf("three"));
        list.delete("three");
        listPrint(list);
        list.add("ok");
        listPrint(list);
        list.update(2,"!");
        listPrint(list);
        list.add(2,"?");
        listPrint(list);
        listSize(list);
        System.out.println("index为2的前驱元素为:"+list.elementPrior(2));
        System.out.println("index为5的后继元素为:"+list.elementNext(5));
        clearList(list);
        listPrint(list);
        System.out.println(list.isEmpty(list));
    }
}

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199

以上，就是线性表顺序存储的实现，小白萌新学习记录，各位大佬点个赞！数据结构陆续更新中！！！
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/538283