数据结构之旅(1) - 表 - Java语言描述

发表于 | 分类于
字数统计: 2,476

在介绍表之前，我们首先得有一个概念：抽象数据类型（abstract data type，ADT）。

ADT是带有 一组操作 的 一些对象 的 集合。抽象数据类型是数学的抽象，在ADT的定义中并没有解释关于这组操作是如何实现的。诸如 表、集合、图以及与他们各自的操作所形成的对象 都可以被看做为ADT，这就像整数、实数、布尔数都属于数据类型一样。对于集合ADT，可以有像添加(add)、删除(remove)以及包含(contain)这样一些操作。

摘自《数据结构与算法分析 Java语言描述（第三版）》的一段 晦涩难懂 简明扼要 的定义。

表的定义

我们将处理形如 A0，A1，A2，··· ，AN-1的一般的表。我们说这个表的大小是N。我们将大小为 0 的特殊的表称为空表（empty list）。

对于一般表（非空表），我们称 Ai后继 Ai-1（或继 Ai-1 之后， 0 < i < N）并称 Ai-1 前驱 Ai。表中的第一个元素是 A0，最后一个元素是 AN-1。我们不定义第一个元素的前驱元（即A0）与最后一个元素的后继元（即AN-1）。表中元素下标从 0 开始，也就是说 元素 Ai 在表中的位置是 i+1 。

假设现在有 表A 2，4，6，8，10，1，3，5，7，9（为了方便起见，在此之后我们都假设表中的元素是整数int）。根据上述有关表的定义，我们可以得出以下结论：

  1. 表A的大小为 10
  2. 表中第一个元素为 A0=2，最后一个元素是A9=9
  3. 元素 10 后继 元素 9，且前驱 元素 8
  4. 元素 2 的下标为 0，在表中的位置是 1

与上述定义还有关的就是我们对于表做的一系列操作，常见的操作有如下几个：

  1. show 打印表的内容、clear 清空表
  2. find 返回表中某一项第一次出现的位置（从表头开始搜索，且表中元素下标从0开始）
  3. insert/remove 在表的指定位置插入/删除某个元素
  4. get 返回表中指定位置上元素的值

例如对于同一个表A：find(4) 将返回 1；get(4) 将返回 10；insert(0,2) 之后，表的结构就更新为 2，4，0，6，8，10，1，3，5，7，9；remove(2) 之后表的结构更新为 4，0，6，8，10，1，3，5，7，9。

除了这些常见操作之外，你还可以设计其他的方法，例如：contains、reverse 等等。

表的实现

表的数组实现

对表的操作可以使用 连续存储 的数组来实现。虽然数据的容量是创建时固定的，但是我们可以在必要的时候创建另一个数组来完成指定操作，这样一来便可以解决数组容量的问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
int[] arr = new int[5];
···
// 判断是否扩容
if( !enough(length) ) {
	//准备好扩容数组
    int[] newArr = new int[arr.length * 2];
    //数组元素copy
    for(int i = 0; i < arr.length; ++i) {
    	newArr[i] = arr[i];
    }
    arr = newArr;
}
//后续操作

用数组实现表，可以使得 show 在线性时间被执行，而 get 则花费常数时间。但是 insert 和 remove 却占用了昂贵的开销。若在表头（位置0）插入一个元素，我们需将整个数组往后移动 1 个位置，若在表头删除一个元素，我们需将表中其它元素往前移动一个位置，这两种操作的最坏情况都是 0(N)，平均来看，这两个操作都要移动表中一半的元素，仍花费线性的时间；若操作都在表尾进行，则两个操作都只需花费 0(1) 的时间。

因此，如果你要对表进行频繁的 insert、remove 操作的话，用数组来实现表实在不是一个明智的选择；但如果你只是为了访问元素，那数组却是节约了不少时间。

简单链表

为了避免 insert、remove 所带来的昂贵开销，我们需要保证表可以不连续存储，否则表的每个部分都需要移动。因此，引入 链表 的概念：链表由一系列节点组成，这些节点在内容中不必连续存储。每一个节点均包含表元素的值和后继节点的地址（或引用，不妨称之为 next ），最后一个节点的 next 为 null。

虽然用链表实现表解决了 insert、remove 的昂贵开销的问题，同时也保证了 find 和 show 都占用线性的时间，但是 get 却花费了更多的时间，因为存储空间不连续的关系，我们必须从第一个节点开始逐个遍历查找。

下面是链表的定义以及相关操作的图解：

linked list

linkedlist

linkedlist

至于一些特殊位置（如链表的尾部）的 insert、remove 操作，大家可以自己亲手画一画，并思考一下 对于节点的引用的正确的赋值顺序 。

