效果型网站,装饰公司logo图片大全,百度网址链接是多少,汕头好的建站网站文章目录 第14章_集合与数据结构拓展练习选择填空题1、前序、中序、后序遍历2、线性结构3、其它 编程题4、单向链表构建5、单向链表及其反转6、字符串压缩 第14章_集合与数据结构拓展练习 选择填空题
1、前序、中序、后序遍历 分析#xff1a;
完全二叉树#xff1a; 叶结点… 文章目录 第14章_集合与数据结构拓展练习选择填空题1、前序、中序、后序遍历2、线性结构3、其它 编程题4、单向链表构建5、单向链表及其反转6、字符串压缩 第14章_集合与数据结构拓展练习 选择填空题
1、前序、中序、后序遍历 分析
完全二叉树 叶结点只能出现在最底层的两层且最底层叶结点均处于次底层叶结点的左侧 题1
前序遍历中左右 ABDECF中序遍历左中右 DBEAFC后序遍历左右中 DEBFCA题2n-i12、线性结构 C3、其它 1、先根次序遍历就是前序遍历
ABDHIECFG
2、队列先进先出
3、C
4、C
5、2的4次方是16个编程题
4、单向链表构建
1定义一个单向链表SingleLinked类 包含私有的静态内部类Node 包含Object类型的data属性和Node类型的next属性包含有参构造Node(Object data, Node next) 包含私有的单链表的Node类型的头结点first 包含public void add(Object element)方法可以添加元素到当前单链表中 包含私有的非静态内部类ItrItr类实现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 OneWayLinkedListE{private NodeE head;private int total;private static class NodeE{E data;NodeE next;Node(E data, NodeE next) {this.data data;this.next next;}}public void add(E e) {NodeE newNode new Node(e,null);if(headnull){head newNode;}else{NodeE node head;while(node.next!null){node node.next;}node.next newNode;}total;}public void delete(E e) {NodeE node head;NodeE find null;NodeE last null;if(enull){while(node!null){if(node.datanull){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(lastnull){head find.next;}else{last.next find.next;}total--;}}public void update(E old, E value) {NodeE node head;NodeE find null;if(oldnull){while(node!null){if(node.datanull){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(enull){int i0;for(NodeE node head; node!null; nodenode.next ){if(node.datae){indexi;break;}i;}}else{int i0;for(NodeE node head; node!null; nodenode.next ){if(e.equals(node.data)){indexi;break;}i;}}return index;}public Object[] getAll() {Object[] all new Object[total];NodeE 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) {NodeE[] all new Node[total];NodeE 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) {OneWayLinkedListInteger 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;LinkedListString 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(count1) {list.addLast(count);}list.addLast(str.charAt(i));count1;}}}if(count1) {list.addLast(count);}while(list.size()!0) {System.out.print(list.pollFirst());}}
}
