抽象數(shù)據(jù)類型與子程序

抽象數(shù)據(jù)類型

屬性（數(shù)據(jù)和操作）明確地與特定實現(xiàn)分離的容器。設(shè)計的目標(biāo)是通過抽象減小復(fù)雜度。

應(yīng)用層（特定問題中的數(shù)據(jù)的視圖）、邏輯層（數(shù)據(jù)值和處理操作的抽象視圖）和實現(xiàn)層（明確存放數(shù)據(jù)項的結(jié)構(gòu)，并用程序設(shè)計語言對數(shù)據(jù)的操作進(jìn)行編碼）

棧

棧是一種抽象復(fù)合結(jié)構(gòu)，只能從一段訪問棧中的元素。

LIFO：可以在第一項插入元素，也可以刪除第一個元素。（push pop）

隊列

項目從一端入，從另一端出，插入在尾部，刪除在頭部。（Enqueue,Enque,Enq,Enter,Insert表示插入，Dequeque,Deque,Deq,Delete Remove表示刪除）

列表

項目是同構(gòu)的，項目是線性的，列表是變長的。

插入：Insert，刪除：Delete，檢索：IsThere，項目數(shù)：GetLength，有些機(jī)制允許查案每一項：Reset,Getext,MoreItems

也可以被形象化為鏈?zhǔn)浇Y(jié)構(gòu)：一個節(jié)點由用戶的數(shù)據(jù)和指向列表的下一個節(jié)點的鏈接或指針組成，最后一個節(jié)點指針存放的是表示列表結(jié)束的符號，通常為null或者“/”有序列表項目有語序關(guān)系

樹

非線形，每個節(jié)點下有多個節(jié)點

二叉樹

每個節(jié)點可以至多有兩個后集結(jié)點，子女，起始節(jié)點叫做根，如果一個節(jié)點沒有子女，則這個節(jié)點叫做樹葉。

二叉檢索樹

任何節(jié)點的值都要大于它的左子樹中的所有節(jié)點的值，并且小于它的右子樹中所有節(jié)點的值

在二叉檢索樹中檢索方法與二分檢索法類似

info（current）：訪問當(dāng)前節(jié)點的用戶數(shù)據(jù)

right(current)：指向current的右子樹的根節(jié)點

left(current)：指向current的左子樹的根節(jié)點

如果一個指針是null，則這個子樹是空的。

沿根節(jié)點開始沿著后繼子樹前進(jìn)，直到找到搜索的項目或者空子樹。

構(gòu)建二叉樹根插入順序有關(guān)，要輸出根的值，先輸出左子樹的所有，本身，再輸出右子樹的所有。

圖

由一組節(jié)點（頂點）和連接節(jié)點的線段（邊/弧）構(gòu)成

如果圖的邊是無向的，則為無向圖，邊有向則為有向圖。

如果兩個頂點有一條邊相連，則把它們稱為鄰頂點

創(chuàng)建一個表格操作如下：

在表格中添加一個頂點

在表格中添加一條邊

在表格中添加一個權(quán)值

圖算法

1. 深度優(yōu)先搜索

從起點到終點的路徑的算法，用棧來存儲訪問頂點，用深度優(yōu)先搜索來檢查第一個與起點相鄰的頂點，看他是不是終點，同時存儲其它和起點相鄰的頂點。一旦我們把一個頂點所有的相鄰頂點都放到棧內(nèi)，就標(biāo)記這個頂點為訪問過。已訪問過的不會被回溯，所以該方法會選擇一條盡可能可以走遠(yuǎn)的路

2. 廣度優(yōu)先搜索

怎樣用最少的停頓次數(shù)到達(dá)。運用隊列而不是棧，優(yōu)先檢查與起點相鄰的頂點，而深度優(yōu)先檢查與相鄰頂點相連的其他頂點

3. 單源最短路搜索

找最短航線。優(yōu)先隊列，尋找與頂點相連的邊權(quán)值最小的頂點。

子程序

一般的軟件庫里有

