2017/05/31

1.线性表(Linear List) ——————本质为："线性表"

特点：具备线性结构的特点，且表中元素属于同一数据对象，元素之间存在一种序偶关系(即有'先后'关系)。
基本操作：

① 初始化
② 插入
③ 删除
④ 查找 (找出特定元素在表中的位置)
⑤ 获取 (获取第 i 个元素)
⑥ 更新(即修改表中数据项的内容)
⑦ 判空
⑧ 遍历度 (即数据表中的数据的个数)
⑩ 销毁
⑨ 求长(整个线性表)

表示形式：

㈠'逻辑结构':

(a1, a2, a3, ..., ai-1, ai, ai+1, ..., an)
可分为有序线性表(递增, 非递增, 递减, 非递减)、无序线性表

㈡'物理存储结构'

(1)顺序存储结构：线性顺序表

即用一组地址连续的存储单元依次存储数据元素。
采用一维数组来描述顺序存储结构，因此存储映像由数组的存储单元组成。

线性顺序表为"空"的条件：length == 0

代码描述：

public class SequenceList<T> {
    private final int maxSize = 10; //顺序表中的数组对象
    private int length;     //保存顺序线性表当前的数据元素个数, 
    private T[] listArray;  //存储元素的数组
    
    /**
    *   1.初始化操作
    *   注意：由于线性顺序表的长度是固定的，初始化时要指定表长。因此，存在两种
    *       初始化方式：1.使用默认的长度
    *                   2.自定义长度
    */
    //构造一个空的线性表，长度(容量)采用默认长度(容量)：maxSize
    public SequenceList() {
        length = 0; //线性表初始为空
        //注意，不可以直接实例化泛型对象，所以先实例化一个Object数组
        //然后把它转换为相应的泛型数组                
        listArray = (T[])new Object[maxSize]; 
    }
    ///构造一个空的线性表，长度(容量)采用自定义长度(容量)：n
    public SequenceList(int n) {
        //首先的输入的参数进行合法性的检查
        if (n <= 0) {
            System.out.println("error");
            System.exit(1);
        }
        length = 0; //线性表初始为空
        //注意，不可以直接实例化泛型对象，所以先实例化一个Object数组
        //然后把它转换为相应的泛型数组    
        listArray = (T[])new Object[maxSize]; 
    }

    // 2.插入操作 (返回是否插入成功的信息)，时间复杂度：O(n)
    public boolean add(T obj, int pos){
        //首先的输入的参数进行合法性的判断: 1<=pos<=length+1
        if (pos < 1 || pos > length + 1) {
            System.out.println("pos值不合法");
            return false;
        }
        /**
        * 注意：由于顺序线性表是基于数组实现的，因此，有表满的问题，需要考虑（链式线性表则无表满的问题）
        * 当前线性表的元素个数等于线性表的存储长度(容量)时，即表已经满了。 
        * 需要对该线性表进行扩容2陪，切勿忘记对原表数据的复制
        */
        if (length == listArray.length) {
            T[] p = (T[]) new Object[length*2];
            for (int i =0; i < length; i++) {
                p[i] = listArray[i];
            }
            listArray = p;
        }
        /**
        *   执行数据插入过程
        *   说明：注意线性表的下标是从1开始的，而数组的下标是从0开始的
        */
        for (int i = length; i >= pos; i--) {
            listArray[i] = listArray[i - 1];
        }
        listArray[pos - 1] = obj; //插入元素
        length ++;  //线性表长度加1
        return true; //插入成功
    }

    // 3.删除操作 (返回被删除的元素)，时间复杂度：O(n)
    public T remove(int pos) {
        //首先判空表是否为空
        if (isEmpty()) {
            System.out.println("该顺序表为空，不能执行删除操作");
            return null;
        }
        //对删除位置的合法性进行检查:1<=pos<=length
        if (pos < 1 || pos > length) {
            System.out.println("pos位置不合法");
            return null;
        }
        //执行删除过程
        T x = listArray[pos - 1]; //先将要删除的元素存储起来，否则会被覆盖了
        for (int i = pos; i < length; i++) {
            listArray[i - 1] = listArray[i];
        }
        length --; //线性表长度减1
        return x;   //返回被删除的元素
    }

