第14章_集合與數(shù)據(jù)結(jié)構(gòu)拓展練習(xí)

---

選擇填空題

1、前序、中序、后序遍歷

分析：

完全二叉樹： 葉結(jié)點(diǎn)只能出現(xiàn)在最底層的兩層，且最底層葉結(jié)點(diǎn)均處于次底層葉結(jié)點(diǎn)的左側(cè)

題1：
前序遍歷：中左右  ABDECF中序遍歷：左中右  DBEAFC后序遍歷：左右中  DEBFCA

題2：n-i+1

2、線性結(jié)構(gòu)

C

3、其它

1、先根次序遍歷，就是前序遍歷：
ABDHIECFG
2、隊(duì)列先進(jìn)先出
3、C
4、C
5、2的4次方是16個(gè)

編程題

4、單向鏈表構(gòu)建

（1）定義一個(gè)單向鏈表SingleLinked類

• 包含私有的靜態(tài)內(nèi)部類Node

  • 包含Object類型的data屬性和Node類型的next屬性
  • 包含有參構(gòu)造Node(Object data, Node next)

• 包含私有的單鏈表的Node類型的頭結(jié)點(diǎn)first

• 包含public void add(Object element)方法，可以添加元素到當(dāng)前單鏈表中

• 包含私有的非靜態(tài)內(nèi)部類Itr，Itr類實(shí)現(xiàn)java.util.Iterator接口

  • 包含Node類型的實(shí)例變量node，初始化為單鏈表的first
  • 重寫boolean hasNext()方法，判斷node結(jié)點(diǎn)是否為空
  • 重寫Object next()方法，獲取node對象的data值，并讓node結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn)

• 單向鏈表SingleLinked類實(shí)現(xiàn)java.lang.Iterable接口，

  • 重寫Iterator iterator()方法，返回非靜態(tài)內(nèi)部類Itr的對象

（2）測試類中創(chuàng)建SingleLinked單鏈表的對象，并添加（張三、李四、王五、趙六）幾個(gè)元素到單鏈表中，并用foreach循環(huán)變量輸出。

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;}}/* 暴露靜態(tài)內(nèi)部類public static class Knot{public Object data;public Knot next;}*/}

public class Exercise4 {public static void main(String[] args) {//違反了高內(nèi)聚低耦合的原則
/*        SingleLinked.Knot k1 = new SingleLinked.Knot();k1.data = "張三";SingleLinked.Knot k2 = new SingleLinked.Knot();k2.data = "李四";k1.next = k2;*///高內(nèi)聚低耦合SingleLinked link = new SingleLinked();link.add("張三");link.add("李四");link.add("王五");link.add("趙六");for (Object o : link) {System.out.println(o);}}
}

5、單向鏈表及其反轉(zhuǎn)

單鏈表的實(shí)現(xiàn)

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、字符串壓縮

實(shí)現(xiàn)簡易字符串壓縮算法，其中連續(xù)出現(xiàn)2次以上（含2次）的字母轉(zhuǎn)換為字母和出現(xiàn)的次數(shù)。
例如：AAAABCCDEEEEE,壓縮之后為A4BC2DE5。

代碼實(shí)現(xiàn)：

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