程序設計基礎
1、程序與程序設計語言的基本知識
1）程序：為解決某一問題而採用程序設計語言編寫的一個指令集合。
程序=算法（對操作的描述）+數據結構（對數據的描述）+程序設計語言+語言工具和環境。
2）程序的特點：目的性、有序性、分步性、有限性、操作性。
3）程序設計語言—按發展過程分類
（1）機器語言
由一連串的0和1二進制代碼組成，能被計算機直接理解和執行的指令集合。
指令格式：
| 操作碼 | 操作數 |
（2）彙編語言
使用「助詞符」來表示指令的操作碼，使用存儲單元或寄存器的名字表示地址碼。
可讀性好，易查錯，方便修改，占存儲空間少，執行速度快。
（3）高級語言
與機器指令系統無關，獨立於機器的程序設計語言，所使用的符號接近人類的自然語言，表達形式接近於被描述的問題。
高級程序設計語言分類：
面向過程的語言：程序不僅要說明做什麼，還要詳細說明如何做，程序需要詳細描述解題的過程和細節；目的在於高效的實現各種算法。
面向問題的語言：又稱為非過程化語言或第四代語言，只需指出要計算機做什麼、數據的輸入和輸出形式，就能得到所需結果；目的在於高效、直接地實現各種應用系統。
面向對象的語言：將客觀事物看作具有屬性和行為的對象，通過抽象找出同一類對象的共同屬性和行為，形成類，通過繼承和多態重用。
4）翻譯程序（編譯器）
（1）定義：其他編程語言必須經過一個翻譯過程才能轉換成機器語言，實現編譯過程的工具是語言處理程序。
（2）彙編程序
定義：將彙編語言編製的程序（稱源程序）翻譯成機器語言程序（稱目標程序）的工具。
翻譯工作的步驟：
用機器操作碼代替符號化的操作符。
用數值地址代替符號名稱。
將常數翻譯為機器的內部表示。
分配指令和數據的存儲單元。
作用：
（3）翻譯程序
定義：將高級語言編寫的源程序翻譯成目標程序的工具。
工作方式：
解釋方式：解釋程序
解釋程序對源程序逐條地解釋執行，不產生目標代碼，程序執行時，解釋程序和源程序一起參加運行。
解釋方式執行速度較慢的原因：
每次運行需重新解釋。
若程序較大，且錯誤發生在程序後面，則前面的運行是無效的。
解釋程序只看到一句語句，無法對整個程序優化。
編譯方式：編譯程序
對整個源程序經過編譯處理後，產生一個與源程序等價的目標程序。
編譯過程的六個階段：詞法分析、語法分析、語義分析、中間代碼生成、代碼優化、目標代碼生成。
5）程序設計語言的支持環境
操作系統是各種軟件的核心和基礎，是整個系統的控制管理中心，為其他軟件提供運行環境。
6）程序設計語言的基本成分和語法
（1）程序的基本語法單位
定義：程序是由語句構成的，而語句又是由數據、表達式、函數等基本語法單位組成的，構成表達式、函數等的最小單位是字符。
字符集：
定義：字符是構成程序設計語言的最小語法單位，每一種程序設計語言都有自己的合法字符集。
基本字符集：數字：0-9
字符：a-z，A-Z
分隔符：，；
運算符：+，-，*，/
數據類型：
定義：數據就是描述客觀事物的數字、字符、圖片等，即所有能輸入到計算機中並能被計算機處理的符號的集合。
分類：基本數據類型：程序設計語言系統內置的。
特點：其值不可再分解。整數類型、實數類型、字符類型、邏輯類型等。
構造數據類型：由基本數據類型按某種方式組合而成的。
數組類型、記錄類型、枚舉類型、集合類型、字符類型、文件等。
使用數據類型的目的：
決定該類型數據的取值形式、範圍和在計算機中的存儲和表示方式。
決定了該類型的數據所能執行的操作種類，即能夠施加到不同類型數據上的運算是不同的。
表達式：
定義：表達式由變量、常量、函數調用和運算符組成。
常量和變量：數據存入內存→存放數據的內存單元命名→內存單元名來訪問其中的數據
常量：在程序運行中數據不變的量。
變量：在程序運行中數據變化的量。
變量在使用前必須聲明其類型和名稱，編譯程序根據其數據類型，在內存中分配相應的存儲空間，以存儲該變量的值。
運算符：
算術運算：加減乘除和乘方。
字符運算：連接、取子串
關係運算：大於、大於等於、小於、小於等於、等於、不等於
邏輯運算：與、或、非
內部函數：按功能分為數學函數、字符串函數、日期函數、轉換函數。
賦值語句：表達式和賦值號構成了程序設計的一條賦值語句。
（2）數據的輸入和輸出
一類：程序之間以文件形式傳送數據。
二類：人機交互，將人們可以識別的形式按一定格式輸入到程序的變量中，輸出則相反，按用戶的要求格式將變量或常量的值顯示或打印。
（3）基本控制結構
順序結構：指程序的執行按照語句出現的先後順序一次執行。
選擇結構：根據條件判斷，決定程序的執行順序。
循環結構：指重複執行某個操作。
（4）過程：指重複處理的程序段或者分解的子功能編寫成一個邏輯上獨立的過程，當程序需要該過程時進行調用。
2、算法的基本知識
1）算法的描述：程序—計算機語言表述的算法。
流程圖—圖形化的算法。
2）計算機的算法
（1）數值計算算法
目的：求數值解。
特點：少量輸入、輸出，複雜的運算。
（2）非數值計算算法
目的：對數據的處理。
特點：大量輸入、輸出，簡單的運算。
3）算法的定義：是解決問題方法的精確描述，但算法並不給出問題的精確解，只是說明怎樣才能得到解。
4）算法的性質：有窮性、確定性、有效性、零個或多個輸入、一個或多個輸出
5）算法=數據對象的運算和操作（算數運算、邏輯運算、關係運算、數據運算）+控制結構（順序結構、選擇結構、循環結構）。
6）描述算法的方法
（1）自然語言
優點：通俗易懂
缺點：易產生歧義，往往根據上下文才能判斷其含義，不嚴格；語句繁瑣、冗長，很難清楚地表達算法的邏輯流程。
（2）流程圖法
定義：用圖框、線條、文字說明，形象直觀的描述算法。
流程圖符號：
—起止框：表示流程的開始或結束。
—輸入輸出框：表示輸入數據或輸出結果。
—判斷框：根據條件判斷，決定算法的繼續執行的走向。
—處理框：表示基本功能的處理的描述。
—流程線：表示流程的路徑和方向。
—連接點：表示流程中「向」和「來自」其他地點的輸出或輸入。
（3）N-S流程圖法：全部算法以一個大的矩形框表示，內包含一些從屬於它的小矩形框。
順序語句：
選擇語句：
循環語句：
（4）偽代碼法：簡稱偽碼，偽代碼是介於自然語言和計算機語言之間的文字和符號來描述算法。
7）算法評價
（1）正確性：設計和評價算法的首要條件。
（2）算法的時間特性：指依據算法編製成程序後在計算機中運作所耗費時間的長短。
算法的時間複雜度：把程序中語句重複執行次數之和作為程序運行時的時間特性。
（3）算法的空間特性：指依據算法編製成程序後在計算機中運行所佔用空間的大小。
算法的空間複雜度：在計算機上運行所佔用的空間同樣也是問題規模n的一個函數。
（4）算法的易理解性。
3、程序設計的過程。
1）程序設計步驟
2）測試的前提：程序通過編譯，沒有語法和連接上的錯誤。
3）測試用例：為了發現程序中的錯誤而設計的測試數據。
4）黑盒測試：又稱功能測試或數據驅動測試，不考慮程序的內部結構和處理過程，只對程序的接口進行測試，檢查程序是否能適當地接受輸入數據併產生正確的輸出信息。
黑盒測試技術有事務處理流程測試、等價類劃分、邊界值分析。
5）白盒測試：又稱結構測試或邏輯驅動測試，檢驗程序內部的邏輯來測試，檢查程序中每條通路是否正確工作。
百合測試有路徑測試、語句測試、分支測試、條件組合測試。
4、程序設計思路
1）三種基本程序結構
（1）順序結構：
特點：只有一個入口點和一個出口點。
組成：說明語句、賦值語句、輸入輸出語句、子函數調用語句、返回語句。
（2）選擇結構：
特點：程序的處理步驟出現分支，根據某一特定的條件選擇其中的一個分支執行。
形式：單選澤、雙選擇、多選擇。
（3）循環結構
當型循環：先判斷後執行。
直到型循環：先執行後判斷。
2）結構化程序設計的基本思想
採用「自頂向下，逐步求精」（基本原則）的程序設計方法，結構化設計以模塊化設計為中心，每個模塊各個擊破，最後再統一組裝。
3）結構化程序設計的特徵
（1）以三種基本結構的組合來描述程序
（2）整個程序採用模塊化結構。
（3）以控制結構為單位，每個結構只有一個入口一個出口，各單位之間接口簡單，邏輯清晰。
（4）採用結構化程序設計語言書寫程序，並採用一定的書寫格式使程序結構清晰，易於閱讀。
（5）注意程序設計風格。
（6）有限制地使用轉移語句，在非用不可的情況下，只限於在一個結構內部跳轉，不允許從一個結構跳到另一個結構。
4）良好的設計風格
語句形式化、程序一致性、結構規範化、適當使用注釋、標識符貼近實際。
5）面對對象的基本概念
（1）對象（object）—最簡單的實體
對現實世界中對象的模式化，是數據和代碼的組合，具有自己的特徵和行為。
對象的特徵用數據來表示，稱屬性。
對象的行為用對象中的代碼來實現，稱為對象的方法。
任何對象都由屬性和方法組成的。
將反映對象的屬性和行為封裝在一起，是面向對象編程的基本元素，是面向對象設計的核心。
（2）類（class）
類是創建對象實例的模板，是同種對象的集合與抽象，它包含所創建對象的屬性描述和行為特徵的定義，對象是類的實例。
（3）屬性（property）
屬性用來表示對象的特徵，不同的對象有不同的屬性。
（4）方法（method）
方法是對對象的屬性的各種操作。
（5）事件、事件過程和事件驅動
事件是面向對象程序設計中對應於「消息」的術語。
對象的事件是指系統事先設定的，能被對象識別和響應的動作。
事件過程：應用程序處理事件的步驟。
事件驅動的編程機制是程序執行後系統等待某個事件的發生，然後去執行處理此事件過程，待事件過程執行完後，系統又處於等待某事件發生的狀態。
（6）封裝
封裝機制將數據和代碼捆綁在一起，避免了外界的干擾和不確定性。一個對象就是一個封裝了數據和操作這些數據的代碼的邏輯實體，封裝的目的在於將對象的使用者和對象的設計者分開。
封裝一方面通過數據抽象把相關的信息結合在一起，另一方面簡化了接口。
封裝性可降低開發過程的複雜性，提高效率和質量，同時也保證了程序中數據的完整性和安全性。
（7）繼承
繼承是可以讓某個類型的對象獲得另一個類型的對象的屬性的方法。
（8）多態性
多態機制使具有不同內部結構的對象可以共享相同的外部接口，雖然針對不同對象的具體操作不同，但通過一個公共類，他們可以通過相同的方式調用。
優點：大大提高程序的抽象程度和簡潔性，降低類和模塊之間的耦合性，有利於程序的開發和維護。
（9）消息傳遞
6）OOP的基本過程
（1）分析現實問題。
（2）建立模型（類屬性/方法的確定及類之間關係的確定）。
（3）編程建立數據模型（屬性、方法）。
（4）用類聲明對象，通過對象間傳遞信息（方法調用）完成預訂功能。
7）OOP的優點
（1）通過繼承，減少多餘的代碼並擴展現有代碼。
（2）在標準的模塊上構建自己的程序，減少軟件開發時間並提高生產效率。
（3）數據隱藏—保護程序免受外部代碼的侵襲。
（4）允許一個對象的多個實例同時存在，彼此之間相互不干擾。
（5）允許將問題空間中的對象直接映射到程序中。
（6）基於對象的工程可以很容易地分割為獨立部分。
（7）以數據為中心的設計方法允許我們抓住可實現模型的更多細節。
（8）面向對象的系統很容易從小到大逐步升級。
（9）對象間通信所使用的消息傳遞技術與外部系統接口部分描述更簡單。
（10）便於控制軟件複雜度。
