wordpress种子站,电脑中怎样安装wordpress,wordpress 编辑代码,淘宝券搜索网站怎么做文章目录 4.1 链表(Linked List)介绍4.2 单链表的应用实例4.3 单链表面试题(新浪、百度、腾讯)4.4 双向链表应用实例4.4.1 双向链表的操作分析和实现4.4.2 课堂作业和思路提示 4.5 单向环形链表应用场景4.6 单向环形链表介绍4.7 Josephu 问题4.8 Josephu 问题的代码实现 4.1 链… 文章目录 4.1 链表(Linked List)介绍4.2 单链表的应用实例4.3 单链表面试题(新浪、百度、腾讯)4.4 双向链表应用实例4.4.1 双向链表的操作分析和实现4.4.2 课堂作业和思路提示 4.5 单向环形链表应用场景4.6 单向环形链表介绍4.7 Josephu 问题4.8 Josephu 问题的代码实现 4.1 链表(Linked List)介绍
链表是有序的列表但是它在内存中是存储如下
小结上图:
链表是以节点的方式来存储,是链式存储每个节点包含 data 域 next 域指向下一个节点.如图发现链表的各个节点不一定是连续存储.链表分带头节点的链表和没有头节点的链表根据实际的需求来确定 单链表(带头结点) 逻辑结构示意图如下
4.2 单链表的应用实例
使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作 注: 删除和修改,查找可以考虑学员独立完成也可带学员完成 第一种方法在添加英雄时直接添加到链表的尾部思路分析示意图: 第二种方式在添加英雄时根据排名将英雄插入到指定位置(如果有这个排名则添加失败并给出提示)思路的分析示意图: 修改节点功能 思路(1) 先找到该节点通过遍历(2) temp.name newHeroNode.name ; temp.nickname newHeroNode.nickname 删除节点 思路分析的示意图: 完成的代码演示: package com.atguigu.linkedlist;import java.util.Stack;public class SingleLinkedListDemo {public static void main(String[] args) {//进行测试//先创建节点HeroNode hero1 new HeroNode(1, 宋江, 及时雨);HeroNode hero2 new HeroNode(2, 卢俊义, 玉麒麟);HeroNode hero3 new HeroNode(3, 吴用, 智多星);HeroNode hero4 new HeroNode(4, 林冲, 豹子头);//创建要给链表SingleLinkedList singleLinkedList new SingleLinkedList();//加入singleLinkedList.add(hero1);singleLinkedList.add(hero4);singleLinkedList.add(hero2);singleLinkedList.add(hero3);// 测试一下单链表的反转功能System.out.println(原来链表的情况~~);singleLinkedList.list();// System.out.println(反转单链表~~);// reversetList(singleLinkedList.getHead());// singleLinkedList.list();System.out.println(测试逆序打印单链表, 没有改变链表的结构~~);reversePrint(singleLinkedList.getHead());/* //加入按照编号的顺序singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);//显示一把singleLinkedList.list();//测试修改节点的代码HeroNode newHeroNode new HeroNode(2, 小卢, 玉麒麟~~);singleLinkedList.update(newHeroNode);System.out.println(修改后的链表情况~~);singleLinkedList.list();//删除一个节点singleLinkedList.del(1);singleLinkedList.del(4);System.out.println(删除后的链表情况~~);singleLinkedList.list();//测试一下 求单链表中有效节点的个数System.out.println(有效的节点个数 getLength(singleLinkedList.getHead()));//2//测试一下看看是否得到了倒数第K个节点HeroNode res findLastIndexNode(singleLinkedList.getHead(), 3);System.out.println(res res);*/ }//方式2//可以利用栈这个数据结构将各个节点压入到栈中然后利用栈的先进后出的特点就实现了逆序打印的效果public static void reversePrint(HeroNode head) {if(head.next null) {return;//空链表不能打印}//创建要给一个栈将各个节点压入栈StackHeroNode stack new StackHeroNode();HeroNode cur head.next;//将链表的所有节点压入栈while(cur ! null) {stack.push(cur);cur cur.next; //cur后移这样就可以压入下一个节点}//将栈中的节点进行打印,pop 出栈while (stack.size() 0) {System.out.println(stack.pop()); //stack的特点是先进后出}}//将单链表反转public static void reversetList(HeroNode head) {//如果当前链表为空或者只有一个节点无需反转直接返回if(head.next null || head.next.next null) {return ;}//定义一个辅助的指针(变量)帮助我们遍历原来的链表HeroNode cur head.next;HeroNode next null;// 指向当前节点[cur]的下一个节点HeroNode reverseHead new HeroNode(0, , );//遍历原来的链表每遍历一个节点就将其取出并放在新的链表reverseHead 的最前端//动脑筋while(cur ! null) { next cur.next;//先暂时保存当前节点的下一个节点因为后面需要使用cur.next reverseHead.next;//将cur的下一个节点指向新的链表的最前端reverseHead.next cur; //将cur 连接到新的链表上cur next;//让cur后移}//将head.next 指向 reverseHead.next , 实现单链表的反转head.next reverseHead.next;}//查找单链表中的倒数第k个结点 【新浪面试题】//思路//1. 编写一个方法接收head节点同时接收一个index //2. index 表示是倒数第index个节点//3. 先把链表从头到尾遍历得到链表的总的长度 getLength//4. 得到size 后我们从链表的第一个开始遍历 (size-index)个就可以得到//5. 如果找到了则返回该节点否则返回nulllpublic static HeroNode findLastIndexNode(HeroNode head, int index) {//判断如果链表为空返回nullif(head.next null) {return null;//没有找到}//第一个遍历得到链表的长度(节点个数)int size getLength(head);//第二次遍历 size-index 位置就是我们倒数的第K个节点//先做一个index的校验if(index 0 || index size) {return null; }//定义给辅助变量 for 循环定位到倒数的indexHeroNode cur head.next; //3 // 3 - 1 2for(int i 0; i size - index; i) {cur cur.next;}return cur;}//方法获取到单链表的节点的个数(如果是带头结点的链表需求不统计头节点)/*** * param head 链表的头节点* return 返回的就是有效节点的个数*/public static int getLength(HeroNode head) {if(head.next null) { //空链表return 0;}int length 0;//定义一个辅助的变量, 这里我们没有统计头节点HeroNode cur head.next;while(cur ! null) {length;cur cur.next; //遍历}return length;}}//定义SingleLinkedList 管理我们的英雄class SingleLinkedList {//先初始化一个头节点, 头节点不要动, 不存放具体的数据private HeroNode head new HeroNode(0, , );//返回头节点public HeroNode getHead() {return head;}//添加节点到单向链表//思路当不考虑编号顺序时//1. 找到当前链表的最后节点//2. 将最后这个节点的next 指向 新的节点public void add(HeroNode heroNode) {//因为head节点不能动因此我们需要一个辅助遍历 tempHeroNode temp head;//遍历链表找到最后while(true) {//找到链表的最后if(temp.next null) {//break;}//如果没有找到最后, 将将temp后移temp temp.next;}//当退出while循环时temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next heroNode;}//第二种方式在添加英雄时根据排名将英雄插入到指定位置//(如果有这个排名则添加失败并给出提示)public void addByOrder(HeroNode heroNode) {//因为头节点不能动因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置//因为单链表因为我们找的temp 是位于 添加位置的前一个节点否则插入不了HeroNode temp head;boolean flag false; // flag标志添加的编号是否存在默认为falsewhile(true) {if(temp.next null) {//说明temp已经在链表的最后break; //} if(temp.next.no heroNode.no) { //位置找到就在temp的后面插入break;} else if (temp.next.no heroNode.no) {//说明希望添加的heroNode的编号已然存在flag true; //说明编号存在break;}temp temp.next; //后移遍历当前链表}//判断flag 的值if(flag) { //不能添加说明编号存在System.out.printf(准备插入的英雄的编号 %d 已经存在了, 不能加入\n, heroNode.no);} else {//插入到链表中, temp的后面heroNode.next temp.next;temp.next heroNode;}}//修改节点的信息, 根据no编号来修改即no编号不能改.//说明//1. 根据 newHeroNode 的 no 来修改即可public void update(HeroNode newHeroNode) {//判断是否空if(head.next null) {System.out.println(链表为空~);return;}//找到需要修改的节点, 根据no编号//定义一个辅助变量HeroNode temp head.next;boolean flag false; //表示是否找到该节点while(true) {if (temp null) {break; //已经遍历完链表}if(temp.no newHeroNode.no) {//找到flag true;break;}temp temp.next;}//根据flag 判断是否找到要修改的节点if(flag) {temp.name newHeroNode.name;temp.nickname newHeroNode.nickname;} else { //没有找到System.out.printf(没有找到 编号 %d 的节点不能修改\n, newHeroNode.no);}}//删除节点//思路//1. head 不能动因此我们需要一个temp辅助节点找到待删除节点的前一个节点//2. 说明我们在比较时是temp.next.no 和 需要删除的节点的no比较public void del(int no) {HeroNode temp head;boolean flag false; // 标志是否找到待删除节点的while(true) {if(temp.next null) { //已经到链表的最后break;}if(temp.next.no no) {//找到的待删除节点的前一个节点tempflag true;break;}temp temp.next; //temp后移遍历}//判断flagif(flag) { //找到//可以删除temp.next temp.next.next;}else {System.out.printf(要删除的 %d 节点不存在\n, no);}}//显示链表[遍历]public void list() {//判断链表是否为空if(head.next null) {System.out.println(链表为空);return;}//因为头节点不能动因此我们需要一个辅助变量来遍历HeroNode temp head.next;while(true) {//判断是否到链表最后if(temp null) {break;}//输出节点的信息System.out.println(temp);//将temp后移 一定小心temp temp.next;}}}//定义HeroNode 每个HeroNode 对象就是一个节点class HeroNode {public int no;public String name;public String nickname;public HeroNode next; //指向下一个节点//构造器public HeroNode(int no, String name, String nickname) {this.no no;this.name name;this.nickname nickname;}//为了显示方法我们重新toStringOverridepublic String toString() {return HeroNode [no no , name name , nickname nickname ];}}4.3 单链表面试题(新浪、百度、腾讯)
单链表的常见面试题有如下: 求单链表中有效节点的个数代码如下 //方法获取到单链表的节点的个数(如果是带头结点的链表需求不统计头节点)/*** * param head 链表的头节点* return 返回的就是有效节点的个数*/public static int getLength(HeroNode head) {if(head.next null) { //空链表return 0;}int length 0;//定义一个辅助的变量, 这里我们没有统计头节点HeroNode cur head.next;while(cur ! null) {length;cur cur.next; //遍历}return length;}查找单链表中的倒数第 k 个结点 【新浪面试题】代码演示: //查找单链表中的倒数第k个结点 【新浪面试题】//思路//1. 编写一个方法接收head节点同时接收一个index //2. index 表示是倒数第index个节点//3. 先把链表从头到尾遍历得到链表的总的长度 getLength//4. 得到size 后我们从链表的第一个开始遍历 (size-index)个就可以得到//5. 如果找到了则返回该节点否则返回nulllpublic static HeroNode findLastIndexNode(HeroNode head, int index) {//判断如果链表为空返回nullif(head.next null) {return null;//没有找到}//第一个遍历得到链表的长度(节点个数)int size getLength(head);//第二次遍历 size-index 位置就是我们倒数的第K个节点//先做一个index的校验if(index 0 || index size) {return null; }//定义给辅助变量 for 循环定位到倒数的indexHeroNode cur head.next; //3 // 3 - 1 2for(int i 0; i size - index; i) {cur cur.next;}return cur;}单链表的反转【腾讯面试题有点难度】 思路分析图解
代码实现 //将单链表反转public static void reversetList(HeroNode head) {//如果当前链表为空或者只有一个节点无需反转直接返回if(head.next null || head.next.next null) {return ;}//定义一个辅助的指针(变量)帮助我们遍历原来的链表HeroNode cur head.next;HeroNode next null;// 指向当前节点[cur]的下一个节点HeroNode reverseHead new HeroNode(0, , );//遍历原来的链表每遍历一个节点就将其取出并放在新的链表reverseHead 的最前端//动脑筋while(cur ! null) { next cur.next;//先暂时保存当前节点的下一个节点因为后面需要使用cur.next reverseHead.next;//将cur的下一个节点指向新的链表的最前端reverseHead.next cur; //将cur 连接到新的链表上cur next;//让cur后移}//将head.next 指向 reverseHead.next , 实现单链表的反转head.next reverseHead.next;}从尾到头打印单链表 【百度要求方式 1反向遍历 。 方式 2Stack 栈】 思路分析图解
代码实现 写了一个小程序测试 Stack 的使用
package com.atguigu.linkedlist;import java.util.Stack;//演示栈Stack的基本使用
public class TestStack {public static void main(String[] args) {StackString stack new Stack();// 入栈stack.add(jack);stack.add(tom);stack.add(smith);// 出栈// smith, tom , jackwhile (stack.size() 0) {System.out.println(stack.pop());//pop就是将栈顶的数据取出}}}单链表的逆序打印代码:
//方式2//可以利用栈这个数据结构将各个节点压入到栈中然后利用栈的先进后出的特点就实现了逆序打印的效果public static void reversePrint(HeroNode head) {if(head.next null) {return;//空链表不能打印}//创建要给一个栈将各个节点压入栈StackHeroNode stack new StackHeroNode();HeroNode cur head.next;//将链表的所有节点压入栈while(cur ! null) {stack.push(cur);cur cur.next; //cur后移这样就可以压入下一个节点}//将栈中的节点进行打印,pop 出栈while (stack.size() 0) {System.out.println(stack.pop()); //stack的特点是先进后出}}合并两个有序的单链表合并之后的链表依然有序【课后练习.】
4.4 双向链表应用实例
4.4.1 双向链表的操作分析和实现
使用带 head 头的双向链表实现 –水浒英雄排行榜 管理单向链表的缺点分析:
单向链表查找的方向只能是一个方向而双向链表可以向前或者向后查找。单向链表不能自我删除需要靠辅助节点 而双向链表则可以自我删除所以前面我们单链表删除时节点总是找到 temp,temp 是待删除节点的前一个节点(认真体会).分析了双向链表如何完成遍历添加修改和删除的思路 对上图的说明:
分析 双向链表的遍历添加修改删除的操作思路》代码实现 遍历 方和 单链表一样只是可以向前也可以向后查找 添加 (默认添加到双向链表的最后) (1) 先找到双向链表的最后这个节点 (2) temp.next newHeroNode (3) newHeroNode.pre temp; 修改 思路和 原来的单向链表一样. 删除 (1) 因为是双向链表因此我们可以实现自我删除某个节点 (2) 直接找到要删除的这个节点比如 temp (3) temp.pre.next temp.next (4) temp.next.pre temp.pre; 双向链表的代码实现 package com.atguigu.linkedlist;public class DoubleLinkedListDemo {public static void main(String[] args) {// 测试System.out.println(双向链表的测试);// 先创建节点HeroNode2 hero1 new HeroNode2(1, 宋江, 及时雨);HeroNode2 hero2 new HeroNode2(2, 卢俊义, 玉麒麟);HeroNode2 hero3 new HeroNode2(3, 吴用, 智多星);HeroNode2 hero4 new HeroNode2(4, 林冲, 豹子头);// 创建一个双向链表DoubleLinkedList doubleLinkedList new DoubleLinkedList();doubleLinkedList.add(hero1);doubleLinkedList.add(hero2);doubleLinkedList.add(hero3);doubleLinkedList.add(hero4);doubleLinkedList.list();// 修改HeroNode2 newHeroNode new HeroNode2(4, 公孙胜, 入云龙);doubleLinkedList.update(newHeroNode);System.out.println(修改后的链表情况);doubleLinkedList.list();// 删除doubleLinkedList.del(3);System.out.println(删除后的链表情况~~);doubleLinkedList.list();}}// 创建一个双向链表的类
class DoubleLinkedList {// 先初始化一个头节点, 头节点不要动, 不存放具体的数据private HeroNode2 head new HeroNode2(0, , );// 返回头节点public HeroNode2 getHead() {return head;}// 遍历双向链表的方法// 显示链表[遍历]public void list() {// 判断链表是否为空if (head.next null) {System.out.println(链表为空);return;}// 因为头节点不能动因此我们需要一个辅助变量来遍历HeroNode2 temp head.next;while (true) {// 判断是否到链表最后if (temp null) {break;}// 输出节点的信息System.out.println(temp);// 将temp后移 一定小心temp temp.next;}}// 添加一个节点到双向链表的最后.public void add(HeroNode2 heroNode) {// 因为head节点不能动因此我们需要一个辅助遍历 tempHeroNode2 temp head;// 遍历链表找到最后while (true) {// 找到链表的最后if (temp.next null) {//break;}// 如果没有找到最后, 将将temp后移temp temp.next;}// 当退出while循环时temp就指向了链表的最后// 形成一个双向链表temp.next heroNode;heroNode.pre temp;}// 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样// 只是 节点类型改成 HeroNode2public void update(HeroNode2 newHeroNode) {// 判断是否空if (head.next null) {System.out.println(链表为空~);return;}// 找到需要修改的节点, 根据no编号// 定义一个辅助变量HeroNode2 temp head.next;boolean flag false; // 表示是否找到该节点while (true) {if (temp null) {break; // 已经遍历完链表}if (temp.no newHeroNode.no) {// 找到flag true;break;}temp temp.next;}// 根据flag 判断是否找到要修改的节点if (flag) {temp.name newHeroNode.name;temp.nickname newHeroNode.nickname;} else { // 没有找到System.out.printf(没有找到 编号 %d 的节点不能修改\n, newHeroNode.no);}}// 从双向链表中删除一个节点,// 说明// 1 对于双向链表我们可以直接找到要删除的这个节点// 2 找到后自我删除即可public void del(int no) {// 判断当前链表是否为空if (head.next null) {// 空链表System.out.println(链表为空无法删除);return;}HeroNode2 temp head.next; // 辅助变量(指针)boolean flag false; // 标志是否找到待删除节点的while (true) {if (temp null) { // 已经到链表的最后break;}if (temp.no no) {// 找到的待删除节点的前一个节点tempflag true;break;}temp temp.next; // temp后移遍历}// 判断flagif (flag) { // 找到// 可以删除// temp.next temp.next.next;[单向链表]temp.pre.next temp.next;// 这里我们的代码有问题?// 如果是最后一个节点就不需要执行下面这句话否则出现空指针if (temp.next ! null) {temp.next.pre temp.pre;}} else {System.out.printf(要删除的 %d 节点不存在\n, no);}}}// 定义HeroNode2 每个HeroNode 对象就是一个节点
class HeroNode2 {public int no;public String name;public String nickname;public HeroNode2 next; // 指向下一个节点, 默认为nullpublic HeroNode2 pre; // 指向前一个节点, 默认为null// 构造器public HeroNode2(int no, String name, String nickname) {this.no no;this.name name;this.nickname nickname;}// 为了显示方法我们重新toStringOverridepublic String toString() {return HeroNode [no no , name name , nickname nickname ];}}4.4.2 课堂作业和思路提示
双向链表的第二种添加方式,按照编号顺序 [示意图]按照单链表的顺序添加稍作修改即可.
4.5 单向环形链表应用场景
Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为设编号为 12… n 的 n 个人围坐一圈约定编号为 k1kn的人从 1 开始报数数到 m 的那个人出列它的下一位又从 1 开始报数数到 m 的那个人又出列依次类推直到所有人出列为止由此产生一个出队编号的序列。
提示用一个不带头结点的循环链表来处理 Josephu 问题先构成一个有 n 个结点的单循环链表然后由 k 结点起从 1 开始计数计到 m 时对应结点从链表中删除然后再从被删除结点的下一个结点又从 1 开始计数直到最后一个结点从链表中删除算法结束。
4.6 单向环形链表介绍 4.7 Josephu 问题
约瑟夫问题的示意图
Josephu 问题 Josephu 问题为设编号为 12… n 的 n 个人围坐一圈约定编号为 k1kn的人从 1 开始报数数到 m 的那个人出列它的下一位又从 1 开始报数数到 m 的那个人又出列依次类推直到所有人出列为止由此产生一个出队编号的序列。
提示 用一个不带头结点的循环链表来处理 Josephu 问题先构成一个有 n 个结点的单循环链表然后由 k 结点起从 1 开始计数计到 m 时对应结点从链表中删除然后再从被删除结点的下一个结点又从 1 开始计数直到最后一个
结点从链表中删除算法结束。
约瑟夫问题-创建环形链表的思路图解
约瑟夫问题-小孩出圈的思路分析图
4.8 Josephu 问题的代码实现
package com.atguigu.linkedlist;public class Josepfu {public static void main(String[] args) {// 测试一把看看构建环形链表和遍历是否okCircleSingleLinkedList circleSingleLinkedList new CircleSingleLinkedList();circleSingleLinkedList.addBoy(125);// 加入5个小孩节点circleSingleLinkedList.showBoy();//测试一把小孩出圈是否正确circleSingleLinkedList.countBoy(10, 20, 125); // 2-4-1-5-3//String str 7*2*2-51-53-3;}}// 创建一个环形的单向链表
class CircleSingleLinkedList {// 创建一个first节点,当前没有编号private Boy first null;// 添加小孩节点构建成一个环形的链表public void addBoy(int nums) {// nums 做一个数据校验if (nums 1) {System.out.println(nums的值不正确);return;}Boy curBoy null; // 辅助指针帮助构建环形链表// 使用for来创建我们的环形链表for (int i 1; i nums; i) {// 根据编号创建小孩节点Boy boy new Boy(i);// 如果是第一个小孩if (i 1) {first boy;first.setNext(first); // 构成环curBoy first; // 让curBoy指向第一个小孩} else {curBoy.setNext(boy);//boy.setNext(first);//curBoy boy;}}}// 遍历当前的环形链表public void showBoy() {// 判断链表是否为空if (first null) {System.out.println(没有任何小孩~~);return;}// 因为first不能动因此我们仍然使用一个辅助指针完成遍历Boy curBoy first;while (true) {System.out.printf(小孩的编号 %d \n, curBoy.getNo());if (curBoy.getNext() first) {// 说明已经遍历完毕break;}curBoy curBoy.getNext(); // curBoy后移}}// 根据用户的输入计算出小孩出圈的顺序/*** * param startNo* 表示从第几个小孩开始数数* param countNum* 表示数几下* param nums* 表示最初有多少小孩在圈中*/public void countBoy(int startNo, int countNum, int nums) {// 先对数据进行校验if (first null || startNo 1 || startNo nums) {System.out.println(参数输入有误 请重新输入);return;}// 创建要给辅助指针,帮助完成小孩出圈Boy helper first;// 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点while (true) {if (helper.getNext() first) { // 说明helper指向最后小孩节点break;}helper helper.getNext();}//小孩报数前先让 first 和 helper 移动 k - 1次for(int j 0; j startNo - 1; j) {first first.getNext();helper helper.getNext();}//当小孩报数时让first 和 helper 指针同时 的移动 m - 1 次, 然后出圈//这里是一个循环操作知道圈中只有一个节点while(true) {if(helper first) { //说明圈中只有一个节点break;}//让 first 和 helper 指针同时 的移动 countNum - 1for(int j 0; j countNum - 1; j) {first first.getNext();helper helper.getNext();}//这时first指向的节点就是要出圈的小孩节点System.out.printf(小孩%d出圈\n, first.getNo());//这时将first指向的小孩节点出圈first first.getNext();helper.setNext(first); //}System.out.printf(最后留在圈中的小孩编号%d \n, first.getNo());}
}// 创建一个Boy类表示一个节点
class Boy {private int no;// 编号private Boy next; // 指向下一个节点,默认nullpublic Boy(int no) {this.no no;}public int getNo() {return no;}public void setNo(int no) {this.no no;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next next;}}
