第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

文章目录

  • 第14章_集合与数据结构拓展练习
    • 选择填空题
      • 1、前序、中序、后序遍历
      • 2、线性结构
      • 3、其它
    • 编程题
      • 4、单向链表构建
      • 5、单向链表及其反转
      • 6、字符串压缩

第14章_集合与数据结构拓展练习


选择填空题

1、前序、中序、后序遍历

在这里插入图片描述

分析:

完全二叉树: 叶结点只能出现在最底层的两层,且最底层叶结点均处于次底层叶结点的左侧

在这里插入图片描述

1:
前序遍历:中左右  ABDECF中序遍历:左中右  DBEAFC后序遍历:左右中  DEBFCA
2:n-i+1

2、线性结构

在这里插入图片描述

C

3、其它

在这里插入图片描述

1、先根次序遍历,就是前序遍历:
ABDHIECFG
2、队列先进先出
3C
4C
524次方是16

编程题

4、单向链表构建

(1)定义一个单向链表SingleLinked类

  • 包含私有的静态内部类Node

    • 包含Object类型的data属性和Node类型的next属性
    • 包含有参构造Node(Object data, Node next)
  • 包含私有的单链表的Node类型的头结点first

  • 包含public void add(Object element)方法,可以添加元素到当前单链表中

  • 包含私有的非静态内部类Itr,Itr类实现java.util.Iterator接口

    • 包含Node类型的实例变量node,初始化为单链表的first
    • 重写boolean hasNext()方法,判断node结点是否为空
    • 重写Object next()方法,获取node对象的data值,并让node结点指向下一个结点
  • 单向链表SingleLinked类实现java.lang.Iterable接口,

    • 重写Iterator iterator()方法,返回非静态内部类Itr的对象

(2)测试类中创建SingleLinked单链表的对象,并添加(张三、李四、王五、赵六)几个元素到单链表中,并用foreach循环变量输出。

