个人简约网站模板,做网站 能挣钱吗,慧聪网登录,抖音推广计划*************************************优雅的分割线 **********************************
分享一波:程序员赚外快-必看的巅峰干货
如果以上内容对你觉得有用,并想获取更多的赚钱方式和免费的技术教程
请关注微信公众号:HB荷包 一个能让你学习技术和赚钱方法的公众号,持续更…*************************************优雅的分割线 **********************************
分享一波:程序员赚外快-必看的巅峰干货
如果以上内容对你觉得有用,并想获取更多的赚钱方式和免费的技术教程
请关注微信公众号:HB荷包 一个能让你学习技术和赚钱方法的公众号,持续更新 *************************************优雅的分割线 ********************************** SimpleExecutor
五、线性表
线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列
前驱元素 若A元素在B元素的前面则称A为B的前驱元素
后继元素 若B元素在A元素的后面则称B为A的后继元素
线性表的特征
第一个数据元素没有前驱这个数据元素被称为头结点最后一个数据元素没有后继这个数据元素被称为尾结点除了第一个和最后一个数据元素外其他数据元素有且仅有一个前驱和一个后继。
如果把线性表用数学语言来定义则可以表示为(a1,…ai-1,ai,ai1,…an)ai-1领先于ai,ai领先于ai1称ai-1是ai的 前驱元素ai1是ai的后继元素 线性表的分类
线性表中数据存储的方式可以是顺序存储也可以是链式存储按照数据的存储方式不同可以把线性表分为顺序 表和链表。
5.1 顺序表☆
顺序表是在计算机内存中以数组的形式保存的线性表线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中再逻辑结构上相邻的数据元素存储在相邻的物理存储单元中即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。 5.1.1 顺序表的实现
API设计
类名SequenceList构造方法SequenceList(int capacity)创建容量为capacity的SequenceList对象成员方法1. public void clear()空置线性表2. publicboolean isEmpty()判断线性表是否为空是返回true否返回false3. public int length():获取线性表中元素的个数4. public T get(int i):读取并返回线性表中的第i个元素的值5. public void insert(int i,T t)在线性表的第i个元素之前插入一个值为t的数据元素。6. public void insert(T t):向线性表中添加一个元素t7. public T remove(int i):删除并返回线性表中第i个数据元素。8. public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号若不存在则返回-1成员变量1. private T[] eles存储元素的数组2. private int N:当前线性表的长度
代码实现
public class SequenceList {/*** 存储元素的数组*/private String[] eles;/*** 当前线性表元素的个数*/private int n;public SequenceList(int capacity) {// 构造一个长度为capacity的顺序表eles new String[capacity];n 0;}/*** 置空线性表*/public void clear() {n 0;// 将数据整个置空eles new String[eles.length];}/*** 判断线性表是否为空** return*/public boolean isEmpty() {return n 0;}/*** 获取线性表中元素个数** return*/public int length() {return n;}/*** 读取并返回线性表中的第index个元素的值** param index* return*/public String get(int index) {// 判断一下下标是否合法if (index 0 || index n) {System.err.println(当前元素不存在);return null;}return eles[index];}/*** 在线性表的第i个元素之前插入一个值为t的数据元素** param index* param v*/public void insert(int index, String v) {if (n eles.length) {System.err.println(当前表已满);return;}if (index eles.length) {System.err.println(下标位置非法);return;}// 判断一下i是否合法if (index 0 || index n) {System.err.println(下标位置非法);return;}// 把index位置空出来index位置以及后面的元素依次向后移动一位for (int i n; i index; i--) {eles[i] eles[i - 1];}// 把v放到index处eles[index] v;n;}/*** 向线性表中添加一个元素t** param v*/public void insert(String v) {// 判断一下元素个数是否已经超过了数组的最大容量if (n eles.length) {System.err.println(当前表已满);return;}eles[n] v;}/*** 删除并返回线性表中第index个元素** param index* return*/public String remove(int index) {if (index 0 || index n) {System.out.println(当前要删除的元素不存在);return null;}// 获取要删除的元素String result eles[index];// 把index后面的元素都向前移动一格for (int i index; i n - 1; i) {eles[i] eles[i 1];}// 元素个数-1n--;return result;}/*** 返回线性表中首次出现的指定的元素数据的索引** param v* return*/public int indexOf(String v) {return 0;}}class Test1 {public static void main(String[] args) {SequenceList list new SequenceList(10);list.insert(刘备);list.insert(张飞);list.insert(关羽);list.insert(曹操);System.out.println(list.get(2));System.out.println(list.remove(0));System.out.println(list.get(0));list.clear();System.out.println(list.length());}
}5.1.2 可变容量的顺序表
在之前的实现中当我们使用SequenceList时先new SequenceList(5)创建一个对象创建对象时就需要指定容 器的大小初始化指定大小的数组来存储元素当我们插入元素时如果已经插入了5个元素还要继续插入数 据则会报错就不能插入了。这种设计不符合容器的设计理念因此我们在设计顺序表时应该考虑它的容量的 伸缩性。
考虑容器的容量伸缩性其实就是改变存储数据元素的数组的大小那我们需要考虑什么时候需要改变数组的大 小
1.添加元素时
添加元素时应该检查当前数组的大小是否能容纳新的元素如果不能容纳则需要创建新的容量更大的数组我 们这里创建一个是原数组两倍容量的新数组存储元素 2.移除元素时
移除元素时应该检查当前数组的大小是否太大比如正在用100个容量的数组存储10个元素这样就会造成内存 空间的浪费应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4则创建一个是原数组容量的1/2的新数组存储元素。 顺序表的容量可变代码
public class SequenceList2 {/*** 存储元素的数组*/private String[] eles;/*** 当前线性表元素的个数*/private int n;public SequenceList2(int capacity) {// 如果传入的个数小于1则默认为1if(capacity 1) {capacity 1;}// 构造一个长度为capacity的顺序表eles new String[capacity];n 0;}/*** 置空线性表*/public void clear() {n 0;// 将数据整个置空eles new String[eles.length];}/*** 判断线性表是否为空** return*/public boolean isEmpty() {return n 0;}/*** 获取线性表中元素个数** return*/public int length() {return n;}/*** 读取并返回线性表中的第index个元素的值** param index* return*/public String get(int index) {// 判断一下下标是否合法if (index 0 || index n) {System.err.println(当前元素不存在);return null;}return eles[index];}/*** 在线性表的第i个元素之前插入一个值为t的数据元素** param index* param v*/public void insert(int index, String v) {// 判断一下i是否合法if (index 0 || index n) {System.err.println(下标位置非法);return;}if (n eles.length) {resize(eles.length * 2);}// 把index位置空出来index位置以及后面的元素依次向后移动一位for (int i n; i index; i--) {eles[i] eles[i - 1];}// 把v放到index处eles[index] v;n;}/*** 向线性表中添加一个元素t** param v*/public void insert(String v) {// 判断一下元素个数是否已经超过了数组的最大容量if (n eles.length) {resize(eles.length * 2);}eles[n] v;}/*** 删除并返回线性表中第index个元素** param index* return*/public String remove(int index) {if (index 0 || index n) {System.out.println(当前要删除的元素不存在);return null;}// 获取要删除的元素String result eles[index];// 把index后面的元素都向前移动一格for (int i index; i n - 1; i) {eles[i] eles[i 1];}// 元素个数-1n--;// 判断一下当前元素数量已经不足数组大小的1/4则重置数组大小if (n 0 n eles.length / 4) {resize(eles.length / 2);}return result;}/*** 将现有的数组改变为容量为newSize的新数组** param newSize*/private void resize(int newSize) {// 记录旧数组String[] temp eles;// 创建新数组eles new String[newSize];// 把就旧组中的元素拷贝到新数组for (int i 0; i n; i) {eles[i] temp[i];}}/*** 返回线性表中首次出现的指定的元素数据的索引** param v* return*/public int indexOf(String v) {return 0;}}class Test2 {public static void main(String[] args) {SequenceList2 list new SequenceList2(0);list.insert(刘备);System.out.println(list.length());list.insert(张飞);System.out.println(list.length());list.insert(关羽);System.out.println(list.length());list.insert(曹操);System.out.println(list.length());}
}5.1.3 时间复杂度
get(i):不难看出不论数据元素量N有多大只需要一次eles[i]就可以获取到对应的元素所以时间复杂度为O(1); insert(int i,T t):每一次插入都需要把i位置后面的元素移动一次随着元素数量N的增大移动的元素也越多时间复杂为O(n);
remove(int i):每一次删除都需要把i位置后面的元素移动一次随着数据量N的增大,移动的元素也越多时间复杂度为O(n);
由于顺序表的底层由数组实现数组的长度是固定的所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的在某些需要扩容的结点处耗时会突增尤其是元素越多这个问题越明显
5.2 链表☆
之前我们已经使用顺序存储结构实现了线性表我们会发现虽然顺序表的查询很快时间复杂度为O(1),但是增删的效率是比较低的因为每一次增删操作都伴随着大量的数据元素移动。这个问题有没有解决方案呢有我们可以使用另外一种存储结构实现线性表链式存储结构。
链表是一种物理存储单元上非连续、非顺序的存储结构其物理结构不能直观的表示数据元素的逻辑顺序数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点链表中的每一个元素称为结点组成结点可以在运行时动态生成。 那我们如何使用链表呢按照面向对象的思想我们可以设计一个类来描述结点这个事物用一个属性描述这个 结点存储的元素用另外一个属性描述这个结点的下一个结点。
节点API设计
类名Node构造方法Node(T t,Node next)创建Node对象成员变量T item:存储数据Node next指向下一个结点
代码实现
public static class Node {public String item;public Node next;public Node(String item, Node next) {this.item item;this.next next;}
}5.2.1 单向链表
单向链表是链表的一种它由多个结点组成每个结点都由一个数据域和一个指针域组成数据域用来存储数据 指针域用来指向其后继结点。链表的头结点的数据域不存储数据指针域指向第一个真正存储数据的结点。 API设计
类名LinkList构造方法LinkList()创建LinkList对象成员方法1. public void clear()空置线性表2. publicboolean isEmpty()判断线性表是否为空是返回true否返回false3. public int length():获取线性表中元素的个数4. public T get(int i):读取并返回线性表中的第i个元素的值5. public void insert(T t)往线性表中添加一个元素6. public void insert(int i,T t)在线性表的第i个元素之前插入一个值为t的数据元素。7. public T remove(int i):删除并返回线性表中第i个数据元素。8. public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号若不存在则返回-1。成员内部类private class Node:结点类成员变量1. private Node head:记录首结点2. private int N:记录链表的长度
代码实现
public class LinkList {/*** 记录首结点*/private Node head;/*** 链表长度*/private int n;public LinkList() {// 初始化链表n 0;head new Node(null, null);}/*** 置空线性表*/public void clear() {head.item null;head.next null;n 0;}/*** 判断线性表是否为空** return*/public boolean isEmpty() {return n 0;}/*** 获取线性表中元素个数** return*/public int length() {return n;}/*** 读取并返回线性表中的第index个元素的值** param index* return*/public String get(int index) {if (index 0 || index n) {System.out.println(下标不合法);return null;}// 获取第一个元素节点Node item head.next;for (int i 0; i index; i) {item item.next;}return item.item;}/*** 在线性表的第i个元素之前插入一个值为t的数据元素** param index* param v*/public void insert(int index, String v) {if(index0||indexn) {System.out.println(位置不合法);return;}// 寻找index之前的节点// pre是我们要插入元素位置的上一个节点Node pre head;for (int i 0; i index; i) {// 取出下一个元素赋值给prepre pre.next;}// 到这里插入下标的上一个节点就找到了// 取出index下一个位置的元素Node next pre.next;// 构建新的NodeNode newNode new Node(v, next);pre.next newNode;// 长度1n;}/*** 向线性表中添加一个元素t** param v*/public void insert(String v) {// 找到最后一个节点Node node head;// 只要node的下一个节点不为null说明还有下一个元素while (node.next ! null) {node node.next;}// 到这里node就是最后一个节点// 创建一个新的节点Node newNode new Node(v, null);// 直接将最后一个节点的下一个结点指向新结点node.next newNode;// 链表长度1n;}/*** 删除并返回线性表中第index个元素** param index* return*/public String remove(int index) {if(index 0 || index n) {System.out.println(下标位置不合法);return null;}// 寻找index之前的元素Node pre head;for (int i 0; i index; i) {// 取出下一个元素赋值给prepre pre.next;}// 到这里就找到了之前的元素// 获取当前index位置的结点Node current pre.next;// 获取当前index位置的下一个节点Node next current.next;// 前一个节点指向下一个节点pre.next next;// 长度-1n--;return current.item;}/*** 返回线性表中首次出现的指定的元素数据的索引** param v* return*/public int indexOf(String v) {return 0;}private class Node {public String item;public Node next;public Node(String item, Node next) {this.item item;this.next next;}}
}class Test3 {public static void main(String[] args) {LinkList list new LinkList();list.insert(刘备);System.out.println(list.get(0));list.insert(关羽);System.out.println(list.get(1));list.insert(0, 张飞);System.out.println(list.get(0)list.get(1));System.out.println(list.remove(1));System.out.println(list.get(1));System.out.println(list.length());list.clear();System.out.println(list.length());System.out.println(list.isEmpty());}
}5.2.2 双向链表
双向链表也叫双向表是链表的一种它由多个结点组成每个结点都由一个数据域和两个指针域组成数据域用 来存储数据其中一个指针域用来指向其后继结点另一个指针域用来指向前驱结点。链表的头结点的数据域不存 储数据指向前驱结点的指针域值为null指向后继结点的指针域指向第一个真正存储数据的结点 按照面向对象的思想我们需要设计一个类来描述结点这个事物。由于结点是属于链表的所以我们把结点类作 为链表类的一个内部类来实现
节点API 设计
类名Node构造方法Node(T t,Node pre,Node next)创建Node对象成员变量T item:存储数据Node next指向下一个结点Node pre:指向上一个结点
双向链表API设计
类名TowWayLinkList构造方法TowWayLinkList()创建TowWayLinkList对象成员方法1. public void clear()空置线性表2. public boolean isEmpty()判断线性表是否为空是返回true否返回false3. public int length():获取线性表中元素的个数4. public T get(int i):读取并返回线性表中的第i个元素的值5. public void insert(T t)往线性表中添加一个元素6. public void insert(int i,T t)在线性表的第i个元素之前插入一个值为t的数据元素。7. public T remove(int i):删除并返回线性表中第i个数据元素。8. public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号若不存在则返回-1。9. public T getFirst():获取第一个元素10. public T getLast():获取最后一个元素成员内部类private class Node:结点类成员变量1.private Node first:记录首结点2.private Node last:记录尾结点3.private int N:记录链表的长度
代码实现
public class TowWayLinkList {/*** 记录首结点*/private Node first;/*** 记录尾结点*/private Node last;/*** 链表长度*/private int n;public TowWayLinkList() {last null;first new Node(null, null, null);n 0;}/*** 置空线性表*/public void clear() {last null;first.next null;first.item null;first.pre null;n 0;}/*** 判断线性表是否为空** return*/public boolean isEmpty() {return n 0;}/*** 获取线性表中元素个数** return*/public int length() {return n;}/*** 读取并返回线性表中的第index个元素的值** param index* return*/public String get(int index) {if (index 0 || index n) {System.out.println(下标不合法);return null;}// 获取第一个元素节点Node item first.next;for (int i 0; i index; i) {item item.next;}return item.item;}/*** 在线性表的第i个元素之前插入一个值为t的数据元素** param index* param v*/public void insert(int index, String v) {if (index 0 || index n) {System.out.println(下标不合法);return;}// 获取头结点Node pre first;for (int i 0; i index; i) {pre pre.next;}// 到这里之后我们就找到了待插入下标位置的前一个元素Node next pre.next;// 构建一个新的节点Node newNode new Node(v, pre, next);pre.next newNode;next.pre newNode;// 长度1n;}/*** 向线性表中添加一个元素t** param v*/public void insert(String v) {if (last null) {// 如果last为空说明链表刚被初始化// 那么第一个元素就是lastlast new Node(v, first, null);first.next last;} else {// 说明链表已经有了元素Node oldLast last;Node node new Node(v, oldLast, null);oldLast.next node;last node;}// 长度1n;}/*** 删除并返回线性表中第index个元素** param index* return*/public String remove(int index) {if (index 0 || index n) {System.out.println(下标不合法);return null;}// 获取头结点Node pre first;for (int i 0; i index; i) {pre pre.next;}// 到这里pre就是我们要删除下标位置的前一个节点// 获取待删除的当前节点Node current pre.next;// 获取待删除节点的下一个节点Node next current.next;pre.next next;next.pre pre;// 长度-1n--;return current.item;}/*** 获取第一个元素** return*/public String getFirst() {if (isEmpty()) {return null;}return first.next.item;}/*** 获取最后一个元素** return*/public String getLast() {if (isEmpty()) {return null;}return last.item;}/*** 返回线性表中首次出现的指定的元素数据的索引** param v* return*/public int indexOf(String v) {return 0;}private class Node {public String item;/*** 指向下一个节点*/public Node next;/*** 指向上一个节点*/public Node pre;public Node(String item, Node pre, Node next) {this.item item;this.pre pre;this.next next;}}
}class Test4 {public static void main(String[] args) {TowWayLinkList list new TowWayLinkList();list.insert(刘备);System.out.println(list.get(0));list.insert(关羽);System.out.println(list.get(1));list.insert(0, 张飞);System.out.println(list.get(0)list.get(1));System.out.println(list.remove(1));System.out.println(list.get(1));System.out.println(list.length());list.clear();System.out.println(list.length());System.out.println(list.isEmpty());}
}5.2.3 时间复杂度
get(int i):每一次查询都需要从链表的头部开始依次向后查找随着数据元素N的增多比较的元素越多时间 复杂度为O(n)
insert(int i,T t):每一次插入需要先找到i位置的前一个元素然后完成插入操作随着数据元素N的增多查找的 元素越多时间复杂度为O(n);
remove(int i):每一次移除需要先找到i位置的前一个元素然后完成插入操作随着数据元素N的增多查找的元素越多时间复杂度为O(n)
相比较顺序表链表插入和删除的时间复杂度虽然一样但仍然有很大的优势因为链表的物理地址是不连续的 它不需要预先指定存储空间大小或者在存储过程中涉及到扩容等操作,同时它并没有涉及的元素的交换。
相比较顺序表链表的查询操作性能会比较低。因此如果我们的程序中查询操作比较多建议使用顺序表增删 操作比较多建议使用链表。
结论链表的查询性能比数组顺序表低但是增删比数组高。其实在我们使用的过程中链表的使用频率是相当低的因为只要我们尽可能的避免了顺序表的扩容并且保证每次插入都是在顺序表最后一位插入那么顺序表的增删操作性能也比链表要高
5.2.4 单链表反转☆ 需求
原链表中数据为1-2-34
反转后链表中数据为4-3-2-1
API设计
方法作用public void reverse()对整个链表反转public Node reverse(Node curr)反转链表中的某个结点curr,并把反转后的curr结点返回
使用递归可以完成反转递归反转其实就是从原链表的第一个存数据的结点开始依次递归调用反转每一个结点 直到把最后一个结点反转完毕整个链表就反转完毕。 代码
public class LinkList2 {/*** 记录首结点*/private Node head;/*** 链表长度*/private int n;public LinkList2() {// 初始化链表n 0;head new Node(null, null);}/*** 置空线性表*/public void clear() {head.item null;head.next null;n 0;}/*** 判断线性表是否为空** return*/public boolean isEmpty() {return n 0;}/*** 获取线性表中元素个数** return*/public int length() {return n;}/*** 读取并返回线性表中的第index个元素的值** param index* return*/public String get(int index) {if (index 0 || index n) {System.out.println(下标不合法);return null;}// 获取第一个元素节点Node item head.next;for (int i 0; i index; i) {item item.next;}return item.item;}/*** 在线性表的第i个元素之前插入一个值为t的数据元素** param index* param v*/public void insert(int index, String v) {if (index 0 || index n) {System.out.println(位置不合法);return;}// 寻找index之前的节点// pre是我们要插入元素位置的上一个节点Node pre head;for (int i 0; i index; i) {// 取出下一个元素赋值给prepre pre.next;}// 到这里插入下标的上一个节点就找到了// 取出index下一个位置的元素Node next pre.next;// 构建新的NodeNode newNode new Node(v, next);pre.next newNode;// 长度1n;}/*** 向线性表中添加一个元素t** param v*/public void insert(String v) {// 找到最后一个节点Node node head;// 只要node的下一个节点不为null说明还有下一个元素while (node.next ! null) {node node.next;}// 到这里node就是最后一个节点// 创建一个新的节点Node newNode new Node(v, null);// 直接将最后一个节点的下一个结点指向新结点node.next newNode;// 链表长度1n;}/*** 删除并返回线性表中第index个元素** param index* return*/public String remove(int index) {if (index 0 || index n) {System.out.println(下标位置不合法);return null;}// 寻找index之前的元素Node pre head;for (int i 0; i index; i) {// 取出下一个元素赋值给prepre pre.next;}// 到这里就找到了之前的元素// 获取当前index位置的结点Node current pre.next;// 获取当前index位置的下一个节点Node next current.next;// 前一个节点指向下一个节点pre.next next;// 长度-1n--;return current.item;}/*** 返回线性表中首次出现的指定的元素数据的索引** param v* return*/public int indexOf(String v) {return 0;}/*** 对整个链表进行翻转*/public void reverse() {if (n 0) {// 空链表不翻转return;}reverse(head.next);}/*** 翻转链表中某个节点并返回当前节点** param current* return*/private Node reverse(Node current) {// 判断一下当前节点是否是最后一个节点if (current.next null) {// 说明当前节点是最后一个节点// 最后一个节点需要让头节点指向它head.next current;return current;}// 如果不是最后一个节点翻转下一个节点Node next reverse(current.next);next.next current;// 当前节点的下一个节点设为nullcurrent.next null;return current;}private class Node {public String item;public Node next;public Node(String item, Node next) {this.item item;this.next next;}}
}class Test5 {public static void main(String[] args) {LinkList2 list2 new LinkList2();list2.insert(刘备);list2.insert(关羽);list2.insert(张飞);System.out.println(list2.get(0) list2.get(1) list2.get(2));list2.reverse();System.out.println(list2.get(0) list2.get(1) list2.get(2));}
}5.2.5 循环链表
循环链表顾名思义链表整体要形成一个圆环状。在单向链表中最后一个节点的指针为null不指向任何结 点因为没有下一个元素了。要实现循环链表我们只需要让单向链表的最后一个节点的指针指向头结点即可。 循环链表的构建
public class ForList {public static void main(String[] args) {Node n1 new Node(1, null);Node n2 new Node(2, null);Node n3 new Node(3, null);Node n4 new Node(4, null);Node n5 new Node(5, null);// 构造循环链表n1.next n2;n2.next n3;n3.next n4;n4.next n5;n5.next n1;}private static class Node {public String item;public Node next;public Node(String item, Node next) {this.item item;this.next next;}}
}5.2.6 快慢指针
快慢指针指的是定义两个指针这两个指针的移动速度一块一慢以此来制造出自己想要的差值这个差值可以然 我们找到链表上相应的结点。一般情况下快指针的移动步长为慢指针的两倍
5.2.6.1 中间值问题
找出链表的中间元素值并返回。
利用快慢指针我们把一个链表看成一个跑道假设a的速度是b的两倍那么当a跑完全程后b刚好跑一半以 此来达到找到中间节点的目的。
如下图最开始slow与fast指针都指向链表第一个节点然后slow每次移动一个指针fast每次移动两个指针。 代码 private static int getMid(Node node) {// 给一个快指针Node fast node;// 给一个慢指针Node slow node;// 遍历链表移动指针while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}return slow.item;}5.2.6.2 单链表有环问题
单链表有环问题和循环链表是两码事。
循环链表是我们为了解决某个问题而给出的解决方案。
而单链表有环问题则是我们在使用链表的过程中失误操作锁带来的bug。 使用快慢指针的思想还是把链表比作一条跑道链表中有环那么这条跑道就是一条圆环跑道在一条圆环跑道 中两个人有速度差那么迟早两个人会相遇只要相遇那么就说明有环。 /*** 判断当前链表是否有环** param node* return*/public static boolean isCircle(Node node) {Node slow node;Node fast node;// 遍历while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if(fast slow) { return true;}}return false;}5.2.6.3 有环链表入口问题
查找有环链表中环的入口结点。
当快慢指针相遇时我们可以判断到链表中有环这时重新设定一个新指针指向链表的起点且步长与慢指针一样 为1则慢指针与“新”指针相遇的地方就是环的入口。 /*** 获取有环链表的环入口返回入口值** param node* return*/public static int getEnter(Node node) {Node slow node;Node fast node;// 定义一个新指针Node temp null;// 遍历链表while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if(fast slow) {// 说明两个指针相遇了有环新指针开始移动temp node;continue;}if(temp!null) {// temp不为空说明新指针已经开始移动了temp temp.next;// 判断一下新指针与慢指针是否相等如相遇则是环起点if(temp slow) {return temp.item;}}}return 0;}5.2.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
public class Joseph {public static void main(String[] args) {// 构建循环链表Node first new Node(1, null);// 记录前一个节点Node pre first;// 构造一个41节点的循环链表for (int i 2; i 41; i) {// 每一次循环构建一个NodeNode node new Node(i, null);pre.next node;// 记录当前节点为上一个节点pre node;if (i 41) {// 说明到最后了让最后一个节点指向第一个节点pre.next first;}}// 计数器countint count 0;// 遍历链表每次循环countNode n first;// 记录上一个节点Node back null;// 循环链表while (n ! n.next) {// 报数count;// 判断count是否为3如果是删除当前节点if (count 3) {back.next n.next;System.out.println(当前死亡的人 n.item);// 计数器清零count 0;// 下一个人继续n n.next;} else {// 记录上一个节点back n;// 下一个人继续n n.next;}}}private static class Node {public int item;public Node next;public Node(int item, Node next) {this.item item;this.next next;}}}5.3 栈
5.3.1 栈概述
栈是一种基于先进后出(FILO)的数据结构是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出 的原则存储数据先进入的数据被压入栈底压栈/入栈最后的数据在栈顶需要读数据的时候从栈顶开始弹出数据弹栈/出栈最后一 个数据被第一个读出来。
我们称数据进入到栈的动作为压栈数据从栈中出去的动作为弹栈 5.3.2 栈的实现
api设计
类名Stack构造方法Stack()创建Stack对象成员方法1. public boolean isEmpty()判断栈是否为空是返回true否返回false2. public int size():获取栈中元素的个数3. public T pop():弹出栈顶元素4. public void push(T t)向栈中压入元素t成员变量1. private Node head:记录首结点2. private int N:当前栈的元素个数
public class Stack {/*** 首结点*/private Node head;/*** 栈中元素个数*/private int n;public Stack() {// 初始化栈head new Node(null, null);n 0;}/*** 判断栈是否为空** return*/public boolean isEmpty() {return n 0;}/*** 获取栈中元素的个数** return*/public int size() {return n;}/*** 弹栈** return*/public String pop() {// 记录第一个元素Node oldFirst head.next;if (oldFirst null) {return null;}// 删除首个元素head.next head.next.next;// 个数-1n--;return oldFirst.item;}/*** 压栈** param t*/public void push(String t) {// 记录旧的下一个节点Node oldNext head.next;// 创建新的节点Node node new Node(t, oldNext);// 个数1n;// 新的节点连接到head的下一个节点head.next node;}private class Node {public String item;public Node next;public Node(String item, Node next) {this.item item;this.next next;}}
}class Test6 {public static void main(String[] args) {Stack stack new Stack();stack.push(a);stack.push(b);stack.push(c);stack.push(d);System.out.println(stack.size());System.out.println(stack.pop());System.out.println(stack.size());System.out.println(stack.isEmpty());stack.pop();stack.pop();stack.pop();System.out.println(stack.isEmpty());System.out.println(stack.size());}
}5.3.3 括号匹配案例
给定一个字符串里边可能包含()小括号和其他字符请编写程序检查该字符串的中的小括号是否成对出现。 左括号数量右括号数量?
例如
“(上海)(长安)”正确匹配
“上海((长安))”正确匹配
“上海(长安(北京)(深圳)南京)”:正确匹配
“上海(长安))”错误匹配
“((上海)长安”错误匹配**
分析
创建一个栈用来存储左括号从左往右遍历字符串拿到每一个字符判断该字符是不是左括号如果是放入栈中存储判断该字符是不是右括号如果不是继续下一次循环如果该字符是右括号则从栈中弹出一个元素t判断元素t是否为null如果不是null则证明有对应的左括号如果是null则证明没有对应的左括号循环结束后判断栈中还有没有剩余的左括号如果有则不匹配如果没有则匹配
代码
class Test7 {public static void main(String[] args) {// 待匹配括号的字符串String str (哈哈(发的(官方)发给我个( 发(发(更好)发(功德符(发顺丰的( 跟我说)(阿发) 吧)ad发)不是是)) GV) 发;boolean isMatch matchBrackets(str);System.out.println(匹配字符串括号结果 isMatch);}/*** 判断str中左右括号是否匹配** param str 待匹配的字符串* return*/private static boolean matchBrackets(String str) {// 1. 创建一个栈来存储左括号Stack stack new Stack();// 2. 从右往右遍历字符串拿到每一个字符for (int i 0; i str.length(); i) {// 拿到每一个字符串String currentChar str.charAt(i) ;// 3.判断该字符串是不是左括号如果是则放入栈中if (currentChar.equals(()) {stack.push(currentChar);// 4. 判断该字符串是否是右括号如果是从栈中弹出一个元素t} else if (currentChar.equals())) {String t stack.pop();// 判断t是否为null。如果为null说明没有左括号匹配否则有左括号匹配if (t null) {return false;}// 如果不是继续下一个循环}}// 循环完毕之后判断栈中是否还有剩余的左括号如果有说明不匹配如果没有则匹配if (stack.size() 0) {return true;} else {return false;}}
}5.4 队列
队列是一种基于先进先出(FIFO)的数据结构是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表它 按照先进先出的原则存储数据先进入的数据在读取数据时先读被读出来。 api设计
类名Queue构造方法Queue()创建Queue对象成员方法1. public boolean isEmpty()判断队列是否为空是返回true否返回false2. public int size():获取队列中元素的个数3. public T dequeue():从队列中拿出一个元素4. public void enqueue(T t)往队列中插入一个元素成员变量1. private Node head:记录首结点2. private int N:当前队列的元素个数3. private Node last:记录最后一个结点
代码实现
public class Queue {/*** 首结点*/private Node head;/*** 当前队列的元素个数*/private int n;/*** 记录最后一个结点*/private Node last;public Queue() {head new Node(null, null);last null;n 0;}/*** 判断队列是否为空** return*/public boolean isEmpty() {return n 0;}/*** 获取队列中元素的个数** return*/public int size() {return n;}/*** 从队列中拿出一个元素** return*/public String dequeue() {if (isEmpty()) {return null;}// 不是空出列// 获取当前的第一个元素(对应图中的1元素)Node oldFirst head.next;// 让head结点指向下一个结点对应图中的2元素head.next head.next.next;// 个数-1n--;if (isEmpty()) {last null;}return oldFirst.item;}/*** 往队列中插入一个元素** param t*/public void enqueue(String t) {// 判断last是否为nullif (last null) {// last为空要插入的元素就是lastlast new Node(t, null);// 让首结点指向lasthead.next last;} else {// 不是第一个元素// 取出旧结点lastNode oldLast last;// 创建新的结点给lastlast new Node(t, null);// 让旧的last元素指向新的结点oldLast.next last;}// 个数1n;}private class Node {public String item;public Node next;public Node(String item, Node next) {this.item item;this.next next;}}
}class Test8 {public static void main(String[] args) {Queue queue new Queue();queue.enqueue(a);queue.enqueue(b);queue.enqueue(c);queue.enqueue(d);System.out.println(queue.size());System.out.println(queue.dequeue());System.out.println(queue.size());System.out.println(queue.isEmpty());queue.dequeue();queue.dequeue();queue.dequeue();System.out.println(queue.isEmpty());System.out.println(queue.size());}
}*************************************优雅的分割线 **********************************
分享一波:程序员赚外快-必看的巅峰干货
如果以上内容对你觉得有用,并想获取更多的赚钱方式和免费的技术教程
请关注微信公众号:HB荷包 一个能让你学习技术和赚钱方法的公众号,持续更新 *************************************优雅的分割线 ********************************** SimpleExecutor
