数据结构学习总结（一）
2018-07-19 本文已影响14人
慕涵盛华
目录
数组
数组(array)是由数据类型相同的一系列元素组成，这些元素按顺序存储。
//动态数组
public class Array<E> {
private E[] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity){
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public Array(){
this(10);
}
// 获取数组的容量
public int getCapacity(){
return data.length;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
// 在index索引的位置插入一个新元素e
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
if(size == data.length)
resize(2 * data.length);
for(int i = size - 1; i >= index ; i --)
data[i + 1] = data[i];
data[index] = e;
size ++;
}
// 向所有元素后添加一个新元素
public void addLast(E e){
add(size, e);
}
// 在所有元素前添加一个新元素
public void addFirst(E e){
add(0, e);
}
// 获取index索引位置的元素
public E get(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改index索引位置的元素为e
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contains(E e){
for(int i = 0 ; i < size ; i ++){
if(data[i].equals(e))
return true;
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e){
for(int i = 0 ; i < size ; i ++){
if(data[i].equals(e))
return i;
}
return -1;
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
E ret = data[index];
for(int i = index + 1 ; i < size ; i ++)
data[i - 1] = data[i];
size --;
data[size] = null; // loitering objects != memory leak
if(size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst(){
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast(){
return remove(size - 1);
}
// 从数组中删除元素e
public void removeElement(E e){
int index = find(e);
if(index != -1)
remove(index);
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
res.append('[');
for(int i = 0 ; i < size ; i ++){
res.append(data[i]);
if(i != size - 1)
res.append(", ");
}
res.append(']');
return res.toString();
}
// 将数组空间的容量变成newCapacity大小
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
data = newData;
}
}
时间复杂度分析
O(n) 中的n在分析具体的方法时有对应的定义。
resize时间复杂度分析
复杂度震荡
当capacity = n时执行addLast会扩容，时间复杂度为O(n),紧接着再执行removeLast，删除后会将缩容为一半，时间复杂度为O(n),重复上诉步骤，就会出现复杂度震荡。
这样的话，就不会出现复杂度震荡了。这也是为什么设置1/4时缩容，而不是1/2。
栈
栈也是一个线性结构，相比数组，栈对应的操作是数组的子集；只能从一端添加元素，从一端取出元素，这一端称为栈顶。（只能从栈顶添加和取出）
像撤销操作，程序的调用都应用到栈。
栈的实现
思路：从数组的最后一个位置添加元素，从最后一个位置取元素。
public interface Stack<E> {
int getSize();
boolean isEmpty();
void push(E e);
E pop();
E peek();
}
public class ArrayStack<E> implements Stack<E> {
//用的是上面自定义的动态数组
private Array<E> array;
public ArrayStack(int capacity){
array = new Array<>(capacity);
}
public ArrayStack(){
array = new Array<>();
}
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
/** 入栈 */
@Override
public void push(E e){
array.addLast(e);
}
/** 出栈 */
@Override
public E pop(){
return array.removeLast();
}
/** 查看栈顶的元素 */
@Override
public E peek(){
return array.getLast();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Stack: ");
res.append('[');
for(int i = 0 ; i < array.getSize() ; i ++){
res.append(array.get(i));
if(i != array.getSize() - 1)
res.append(", ");
}
res.append("] top");
return res.toString();
}
}
栈的应用
（LeetCode）给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
思路：遍历字符串，如果是左括号就入栈，如果是右括号就跟栈顶的元素比较，看是是否是匹配的括号。
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(int i = 0 ; i < s.length() ; i ++){
char c = s.charAt(i);
if(c == '(' || c == '[' || c == '{')
stack.push(c);
else{
if(stack.isEmpty())
return false;
char topChar = stack.pop();
if(c == ')' && topChar != '(')
return false;
if(c == ']' && topChar != '[')
return false;
if(c == '}' && topChar != '{')
return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println((new Solution()).isValid("()[]{}"));
System.out.println((new Solution()).isValid("([)]"));
}
}
队列
队列也是一种线性结构，相比数组，它的操作也是数组的子集；只能从一端（队尾）添加元素，从一端（队首）取出元素。是一种先进先出的数据结构（FIFO）
public interface Queue<E> {
int getSize();
boolean isEmpty();
/** 进队 */
void enqueue(E e);
/** 出队 */
E dequeue();
E getFront();
}
数组队列
思路：从数组的最后一个位置添加元素，从第0个位置取出元素。
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array;
public ArrayQueue(int capacity){
array = new Array<>(capacity);
}
public ArrayQueue(){
array = new Array<>();
}
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void enqueue(E e){
array.addLast(e);
}
@Override
public E dequeue(){
return array.removeFirst();
}
@Override
public E getFront(){
return array.getFirst();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue: ");
res.append("front [");
for(int i = 0 ; i < array.getSize() ; i ++){
res.append(array.get(i));
if(i != array.getSize() - 1)
res.append(", ");
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args){
ArrayQueue<Integer> queue = new ArrayQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
时间复杂度分析
循环队列
front记录队首的位置，tail记录队尾的位置。当7的位置有元素的时候，tail就只指向0的位置，再有元素入队的时候放在0的位置，tail就会指向1的位置。（将数组看成一个环）
让数组空着一个元素，用来判断队列满的情况。因为是循环，所以对数组的长度取余数来判断。
public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int front, tail;
private int size;
public LoopQueue(int capacity){
data = (E[])new Object[capacity + 1];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue(){
this(10);
}
public int getCapacity(){
return data.length - 1;
}
@Override
public boolean isEmpty(){
return front == tail;
}
@Override
public int getSize(){
return size;
}
@Override
public void enqueue(E e){
if((tail + 1) % data.length == front)
resize(getCapacity() * 2);
data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}
@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
E ret = data[front];
data[front] = null;
front = (front + 1) % data.length;
size --;
if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
resize(getCapacity() / 2);
return ret;
}
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return data[front];
}
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity + 1];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[(i + front) % data.length];
data = newData;
front = 0;
tail = size;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
res.append("front [");
for(int i = front ; i != tail ; i = (i + 1) % data.length){
res.append(data[i]);
if((i + 1) % data.length != tail)
res.append(", ");
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args){
LoopQueue<Integer> queue = new LoopQueue<>(5);
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
时间复杂度分析
循环队列将出队的时间复杂变成了O(1)
下面测试一下数组队列和循环队列在相同操作下的效率：
public class Main {
// 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒
private static double testQueue(Queue<Integer> q, int opCount){
long startTime = System.nanoTime();
Random random = new Random();
for(int i = 0 ; i < opCount ; i ++)
q.enqueue(random.nextInt(Integer.MAX_VALUE));
for(int i = 0 ; i < opCount ; i ++)
q.dequeue();
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue, time: " + time1 + " s");
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue, time: " + time2 + " s");
}
}
输出
可以看出在操作次数较多的情况下，循环队列明显比数组队列的效率要高很多，这是因为循环队列的出队方法的均摊时间复杂度为O(1)。通过这个例子可以看不不同的数组结构在相同的情况下的效率是不一样的，这也正是数据结构的作用。
链表
- 最简单的动态数据结构
- 辅助组成其他数据结构
- 真正的动态结构，不需要考虑处理固定容量的问题。
当节点中的下一个节点为null时，表示是最后一个元素。
在链表头部添加元素
链表是没有索引的概念的，这里指在元素2的地方插入元素。prev表示要插入地方的元素的上一个节点。关键是找到要插入元素的前一个节点。
public class LinkedList<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@Override
public String toString(){
return e.toString();
}
}
//头结点
private Node head;
private int size;
public LinkedList(){
head = null;
size = 0;
}
// 获取链表中的元素个数
public int getSize(){
return size;
}
// 返回链表是否为空
public boolean isEmpty(){
return size == 0;
}
// 在链表头添加新的元素e
public void addFirst(E e){
// Node node = new Node(e);
// node.next = head;
// head = node;
head = new Node(e, head);//等价于上面三句话
size ++;
}
// 在链表的index(0-based)位置添加新的元素e
// 在链表中不是一个常用的操作，练习用：）
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");
if(index == 0)
addFirst(e);
else{
Node prev = head;
for(int i = 0 ; i < index - 1 ; i ++)
prev = prev.next;
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
prev.next = new Node(e, prev.next);
size ++;
}
}
// 在链表末尾添加新的元素e
public void addLast(E e){
add(size, e);
}
}
为链表添加虚拟头结点
在第一个元素前面添加一个虚拟的头结点，元素值为：null，虚拟头结点的next指向0元素所在的结点。
//含有虚拟头结点
public class LinkedList<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@Override
public String toString(){
return e.toString();
}
}
private Node dummyHead;
private int size;
public LinkedList(){
dummyHead = new Node();
size = 0;
}
// 获取链表中的元素个数
public int getSize(){
return size;
}
// 返回链表是否为空
public boolean isEmpty(){
return size == 0;
}
// 在链表的index(0-based)位置添加新的元素e
// 在链表中不是一个常用的操作，练习用：）
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");
Node prev = dummyHead;
for(int i = 0 ; i < index ; i ++)
prev = prev.next;
prev.next = new Node(e, prev.next);
size ++;
}
// 在链表头添加新的元素e
public void addFirst(E e){
add(0, e);
}
// 在链表末尾添加新的元素e
public void addLast(E e){
add(size, e);
}
}
链表的修改和查询
思路：以头结点为基础，从头开始遍历到指定的位置，依次取出结点的下一个节点。
// 获得链表的第index(0-based)个位置的元素
// 在链表中不是一个常用的操作，练习用：）
public E get(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Illegal index.");
Node cur = dummyHead.next;
for (int i = 0; i < index; i++)
cur = cur.next;
return cur.e;
}
// 获得链表的第一个元素
public E getFirst() {
return get(0);
}
// 获得链表的最后一个元素
public E getLast() {
return get(size - 1);
}
// 修改链表的第index(0-based)个位置的元素为e
// 在链表中不是一个常用的操作，练习用：）
public void set(int index, E e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Illegal index.");
Node cur = dummyHead.next;
for (int i = 0; i < index; i++)
cur = cur.next;
cur.e = e;
}
// 查找链表中是否有元素e
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e))
return true;
cur = cur.next;
}
return false;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
// Node cur = dummyHead.next;
// while(cur != null){
// res.append(cur + "->");
// cur = cur.next;
// }
for (Node cur = dummyHead.next; cur != null; cur = cur.next)
res.append(cur + "->");
res.append("NULL");
return res.toString();
}
链表的删除
// 从链表中删除index(0-based)位置的元素, 返回删除的元素
// 在链表中不是一个常用的操作，练习用：）
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
Node prev = dummyHead;
for(int i = 0 ; i < index ; i ++)
prev = prev.next;
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
size --;
return retNode.e;
}
// 从链表中删除第一个元素, 返回删除的元素
public E removeFirst(){
return remove(0);
}
// 从链表中删除最后一个元素, 返回删除的元素
public E removeLast(){
return remove(size - 1);
}
// 从链表中删除元素e
public void removeElement(E e){
Node prev = dummyHead;
while(prev.next != null){
if(prev.next.e.equals(e))
break;
prev = prev.next;
}
if(prev.next != null){
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
}
}
链表的时间复杂度分析
使用链表实现栈
public class LinkedListStack<E> implements Stack<E> {
private LinkedList<E> list;
public LinkedListStack(){
list = new LinkedList<>();
}
@Override
public int getSize(){
return list.getSize();
}
@Override
public boolean isEmpty(){
return list.isEmpty();
}
@Override
public void push(E e){
list.addFirst(e);
}
@Override
public E pop(){
return list.removeFirst();
}
@Override
public E peek(){
return list.getFirst();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Stack: top ");
res.append(list);
return res.toString();
}
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<>();
for(int i = 0 ; i < 5 ; i ++){
stack.push(i);
System.out.println(stack);
}
stack.pop();
System.out.println(stack);
}
}
对于数组实现的栈和链表实现的栈的效率问题，其实这个时间比较很复杂，因为LinkedListStack中包含更多的new操作。相同的次数操作，耗时大小不一定。次数少的情况下链表实现的要快一些。（它们的时间复杂度是一样的）
改进的链表实现队列
定义一个尾指针指向链表的最后一个节点，在tail节点添加元素很简单（O(1)），但是在tail删除一个节点就比较麻烦（O(n)），因为我们不能直接找到tail的前一个节点，还得通过遍历的方式寻找，所以head处当做队首，tail处当做队尾。
public class LinkedListQueue<E> implements Queue<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@Override
public String toString(){
return e.toString();
}
}
//头结点和尾节点
private Node head, tail;
private int size;
public LinkedListQueue(){
head = null;
tail = null;
size = 0;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
@Override
public void enqueue(E e){
if(tail == null){
tail = new Node(e);
head = tail;
}
else{
tail.next = new Node(e);
tail = tail.next;
}
size ++;
}
@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
Node retNode = head;
head = head.next;
retNode.next = null;
if(head == null)
tail = null;
size --;
return retNode.e;
}
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return head.e;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue: front ");
Node cur = head;
while(cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL tail");
return res.toString();
}
public static void main(String[] args){
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
从上面的实现可以看出，链表之所以能存储一系列的元素，是因为创建了很多对象，这些对象之间，一个节点含有下一个节点对象的引用。这样就会把这些对象“串成”一串。
双向链表
双向链表每一个节点里面都包含上一个节点和下一个节点的引用。这样的话在tail处删除节点就比较容易了。但是维护起来就比较麻烦些。
循环链表
循环链表的尾节点的next不指向null而是指向虚拟头结点dummyHead。如果想在循环链表的尾部添加一个元素，就是在虚拟头结点dummyHead的前面（dummyHead和5之间）添加一个元素，这样就很方便了。
数组链表
数组链表，数组中存储每一个节点，节点中存有元素的值和下一个节点在数组中的索引。当索引为-1时表示是尾节点。可以看出在数组链表中节点中指向下一个节点的数据类型是int。
