【数据结构与算法】第五、六章：线性表（顺序表、链表、栈、队列）符号表

本文主要是介绍【数据结构与算法】第五、六章：线性表（顺序表、链表、栈、队列）符号表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

5、线性表

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列

前驱元素： 若A元素在B元素的前面，则称A为B的前驱元素

后继元素： 若B元素在A元素的后面，则称B为A的后继元素

线性表的特征：数据元素之间具有一种“一对一”的逻辑关系。

1. 第一个数据元素没有前驱，这个数据元素被称为头结点

2. 最后一个数据元素没有后继，这个数据元素被称为尾结点

3. 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继

如果把线性表用数学语言来定义，则可以表示为(a1,…ai-1,ai,ai+1,…an)，ai-1领先于ai，ai领先于ai+1，
称ai-1是ai的前驱元素，ai+1是ai的后继元素

线性表的分类： 线性表中数据存储的方式可以是 顺序存储，也可以是 链式存储， 按照数据的存储方式不同，可以把线性表分为 顺序表 和 链表

5.1、顺序表

顺序表是在计算机内存中以 数组 的形式保存的线性表， 线性表的顺序存储是指用一组 地址连续 的存储单元，依 次存储线性表中的各个元素、使得线性表中在逻辑结构上，相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系

物理存储 和 逻辑 上的相邻关系 相同

1）顺序表的实现

• API设计

• 代码实现

package chapter03;/*** @author 土味儿* Date 2021/9/3* @version 1.0* 顺序表*/
public class SequenceList<T> {/*** 存储元素的数组*/private T[] eles;/*** 记录当前顺序表中元素的个数*/private int n;/*** 当前顺序表的容量*/private int capacity;/*** 构造容量为capacity的数组** @param capacity*/public SequenceList(int capacity) {this.eles = (T[]) new Object[capacity];this.n = 0;this.capacity = capacity；}/*** 清空表*/public void clear() {n = 0;}/*** 判断表是否为空** @return*/public boolean isEmpty() {return n == 0;}/*** 得到表的长度：表中元素个数** @return*/public int length() {return n;}/*** 返回表中i位置的元素** @param i* @return*/public T get(int i) {if (i < 0 || i >= n) {throw new RuntimeException("没有索引为" + i + "的元素");}return eles[i];}/*** 向表中索引为i的位置插入元素t** @param i* @param t*/public void insert(int i, T t) {// 判断表是否已满if (n == capacity) {throw new RuntimeException("表已满！");}// 判断i是否合法if (i < 0 || i >= n) {throw new RuntimeException("插入位置不合法！");}// 把i后的元素后移：从后向前依次后移for (int index = n; index > i; index--) {eles[index] = eles[index - 1];}// 把t放到i处eles[i] = t;// 元素数量n加1n++;}/*** 向表的结尾插入元素t** @param t*/public void insert(T t) {if (n == capacity) {throw new RuntimeException("表已满！");}eles[n++] = t;}/*** 删除表中索引为i位置的元素** @param i* @return*/public T remove(int i) {// 判断i是否合法if (i < 0 || i >= n) {throw new RuntimeException("没有索引为" + i + "的元素");}// 记录i位置的元素T res = eles[i];// 把i位置后的元素依次前移for (int index = i; index < n - 1; index++) {eles[index - 1] = eles[index];}// 元素数量减1n--;// 返回删除的元素return res;}/*** 查询元素t在表中首次出现的索引** @param t* @return*/public int indexOf(T t) {// 判断t是否合法if (t == null) {throw new RuntimeException("元素不合法！");}// 遍历数组，如匹配，返回索引for (int i = 0; i < n; i++) {if (eles[i].equals(t)) {return i;}}// 遍历后找不到，返回-1return -1;}
}

public class TestSequenceList {@Testpublic void test(){SequenceList<String> sl = new SequenceList<>(5);//Assert.assertEquals(3,sl.length());sl.insert("姚明");sl.insert("科比");sl.insert("麦迪");sl.insert(1,"詹姆斯");sl.insert("奥尼尔");//sl.insert("易建联");System.out.println(sl.get(2));System.out.println(sl.remove(3));sl.clear();System.out.println(sl.length());}
}

科比
麦迪
0

2）顺序表的遍历

一般作为容器存储数据，都需要向外部提供遍历的方式，因此需要给顺序表提供遍历方式。

在java中，遍历集合的方式一般都是用的是foreach循环，如果想让的SequenceList也能支持foreach循环，则需要做如下操作：

1. 让SequenceList实现Iterable接口，重写iterator方法；

2. 在SequenceList内部提供一个内部类SIterator,实现Iterator接口，重写hasNext方法和next方法；

代码：

public class SequenceList<T> implements Iterable<T>{// 省略其它方法.../*** 获取迭代器* @return*/@Overridepublic Iterator<T> iterator() {return new Siterator();}/*** 内部类：迭代器*/private class Siterator implements Iterator{/*** 游标*/private int cursor;/*** 构造器*/public Siterator() {this.cursor = 0;}/*** 判断是否有下一个* @return*/@Overridepublic boolean hasNext() {return cursor<n;}/*** 得到下一个元素* @return*/@Overridepublic T next() {return eles[cursor++];}}
}

public void test(){SequenceList<String> sl = new SequenceList<>(5);//Assert.assertEquals(3,sl.length());sl.insert("姚明");sl.insert("科比");sl.insert("麦迪");sl.insert(1,"詹姆斯");sl.insert("奥尼尔");//sl.insert("易建联");// 增强for循环底层实现是迭代器，就是简化版本的迭代器for (String s : sl) {System.out.println(s);}
}

姚明
詹姆斯
科比
麦迪
奥尼尔

3）顺序表的容量可变

在设计顺序表时，应该考虑它的容量的 伸缩性

考虑容器的容量伸缩性，其实就是改变存储数据元素的数组的大小

• 添加元素时

