20172324 2018-2019-1《程序設計與數據結構》實驗2報告

課程：《程序設計與數據結構》
班級： 1723
姓名： 曾程
學號：20172324
實驗教師：王志強
實驗日期：2018年9月30日
必修/選修： 必修

一、實驗內容

鏈表練習

• 實驗一：參考教材p212,完成鏈樹LinkedBinaryTree的實現（getRight,contains,toString,preorder,postorder

  1. 用JUnit或自己編寫驅動類對自己實現的LinkedBinaryTree進行測試，提交測試代碼運行截圖，要全屏，包含自己的學號信息
• 實驗二：基于LinkedBinaryTree，實現基于（中序，先序）序列構造唯一一棵二?樹的功能

  1. 比如給出中序HDIBEMJNAFCKGL和后序ABDHIEJMNCFGKL,構造出附圖中的樹

  2. 用JUnit或自己編寫驅動類對自己實現的功能進行測試，提交測試代碼運行截圖，要全屏，包含自己的學號信息

• 實驗三：自己設計并實現一顆決策樹
  

• 實驗四：輸入中綴表達式，使用樹將中綴表達式轉換為后綴表達式，并輸出后綴表達式和計算結果
  1. 如果沒有用樹，則為0分
  2. 提交測試代碼運行截圖，要全屏，包含自己的學號信息
• 實驗五：完成PP11.3

• 實驗六：：參考http://www.cnblogs.com/rocedu/p/7483915.html對Java中的紅黑樹（TreeMap，HashMap）進行源碼分析，并在實驗報告中體現分析結果

二、實驗過程及結果

• 實驗1結果截圖：

  • LinkedBinaryTree中有給出getLeft的方法，所以根據所給的getLeft補寫出getRight方法
  • 書上說：contains方法留作程序設計項目，它可以使用find方法判定目標元素是否存在于樹中
  • LinkedBinaryTree要補寫preorder,postorder，LinkedBinaryTree中給出了inorder的方法，根據inorder寫出preorder和postorder
    

• 實驗2結果截圖：

  • 前序是：根左右的順序，中序是左根右的順序。首先找root，前序的第一個是root；觀察前序，除根之外的必在左右子樹；觀察中序，root左側的為左子樹，右側的為右子樹；在左子樹和右子 樹中根據前序再判斷誰是根；同樣道理，以此類推
    

• 實驗3結果截圖：
  

• 實驗4結果截圖：
  

• 實驗5結果截圖：
  二叉搜索樹是一種特殊的二叉樹，即：節點的左子節點的值都小于這個節點的值，節點的右子節點的值都大于等于這個節點的值
  比根節點要小的數會放在當前根節點的左子結點，因此要實現findMin()只要獲取該樹的最左邊的結點即是最小值
  比根節點要大的數會放在當前根節點的右子結點，因此要實現findMax()只要獲取該樹的最右邊的結點即是最大值

• 實驗6分析：
  最后一個實驗是對Java中的紅黑樹（TreeMap，HashMap）進行源碼分析，首先要了解紅黑樹是什么，第七周博客中有提到過。
  TreeMap類

public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable

• TreeMap(K,V) K - 此映射維護的鍵的類型 V - 映射值的類型
• TreeMap 繼承于AbstractMap，所以它是一個Map，即一個key-value集合。
• TreeMap 實現了NavigableMap接口，意味著它支持一系列的導航方法。比如返回有序的key集合。
• TreeMap 實現了Cloneable接口，意味著它能被克隆。
• TreeMap 實現了java.io.Serializable接口，意味著它支持序列化。
• TreeMap() 使用鍵的自然順序構造一個新的、空的樹映射。
• TreeMap(Comparator<? super K> comparator) 構造一個新的、空的樹映射，該映射根據給定比較器進行排序。
• TreeMap(Map<? extends K,? extends V> m) 構造一個與給定映射具有相同映射關系的新的樹映射，該映射根據其鍵的自然順序 進行排序。
• TreeMap(SortedMap<K,? extends V> m) 構造一個與指定有序映射具有相同映射關系和相同排序順序的新的樹映射。
  firstEntry()和getFirstEntry()方法：

