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

这篇具有很好参考价值的文章主要介绍了第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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


选择填空题

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

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

分析:

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

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

1:
前序遍历:中左右  ABDECF

中序遍历:左中右  DBEAFC

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

2、线性结构

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

C

3、其它

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

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;
    }

    @Override
    public Iterator iterator() {
        return new Itr();
    }

    private class Itr implements Iterator{
        Node node = first;
        @Override
        public boolean hasNext() {
            return node != null;
        }

        @Override
        public 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、单向链表及其反转

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

单链表的实现

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、字符串压缩

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

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

代码实现:文章来源地址https://www.toymoban.com/news/detail-816616.html

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());
		}
	}
}

到了这里,关于第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构|二叉树遍历】递归与非递归实现前序遍历、中序遍历、后序遍历

    递归与非递归实现二叉树的前序遍历、中序遍历、后序遍历。 二叉树图 定义 前序遍历(Preorder Traversal): 前序遍历的顺序是先访问根节点,然后按照先左后右的顺序访问子节点。对于上面的二叉树,前序遍历的结果是:4 - 2 - 1 - 3 - 6 - 5 - 7。 中序遍历(Inorder Traversal): 中

    2024年02月14日
    浏览(44)
  • 初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)

    本篇博客是初阶数据结构树的收尾,将会讲掉 基本二叉树链式结构的具体内容和实现,包括二叉树的构建,前序遍历,中序遍历,后序遍历和层序遍历,计算二叉树结点个数,第k层结点个数,二叉树叶子结点个数,以及判断一个二叉树是否为完全二叉树 。话不多说,开始我

    2024年03月24日
    浏览(50)
  • 第14章_数据结构与集合源码

    我们举一个形象的例子来理解数据结构的作用:    战场: 程序运行所需的软件、硬件环境 敌人: 项目或模块的功能需求 指挥官: 编写程序的程序员 士兵和装备: 一行一行的代码 战术和策略: 数据结构    上图:没有战术,打仗事倍功半    上图:有战术,打仗事半功

    2023年04月16日
    浏览(32)
  • JAVA基础学习笔记-day14-数据结构与集合源码2

    博文主要是自己学习JAVA基础中的笔记,供自己以后复习使用,参考的主要教程是B站的 尚硅谷宋红康2023大数据教程 君以此始,亦必以终。—左丘明《左传·宣公十二年》 7.1 List接口特点 List集合所有的元素是以一种 线性方式 进行存储的,例如,存元素的顺序是11、22、33。那

    2024年01月18日
    浏览(60)
  • 算法刷题Day14 二叉树的前序、中序、后序遍历(递归、迭代、统一迭代方法)

    二叉树的定义 递归 迭代 普通的遍历(包括前序,中序和后续)迭代方法都需要借助到栈 统一迭代 统一迭代使用标记法,在栈中要处理的结点压入空指针 递归 迭代 中序遍历的迭代方法稍微特殊一点 中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问

    2024年02月15日
    浏览(47)
  • 算法D14 | 二叉树1 | 144. 二叉树的前序遍历 145. 二叉树的后序遍历 94. 二叉树的中序遍历

    理论基础  需要了解 二叉树的种类,存储方式,遍历方式 以及二叉树的定义  文章讲解: 二叉树既可以链式存储(利用指针,类似栈和队列),也可以用数组表示。 深度优先遍历 前序遍历(递归法,迭代法) 中序遍历(递归法,迭代法) 后序遍历(递归法,迭代法)

    2024年02月20日
    浏览(38)
  • 【数据结构】二叉树的前序遍历(七)

    题目详情: 给你二叉树的根节点 root ,返回它节点值的  前序   遍历; 我们先来看几个示例: 输入:root = [ 1,null,2,3 ] 输出:[ 1,2,3 ]  示例2: 输入:root = [ 1,2 ] 输出:[ 1,2 ] 示例三: 输入:root = [  ] 输出:[  ] 提示: 树中结点数目在范围【0,100】内 -100 = Nod

    2024年02月07日
    浏览(43)
  • 【Leetcode60天带刷】day14二叉树——144.二叉树的前序遍历,145.二叉树的后序遍历,94.二叉树的中序遍历

    144. 二叉树的前序遍历 给你二叉树的根节点  root  ,返回它节点值的  前序   遍历。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 树中节点数目在范围  [0, 100]  内 -100 = Node.val = 100 145. 二叉树的后序遍历 给你一棵二叉树的根节点  root  ,返回其节点值的  后序遍历

    2024年02月10日
    浏览(52)
  • 数据结构——二叉树先序、中序、后序三种遍历

    先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解    

    2024年02月11日
    浏览(49)
  • 【数据结构】二叉树的创建和遍历(先序、中序、后序)

    最近一段时间学习了数据结构中二叉树的基本操作,包括二叉树的结构、二叉树的创建、递归先序中序后序遍历、非递归遍历等,想着把二叉树的相关知识和自己的见解放到网上来让网友看看是否正确,想和网友一起共同交流。 先了解一下二叉树的三个基本性质: 性质1:在

    2024年02月04日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包