    // 4.查找操作 (返回元素所在的位置),时间复杂度：O(n)
    public int find(T obj) {
        //判断线性表是否为空
        if (isEmpty()) {
            System.out.println("该顺序表为空，没有任何元素可查询");
            return -1;
        }
        //返回待查找的元素
        for (int i = 0; i < length; i++) {
            if (listArray[i].equals(obj)) {
                return i + 1; //注意：线性表的位置和数组的位置差1                               
            }
        }
        return -1;
    }
    // 5.获取元素操作 (返回获取到的元素)
    public T value(int pos) {
        //先进行判空
        if (isEmpty()) {
            System.out.println("该线性表为空，没有元素可获取");
            return null;
        }
        //进行pos位置合法性的检查
        if (pos < 1 || pos > length) {
            System.out.println("error");
            return null;
        }
        //返回待查找的元素
        return listArray[pos - 1]; //注意减1
    }
    // 6.更新元素内容操作 (返回是否更新成功的信息)
    public boolean modify(T newObj, int pos) {
        //先进行判空
        if (isEmpty()) {
            System.out.println("该线性表为空，没有元素可更新");
            return false;
        }
        //进行pos位置合法性的检查
        if (pos < 1 || pos > length) {
            System.out.println("error");
            return false;
        }
        //元素内容更新
        listArray[pos - 1] = newObj;
        return true;
    }
    // 7.判空操作 (返回是否为空的信息)
    public boolean isEmpty() {

        //当length为0，则表明该线性表为空
        return length == 0;
    }
    // 8.求长度 (返回线性表中的数据的个数)
    public int size() {
        //内部变量length就是记录了线性表当前的元素个数
        return length;
    }
    // 9.正向遍历数据表
    public void nextOrder() {
        System.out.print("[");
        for (int i = 0; i < length; i++) {
            if (i == length - 1) {
                System.out.println(listArray[i] + "]");
            } else {
                System.out.print(listArray[i] + ", ");
            }
            
        }
    }
    // 10.销毁线性顺序表
    public void clear() {
        //将该线性表的元素个数(length)修改为0，即可达到销毁线性表的效果
        length = 0;
    }

}

(2) 链式存储结构:单链表、循环链表、双向链表
采用一组'任意(可以连续也可以不连续)'的存储单元来存放线性表的数据元素。

1."单链表"(带头结点)
由于在物理上存储位置和逻辑顺序不一致，因此，必须在存放某一元素时还须存储一个指示其直接“后继存放位置”（即后继结点）的指针。因此，每个数据元素对应的“存储映像”（又称为结点）由两部分组成：数据域、指针域
　 ┌───────┬───────┐
结点(Node)： │ 数据域│ 指针域│
└───────┴───────┘

含有头结点的单链表：
head——> 头结点(数据域通常无意义)——> 结点1——> 结点2——> ... 结点n(指针域为null)

单链表为空的条件：head.next == null
到达表尾的条件：p.next == null

头指针和头结点的联系与区别
头指针：
指向链表第一个结点(当没有头结点存在时)的指针
头指针具有标识作用，常用它作为链表的名字
无论链表是否为空，头指针均不为空(即头指针是必须存在的)
头指针是链表的必要元素
头结点：
头结点的存在是为了操作(如对第一个结点进行增、删等操作时)的统一和方便
头结点放在第一个结点的前面，其数据域通常无意义(有时可以用来存放链表的长度)
头结点不是链表的必要元素(可有可无)

注意："单链表"(又称为线性链表)是重要考察的

代码描述：
1)"结点"代码描述：

/**
*   分为两部分：数据域、指针域
*/
public class Node<T> {
    T data;
    Node<T> next; //因为指针就是一个地址，代表下一个Node的地址。
    //该构造器表示只初始化了指针域，数据域不存储有效的用户数据
    public Node(Node<T> n) {
        next = n;
    }
    //数据域和指针域均初始化
    public Node(T obj, Node<T> n) {
        data = obj;
        next = n;
    }

    public T getData() {
        return data;
    }

    public Node<T> getNext() {
        return next;
    }
}

2)"单链表"代码描述:

