3.6 練習¶
3.6.1 知識鞏固¶
1. 生活場景中的資料關係¶
請根據資料之間的關係，為下面三個場景選擇“線性結構、樹形結構、網狀結構”中的一種，並說明理由：
- 同學們排成一列，每人只關心自己前面和後面的人；
- 學校按“學校 → 年級 → 班級”分層管理；
- 城市道路連線多個路口，一個路口可以通向多個其他路口，也可能形成環路。
參考答案
-
是線性結構。除排在最前和最後的人外，每個人都只與前面和後面各一人相鄰，關係沿一條線展開。
-
是樹形結構。每個班級屬於一個年級，每個年級又屬於學校，關係從上到下分層展開。
-
是網狀結構。一個路口可以連線多個路口，路線之間還能形成環，不能排成單一順序或嚴格層級。
判斷結構時應先觀察元素之間的關係，而不是先考慮它在記憶體中佔多少空間。
2. 邏輯順序怎樣存進記憶體¶
為了儲存邏輯順序 A → B → C，現有兩種簡化的記憶體安排：
- 方案甲：
A、B、C分別放在編號為20、21、22的記憶體格中； - 方案乙：
A、B、C分別放在編號為20、7、31的記憶體格中，並由A記錄B的位置、B記錄C的位置。
- 哪個方案屬於連續空間儲存？哪個屬於分散空間儲存？
- 兩個方案分別更接近陣列還是鏈結串列？
- 方案乙的記憶體格編號沒有按大小排列，為什麼仍能表示
A → B → C的邏輯順序？
參考答案
-
方案甲使用連續的記憶體格，屬於連續空間儲存；方案乙的節點分散在不同位置，屬於分散空間儲存。
-
方案甲更接近陣列，方案乙更接近鏈結串列。
-
邏輯順序由節點之間記錄的連線關係決定，而不是由記憶體格編號的大小決定。 從
A記錄的位置可以找到B，再從B記錄的位置找到C，所以仍能依次訪問A、B、C。這也說明邏輯結構和物理結構是觀察同一組資料的兩個不同角度。
3. 作業記錄中的資料型別與結構¶
某學習小組按座位順序記錄 4 名同學是否交了作業，得到：
[true, false, true, true]
- 每個元素適合使用哪種基本資料型別？
- 這 4 個元素按座位順序排成一列，使用了什麼邏輯結構？
- 如果以後改為記錄每人的作業分數
[90, 0, 85, 100]，改變的是資料的“內容型別”還是“組織方式”？說明理由。
參考答案
-
每個元素只表示“是”或“否”，適合使用布林型別
bool。 -
這些元素按座位順序排列，形成線性結構，可以用陣列儲存。
-
改變的是內容型別：元素由布林值變成了整數。組織方式沒有改變， 這些資料仍然按座位順序排成一列，仍可使用陣列這一線性結構。
基本資料型別描述“存的是什麼”，資料結構描述“資料怎樣組織”。
3.6.2 程式設計練習¶
1. 統計二進位制表示中的 1¶
給定非負整數 n，請統計它的二進位制表示中共有多少個 1。
要求使用位運算完成，不把二進位制表示轉換成字串，也不使用直接統計 1 的內建函式。
解題提示
- n & 1 可以取出 n 的最右邊一位，用它判斷這一位是否為 1
- 右移一位表示丟掉當前最右邊的二進位制位；多數語言使用運算子 >>
- 完成逐位檢查並右移的方法後，再觀察：n & (n - 1) 會把 n 中最右邊的一個 1 變成 0