【代码】线性表

发表于 更新于 阅读次数：

前言

线性表的Java实现

源代码

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
- 基本类

package line;
/**
 * 基本类
 */
public class Line {
    // 属性
    private int date[];
    private int length;

    // 方法
    public int[] getDate() {
        return date;
    }
    public void setDate(int[] date) {
        this.date = date;
    }
    public int getLength() {
        return length;
    }
    public void setLength(int length) {
        this.length = 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
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
package line;
/**
 * 顺序表的基本操作类（积木）
 */
public class LineAlgorithm {
    
        // 建立线性表的初始结构，建空表
        public void line_Ininal(Line L) {
            int d[] = new int[100];
            L.setDate(d);
            L.setLength(0);
        }
        
        // 求表的长度
        public int line_Length(Line L) {
            return L.getLength();
        }
        
        // 顺序表表尾放数据
        public void line_In(Line L, int x) {
            L.getDate()[L.getLength()] = x;
            L.setLength(L.getLength()+1);
        }
        
        // 在顺序表的n位置放x值
        public void line_In(Line L, int x, int n) {
            L.getDate()[n] = x;
            L.setLength(L.getLength()+1);
        }
        
        // 顺序表输出
        public void line_Out(Line L) {
            for (int i = 0; i < L.getLength(); i++) {
                System.out.println(L.getDate()[i]);
            }
        }
        
        // 按序号查询元素
        public int line_Get(Line L, int i) {
            return L.getDate()[i];
        }
        
        // 按值查询元素
        public int line_Search(Line L, int x) {
            // 表达座位号
            int t = -1;
            for(int i = 0; i < L.getLength(); i++) {
                if(x == L.getDate()[i]) {
                    t = i;
                }
            }
            return t;
        }
        
        // 移动元素
        public void line_Move(Line L, int n1, int n2) {
            L.getDate()[n2] = L.getDate()[n1];
        }
        
        // 判表空
        public boolean line_Empty(Line L) {
            boolean f = false;
            if(L.getLength() == 0) {
                f = true;
            }
            return f;
        }
        
        // 判表满
        public boolean line_Full(Line L) {
            boolean f = false;
            if(L.getLength() == L.getDate().length) {
                f = true;
            }
            return f;
        }
        
        // 删除数据
        public void line_Delete(Line L, int n) {
            for(int i = n; i < L.getLength()-1; i++) {
                L.getDate()[n] = L.getDate()[n+1];
            }
            L.setLength(L.getLength()-1);
        }
        
        // 表置空
        public void line_Null(Line L) {
            L.setLength(0);
        }
        public void line_Null(Line L, int n) {
            L.setLength(n);
        }
        
        // 冒泡排序（从小到大）
        public void line_Bubble(Line L) {
            boolean f;
            for(int i = 0; i < L.getLength()-1; i++) {
                f = false;
                for(int j = 0; j < L.getLength()-1-i; j++) {
                    if(L.getDate()[j] > L.getDate()[j+1]) {
                        int t = L.getDate()[j];
                        L.getDate()[j] = L.getDate()[j+1];
                        L.getDate()[j+1] = t;
                        f = true;
                    }
                }
                if(!f) {
                    break;
                }
            }
        }
        
        // 选择排序（从大到小）
        public void line_Select(Line L) {
            for(int i = 0; i < L.getLength()-1; i++) {
                int max = i;
                for(int j = i; j < L.getLength(); j++) {
                    if(L.getDate()[j] > L.getDate()[max]) {
                        max = j;
                    }
                }
                if(max != i) {
                    int t = L.getDate()[i];
                    L.getDate()[i] = L.getDate()[max];
                    L.getDate()[max] = t;
                }
            }
        }
        
        
        
}
  • 菜单类
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
package line;

public class LineMenu {
    void display() { 
        System.out.printf("|----------------------------------------------------------------------------|\n");
        System.out.printf("|------------------------------链表操作---------------------------------------|\n");
        System.out.printf("|----------------------------------------------------------------------------|\n");
        System.out.printf("|-----------  1.顺序表中连续放多个数据（建议初始化的第一个操作）      -----------|\n");  
        System.out.printf("|-----------  2.在顺序表中的指定位置插入指定值                      -----------|\n");    
        System.out.printf("|-----------  3.顺序表排序操作                                     -----------|\n");
        System.out.printf("|-----------  4.有序顺序表中的插入操作，插入后仍然有序               -----------|\n");
        System.out.printf("|-----------  5.顺序表中删除指定位置的值                            -----------|\n");
        System.out.printf("|-----------  6.顺序表中删除确定的值                                -----------|\n");
        System.out.printf("|-----------  7.合并两个有序顺序表                                  -----------|\n");
        System.out.printf("|-----------  8.判断子集                                           -----------|\n");
        System.out.printf("|-----------  0.退出                                               -----------|\n");
        System.out.printf("|-----------  9.显示菜单                                           ------------|\n");
        System.out.printf("|-----------------------------------------------------------------------------|\n");
        System.out.printf("|-----------------------------------------------------------------------------|\n");
        System.out.printf("（谢谢使用本软件）\n");
        System.out.printf("请选择菜单中操作所对应的编号（1~12，0退出）：\n");
    }
    void order() {
        System.out.printf("|--------------------------------------------------------------------------|\n");
        System.out.printf("|-----------  A.从小到大冒泡排序                                 -----------|\n");                 
        System.out.printf("|-----------  B.从大到小选择排序                                 -----------|\n");    
        System.out.printf("|--------------------------------------------------------------------------|\n");
        System.out.printf("请选择菜单中操作对应的字符：\n");
    }

}
  • 解决实际问题
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
package line;

import java.util.Scanner;

/**
 * 解决实际问题
 */
public class LineTest {
    public static void main(String[] args) {
        // 菜单选择项
        Scanner scanner = new Scanner(System.in);
        LineMenu M = new LineMenu();
        Line L1 = new Line();
        LineAlgorithm A = new LineAlgorithm();
        A.line_Ininal(L1);
        int N;
        M.display();
        while(true) {
            System.out.println("请输入您要的操作对应的序号：");
            N = scanner.nextInt();
            switch (N) {
            case 1:
                // 在顺序表中连续放多个数据，放0结束
                int x;
                System.out.println("请输入数据：");
                x = scanner.nextInt();
                while(x!=0) {
                    A.line_In(L1, x);
                    System.out.println("请输入数据：");
                    x = scanner.nextInt();
                }
                System.out.println("是否查看已插入数据的列表（1|0）：");
                int num1 = scanner.nextInt();
                if(num1 == 1) {
                    System.out.println("是否查看全部数据列表（1|0）：");
                    int num2 = scanner.nextInt();
                    if(num2 == 1) {
                        A.line_Out(L1);
                    }else {
                        System.out.println("请输入需要查看的元素的序号：");
                        int num3 = scanner.nextInt();
                        System.out.println(A.line_Get(L1, num3-1));
                    }
                }
                break;
            case 2:
                // 实现菜单2:在顺序表中的指定位置插入指定值
                if(A.line_Full(L1)) {
                    System.out.println("表满，不能插入");
                }else {
                    // 输入插入位置，判断插入位置合理
                    System.out.println("请输入插入位置：");
                    int n = scanner.nextInt();
                    if(n < 0 || n > A.line_Length(L1)) {
                        System.out.println("输入的插入位置不合法");
                    }else {
                        // 插入操作
                        // 移动数据，把插入位置空出来
                        for(int i = A.line_Length(L1)-1; i >= n; i--) {
                            A.line_Move(L1, i+1, i);
                        }
                        // 插入数据
                        System.out.println("请输入要插入的值");
                        x = scanner.nextInt();
                        A.line_In(L1, x, n);
                    }
                    
                }
                break;
            case 3:
                // 实现菜单3：排序操作
                // 菜单选择变量
                M.order();
                System.out.println("请输入你要选择的排序操作：");
                char c = scanner.next().charAt(0);
                if(c == 'A' || c == 'a') {
                    // 冒泡
                    A.line_Bubble(L1);
                }else if(c == 'B' || c == 'b') {
                    // 选择
                    A.line_Select(L1);
                }
                A.line_Out(L1);
                break;
            case 6:
                // 菜单6：顺序表中删除一个值
                if(A.line_Empty(L1)) {
                    System.out.println("表为空，不能删除");
                }else {
                    System.out.println("请输入一个要删除的数据：");
                    x = scanner.nextInt();
                    int t = A.line_Search(L1, x);
                    if(t < 0 || t > A.line_Length(L1)) {
                        System.out.println("您输入的位置不合法");
                    }else {
                        for(int i = t; i < A.line_Length(L1); i++) {
                            A.line_Move(L1, i+1, i);
                        }
                        A.line_Null(L1, A.line_Length(L1)-1);
                        A.line_Out(L1);
                    }
                }
                break;
            case 7:
                Line L2 = new Line();
                A.line_Ininal(L2);
                // 输入数据
                System.out.println("请输入数据：");
                x = scanner.nextInt();
                while(x!=0) {
                    A.line_In(L1, x);
                    System.out.println("请输入数据：");
                    x = scanner.nextInt();
                }
                // 排序，和L1顺序表具有相同的排序，从小到大排序
                A.line_Bubble(L1);
                A.line_Bubble(L2);
                // 合并操作
                // 有序合并
                // 准备一个新的空表
                Line L3 = new Line();
                A.line_Ininal(L3);
                int i1 = 0, i2 = 0;
                while(i1 < A.line_Length(L1) && i2 < A.line_Length(L2)) {
                    if(A.line_Get(L1, i1) < A.line_Get(L2, i2)) {
                        A.line_In(L3, A.line_Get(L1, i1));
                        i1++;
                    }else {
                        A.line_In(L3, A.line_Get(L2, i2));
                        i2++;
                    }
                }
                // 推出循环判断那个表还有剩余元素
                // L1表有剩余元素
                if(i1 < A.line_Length(L1)) {
                    while(i1 < A.line_Length(L1)) {
                        A.line_In(L3, A.line_Get(L1, i1));
                        i1++;
                    }
                }else {
                    while(i2 < A.line_Length(L2)) {
                        A.line_In(L3, A.line_Get(L2, i2));
                        i2++;
                    }
                }
                // 输出顺序表
                A.line_Out(L3);
                break;
            case 8:
                // 实现菜单8：判断子集
                // 有序列表判断子集
                // 创建一个主表
                Line L = new Line();
                A.line_Ininal(L);
                // 对主表数据输入
                System.out.println("请输入数据：");
                x = scanner.nextInt();
                while(x!=0) {
                    A.line_In(L, x);
                    System.out.println("请输入数据：");
                    x = scanner.nextInt();
                }
                // 对两个表进行排序操作
                A.line_Bubble(L);
                A.line_Bubble(L1);
                // 准备工作做好，开始子集的判断
                int i = 0;
                i1 = 0;
                while(i < A.line_Length(L) && i1 < A.line_Length(L1)) {
                    if(A.line_Get(L1, i1) > A.line_Get(L, i)) {
                        i++;
                    }else if(A.line_Get(L1, i1) == A.line_Get(L1, i1)) {
                        i++;
                        i1++;
                    }else if(A.line_Get(L, i) < A.line_Get(L1, i1)) {
                        break;
                    }
                }
                // 对各种情况的判断
                if(i1 >= A.line_Length(L1)) {
                    System.out.println("子表是主表的子集");
                }else {
                    System.out.println("子表不是主表的子集");
                }
                break;
            default :
                return;
            }
            
        }
    }
}

完成