public Map.Entry<K,V> firstEntry() {return exportEntry(getFirstEntry());
}
final Entry<K,V> getFirstEntry() {Entry<K,V> p = root;if (p != null)while (p.left != null)p = p.left;return p;
}

firstEntry() 和 getFirstEntry() 都是用于獲取第一個節點。firstEntry() 是對外接口；getFirstEntry() 是內部接口。而且，firstEntry() 是通過 getFirstEntry() 來實現的。
那么為什么不直接調用getFirstEntry() ，而調用 firstEntry() 呢?這么做的目的是：防止用戶修改返回的Entry。getFirstEntry()返回的Entry是可以被修改的，但是經過firstEntry()返回的Entry不能被修改，只可以讀取Entry的key值和value值。

HashMap類
初始容量與加載因子是影響HashMap的兩個重要因素：

public HashMap(int initialCapacity, float loadFactor)

初始容量默認值：

/*** The default initial capacity - MUST be a power of two.*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

加載因子默認值：

/*** The load factor used when none specified in constructor.*/static final float DEFAULT_LOAD_FACTOR = 0.75f;

• HashMap<K,V> K - 此映射所維護的鍵的類型 V- 所映射值的類型
• HashMap() 構造一個具有默認初始容量 (16) 和默認加載因子 (0.75) 的空 HashMap。
• HashMap(int initialCapacity) 構造一個帶指定初始容量和默認加載因子 (0.75) 的空 HashMap。
• HashMap(int initialCapacity, float loadFactor) 構造一個帶指定初始容量和加載因子的空 HashMap。

• HashMap(Map<? extends K,? extends V> m) 構造一個映射關系與指定 Map 相同的新 HashMap。
  如果在map中包含對應的特定的鍵值則返回true，否則返回false。
  方法有些類似于contains方法，在功能上contains檢測是否有對應關聯的鍵，containsValue檢測是否有對應的值，內部使用V（泛型）定義一個值，而Node<K,V>實現了Map.Entry<K,V>這個接口，每個key-value都放在了Node<K,V>這個對象中，采用 Node<K,V>[] tab 數組的方式來保存key-value對，之后判斷tab數組是否為空，size是transient聲明的實例變量，確保其大于0后，遍歷存放key-value的tab數組，每對鍵值又定義了e來保存并遍歷，直到e對應的下一個值為空，將e對應的某值賦給v，最后判斷是否和指定值地址相同，或者判斷是否鍵值不為空并且字符完全相同，至少一者成立才能返回true，比之前鏈表中contains方法的開銷、時間復雜度更大。

  三、實驗過程中遇到的問題和解決過程

• 問題一：實驗四的思考過程

• 問題一解決方案：根據上學期學習的后綴表達式的特點，我們可以知道，只要是運算符的就都是根結點。我們這里需要使用一個棧來保存字符。遍歷后綴表達式，每當遇到是非運算符的字符，就將它入棧，當遇到是運算符，就將棧中前兩個結點出棧，和運算符組成一棵子樹，然后入棧。遍歷完成后，棧中剩下的唯一的一個結點就是該后綴表達式的二叉樹的根結點。但是做著做著發現好像和書上提供的代碼是一樣的，Java實驗肯定不會只是書上的代碼，然后仔細分析了題目發現和書上不一樣的地方在書上是直接輸入后綴表達式，實驗要求的是利用樹將中綴轉后綴之后再用后綴表達式計算。大概想法就變成了將表達式的每一個元素進行拿出，按照數字、加減運算符、乘除運算符分成三種情況，用兩個棧或者鏈表進行保存加減和構成樹的結點。

四、其他（感悟、思考等）

五、參考資料

• Java Collections API源碼分析

轉載于:https://www.cnblogs.com/amberR/p/9942355.html

總結

以上是生活随笔為你收集整理的20172324 2018-2019-1《程序设计与数据结构》实验2报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。