SOP-C#資料結構-筆記

=========

C#資料結構(參考書目：資料結構使用Visual C#。ISBN：978-986-500-413-2)

  CH4-鏈結串列

    類別,物件及成員(屬性,方法)

      1.public 公開 所有類別皆可存取

      2.private 私有 只適用該類別的成員函數

      3.protected 保護 產生繼承關係的衍生類別可取用

      4.internal 內部 只適用於目前專案(組件)

      5.protected internal 只適用於目前(組件)或衍生自包含類別的型別

    

    建構子

      1. 語法：ClassName() ex. Student()

      2. 建構子存取修飾詞必須使用 public

      3. 一個類別可以有多個建構子(又稱多載),它不能有回傳值,也毋須用void

      4. 類別若不含任何具參數建構子時,程式自動呼叫<預設建構函式>

    解構子

      1. 語法：~ClassName() ex. ~Student()

      2. 解構子不能使用存取修飾詞

      3. 一個類別只能有1個解構子,它不含任何參數,不能有回傳值,無法被繼承或多載

      4. 解構子無法直接呼叫,只有物件被清除時才會執行

    環狀串列

      1.它和單向鏈結串列相似,不同點在於必須將 (最後1個節點) 指向 (第1個節點)

      2.優:

          回收時間固定,無關長度

          可從任一節點追蹤所有節點

      3.缺:

          多1個鏈結空間

          插入節點須改變兩個鏈結

          讀取較慢,因為須多讀取一個鏈結指標

    

    雙向鏈結串列

      1.它和單向鏈結串列相似,不同點在於它有 (左) 和 (右) 兩個節點,而單向鏈結串列只有1個節點 (指向下個節點)

      2.它的(左) 和 (右) 兩個節點,(左)節點指向前節點,(右)節點指向次節點

      3.優:

          已知前後節點,刪除或新增時,較單向節點快

          鏈結斷裂時,可從另一方向重建

      4.缺:

          多一個鏈結空間

          新增節點時,要變更4個鏈結

          刪除節點時,要變更2個鏈結

  CH3-善用陣列

    稀疏矩陣,儲存方式

      1.直接利用 M*N 兩維陣列來儲存，但是浪費空間

      2.利用 三行式結構 儲存非零元素 (row,column,value)

        範例：假設有1個 M*N 的稀疏矩陣，內有 K 個非零元素，須準備 Ary[0:K,1:3]的二維陣列。

        另外,Ary[0,1]：存放稀疏矩陣的列數(M)

            Ary[0,2]：存放稀疏矩陣的欄數(N)

            Ary[0,3]：稀疏矩陣內非零元素(K)

    1.靜態資料結構又稱為 <陣列> ，它使用 <連續記憶體空間> ，儲存有序串列的資料。

    2.<動態記憶體配置> 是指變數儲存配置的過程是在執行(Run time)時，透過作業系統提供可用的記憶體空間。

    3.陣列結構具有的特色，是 佔用 <連續> 的記憶體空間，所存放的元素，其 <資料型態> 皆相同。

    4.int[] grade = {51,63,92,75,84};

      上述宣告了grade是 <1維數值> 陣列，並以大括號作 <陣列值初始化>

    5.要設定陣列元素，可呼叫Array類別的方法 <Array.SetValue(value,index)> ，其屬性 <Array.Length> 能取得陣列長度。

    6.要排序陣列元素，可呼叫Array類別的方法 <Array.Sort(array)>，反轉陣列元素則為 <Array.Reverse(array)>

    7.int[,] Ary = new int[3,4];

      上述宣告了Ary <2維數值> 陣列，其中的 <3> 是列數，欄數是 <4>，取得2維陣列長度的方法為 GetLength(維度);

    8.宣告 <2 * 3 * 4>的3維陣列

      int[,,] aryT = new int[2,3,4];

    9.如何處理稀疏矩陣？

      作法1：直接以 <M*N> 2維陣列儲存

      作法2：使用 <三行式結構> 儲存非零元素

    10.字串初始化為空字串，使用 <String.Empty> 屬性

      字串中插入指定字串，使用 <string.Insert(index,value)> 方法

      字串中取得部份字串，使用 <string.Substring(index,?length)> 方法

      

  CH2-話說資料結構

    演算法的特性(五大特性)

      輸入：零個或多個輸入資料，輸入要清楚的描述或定義。

      輸出：至少會有一個輸出結果，不可以沒有輸出結果。

      明確性：每個指令或步驟必須簡潔明確。

      有限性：在有限步驟後會結束，不會產生無窮迴圈。

      有效性：步驟清楚可行，可用紙筆算出結果。

    

    試述演算法與程式流程圖的關係為何？

      演算法可以用程式流程圖來表現，但是程式流程圖可包含無限迴圈，所以無法利用演算法來表達。

    

      利用文字描述來表示其演算法，並以C#自訂方法來寫出此程式

      情境2：輸入1數值，計算其階乘值

        演算法(文字描述)：

          步驟1：輸入1數值

          步驟2：(執行次數為輸入數值-1次)減1前數值 * 減1後數值

      情境1：有3位同學，每人有5科成績，求每位同學的總分及平均分數，及平均分數高於60分的同學。

        演算法(文字描述)：

          步驟1：輸入{同學X}的5科成績

          步驟2：計算{同學X}的總分及平均分數

          步驟3：若平均分數大於60分，則顯示出來

          步驟4：總共執行3次