public class LinkList<T> {
    private Node<T> head; //头指针
    private int length; //单链表的长度(即元素个数)
    /**
    *   1.初始化
    *   链表的初始化不需要在开始就确定其存储长度,因为它的长度是可变的
    *   因此，链表的初始化就只有一种方式
    */
    public LinkList() {
        length = 0; //初始化线性链表为空
        //只初始化了该结点的指针域，因此这个结点是头结点，而非第一个结点
        head = new Node<T>(null); // 让head指向头结点
    }
    //2.获取链表头结点的地址
    public Node<T> getHead() {
        return head;
    }
    /**
    *   3.插入元素:指在第pos-1和第pos个结点之间插入新的结点。
    *   时间复杂度：O(n)
    */
    public boolean add(T obj, int pos) {

        //先对插入位置的参数合法性进行检查:1<=pos<=length+1
        if (pos < 1 || pos > length + 1) {
            System.out.println("pos参数不合法");
            return false;
        }
        /**
        * 注意：由于线性链表没有表满的问题，则不需要考虑扩容的问题（线性顺序表则要考虑表满的问题）
        * 先寻找到pos位置所对应的结点
        *   由于线性链表不具有随机访问（即任意访问）的特点，所以插入
        *   数据前，必须从头到插入点顺序扫描每个结点，从而找到待插入
        *   位置的结点。这点是不同于线性顺序表(可以随机找到某位的元素)
        */
        int num = 1;//辅助寻找pos位置的
        Node<T> p = head;
        Node<T> q = head.next;
        while(num < pos) {
            p = q;
            q = q.next;
            num ++;
        }
        /**
        *   此时p指向pos-1位置的结点,q指向pos位置的结点.
        *   要往p和q之间插入新的元素，则先将数据obj封装进Node结点中
        */
        p.next = new Node<T>(obj, q); //这句话好好体会
        length ++;
        return true;
    }
    /**
    *   4.删除元素:指删除线性链表的第pos个结点
    *   时间复杂度：O(n)
    *   
    */
    public T remove(int pos) {
        //先对链表进行判空
        if (isEmpty()) {
            System.out.println("链表为空，不可以进行删除操作");
            return null;
        }
        //再对删除位置的参数合法性进行检查:1<=pos<=length
        if (pos < 1 || pos > length) {
            System.out.println("pos参数不合法");
            return null;
        }
        /**
        * 先寻找到pos位置所对应的结点
        *   由于线性链表不具有随机访问（即任意访问）的特点，所以插入
        *   数据前，必须从头到插入点顺序扫描每个结点，从而找到待插入
        *   位置的结点。这点是不同于线性顺序表(可以随机找到某位的元素)
        */
        int num = 1;
        Node<T> p = head;
        Node<T> q = head.next;
        while (num < pos) {
            p = q;
            q = q.next;
            num ++;
        }
        /**
        *   此时p指向pos-1位置的结点,q指向pos位置的结点.
        *   要删除q指向的元素
        */
        p.next = q.next;
        length --;
        return q.data;                          
    }
    //5.获取元素:获取第pos位置处的结点对应的元素
    public T value(int pos) {
        //先对链表进行判空
        if (isEmpty()) {
            System.out.println("链表为空，不可以进行获取操作");
            return null;
        }
        //再对获取位置的参数合法性进行检查:1<=pos<=length
        if (pos < 1 || pos > length) {
            System.out.println("pos参数不合法");
            return null;
        }
        //进行"获取"过程:从头至尾进行搜索
        int num = 1;
        Node<T> q = head.next; //q的初始位置指向第一个结点处
        while (num < pos) {
            q = q.next;
            num ++;
        }
        //此时搜索至pos位置处
        return q.data;                          
    }
    //6.查找元素
    public int find(T obj) {
        //先对链表进行判空
        if (isEmpty()) {
            System.out.println("链表为空，不可以进行查找操作");
            return -1;
        }
        //进行查找过程:从头到尾挨个比较待查找元素和链表中元素是否相等
        int num = 1;
        Node<T> q = head.next; //q的初始位置指向第一个结点处
        while (q != null) {
            if (q.data.equals(obj) == false) {
                //表明还没有查找到
                q = q.next;
                num ++;                                 
            }else {
                break;
            }               
        }
        //此时表明已经查找到或者搜索至尾仍没有查找到,所以要进行判断是哪种情况
        if (q == null) {
            //表明搜索至尾仍没有查找到
            return -1;
        }
        //此时肯定是查找到了
        return num;                         
    }
    //7.修改元素
    public boolean modify(T newObj, int pos) {
        //先对链表进行判空
        if (isEmpty()) {
            System.out.println("链表为空，不可以进行修改操作");
            return false;
        }
        //再对获取位置的参数合法性进行检查:1<=pos<=length
        if (pos < 1 || pos > length) {
            System.out.println("pos参数不合法");
            return false;
        }

        //进行修改过程
        int num = 1;
        Node<T> q = head.next; //q的初始位置指向第一个结点处
        while (num < pos) {
            q = q.next;
            num ++;
        }
        //此时已经找到pos处，q指向pos处的结点
        q.data = newObj;
        return true;
    }
    //8.判空
    public boolean isEmpty() {
        return length == 0;
    }
    //9.求长度 (返回线性链表中的数据的个数)
    public int size() {
        return length;
    }
    //10.正向遍历线性链表
    public void nextOrder() {
        System.out.print("[");
        Node<T> q = head.next;
        int num = 1;
        while (q != null) {
            if (num == length) {
                System.out.println(q.data + "]");
                break;
            }
            System.out.print(q.data + ", ");
            q = q.next;
            num ++;         
        }
    }
    //11.销毁线性链表
    public void clear() {
        length = 0;
        head.next = null;//把头结点的指针域置为空
    }
}