  应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，这里创建一个是原数组两倍容量的新数组存储元素

• 移除元素时

  应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存空间的浪费，应该创建一个容量更小的数组存储元素。如果发现数据元素的数量不足数组容量的1/4，则创建 一个是原数组容量的1/2的新数组存储元素
  

• 代码实现

public void insert(int i, T t) {// 判断表是否已满，如果满，扩容if (n == capacity) {//throw new RuntimeException("表已满！");resize(2 * capacity);}//....
} public void insert(T t) {// 判断表是否已满，如果满，扩容if (n == capacity) {//throw new RuntimeException("表已满！");resize(2 * capacity);}eles[n++] = t;
}public T remove(int i) {// ....// 如果元素数量小于容量的1/4，把容量改为1/2if (n < capacity / 4) {resize(capacity / 2);}  // ....    
}  /**
* 改变顺序表容量
*
* @param newCapacity
*/
private void resize(int newCapacity) {// 记录旧数组T[] temp = eles;// 创建新数组eles = (T[]) new Object[newCapacity];// 把旧数组元素复制到新数组for (int i = 0; i < n; i++) {eles[i] = temp[i];}// 更新数组容量值capacity = newCapacity;
}

public class TestSequenceList {@Testpublic void test(){SequenceList<String> sl = new SequenceList<>(3);//Assert.assertEquals(3,sl.length());sl.insert("姚明");sl.insert("科比");sl.insert("麦迪");sl.insert(1,"詹姆斯");sl.insert("奥尼尔");sl.insert("易建联");for (String s : sl) {System.out.println(s);}}
}

姚明
詹姆斯
科比
麦迪
奥尼尔
易建联

4）顺序表的时间复杂度

• get(i)：不论数据元素量N有多大，只需要一次eles[i]就可以获取到对应的元素，所以时间复杂度为 O(1)
• insert(int i,T t)：每一次插入，都需要把i位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时间复杂为 O(n)
• remove(int i)：每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大,移动的元素也越多，时间复杂度为 O(n)
• 由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器 扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显

5）java中ArrayList实现

java中ArrayList集合的底层也是一种顺序表，使用 数组 实现，同样提供了增删改查以及扩容等功能

5.2、链表

1）介绍

• 顺序表的缺点

  顺序存储结构实现了线性表，虽然顺序表的查询很快，时间复杂度为O(1)，但是 增删的效率是比较低的，因为每一次 增删操作 都伴随着大量的数据元素移动

  这个问题有没有解决方案呢？有，可以使用另外一种存储结构实现线性表，链式存储结构

• 链表

  是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能直观的表示数据元素的逻辑顺序，
  数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

