线性表

线性表的基本概念

• 对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型；
• 数据元素之间具有一种线性的或“一对一”的逻辑关系。
  1. 第一个数据元素没有前驱，这个数据元素被称为开始节点；
  2. 最后一个数据元素没有后继，这个数据元素被称为终端节点；
  3. 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

线性表的抽象数据类型描述

基本操作如下：

1. 线性表的置空操作clear()：将一个已经存在的线性表置为空表。
2. 线性表判空操作isEmpty()：判断线性表是否为空，若为空，则返回true；否则，返回为false。
3. 求线性表的长度操作length()：求线性表中的数据元素的个数并返回其值。
4. 取元素操作get(i)：读取并返回线性表中的第i个数据元素的值。其中i的取值范围为0≤i≤length()-1。
5. 插入操作insert(i,x)：在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i的取值范围为0≤i≤length()。当i=0时，在表头插入x；当i=length()时，在表尾插入x。
6. 删除操作remove(i)：删除并返回线性表中第i个数据元素。其中i的取值范围为0≤i≤length()-1。
7. 查找操作indexOf(x)：返回线性表中首次出现的指定的数据元素的位序号，若线性表中不包含此数据元素，则返回-1。

线性表的抽线数据类型用Java接口描述如下：

/**
 * 
 * @author Accper
 * 
 */
public interface IList {
    // 线性表置空操作
    public void clear();

    // 判断线性表是否为空操作
    public boolean isEmpty();

    // 获取线性表中元素的长度操作
    public int length();

    // 获取指定位置上面的元素操作
    public Object get(int i);

    // 在指定位置上面插入元素的操作
    public void insert(int i, Object x);

    // 删除指定位置上面的元素的操作
    public void remove(int i);

    // 查找指定元素的位置首次出现的位置操作
    public int indexOf(Object x);

    // 显示线性表中的内容操作
    public void display();
}

线性表的顺序存储及实现

1. 顺序表的定义
   • 所谓顺序表就是顺序存储的线性表。顺序存储是用一组地址连续的存储单元依次存放线性表中各个元素的存储结构。
2. 顺序表的特点：
   • 在线性表中逻辑上相邻的数据元素，在物理存储上也是相邻的。
   • 存储密度高，但要预先分配“足够应用”的存储空间，这可能会造成存储空间的浪费。
   • 便于随机存储。
   • 不便于插入和删除操作，这是因为在顺序表上进行的插入和删除操作会引起大量数据元素的移动。
3. 顺序存储结构类的描述

/**
 * 
 * @author Accper
 * 
 */
public class SqList implements IList {
    // 线性表存储空间
    private Object[] listElem;
    // 线性表的当前长度
    private int curLen;

    // 顺序表类的构造函数，构造一个存储空间容量为maxSize的线性表
    public SqList(int maxSize) {
        // TODO Auto-generated constructor stub
        curLen = 0;
        listElem = new Object[maxSize];
    }

    // 将一个已经存在的线性表置成空表
    public void clear() {
        // TODO Auto-generated method stub
        // 置顺序表的当前长度为0
        curLen = 0;
    }

    // 判断线性表中的数据元素的个数是否为0，若为0则返回true，否则返回false
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return curLen == 0;
    }

    // 求线性表中的数据元素的个数并返回其值
    public int length() {
        // TODO Auto-generated method stub
        // 返回顺序表的当前长度
        return curLen;
    }

    // 读取到线性表中的第i个数据元素并由函数返回其值，其中i的取值范围为0≤i≤length()-1，若i不在此范围则抛出异常
    public Object get(int i) {
        // TODO Auto-generated method stub
        if (i < 0 || i >= curLen) {
            throw new RuntimeException("第" + i + "个元素不存在");
        }
        return listElem[i];
    }

    // 在线性表的第i个数据元素之前插入一个值位x的数据元素
    public void insert(int i, Object x) {
        // TODO Auto-generated method stub
        // 判断表是否满了
        if (curLen == listElem.length) {
            throw new RuntimeException("存储空间已经满了，无法插入新的元素");
        }
        // 插入的位置不合法
        if (i < 0 || i > curLen) {
            throw new RuntimeException("插入的位置不合法");
        }
        // 必须要从最后一个元素开始依次逐个后移动，直到第i个数据元素移动完毕为止。
        for (int j = curLen; j > i; j--) {
            listElem[j] = listElem[j - 1];
        }
        listElem[i] = x;
        curLen++;
    }

    public void remove(int i) {
        // TODO Auto-generated method stub
        if (i < 0 || i > curLen - 1) {
            throw new RuntimeException("删除的位置不合法");
        }
        for (int j = i; j < curLen; j++) {
            listElem[j] = listElem[j+1];
        }
        curLen--;
    }

    // 返回线性表中首次出现指定的数据元素的位序号，若线性表中不包含此数据元素，则返回-1
    public int indexOf(Object x) {
        // TODO Auto-generated method stub
        for (int i = 0; i < curLen; i++) {
            if (listElem[i].equals(x)) {
                return i;
            }
        }
        return -1;
    }

    // 输出线性表中的数据元素
    public void display() {
        // TODO Auto-generated method stub
        for (int i = 0; i < curLen; i++) {
            System.out.print(listElem[i] + " ");
        }
        System.out.println();
    }

    // 测试
    public static void main(String[] args) {
        SqList sqList = new SqList(10);
        sqList.insert(0, "a");
        sqList.insert(1, "z");
        sqList.insert(2, "d");
        sqList.insert(3, "m");
        sqList.insert(4, "z");
        int order = sqList.indexOf("z");
        if (order!=-1) {
            System.out.println("顺序表中第一次出现的值为z的数据元素的位置为："+order);
        }else {
            System.out.println("顺序表中不包括z元素");
        }
    }
}