2."循环链表"
该类链表最后一个节点的指针域不再为空，而是指向表头结点，使整个链表形成一个环这样，可以从表中任意地方出发均可到达其他结点(这点不同于单链表：必须从表头head去访问)，这是循环链表最大的优点处。

'循环链表的标记方式'(2种):
(1)用头指针head标记：
_____________________________________________________
↓ |
head——> 头结点(数据域通常无意义)——> 结点1——> 结点2——> ... 结点n(指针域为head.next)

判断链表为空的条件: head.next == head
到达表尾的条件：p.next == head
到达表头的时间复杂度：O(1)
到达表尾的时间复杂度：O(n)

(2)用尾指针rear标记：
如果，将循环链表的标识'头指针'从头结点处移至'尾结点'处，形成"尾指针"，用rear来表示。
则到达表头、表尾都很方便。
____________________________________________________
↓ |
'头结点(数据域通常无意义)——> 结点1——> 结点2——> ... 结点n(指针域为head.next) <—— rear'

判断链表为空的条件: head.next == head
到达表尾的条件：p.next == head
到达表头的时间复杂度：O(1)
到达表尾的时间复杂度：O(1)

3."双向链表"
单向链表和循环链表找后继结点的时间复杂度均为：O(1),而找前驱结点的T[n]=O(n)若采用双向链表的方式，则到其后继结点和前驱结点的T[n]均为：O(1),但为此付出了空间上的代价:为每个元素结点增加了前驱指针域，prior

                    ┌───────┬───────┬──────┐

双向链表结点(DuNode)： │ prior │ data │ next │
└───────┴───────┴──────┘

注意：'双向循环链表'

代码描述:
1)"双向链表结点"描述：

public class DuNode<T> {
    T data;
    DuNode<T> prior;
    DuNode<T> next;
    public DuNode(DuNode<T> n) {
        next = n;
        prior = null
    }

    public DuNode(T obj, DuNode<T> n, DuNode<T> p) {
        data = obj;
        next = n;
        prior = p;
    }
}

2)"双向链表"描述(伪代码)：

    public class DuLinkList<T> {
        //插入操作：...a, p...之间插入s(注意顺序)
        s.prior = p.prior
        p.prior.next = s
        s.next = p
        p.prior = s

        //删除操作：...a, p, s...删除p
        p.prior.next = p.next
        p.next.prior = p.prior
    }

4."静态链表"
用一组数组(存储地址连续)来实现的链表
┌────┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│游标│ 6 │ 5 │ 3 │ 4 │'0'│ 2 │ │ │ │ │ │ │ 1 │
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
│数据│空 │ A │ C │ D │ E │ B │ │ │ │ │ │ │ │
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
│下标│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10│...│999│
└────┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
1)第一位置的游标总是指向链表中为空的存储单元（这些为空的单元也称之为'备用链表'）的下标，且其数据域中不存储数据
2)最后一个有数据的单元的游标为0（即是指向第一个存储单元的）
3)数组最后一个元素的游标指向第一个有数据的存储单元

静态链表的优缺点：
优点：
1.在插入和删除时，只需修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点

缺点：
1.没有解决连续存储分配（即数组的分配）带来的表长难以确定的问题
2.失去了顺序存储结构随机存取的特性。

言而总之：静态链表是为了给没有指针的编程语言设计的一种实现单链表功能的方法
虽然现在大多数编程语言不需用静态链表了，但这种思路很值得思考学习