第14章_集合與數(shù)據(jù)結(jié)構(gòu)拓展練習(xí)
選擇填空題
1、前序、中序、后序遍歷
分析：
完全二叉樹(shù)： 葉結(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類(lèi)
-
包含私有的靜態(tài)內(nèi)部類(lèi)Node
- 包含Object類(lèi)型的data屬性和Node類(lèi)型的next屬性
- 包含有參構(gòu)造Node(Object data, Node next)
-
包含私有的單鏈表的Node類(lèi)型的頭結(jié)點(diǎn)first
-
包含public void add(Object element)方法，可以添加元素到當(dāng)前單鏈表中
-
包含私有的非靜態(tài)內(nèi)部類(lèi)Itr，Itr類(lèi)實(shí)現(xiàn)java.util.Iterator接口
- 包含Node類(lèi)型的實(shí)例變量node，初始化為單鏈表的first
- 重寫(xiě)boolean hasNext()方法，判斷node結(jié)點(diǎn)是否為空
- 重寫(xiě)Object next()方法，獲取node對(duì)象的data值，并讓node結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn)
-
單向鏈表SingleLinked類(lèi)實(shí)現(xiàn)java.lang.Iterable接口，
- 重寫(xiě)Iterator iterator()方法，返回非靜態(tài)內(nèi)部類(lèi)Itr的對(duì)象
（2）測(cè)試類(lèi)中創(chuàng)建SingleLinked單鏈表的對(duì)象，并添加（張三、李四、王五、趙六）幾個(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;
}
@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;
}
}
/*
暴露靜態(tài)內(nèi)部類(lè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、字符串壓縮
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-816616.html
實(shí)現(xiàn)簡(jiǎn)易字符串壓縮算法，其中連續(xù)出現(xiàn)2次以上（含2次）的字母轉(zhuǎn)換為字母和出現(xiàn)的次數(shù)。
例如：AAAABCCDEEEEE,壓縮之后為A4BC2DE5。
代碼實(shí)現(xiàn)：文章來(lái)源地址http://www.zghlxwxcb.cn/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());
}
}
}
到了這里，關(guān)于第14章_集合與數(shù)據(jù)結(jié)構(gòu)拓展練習(xí)(前序、中序、后序遍歷,線性結(jié)構(gòu),單向鏈表構(gòu)建,單向鏈表及其反轉(zhuǎn),字符串壓縮)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