线性表的链式存储及实现

1. 结点类的描述

/**
 * 
 * @author Accper
 *
 */
public class Node {
    // 存放结点的值
    private Object data;
    // 后继结点的引用
    private Node next;

    // 无参数时的构造函数
    public Node() {
        // TODO Auto-generated constructor stub
        this(null, null);
    }

    // 带有一个参数时的构造函数
    public Node(Object data) {
        this(data, null);
    }

    // 带有两个参数时的构造函数
    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

单链表类的描述

/**
 * 
 * @author Accper
 *
 */
public class LinkList implements IList {
    // 单链表的头指针
    private Node head;

    // 单链表的构造函数
    public LinkList() {
        // TODO Auto-generated constructor stub
        // 初始化头结点
        head = new Node();
    }

    public LinkList(int n, boolean Order) {
        // 初始化头结点
        this();
        if (Order) {
            // 用尾插法顺序建立单链表
            create1(n);
        } else {
            // 用头插法顺序建立单链表
            create2(n);
        }
    }

    // 用头插法顺序建立单链表
    private void create2(int n) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < n; i++) {
            insert(0, sc.next());
        }
    }

    // 用尾插法顺序建立单链表
    private void create1(int n) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < n; i++) {
            insert(length(), sc.next());
        }
    }

    // 将一个已经存在的带头结点的单链表置成空表
    @Override
    public void clear() {
        // TODO Auto-generated method stub
        head.setData(null);
        head.setNext(null);
    }

    // 判断带头结点的单链表是否为空
    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return head.getNext() == null;
    }

    // 求带头结点的单链表的长度
    @Override
    public int length() {
        // TODO Auto-generated method stub
        // 初始化，p指向头结点，length为计数器
        Node p = head.getNext();
        int length = 0;
        // 从头结点开始向后查找，直到p为空
        while (p != null) {
            // 指向后继结点
            p = p.getNext();
            // 长度加1
            length++;
        }
        return length;
    }

    // 读取带头结点的单链表中的第i个结点
    @Override
    public Object get(int i) {
        // TODO Auto-generated method stub
        Node p = head.getNext();
        int j = 0;
        while (p != null && j < i) {
            p = p.getNext();
            j++;
        }
        // i小于0或者大于表长减1
        if (j > i || p == null) {
            throw new RuntimeException("第" + i + "个元素不存在");
        }
        return p.getData();
    }

    // 在头结点的单链表中的第i个结点之前插入一个值为x的新结点
    @Override
    public void insert(int i, Object x) {
        // TODO Auto-generated method stub
        Node p = head;
        int j = -1;
        // 寻找第i个结点的前驱
        while (p != null && j < i - 1) {
            p = p.getNext();
            j++;
        }
        if (j > i - 1 || p == null) {
            throw new RuntimeException("插入位置不合法");
        }
        Node s = new Node(x);
        // 修改链，使新结点插入到单链表中
        s.setNext(p.getNext());
        p.setNext(s);
    }

    // 删除带头结点的单链表中的第i个结点
    @Override
    public void remove(int i) {
        // TODO Auto-generated method stub
        Node p = head;
        int j = -1;
        while (p.getNext() != null && j < i - 1) {
            p = p.getNext();
            j++;
        }
        if (j > i - 1 || p.getNext() == null) {
            throw new RuntimeException("删除位置不合法");
        }
        // 修改链指针，使待删除结点从单链表中脱离
        p.setNext(p.getNext().getNext());
    }

    // 查找指定单链表中元素的位置，若在单链表中值发回该位置，如果不在单链表中则返回-1
    @Override
    public int indexOf(Object x) {
        // TODO Auto-generated method stub
        Node p = head.getNext();
        int j = 0;
        while (p != null && p.getData().equals(x)) {
            p = p.getNext();
            j++;
        }
        if (p == null) {
            return -1;
        } else {
            return j;
        }
    }

    // 输出单链表中的所有结点
    @Override
    public void display() {
        // TODO Auto-generated method stub
        // 取出带头结点的单链表中的首结点
        Node p = head.getNext();
        while (p != null) {
            // 输出结点的值
            System.out.print(p.getData() + " ");
            // 取下一个结点
            p = p.getNext();
        }
        System.out.println();
    }

    // 测试
    public static void main(String[] args) {
        int n = 10;
        LinkList L = new LinkList();
        for (int i = 0; i < n; i++) {
            L.insert(i, i);
        }
        System.out.println("请输入i的值：");
        int i = new Scanner(System.in).nextInt();
        if (0 < i && i <= n) {
            System.out.println("第" + i + "个元素的前驱是:" + L.get(i - 1));
        } else {
            System.out.println("第" + i + "个元素的直接前驱不存在");
        }
    }
}