2019-2020-1學期 20192413《網路空間安全專業導論》第四周讀書筆記

• 2019 年 10 月 30 日
• 筆記

第8章 抽象數據類型與子程式
8.1 抽象數據類型
抽象數據類型（Abstract Data Type,ADT):屬性（數據和操作）明確地與特定實現分離的容器。
在計算領域，可以從應用層、邏輯層和實現層這三個方面來觀察數據。
1.應用層：特定問題中的數據的視圖。
2.邏輯（或抽象）層：數據值（域）和處理它們的操作的抽象視圖。
3.實現層：明確表示出了存放數據項的結構，並用程式設計語言對數據的操作進行編碼。
數據結構（data structure）：一種抽象數據類型中的複合數據域的實現。
容器（container）：存放和操作其他對象的對象。
8.2 棧
棧（Stack）：抽象複合結構，只能從一端訪問棧中的元素
1.可以在第一個位置插入元素，也可以刪除第一個元素
2.LIFO(Last In First Out)
3.刪除的項總是在棧中時間最短的項目
4.插入操作（Push推進）沒有任何約束；整個LIFO行為都體現在刪除操作（Pop彈出）上
5.沒有長度屬性，沒有返回棧中項目個數的操作
6.需要確定棧是否為空，當棧空時再彈出項目會出錯
8.3 隊列
隊列（Queue）：一種抽象複合結構，隊列中的項目從一端入，從另一端出
1.插入操作在隊列的尾部（rar）進行，刪除操作在隊列的頭部（front）進行
2.FIFO
3.刪除的總是在隊列中時間最長的項目
4.插入操作沒有任何約束；整個FIFO行為都體現在刪除操作上
8.4 列表
列表的列是無止境的。
列表有三個屬性特徵：項目是同構的，項目是 線性的，列表是 變長的。
項目可以被刪除和檢索，所以列表中的項目必須能夠相互比較。
注意：不要把列表誤認為是數組，因為數組的結構是 內嵌，列表的結構是抽象，而且列表應用於數組中。
鏈式結構（linked structure）：一個將數據項和找到下一項位置的資訊保存到同一容器的實現方法。
鏈式結構以節點的概念為基礎。其中一個節點由兩部分構成： 用戶的數據和指向列表的下一個節點的鏈接或指針。
列表的最後一個節點的指針變數存放的是表示列表結束的符號，通常為 null ，用「/」表示。
無序列表與有序列表的相互比較：
無序列表：該列表的順序並不重要，項目只是隨意被放入其中。
有序列表：項目之間具有語義關係。除了第一個項目之外所有項目都存在某種 排序關係 。除了最後一個項目，所有項目都有著 相同的關係 。
8.5 樹
8.5.1 二叉樹
二叉樹：具有唯一起始節點（根節點）的抽象複合結構，其中每個節點可以有兩個子女節點，根節點和每個節點之間都有且只有一條路徑。
根：樹中唯一的開始節點。
葉節點：沒有子女的樹節點。
除了根節點之外，每個節點都只有一個父母節點。
8.5.2 二叉檢索樹
要在樹上找一個項目，我們必須檢查每一個節點，直到找到想要的那個，或者發現它並不在樹上。
二叉檢索樹就像已排序的列表，節點間存在語義排序。
二叉檢索樹中的節點可以具有0個，1個，2個子女。
二叉檢索樹還具有語義屬性來刻畫樹中節點上的值。（任何節點的值都要大於它的左子樹中的所有節點的值，並且要小於它的右子樹中的所有節點的值）
-在二叉檢索樹中搜索
這種搜索法與線性結構的二分檢索之間很相似，一次計較就排除很大一部分數據。
info（current）：指的就是這個節點的用戶數據。
left（current）：指向的就是這個節點的左子樹的根節點。
null說明指針指向空值
樹的形狀是由項目插入樹的順序決定的。
構造二叉檢索樹
輸出二叉檢索數中的數據
8.5.3 其他操作
8.6 圖
1.樹是表示存在的體系結構中關係的有效方式，也就是說，一個節點之多只有一個指向它的節點(它的父母)。如果去掉這種約束，就得到了另一種數據結構–圖。
2.圖(graph):由一組節點和一組把節點相互連接起來的邊構成的數據結構。
頂點(vertex)：圖中的節點。
邊(弧)(edge(arc)):表示圖中兩個節點的連接的頂點對。
臨頂點(adjacent vertice):通過邊連接起來的兩個頂點。
路徑(path):連接圖中兩個頂點的一系列頂點。
3.無向圖(undirected graph):其中的邊沒有方向的圖。
有向圖(directed graph(digraph)):其中的邊是從一個頂點指向另一個頂點(或同一個頂點)的圖。
8.6.1 創建圖
許多資訊可以被呈現在圖上：頂點、邊和權值。
創建一個表格需要以下操作：
•在表格中添加一個頂點
•在表格中添加一條邊
•在表格中添加一個權值
8.6.2 圖演算法
1.深度優先搜索
當我們試圖在兩個頂點間尋找路徑時，用棧來儲存訪問的頂點。用深度優先搜索來檢查第一個與起點相鄰的頂點。如果它是終點，則搜索結束。否則，檢查所有與第一個頂點相鄰的頂點。同時，我們需要存儲其他和起點相鄰的頂點，隨後需要的時候會用到它們。如果不存在一條從與起點相鄰的第一個頂點出發的路徑，那麼我們回到頂點，嘗試第二個頂點、第三個頂點，以此類推。
2.廣度優先搜索
在廣度優先搜索中，我們想要回溯到儘可能遠，以找到從最初的頂點出發的路徑。因此棧不再是一個適合尋找較早路徑的數據結構。我們採用隊列來保存元素的順序。
3.單源最短路搜索
最小行程次數的航線並不意味著是最短的總距離。最短路遍歷必須說明在搜索過程中城市間的公里數(邊權值的和)，而不是像深度優先搜索和廣度優先搜索那樣。我們想要檢索離當前頂點最近的頂點，也就是說，與此頂點相連的邊權值最小的頂點。我們稱這種抽象容器位優先隊列，被檢索的元素是在隊列中擁有最高優先度的元素。
8.7
許多子程式都是高級語言或語言附帶庫的一部分
參數列表：程式中兩部分之間的通訊機制
形參：列在子程式後的括弧中的標識符
實參：子程式調用中列在括弧中的標識符
8.7.2
傳遞參數的基本方式有兩種：通過值傳遞和通過引用（地址）傳遞
如果一個形參是值參，調用單元將把實參的一個副本傳遞給子程式
如果一個形參是引用參數，調用單元將把實參的地址傳遞給子程式
第九章 面向對象設計與高級程式設計語言
9.1 面向對象方法
9.1.1 面向對象
對象：在問題背景中相關的事物或實體。
類：一組具有相似屬性和行為的對象的描述。
域：類中的特定項，可以是數據或子程式。
方法：定義了類的一種行為的特定演算法。
9.1.2 設計方法
集體討論（第一階段），過濾，場景（確定每個類的行為），責任演算法(為列出的類的責任編寫演算法)
9.1.3 一個電腦示例
9.2 翻譯過程
彙編語言輸入彙編器
9.2.1 編譯器
編譯器：把高級語言編寫的程式翻譯成機器碼的程式。
9.2.2 解釋器
解釋器：輸入用高級語言編寫的程式，指導電腦執行每個語句指定的動作的程式。
編譯/解釋
位元組碼：編譯Java源程式碼使用的標準機器語言。
Java具有可移植性
Java編譯器輸出的程式將被解釋而不是被執行。
Java程式總是被翻譯成位元組碼而不是機器碼。
9.3 程式設計語言的范型
范型：用作模式或模型的實體和一組假設、概念、值和實踐，構成了共享它們的 聚合體 觀察現實的方式，尤其適用於精神學科。
9.3.1 命令式范型
面向過程的范型
面向對象的范型
9.3.2 聲明式范型
聲明式范型是一個描述結果的模型，但是完成結果的過程則不被描述。
這種范型中有兩種基本模型：函數式和邏輯式。
函數式模型：基於函數的數學概念。計算通過對函數求值來實現，而問題求解通過函數調用來實現。因此基本的原理是函數的求值，而不是變數和賦值語句。
Scheme是解釋型語言，因此結果在聲明後立即顯示。
邏輯編程基於象徵邏輯的原則。這個模型包括了一系列關於對象的事實和 一系列關於對象間關係的規則。
一個程式包括了向這些對象和關係詢問可以通過事實和規則推演的問題。
解決潛在問題的演算法用邏輯的規則來推演出事實和規則的答案。