參數(shù)列表是子程序要使用的標(biāo)識符或值的列表，它放置在子程序名后的括號中。括號中聲明了一個變量名的列表（形參），調(diào)用單元列出子程序名，這時括號中的一系列標(biāo)識符為實參。在調(diào)用過程中，實參逐步替代形參。實參個數(shù)必須與形參一致。

值參與引用參數(shù)

如果一個形參是值參，調(diào)用單元將把實參的一個副本傳遞給子程序。如果一個形參是引用參數(shù)，調(diào)用單元將把實參的地址傳遞給子程序。前者調(diào)用單元不會改變原是變量，而后者可以改變實際變量。

面向?qū)ο笤O(shè)計與高級程序設(shè)計語言

面向?qū)ο笤O(shè)計的重點是對象以及他們在問題中的交互，一旦收集到了問題中的所有對象，他們就能構(gòu)成問題的解決方案。面向?qū)ο笤O(shè)計的底層概念是類和對象。對象是在問題背景中具有意義的事物或?qū)嶓w。對象類簡稱類，描述了一組類似的對象，是把對象歸入相關(guān)的組，并描述他們共性的思想，特定的對象只是類的一個實例，類中包括的字段表示類的屬性，方法是處理對象中的數(shù)據(jù)值的指定算法。類是一個模式，說明了對象是什么（字段）以及他的行為（方法）。面向?qū)ο笤O(shè)計的重點是要轉(zhuǎn)換的數(shù)據(jù)對象，結(jié)果生成的是對象的體系結(jié)構(gòu)

設(shè)計方法

頭腦風(fēng)暴→過濾→場景→責(zé)任算法→總結(jié)

注解：

頭腦風(fēng)暴為的是生成解決某個特定問題要用到的候選類的列表

場景：給每個類分配責(zé)任（類自身必須知道什么和類必須能夠做什么）

封裝：把數(shù)據(jù)和動作集中在一起，使數(shù)據(jù)和動作的邏輯屬性與它們的實現(xiàn)細(xì)節(jié)分離（抽象關(guān)鍵）

翻譯過程

編譯器

翻譯用高級程序設(shè)計語言編寫的程序的程序叫編譯器。任何計算機(jī)只要有具有一種高級語言的編譯器，就能運用這種語言編寫的程序，要編譯一個程序，就必須具有這個編譯器在特定機(jī)器上的機(jī)器碼版本。

解釋器

解釋器是一種程序，用于翻譯和執(zhí)行語句序列。解釋器在翻譯過語句之后，會立即執(zhí)行這個語句，可以把解釋器看做編寫程序所使用的語言的模擬器或虛擬機(jī)。JAVA 被編譯成一種標(biāo)準(zhǔn)機(jī)器語言字節(jié)碼，一種名為JVM的軟件解釋器接受字節(jié)碼程序，然后執(zhí)行它。字節(jié)碼不是特定硬件處理器的機(jī)器語言，任何具有JVM的機(jī)器都可以運行編譯過的JAVA程序

程序設(shè)計語言范型

命令式范型

1. 面向過程的范型：語句被分組為子程序，程序是子程序分層次構(gòu)成的，每一層執(zhí)行整個問題求解的一個必要的特定任務(wù)
2. 面向?qū)ο蟮姆缎停好嫦驅(qū)ο笠暯鞘桥c對象交互的一種方式。每個對象負(fù)責(zé)制行它自己的動作，數(shù)據(jù)被認(rèn)為是被動并且被程序所操控的，在此類型中，數(shù)據(jù)對象是活躍的。

聲明式范型

函數(shù)式模型：計算通過對函數(shù)求值來實現(xiàn)，而問題求解通過函數(shù)調(diào)用來實現(xiàn)（形式：（函數(shù) 操作數(shù)））

邏輯編程：邏輯編程基于數(shù)理邏輯，模型包括了一系列關(guān)于對象的事實和一系列關(guān)于對象間關(guān)系的規(guī)則

高級程序設(shè)計語言的功能性

選擇和重復(fù)（循環(huán)）是命令式語言的標(biāo)志