  链表由一系列的 结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成

那我们如何使用链表呢？按照面向对象的思想，我们可以设计一个类，来描述结点这个事物，用一个属性描述这个 结点存储的元素，用另外一个属性描述这个结点的下一个结点

• 结点类实现

public class Node<T> {/*** 存储元素*/public T item;/*** 指向下一个结点*/public Node next;/*** 构造器** @param item* @param next*/public Node(T item, Node next) {this.item = item;this.next = next;}
}

• 生成链表

public static void main(String[] args) {Node<Integer> n1 = new Node<>(11, null);Node<Integer> n2 = new Node<>(13, null);Node<Integer> n3 = new Node<>(15, null);Node<Integer> n4 = new Node<>(18, null);Node<Integer> n5 = new Node<>(9, null);Node<Integer> n6 = new Node<>(5, null);n1.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;n5.next = n6;
}

2）单向链表

单向链表是链表的一种，它由多个结点组成，每个结点都由 一个数据域和一个指针域组成，数据域用来存储数据， 指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向 第一个真正存储数据的结点

1、单向链表API设计

2、代码实现

package chapter03;import java.util.Iterator;/*** @author 土味儿* Date 2021/9/3* @version 1.0* 单向链表*/
public class LinkList<T> implements Iterable<T> {/*** 头结点*/private Node head;/*** 链表长度*/private int n;/*** 构造器*/public LinkList() {// 初始化头结点this.head = new Node(null, null);this.n = 0;}/*** 清空链表*/public void clear() {head.next = null;n = 0;}/*** 获取链表长度** @return*/public int length() {return n;}/*** 判断链表是否为空** @return*/public boolean isEmpty() {return n == 0;}/*** 获取i处的元素** @param i* @return*/public T get(int i) {// 检测i的合法性if (i < 0 || i >= n) {throw new RuntimeException("位置不合法！");}// 遍历链表，找到iNode node = head.next;for (int index = 0; index < i; index++) {node = node.next;}return node.item;}/*** 向链表结尾添加元素** @param t*/public void insert(T t) {// 找到最后结点Node lastNode = head;while (lastNode.next != null) {lastNode = lastNode.next;}// 创建新结点Node newNode = new Node(t, null);// 把最后结点指向新结点lastNode.next = newNode;// 链接数量加1n++;}/*** 向链表中i处添加元素** @param i* @param t*/public void insert(int i, T t) {// 检测参数有效性if (i < 0 || i >= n) {throw new RuntimeException("位置不合法！");}// 找到i处的上一个结点Node preNode = head;for (int index = 0; index < i; index++) {preNode = preNode.next;}// 得到i处的结点Node node = preNode.next;// 创建新结点，并指向i处的结点Node newNode = new Node(t, node);// 把i处的上一个结点指向新结点preNode.next = newNode;// 链表数量加1n++;}/*** 删除链表中i处的元素** @param i* @return*/public T remove(int i) {// 检测参数有效性if (i < 0 || i >= n) {throw new RuntimeException("位置不合法！");}// 找到i处之前的结点Node preNode = head;for (int index = 0; index < i; index++) {preNode = preNode.next;}// 得到i处结点Node node = preNode.next;// 把i处之前的结点 指向 i处的下一个结点preNode.next = node.next;// 链表长度减1n--;return node.item;}/*** 获取元素在链表中首次出现的位置** @param t* @return*/public int indexOf(T t) {// 遍历链表Node node = head;// 循环条件可为：n.next != nullfor (int i = 0; i < n; i++) {if (node.next.item.equals(t)) {return i;}}return -1;}/*** 获取迭代器** @return*/@Overridepublic Iterator<T> iterator() {return new LIterator();}/*** 内部类：迭代器*/private class LIterator implements Iterator {/*** 当前结点*/private Node node;/*** 构造器*/public LIterator() {this.node = head;}/*** 判断当前结点是否有下一个结点* @return*/@Overridepublic boolean hasNext() {return node.next != null;}/*** 得到下一个结点的数据* @return*/@Overridepublic T next() {// 把下一个结点设为当前结点node = node.next;return node.item;}}/*** 内部结点类*/private class Node {// 存储数据T item;// 下一个结点Node next;/*** 构造器** @param item* @param next*/public Node(T item, Node next) {this.item = item;this.next = next;}}
}

@Test
public void test(){LinkList<String> sl = new LinkList<>();//Assert.assertEquals(3,sl.length());sl.insert("姚明");sl.insert("科比");sl.insert("麦迪");sl.insert(1,"詹姆斯");sl.insert("奥尼尔");sl.insert("易建联");for (String s : sl) {System.out.println(s);}System.out.println();System.out.println(sl.get(2));System.out.println(sl.remove(3));sl.clear();System.out.println(sl.length());
}

姚明
詹姆斯
科比
麦迪
奥尼尔
易建联科比
麦迪
0

3）双向链表

双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由 一个数据域 和 两个指针域 组成

数据域用来存储数据，其中一个指针域用来指向其 后继结点，另一个指针域用来指向前驱结点

链表的 头结点 的数据域不存储数据，指向前驱结点的指针域值为 null，指向后继结点的指针域指向第一个真正存储数据的结点

1、结点API设计

2、双向链表API设计

3、代码实现

package chapter03;import java.util.Iterator;/*** @author 土味儿* Date 2021/9/3* @version 1.0* 双向链表*/
public class TwoWayLinkList<T> implements Iterable<T> {/*** 头结点*/private Node head;/*** 尾结点*/private Node last;/*** 链表长度*/private int n;/*** 构造器*/public TwoWayLinkList() {this.head = new Node(null, null, null);this.last = null;this.n = 0;}/*** 清空表*/public void clear() {head.pre = null;head.item = null;head.next = null;last = null;n = 0;}/*** 判断链表是否为空** @return*/public boolean isEmpty() {return n == 0;}/*** 得到链表长度** @return*/public int length() {return n;}/*** 得到i处元素** @param i* @return*/public T get(int i) {// 检测参数合法性if (i < 0 || i >= n) {throw new RuntimeException("位置不合法！");}// 遍历Node node = head.next;for (int index = 0; index < i; index++) {node = node.next;}return node.item;}/*** 向链表尾部插入元素** @param t*/public void insert(T t) {if (isEmpty()) {// 链表为空// 创建新结点Node newNode = new Node(t, head, null);// 让新结点成为尾结点last = newNode;// 让头结点指向尾结点head.next = last;} else {// 链表不为空Node oldLast = last;// 创建新结点Node newNode = new Node(t, oldLast, null);// 让当前尾结点指向新结点oldLast.next = newNode;// 让新结点成为尾结点last = newNode;}// 链表数量加1n++;}/*** 把元素t插入i处** @param i* @param t*/public void insert(int i, T t) {// 检测参数有效性if (i < 0 || i >= n) {throw new RuntimeException("插入位置不合法！");}// 找到i位置的前一个结点Node preNode = head;for (int index = 0; index < i; index++) {preNode = preNode.next;}// 得到i位置的结点Node currentNode = preNode.next;// 创建新结点Node newNode = new Node(t, preNode, currentNode);// 修改i位置的前一个结点的next指针为新结点preNode.next = newNode;// 修改i位置结点的pre指针为新结点currentNode.pre = newNode;// 链接数量加1n++;}/*** 删除i处元素** @param i* @return*/public T remove(int i) {// 检测参数有效性if (i < 0 || i >= n) {throw new RuntimeException("删除位置不合法！");}// 找到i位置的上一个结点Node preNode = head;for (int index = 0; index < i; index++) {preNode = preNode.next;}// 找到i位置结点Node currentNode = preNode.next;// 找到i位置的下一个结点；如果currentNode是最后一个结点，那么nextNode=nullNode nextNode = currentNode.next;// 修改i位置的上一个结点的next指针为 i位置的下一个结点preNode.next = nextNode;// 修改i位置的下一个结点的pre指针为 i位置的上一个结点if (i < n - 1) {// 非尾结点nextNode.pre = preNode;} else {// 尾结点// nextNode是null，nextNode.pre是空指针last = preNode;}// 链表数量减1n--;return currentNode.item;}/*** 得到元素t首次出现的位置** @param t* @return*/public int indexOf(T t) {Node node = head;for (int i = 0; i < n; i++) {if (node.next.item.equals(t)) {return i;}}return -1;}/*** 得到第一个元素（非头结点）** @return*/public T getFirst() {if (isEmpty()) {return null;}return head.next.item;}/*** 得到结尾元素** @return*/public T getLast() {if (isEmpty()) {return null;}return last.item;}@Overridepublic Iterator<T> iterator() {return new TIterator();}/*** 内部结点类*/private class Node {/*** 存储数据*/private T item;/*** 上一个结点*/private Node pre;/*** 下一个结点*/private Node next;/*** 构造器** @param item* @param pre* @param next*/public Node(T item, Node pre, Node next) {this.item = item;this.pre = pre;this.next = next;}}/*** 内部类：迭代器*/private class TIterator implements Iterator {/*** 当前结点*/private Node node;/*** 构造器*/public TIterator() {this.node = head;}/*** 是否有下一个元素** @return*/@Overridepublic boolean hasNext() {return node.next != null;}/*** 得到下一个元素** @return*/@Overridepublic T next() {node = node.next;return node.item;}}
}

@Test
public void test2(){TwoWayLinkList<String> sl = new TwoWayLinkList<>();//Assert.assertEquals(3,sl.length());sl.insert("姚明");sl.insert("科比");sl.insert("麦迪");sl.insert(1,"詹姆斯");sl.insert("奥尼尔");sl.insert("易建联");for (String s : sl) {System.out.println(s);}System.out.println();System.out.println(sl.get(0));System.out.println(sl.remove(0));System.out.println();System.out.println(sl.getFirst());System.out.println(sl.getLast());sl.clear();System.out.println(sl.length());
}

姚明
詹姆斯
科比
麦迪
奥尼尔
易建联姚明
姚明詹姆斯
易建联
0

4、java中LinkedList实现

java中LinkedList集合也是使用 双向链表 实现，并提供了增删改查等相关方法

3）链表复杂度分析

• get(int i)：每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为：O(n)

• insert(int i,T t)：每一次插入，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为：O(n)

• remove(int i)：每一次移除，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为：O(n)

相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的，不需要预先指定存储空间大小，不涉及到 扩容 等操作，同时并没有涉及的元素的 交换
相比较顺序表，链表的查询操作性能会比较低。因此，如果程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表

4）链表反转

单链表的反转，是面试中的一个高频题目

• 需求： 原链表中数据为：1->2->3>4 反转后链表中数据为：4->3->2->1
• 反转API：

• 原理

