【代码】线性表

前言

线性表的Java实现

源代码

- 基本类

package line;
/**
 * 基本类
 * @author hatsunemiku
 *
 */
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;
    }
    
}

• 基本操作类

package line;
/**
 * 顺序表的基本操作类（积木）
 * @author hatsunemiku
 *
 */
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;
                }
            }
        }
        
        
        
}

• 菜单类

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");
    }

}

• 解决实际问题

package line;

import java.util.Scanner;

/**
 * 解决实际问题
 * @author hatsunemiku
 *
 */
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;
            }
            
        }
    }
}

完成