具体代码实现

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
/**
* 这里仅给出链式的实现，数组和双向链表大家可以亲自试试。
* 仅实现常见操作：
* 	1. show/clear      展示/清空
*	2. insert/remove   插入/删除
*	3. get             获取指定位置元素值
*	4. find            根据值查找元素位置
*
* 图个方便：
* 	1. 数据类型选取 int 类型
*	2. private + getter&&setter -> public 
*/
class MyLinkedList {

    public Node root; //第一个节点
    public int size;  //当前链表的长度

    //构造函数 - 根据数组值建立一个链表
    public MyLinkedList(int[] values) {
        if(values != null && values.length != 0) {
            root = new Node(values[0]); //第一个节点
            this.size++;
            Node temp = root;
            for(int i = 1; i < values.length; ++i) {
                temp.next = new Node(values[i]); //后续节点逐一后继(next)
                temp = temp.next; //传递后继节点的引用
                this.size++; //每后继一个链表长度+1
            }
        }
    }

    //依次打印链表所有节点值
    public void show() {
        if(root != null) {
            Node temp = root; //采用temp是为了避免修改对于root的引用,避免链表结构破坏
            while(temp != null) {
                System.out.print(temp.value + " ");
                temp = temp.next; //传递后继引用
            }
        } else {
            System.out.println("Please init linkedlist first !!!");
        }
    }

    //清空链表
    public void clear() {
        if(root != null) {
            root = null; //root引用赋null
            this.size = 0; //链表长度修改为0
        }
    }

    //在index位置插入值为value的节点
    public void insert(int value, int index) {
        if(index < 0 || index > this.size) { //判断index是否合法
            System.out.println("请选择正确的位置插入 !!!");
        } else {
            this.size++; //链表长度+1
            int cnt = 0; //记录当前位置
            Node temp = root; //存储当前引用
            while(temp != null) {
                if(index == 0) { //index=0时无前驱
                    Node newNode = new Node(value);
                    newNode.next = root;
                    root = newNode; //修改root引用
                    break;
                }
                if(cnt == index - 1) { //index!=0时到index-1开始插入
                    Node flag = temp.next; //暂存下一节点的引用
                    temp.next = new Node(value); //对于当前节点赋值后继
                    temp.next.next = flag; //对于新插入节点复制后继
                    break;
                }
                temp = temp.next; //传递后继引用
                cnt++; //更新位置
            }
        }
    }

    //移出index位置的节点
    public void remove(int index) {
        if(index < 0 || index >= this.size) { //判断index是否合法
            System.out.println("请选择正确的位置删除 !!!");
        } else {
            this.size--; //链表长度-1
            int cnt = 0; //记录当前位置
            Node temp = root; //记录当前引用
            while(temp != null) {
                if(index == 0) {
                    root = root.next; //若index=0无前驱,直接修改root引用
                    break;
                }
                if(cnt == index - 1) {
                    temp.next = temp.next.next; //若index!=0,修改当前节点后继
                    break;
                }
                temp = temp.next; //传递后继引用
                cnt++; //更新位置
            }
        }
    }

    //获取index位置的节点的值
    public int get(int index) {
        if(index < 0 || index >= this.size) { //判断index是否合法
            System.out.println("请选择正确的位置 !!!");
        } else {
            int cnt = 0; //记录当前位置
            Node temp = root; //记录当前引用
            while(temp != null) {
                if(cnt == index) { //判断是否到达指定位置
                    return temp.value;
                }
                temp = temp.next; //传递后继引用
                cnt++; //更新位置
            }
        }
        return Integer.MIN_VALUE; //若index不合法,则返回最小的int值
    }

    //获取第一个值为target的节点的位置 - 注意是第一个!!!
    public int find(int target) {
        if(this.size <= 0) { //若当前链表长度为0,则肯定不存在值为target的元素
            System.out.println("请选择正确的位置 !!!");
        } else {
            int cnt = 0; //记录当前位置
            Node temp = root; //记录当前引用
            while(temp != null) {
                if(temp.value == target) { //判断是否满足值为target
                    return cnt;
                }
                temp = temp.next; //传递后继引用
                cnt++; //更新位置
            }
        }
        return Integer.MIN_VALUE; //若链表长度为0或者不存在值为target的节点,则返回最小的int值
    }

}

/**
* 节点类,存储节点值(value)以及后继节点的引用(next)
*/
class Node {

    public int value;
    public Node next;

    //构造函数,默认后继为null
    public Node(int value) {
        this.value = value;
        this.next = null;
    }

}

一些小练习（顺序随机）

  1. 输入一个链表，从尾到头打印链表每个节点的值。
  2. 输入一个链表，输出该链表中倒数第k个结点。
  3. 输入一个链表，反转链表后，输出链表的所有元素。
  4. Missing Number : Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
  5. Merge Sorted Array : Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
  6. Rotate Array : Rotate an array of n elements to the right by k steps.