  使用递归可以完成反转，递归反转其实就是从原链表的第一个存数据的结点开始，依次递归调用反转每一个结点， 直到把最后一个结点反转完毕，整个链表就反转完毕

  反转就是把结点指针的指向进行修改

• 代码实现

	/*** 链表反转*/public void reverse() {// 如果元素为空或只有一个元素时，不用反转if (n < 2) {return;}// 调用重载方法反转reverse(head.next);}/*** 对当前结点进行反转** @param curr* @return 把curr反转后返回*/private Node reverse(Node curr) {// 如果是尾结点，把头结点指向尾结点，并返回if (curr.next == null) {// 头结点指向尾结点head.next = curr;return curr;}//当前结点的上一个结点Node pre = reverse(curr.next);pre.next = curr;//当前结点的下一个结点设为nullcurr.next = null;//返回当前结点return curr;}

@Test
public void test3(){LinkList<String> sl = new LinkList<>();sl.insert("姚明");sl.insert("科比");sl.insert("麦迪");//sl.insert("詹姆斯");//sl.insert("奥尼尔");//sl.insert("易建联");for (String s : sl) {System.out.println(s);}System.out.println("----------------");sl.reverse();for (String s : sl) {System.out.println(s);}
}

姚明
科比
麦迪
----------------
麦迪
科比
姚明

Idea中用debug调试模式，配合F7、F8，仔细分析运行过程，多运行几遍就明白了

5）快慢指针

快慢指针指的是定义两个指针，这两个指针的移动速度一快 一慢，以此来制造出自己想要的差值，这个差值可以让我们找 到链表上相应的结点。一般情况下，快指针的移动步长为慢指针的 两倍

1、中间值问题

• 原理

  利用快慢指针，把一个链表看成一个跑道，假设a的速度是b的 两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间节点的目的

  如下图，最开始，slow与fast指针都指向链表第一个节点，然后slow每次移动一个指针，fast每次移动两个指针

• 代码实现

    /*** 用快慢指针查找中间结点* @return*/public T getMid(){// 定义快慢指针：都指向第一个元素结点Node fast = head.next;Node slow = head.next;// 遍历链表：当快指针到链表最后时，结束while(fast!=null && fast.next!=null){// 快指针每次走两步fast = fast.next.next;// 慢指针每次走一步slow = slow.next;}return slow.item;}

    @Testpublic void testGetMid(){LinkList<String> sl = new LinkList<>();sl.insert("姚明");sl.insert("科比");sl.insert("麦迪");sl.insert("詹姆斯");sl.insert("奥尼尔");//sl.insert("易建联");for (String s : sl) {System.out.println(s);}System.out.println("-----------");System.out.println(sl.getMid());}

姚明
科比
麦迪
詹姆斯
奥尼尔
-----------
麦迪

2、单向链表是否有环问题

• 原理

  使用快慢指针的思想，把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道中，两个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环

• 代码实现

    /*** 判断链表中是否有环* @param first 链表首结点* @return ture为有环，false为无环*/public static boolean isCircle(Node<String> first) {Node<String> slow = first;Node<String> fast = first;// 如果有环，fast永远不会为null，循环内要有出口判断条件while(fast!=null && fast.next!=null){fast = fast.next.next;slow = slow.next;if (fast.equals(slow)){return true;}}return false;}

判断单向链表是否有环另一思路：

遍历链表，如果遍历次数超出链表中元素数量，即为有环；如果遍历次数等于元素数量，且能退出，就是无环；这样只需要遍历一个周期即可；快慢指针在有环时，遍历次数将超过一个周期，因为快指针达到一个周期后，还要再追上慢指针才结束

3、有环链表入口问题

• 原理

  当快慢指针相遇时，可以判断到链表中有环，这时重新设定一个 新指针 指向链表的起点，且步长与慢指针一样为 1，则慢指针与“新”指针 相遇 的地方就是环的入口

  证明这一结论牵涉到数 论的知识，这里略，只讲实现

6）循环链表

循环链表，顾名思义，链表整体要形成一个圆环状。在单向链表中，最后一个节点的指针为null，不指向任何结点，因为没有下一个元素了。要实现循环链表，只需要让单向链表的最后 一个节点的指针指向头结点即可

7）约瑟夫问题

• 问题描述

  传说有这样一个故事，在罗马人占领乔塔帕特后，39个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，从而逃过了这场死亡游戏

• 问题转换

  41个人坐一圈，第一个人编号为1，第二个人编号为2， 第n个人编号为n

  1. 编号为1的人开始从1报数，依次向后，报数为3的那个人退出圈

  2. 自退出那个人开始的下一个人再次从1开始报数，以此类推

  3. 求出最后退出的那个人的编号

• 解题思路

  1. 构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人

  2. 使用计数器count，记录当前报数的值

  3. 遍历链表，每循环一次，count++

  4. 判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0

• 代码实现

package chapter03;import org.junit.Test;/*** @author 土味儿* Date 2021/9/4* @version 1.0* 约瑟夫问题*/
public class JosephTest<T> {@Testpublic void test() {// 1、构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人// 记录首结点Node<Integer> first = null;// 记录上一个结点Node<Integer> pre = null;// 循环构造链表for (int i = 1; i < 42; i++) {// 首结点if (i < 2) {first = new Node<>(i, null);pre = first;// 跳出本次循环continue;}// 中间结点Node<Integer> node = new Node<>(i, null);pre.next = node;pre = node;// 尾结点if (i > 40) {node.next = first;}}// 2、使用计数器count，记录当前报数的值int count = 0;// 3、遍历链表，每循环一次，count++// 当前结点Node<Integer> n = first;// 当前结点的上一个结点Node<Integer> before = null;while (n != n.next) {// 模拟报数count++;// 判断count是否为3if (count == 3) {// 等于3，删除当前结点，打印当前结点，重置count，当前结点后移// 删除当前结点：直接用上一个结点指向下一个结点before.next = n.next;System.out.print(n.item + ",");// 重置countcount = 0;// 当前结点后移n = n.next;} else {// 不等于3，当前结点后移// 把上一个结点后移，记为当前结点before = n;// 当前结点后移n = n.next;}}// 打印最后一个元素System.out.print(n.item);}/*** 内部结点类*/private class Node<T> {/*** 存储数据*/private T item;/*** 下一个结点*/private Node next;/*** 构造器** @param item* @param next*/public Node(T item, Node next) {this.item = item;this.next = next;}}
}

3,6,9,12,15,18,21,24,27,30,33,36,39,1,5,10,14,19,23,28,32,37,41,7,13,20,26,34,40,8,17,29,38,11,25,2,22,4,35,16,31

5.3、栈

1）栈概念

• 生活中的栈

  存储货物或供旅客住宿的地方,可引申为仓库、中转站 。例如现在生活中的酒店，在古时候叫客栈，是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开客栈

• 计算机中的栈

  • 我们把生活中的栈的概念引入到计算机中，就是 供数据休息的地方，它是一种数据结构，数据既可以进入到栈中，又可以从栈中出去
  • 栈是一种基于 先进后出(FILO) 的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）
  • 我们称数据进入到栈的动作为 压栈，数据从栈中出去的动作为 弹栈

2）栈的实现

• API设计

• 代码实现

package chapter03;import java.util.Iterator;/*** @author 土味儿* Date 2021/9/4* @version 1.0* 栈*/
public class Stack<T> implements Iterable<T> {/*** 首结点*/private Node head;/*** 栈内元素个数*/private int n;/*** 构造器*/public Stack() {this.head = new Node(null, null);this.n = 0;}/*** 栈是否为空** @return*/public boolean isEmpty() {return n == 0;}/*** 栈中元素个数** @return*/public int size() {return n;}/*** 压栈** @param t*/public void push(T t) {// 找到首结点指向的第一个结点Node oldFirst = head.next;// 创建新结点Node newNode = new Node(t, null);// 把首结点指向新结点head.next = newNode;// 把新结点指向原来的第一个结点newNode.next = oldFirst;// 元素数量加1n++;}/*** 弹栈** @return*/public T pop() {// 找到首结点指向的第一个结点Node first = head.next;// 把首结点指向第二个结点：判断第一个结点是否存在if (first != null) {head.next = first.next;// 元素数量减1n--;// 返回第一个元素return first.item;}// 空栈，返回nullreturn null;}/*** 迭代器** @return*/@Overridepublic Iterator<T> iterator() {return new SIterator();}/*** 内部类：迭代器* @param*/private class SIterator implements Iterator {private Node node;public SIterator() {this.node = head;}@Overridepublic boolean hasNext() {return node.next != null;}@Overridepublic T next() {node = node.next;return node.item;}}/*** 内部结点类*/private class Node {T item;Node next;public Node(T item, Node next) {this.item = item;this.next = next;}}
}

public class StackTest {@Testpublic void test(){Stack<String> stack = new Stack<>();stack.push("a");stack.push("b");stack.push("c");stack.push("d");for (String s : stack) {System.out.println(s);}System.out.println("--------");System.out.println("弹出："+stack.pop());System.out.println("剩余："+stack.size());System.out.println("--------");for (String s : stack) {System.out.println(s);}}
}

d
c
b
a
--------
弹出：d
剩余：3
--------
c
b
a

3）案例

1、括号匹配问题

一个字符串里边可能包含"()"小括号和其他字符，编写程序检查该字符串的中的小括号是否成对出现
例如：
“(上海)(长安)”：正确匹配
“上海((长安))”：正确匹配
“上海(长安(北京)(深圳)南京)”:正确匹配
“上海(长安))”：错误匹配
“((上海)长安”：错误匹配

• 思路

  1. 创建一个栈用来存储左括号

  2. 从左往右遍历字符串，拿到每一个字符

  3. 判断该字符是不是左括号，如果是，放入栈中存储

  4. 判断该字符是不是右括号，如果不是，继续下一次循环

  5. 如果该字符是右括号，则从栈中弹出一个元素t

  6. 判断元素t是否为null，如果不是，则证明有对应的左括号，如果是，则证明没有对应的左括号

  7. 循环结束后，判断栈中还有没有剩余的左括号，如果有，则不匹配，如果没有，则匹配

• 代码实现

@Test
public void test1(){String str = "(上海)((长安)";boolean match = isMatch(str);System.out.println(str + " 中的括号是否匹配：" + match);
}/**
* 利用栈判断str中的左右括号是否匹配
* @param str
* @return
*/
private boolean isMatch(String str){// 创建一个栈用来存储左括号Stack<String> stack = new Stack<>();// 从左到右遍历字符串，取出每一个字符String s;for(int i=0;i<str.length();i++){s = str.charAt(i)+"";// 判断该字符是不是左括号if("(".equals(s)){// 如果是，压入栈中stack.push(s);}else if(")".equals(s)){// 如果是右括号，则从栈中弹出一个元素String t = stack.pop();// 如果弹出的元素是null，则没有对应的左括号，返回falseif(t==null){return false;}// 弹出的元素不是null，说明有对应的左括号，继续下次循环}// 不是左右括号，继续下次循环}// 循环结束后，判断栈中是否还有多余的左括号，如果有，则不匹配，返回false，反之返回trueif(stack.isEmpty()){return true;}else{return false;}
}

(上海)((长安) 中的括号是否匹配：false

2、逆波兰表达式求值问题

逆波兰表达式求值问题是我们计算机中经常遇到的一类问题， 要研究明白这个问题，首先我们得搞清楚什么是逆波兰表达式？要搞清楚逆波兰表达式，我们得从中缀表达式说起

• 中缀表达式
  • 中缀表达式就是我们平常生活中使用的表达式，例如：1+3*2，2-(1+3)等等
  • 中缀表达式的特点是：二元运算符总是置于两个操作数 中间
  • 中缀表达式是人们最喜欢的表达式方式，因为简单，易懂。但是对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先级相关操作
• 逆波兰表达式 (后缀表达式)
  逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法，后缀表达式的特点：运算符总是放在跟它相关的操作数 之后

• 需求： 给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式，求出该逆波兰表达式的结果

• 分析

  1. 创建一个栈对象oprands存储操作数

  2. 从左往右遍历逆波兰表达式，得到每一个字符串

  3. 判断该字符串是不是运算符，如果不是，把该操作数压入oprands栈中

  4. 如果是运算符，则从oprands栈中弹出两个操作数o1,o2

  5. 使用该运算符计算o1和o2，得到结果result

  6. 把该结果压入oprands栈中

  7. 遍历结束后，拿出栈中最终的结果返回

• 代码实现

public class StackTest {@Testpublic void test2(){// 中缀表达式3*（17-15）+18/6的逆波兰表达式如下：结果9String[] notation = {"3", "17", "15", "-", "*", "18", "6", "/", "+"};int result = caculate(notation);System.out.println("逆波兰表达式的结果为：" + result);}/*** 计算逆波兰表达式的结果* @param notation  逆波兰表达式的数组表示方式* @return*/private int caculate(String[] notation){// 创建一个栈对象存储操作数Stack<Integer> oprands = new Stack<>();// 从左往右遍历逆波兰表达式，得到每一个字符串String curr;Integer o1;Integer o2;for (int i = 0; i < notation.length; i++) {curr = notation[i];switch (curr){case "+":// 是运算符，则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();// 使用该运算符计算o1和o2，得到结果，把结果压入栈中oprands.push(o2 + o1);break;case "-":// 是运算符，则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();// 使用该运算符计算o1和o2，得到结果，把结果压入栈中oprands.push(o2 - o1);break;case "*":// 是运算符，则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();// 使用该运算符计算o1和o2，得到结果，把结果压入栈中oprands.push(o2 * o1);break;case "/":// 是运算符，则从oprands栈中弹出两个操作数o1,o2o1 = oprands.pop();o2 = oprands.pop();// 使用该运算符计算o1和o2，得到结果，把结果压入栈中oprands.push(o2 / o1);break;default:// 不是运算符，把该操作数压入oprands栈中oprands.push(Integer.parseInt(curr));}}// 遍历结束后，拿出栈中最终的结果返回return oprands.pop();}
}

逆波兰表达式的结果为：9

5.4、队列

• 队列是一种基于 先进先出(FIFO) 的数据结构，是一种只能在 一端进行插入，在另一端进行删除操作的特殊线性表，它 按照先进先出的原则存储数据，先进入的数据，在读取数据 时先读被读出来

• API设计

• 代码实现

public class Queue<T> implements Iterable<T> {/*** 首结点*/private Node head;/*** 尾结点*/private Node last;/*** 元素个数*/private int n;/*** 构造器*/public Queue() {this.head = new Node(null, null);this.last = null;this.n = 0;}/*** 判断队列是否为空** @return*/public boolean isEmpty() {return n == 0;}/*** 队列中元素数量** @return*/public int size() {return n;}/*** 向队列中存数据** @param t*/public void enQueue(T t) {if (isEmpty()) {// 队列为空last = new Node(t, null);head.next = last;} else {// 队列不为空Node oldLast = last;last = new Node(t, null);oldLast.next = last;}// 元素数加1n++;}/*** 从队列中取数据** @return*/public T deQueue() {// 队列为空时if (isEmpty()) {return null;}// 不为空时，取第一个，把首结点指向第二个Node oldFirst = head.next;head.next = oldFirst.next;// 取完后判断队列是否为空if (isEmpty()) {last = null;}// 元素数量减1n--;return oldFirst.item;}/*** 迭代器** @return*/@Overridepublic Iterator<T> iterator() {return new QIterator();}/*** 迭代器内部类*/private class QIterator implements Iterator<T> {Node node;public QIterator() {this.node = head;}@Overridepublic boolean hasNext() {return node.next != null;}@Overridepublic T next() {node = node.next;return node.item;}}/*** 结点内部类*/private class Node {T item;Node next;public Node(T item, Node next) {this.item = item;this.next = next;}}
}

public class QueueTest {@Testpublic void test() {Queue<String> queue = new Queue<>();queue.enQueue("a");queue.enQueue("b");queue.enQueue("c");queue.enQueue("d");for (Object q : queue) {System.out.println(q);}System.out.println("------------");String s = queue.deQueue();System.out.println("出队列的元素是：" + s);System.out.println("队列数量：" + queue.size());}
}

a
b
c
d
------------
出队列的元素是：a
队列数量：3

6、符号表

符号表最主要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值

符号表中，键具有唯一性

符号表在实际生活中的使用场景是非常广泛的，见下表：

6.1、符号表API设计

6.2、符号表实现

package chapter04;/*** @author 土味儿* Date 2021/9/6* @version 1.0* 符号表*/
public class SymbolTable<K, V> {/*** 首结点*/private Node head;/*** 元素数量*/private int n;/*** 构造器*/public SymbolTable() {this.head = new Node(null, null, null);this.n = 0;}/*** 获取key对应value** @param key* @return*/public V get(K key) {Node node = head;while (node.next != null) {node = node.next;if (node.key.equals(key)) {return node.value;}}return null;}/*** 向符号表中存入链值对** @param key* @param value*/public void put(K key, V value) {// 如果表中已有键为key的结点，替换值value即可Node node = head;while (node.next != null) {// 移动node指针node = node.next;// 判断if (node.key.equals(key)) {node.value = value;return;}}// 如果表中没有键为key的结点，创建结点，并放入表的前面（也可以放在表的结尾，实现较麻烦），元素数量加1Node oldFirst = head.next;Node newNode = new Node(key, value, oldFirst);head.next = newNode;n++;}/*** 删除key的键值对** @param key*/public void delete(K key) {Node node = head;while (node.next != null) {// 判断结点node的下一个结点的键是否与key相等if (node.next.key.equals(key)) {// 相等；把node的next指向下下一个结点node.next = node.next.next;// 元素数量减1n--;return;}// 移动node批针node = node.next;}}/*** 获取元素数量** @return*/public int size() {return n;}/*** 内部结点类*/private class Node {private K key;private V value;private Node next;public Node(K key, V value, Node next) {this.key = key;this.value = value;this.next = next;}}
}

package chapter03;import chapter04.SymbolTable;
import org.junit.Test;/*** @author 土味儿* Date 2021/9/6* @version 1.0* 测试符号表*/
public class SymbolTableTest {@Testpublic void test(){SymbolTable<Integer, String> st = new SymbolTable<>();st.put(1, "a");st.put(3, "b");st.put(5, "c");System.out.println(st.size());st.put(1,"a1");System.out.println(st.get(1));System.out.println(st.size());st.delete(1);System.out.println(st.size());}
}

3
a1
3
2

6.3、有序符号表

前面的符号表称之为无序符号表，因为在插入的时候，并没有考虑键值对的顺序，而在实际生活 中，有时需要根据键的大小进行排序，插入数据时要考虑顺序，那么接下来就实现一下有序符号表

• 代码实现

package chapter04;/*** @author 土味儿* Date 2021/9/6* @version 1.0* 有序符号表* 插入时按key排序*/
public class OrderSymbolTable<K extends Comparable<K>, V> {/*** 首结点*/private Node head;/*** 元素数量*/private int n;/*** 构造器*/public OrderSymbolTable() {this.head = new Node(null, null, null);this.n = 0;}/*** 获取key对应value** @param key* @return*/public V get(K key) {Node node = head;while (node.next != null) {node = node.next;if (node.key.equals(key)) {return node.value;}}return null;}/*** 向符号表中存入链值对** @param key* @param value*/public void put(K key, V value) {// 记录当前结点Node curr = head.next;// 记录上一个结点Node pre = head;// 遍历符号表，跳过比key小的结点while (curr != null && curr.key.compareTo(key) < 0) {pre = curr;curr = curr.next;}// 跳过比key小的结点后，下面就是等于key，或大于key的结点// 等于key时，替换掉value，并返回if (curr != null && curr.key.compareTo(key) == 0) {curr.value = value;return;}// 大于key时，创建新结点，插入到当前结点前面，元素数量加1Node newNode = new Node(key, value, curr);pre.next = newNode;n++;}/*** 删除key的键值对** @param key*/public void delete(K key) {Node node = head;while (node.next != null) {// 判断结点node的下一个结点的键是否与key相等if (node.next.key.equals(key)) {// 相等；把node的next指向下下一个结点node.next = node.next.next;// 元素数量减1n--;return;}// 移动node批针node = node.next;}}/*** 获取元素数量** @return*/public int size() {return n;}/*** 内部结点类*/private class Node {private K key;private V value;private Node next;public Node(K key, V value, Node next) {this.key = key;this.value = value;this.next = next;}}
}

public class SymbolTableTest {@Testpublic void testOrderSymbolTable(){OrderSymbolTable<Integer, String> st = new OrderSymbolTable<>();st.put(1,"张三");st.put(2,"李四");st.put(4,"赵六");st.put(5,"四七");st.put(3,"王五");}
}

这篇关于【数据结构与算法】第五、六章：线性表（顺序表、链表、栈、队列）符号表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---