布爾表達(dá)式

是一個標(biāo)識符序列，標(biāo)識符之間由相容的運算符分隔，求得的值是true or false，可以是一個布爾變量，一個算術(shù)表達(dá)式加一個關(guān)系運算符再加一個算術(shù)表達(dá)式，一個布爾表達(dá)式加一個布爾運算符再加一個布爾表達(dá)式。

！=或/=或<>表示不等于

數(shù)據(jù)歸類

只能在變量中存儲合適的類型的要求叫做強(qiáng)類型化。

數(shù)據(jù)類型（簡單數(shù)據(jù)類型、原子數(shù)據(jù)類型）

• 整數(shù)
• 實數(shù)（通常不精確）
• 字符
• 布爾型

字符串：字符序列，在某些語言中整個序列被看作一個數(shù)據(jù)值。

聲明

聲明是把變量、動作或語言中的其他實體與標(biāo)識符關(guān)聯(lián)起來的語句，是程序員可以通過名字引用這些項目。

保留字是一種語言中具有特殊意義的字，不能用作標(biāo)識符。

輸入/輸出結(jié)構(gòu)

變量在輸入語句中的順序必須與值出現(xiàn)在輸入流中的順序一樣，輸入的變量的類型決定了如何解釋輸入流中的字符。非強(qiáng)類型中，輸入格式?jīng)Q定類型。如果輸入出現(xiàn)在引號之間，則它被假定為一個字符串。

輸出語句創(chuàng)建字符流，項目可以是文字值（直接在輸出語句中寫的東西）或者變量名。

關(guān)鍵在于數(shù)據(jù)類型，它決定了字符是如何被轉(zhuǎn)化為位模式（輸入）及如何被轉(zhuǎn)換為字符（輸出），在非強(qiáng)類型中，輸入格式?jīng)Q定了位模式是如何轉(zhuǎn)換的。

控制結(jié)構(gòu)

重復(fù)、選擇和子程序

• 嵌套邏輯 一個控制結(jié)構(gòu)中含有另一個
• 異步處理 與程序的操作不同步，也叫做事件驅(qū)動處理

面向?qū)ο笳Z言的功能性

封裝

包括信息隱蔽和抽象。信息隱蔽是為了控制對細(xì)節(jié)的訪問，是實現(xiàn)抽象的方法。

封裝用具有正式定義的接口的獨立模塊把實現(xiàn)模塊隱藏了起來。用于提供封裝的結(jié)構(gòu)叫作類。

類

主動結(jié)構(gòu)，將子程序用作字段。如果用標(biāo)識符來表示一個類，需要用new操作符來實例化這個類。算法聲明類的對象只能通過子程序訪問類的字段

繼承

一個類可以繼承另一個來的數(shù)據(jù)和方法。超類是被繼承的類；派生類是繼承的類。在類的體系中，所處的層次越低，對象越專門化。繼承通過允許應(yīng)用程序使用已經(jīng)被測試過的類和從一個類中繼承應(yīng)用所需的屬性來促進(jìn)重用，可以繼承后添加內(nèi)容。

多態(tài)

程序設(shè)計語言處理中的明顯二義性叫作多態(tài)。

過程設(shè)計與面向?qū)ο笤O(shè)計的區(qū)別

通過ADT列表算法的實現(xiàn)來描述值返回和非值返回子程序，ADT的實現(xiàn)是一個變量列表的記錄，其中存儲了一個數(shù)組的值和字段的長度。

列表數(shù)據(jù)結(jié)構(gòu)和子程序需要在類中綁定在一起，方法代碼需要直接訪問到類變量，用戶代碼需要在程序中包含它。

在面向過程的版本中，列表被呈現(xiàn)為傳遞給子程序的記錄，以便子程序可以對其操作，操作它的數(shù)據(jù)結(jié)構(gòu)和子程序是用戶程序的一部分；面向?qū)ο蟮陌姹局校悓ο蟮膶崿F(xiàn)通過封裝實現(xiàn)對用戶的隱藏。