public class SingleLinked implements Iterable{private Node first;//单向链表的头private static class Node{Object data;Node next;Node(Object data, Node node) {this.data = data;this.next = node;}}public void add(Object element){Node newNode = new Node(element, null);if(first == null){first = newNode;return;}Node node = first;while(node.next !=null){node = node.next;}node.next = newNode;}@Overridepublic Iterator iterator() {return new Itr();}private class Itr implements Iterator{Node node = first;@Overridepublic boolean hasNext() {return node != null;}@Overridepublic Object next() {Object element = node.data;node = node.next;return element;}}/* 暴露静态内部类public static class Knot{public Object data;public Knot next;}*/}
public class Exercise4 {public static void main(String[] args) {//违反了高内聚低耦合的原则
/*        SingleLinked.Knot k1 = new SingleLinked.Knot();k1.data = "张三";SingleLinked.Knot k2 = new SingleLinked.Knot();k2.data = "李四";k1.next = k2;*///高内聚低耦合SingleLinked link = new SingleLinked();link.add("张三");link.add("李四");link.add("王五");link.add("赵六");for (Object o : link) {System.out.println(o);}}
}

5、单向链表及其反转

在这里插入图片描述

单链表的实现

public class OneWayLinkedList<E>{private Node<E> head;private int total;private static class Node<E>{E data;Node<E> next;Node(E data, Node<E> next) {this.data = data;this.next = next;}}public void add(E e) {Node<E> newNode = new Node<>(e,null);if(head==null){head = newNode;}else{Node<E> node = head;while(node.next!=null){node = node.next;}node.next = newNode;}total++;}public void delete(E e) {Node<E> node = head;Node<E> find = null;Node<E> last = null;if(e==null){while(node!=null){if(node.data==null){find = node;break;}last = node;node = node.next;}}else{while(node!=null){if(e.equals(node.data)){find = node;break;}last = node;node = node.next;}}if(find != null){if(last==null){head = find.next;}else{last.next = find.next;}total--;}}public void update(E old, E value) {Node<E> node = head;Node<E> find = null;if(old==null){while(node!=null){if(node.data==null){find = node;break;}node = node.next;}}else{while(node!=null){if(old.equals(node.data)){find = node;break;}node = node.next;}}if(find != null){find.data = value;}}public boolean contains(E e) {return indexOf(e) != -1;}public int indexOf(E e) {int index = -1;if(e==null){int i=0;for(Node<E> node = head; node!=null; node=node.next ){if(node.data==e){index=i;break;}i++;}}else{int i=0;for(Node<E> node = head; node!=null; node=node.next ){if(e.equals(node.data)){index=i;break;}i++;}}return index;}public Object[] getAll() {Object[] all = new Object[total];Node<E> node = head;for (int i = 0; i < all.length; i++,node = node.next) {all[i] = node.data;}return all;}public int size() {return total;}@SuppressWarnings("unchecked")public void reverse() {if(head!=null) {Node<E>[] all = new Node[total];Node<E> node = head;for (int i = 0; i < all.length; i++) {all[i] = node;node = node.next;}head = all[all.length-1];node = head;for (int i = all.length-2; i >= 0; i--) {node.next = all[i];node = node.next;}}}
}
public class Exercise5 {public static void main(String[] args) {OneWayLinkedList<Integer> list = new OneWayLinkedList<>();for (int i = 1; i <= 5; i++) {list.add(i);}Object[] all = list.getAll();System.out.println(Arrays.toString(all));list.reverse();all = list.getAll();System.out.println(Arrays.toString(all));}
}

6、字符串压缩

在这里插入图片描述

实现简易字符串压缩算法,其中连续出现2次以上(含2次)的字母转换为字母和出现的次数。
例如:AAAABCCDEEEEE,压缩之后为A4BC2DE5

代码实现:

public class Exercise6 {public static void main(String[] args) {
//		String str = "AAAABCCDEEEEE";String str = "AAAABCCDEEEEEF";LinkedList<String> list = new LinkedList<>();int count = 0;for (int i = 0; i < str.length(); i++) {if(list.size()==0) {list.addLast(str.charAt(i)+"");count++;}else {if(list.getLast().equals(str.charAt(i)+"")) {count++;}else {if(count>1) {list.addLast(count+"");}list.addLast(str.charAt(i)+"");count=1;}}}if(count>1) {list.addLast(count+"");}while(list.size()!=0) {System.out.print(list.pollFirst());}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/243167.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ElasticSearch的常用增删改查DSL和代码

es增删改查常用语法 我们日常开发中&#xff0c;操作数据库写sql倒是不可能忘记&#xff0c;但是操作es的dsl语句有时候很容易忘记&#xff0c;特地记录一下方便查找。 DSL语句 1、创建索引 -- 创建索引 PUT /my_index {"mappings": {"properties": {&…

Python实现Lasso回归模型

• Tibshirani(1996)提出了Lasso(The Least Absolute Shrinkage and Selectionator operator)算法。 • 通过构造一个一阶惩罚函数获得一个精炼的模型&#xff1b;通过最终确定一些指标&#xff08;变量&#xff09;的系数为零&#xff08;岭回归估计系数等于0的机会微乎其微&a…

【HarmonyOS】体验鸿蒙电商平台的未来之旅!

从今天开始&#xff0c;博主将开设一门新的专栏用来讲解市面上比较热门的技术 “鸿蒙开发”&#xff0c;对于刚接触这项技术的小伙伴在学习鸿蒙开发之前&#xff0c;有必要先了解一下鸿蒙&#xff0c;从你的角度来讲&#xff0c;你认为什么是鸿蒙呢&#xff1f;它出现的意义又是…

【堂堂狼人杀(定制开发)】

堂堂狼人杀游戏♨️风险规避与优势。?零投资也可参与规避五大风险 政策风险(点对点场外交易)账户风险(无资金池&#xff09; 推广风险(免费注册&#xff0c;注册送大礼包&#xff09; 网络风险(大平台&#xff0c;全网场外交易) 人脉风险(预约角色&#xff0c;强制出售) …

力扣hot100 相交链表 超全注释 满级表达

Problem: 160. 相交链表 文章目录 思路复杂度&#x1f496; Ac Code 思路 &#x1f468;‍&#x1f3eb; 参考题解 &#x1f469;‍&#x1f3eb; 参考图解 复杂度 时间复杂度: O ( n m ) O(nm) O(nm) 空间复杂度: 添加空间复杂度, 示例&#xff1a; O ( 1 ) O(1) O(…

python 正则表达式学习(1)

正则表达式是一个特殊的字符序列&#xff0c;它能帮助你方便的检查一个字符串是否与某种模式匹配。 1. 特殊符号 1.1 符号含义 模式描述^匹配字符串的开头$匹配字符串的末尾.匹配任意字符&#xff0c;除了换行符&#xff0c;当re.DOTALL标记被指定时&#xff0c;则可以匹配包…

飞书+ChatGPT+cpolar搭建企业智能AI助手并实现无公网ip远程访问

文章目录 推荐 前言环境列表1.飞书设置2.克隆feishu-chatgpt项目3.配置config.yaml文件4.运行feishu-chatgpt项目5.安装cpolar内网穿透6.固定公网地址7.机器人权限配置8.创建版本9.创建测试企业10. 机器人测试 推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂…

用pandas实现用前一行的excel的值填充后一行

今天接到一份数据需要分析&#xff0c;数据在一个excel文件里&#xff0c;内容大概形式如下&#xff1a; 后面空的格子里的值就是默认是前面的非空的值&#xff0c;由于数据分析的需要需要对重复的数据进行去重&#xff0c;去重就需要把控的cell的值补上&#xff0c;然后根据几…

数字IC后端设计实现 | PR工具中到底应该如何控制density和congestion?(ICC2Innovus)

吾爱IC社区星友提问&#xff1a;请教星主和各位大佬&#xff0c;对于一个模块如果不加干预工具会让inst挤成一团&#xff0c;后面eco修时序就没有空间了。如果全都加instPadding会导致面积不够overlap&#xff0c;大家一般怎么处理这种问题&#xff1f; 在数字IC后端设计实现中…

Python内置的20个高阶函数的功能和示例详解

更多资料获取 &#x1f4da; 个人网站&#xff1a;ipengtao.com Python是一门功能丰富的编程语言&#xff0c;提供了许多内置函数来处理各种数据操作。其中&#xff0c;高阶函数是一类特殊的函数&#xff0c;它们接受其他函数作为参数&#xff0c;或者返回函数作为结果。高阶函…

如何禁用WordPress站点的管理员电子邮件验证或修改检查频率?

今天boke112百科登录某个WordPress站点时&#xff0c;又出现“管理员邮件确认”的提示&#xff0c;要求确认此站点的管理员电子邮箱地址是否仍然正确。具体如下图所示&#xff1a; 如果点击“稍后提醒我”&#xff0c;那么管理员邮件验证页面就会在3天后重新显示。 说实话&…

Unity - 简单音频

“Test_04” AudioTest public class AudioTest : MonoBehaviour {// 声明音频// AudioClippublic AudioClip music;public AudioClip se;// 声明播放器组件private AudioSource player;void Start(){// 获取播放器组件player GetComponent<AudioSource>();// 赋值…

搭建开源数据库中间件MyCat2-配置mysql数据库双主双从

mycat2官网&#xff1a;MyCat2 前言&#xff1a;mycat2下载地址无法访问&#xff0c;不知道是不是被DNS污染了&#xff0c;还是需要搭梯子访问&#xff0c;所以我只能找到1.21的版本进行安装。搭建mycat2的前提是搭建数据库主从复制。 架构&#xff1a;双主双从 配置&#xf…

Verilog基础:强度建模与net型信号的多驱动问题(三)

相关阅读 Verilog基础https://blog.csdn.net/weixin_45791458/category_12263729.html?spm1001.2014.3001.5482 四、一般情况下的net型信号的线与组合&#xff08;线网多驱动&#xff09; 在Verilog基础&#xff1a;强度建模与net型信号的多驱动问题&#xff08;二&#xff0…

成功解决java.nio.charset.MalformedInputException: Input length = 1

项目启动时报错如下 Connected to the target VM, address: 127.0.0.1:5309, transport: socket 18:01:22.607 [main] ERROR o.s.b.SpringApplication - [reportFailure,843] - Application run failed org.yaml.snakeyaml.error.YAMLException: java.nio.charset.MalformedIn…

开年大瓜!Mobileye股价暴跌

编者按&#xff1a;作为汽车智能化的第一波受益者&#xff0c;Mobileye的市场红利已经接近尾声。尤其是汽车芯片市场的白热化竞争&#xff0c;新一轮格局重构正在开启。 汽车智能化的供给关系&#xff0c;正在发生微妙变化。 本周&#xff0c;作为全球主要的辅助驾驶芯片及感知…

Joern环境的安装(Windows版)

Joern环境的安装(Windows版) 网上很少有关于Windows下安装Joern的教程&#xff0c;而我最初使用也是装在Ubuntu虚拟机中&#xff0c;这样使用很占内存&#xff0c;影响体验感。在Windows下使用源码安装Joern也是非常简单的过程&#xff1a; 提前需要的本地环境&#xff1a; …

【大数据】流处理基础概念(一):Dataflow 编程基础、并行流处理

流处理基础概念&#xff08;一&#xff09;&#xff1a;Dataflow 编程基础、并行流处理 1.Dataflow 编程基础1.1 Dataflow 图1.2 数据并行和任务并行1.3 数据交换策略 2.并行流处理2.1 延迟与吞吐2.1.1 延迟2.1.2 吞吐2.1.3 延迟与吞吐 2.2 数据流上的操作2.2.1 数据接入和数据…

GPS位置虚拟软件 AnyGo mac激活版

AnyGo for Mac是一款一键将iPhone的GPS位置更改为任何位置的强大软件&#xff01;使用AnyGo在其iOS或Android设备上改变其GPS位置&#xff0c;并在任何想要的地方显示自己的位置。这对那些需要测试应用程序、游戏或其他依赖于地理位置信息的应用程序的开发人员来说非常有用&…

【网络奇遇记】揭秘计算机网络性能指标:全面指南

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;网络奇遇记、数据结构 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. 速率1.1 数据量1.2 速率 二. 带宽三. 吞吐量四. 时延4.1 发送时延4.2 传播时延…