1、棧棧 一端開口（棧頂），一端封閉（棧底）一端開口（棧頂），一端封閉（棧底） 棧頂棧頂top 先進后出（相反）先進后出（相反） 棧棧滿：滿：top=n；棧空：；棧空：top=0 計算棧中數據個數計算棧中數據個數：初始棧滿初始棧滿n-當前；當前當前；當前-初始棧空初始棧空0 方法：大數方法：大數-小數小數隊列隊列 兩端均開放兩端均開放 循環隊列人數的計算循環隊列人數的計算 1.隊尾隊尾隊頭隊頭:隊尾隊尾-隊頭隊頭 2.隊尾隊尾希希爾爾排序排序其余四種其余四種 選擇排序（選擇排序（2種）種） 插入排序（插入排序（2種）種） 交換排序（交換排序（2種）種） 最壞比較次數為最壞比較次數為n(n-1)/2

2、程序設計方法程序設計方法 分類分類: 面向結構化程序設計面向結構化程序設計 面向對象程序設計面向對象程序設計 設計要求設計要求:清晰第一清晰第一,效率第二效率第二面向結構化程序設計面向結構化程序設計 三種基本結構三種基本結構 順序順序、選擇選擇、循環循環 主要特點主要特點: 自上而下自上而下 逐步求精逐步求精 模塊化模塊化 避免使用避免使用goto語句語句面向對象程序設計面向對象程序設計 對象對象:屬性屬性和和操作操作的封裝體。的封裝體。 類類:具有相似屬性與操作的一組對象。具有相似屬性與操作的一組對象。 實例實例 對象的屬性對象的屬性: 標識唯一性標識唯一性,封裝性封裝性,分類性分類性,多態

3、性多態性 類的屬性類的屬性:繼承性繼承性軟件軟件 組成組成:程序程序,數據數據和和文檔文檔。 軟件分類軟件分類:系統軟件系統軟件,工具軟件（通用性）和工具軟件（通用性）和應用軟件（非通用性）。應用軟件（非通用性）。 軟件工程三要素軟件工程三要素:方法方法,工具和過程。工具和過程。 軟件生命周期軟件生命周期: 定義階段定義階段,開發階段開發階段和維護階段。和維護階段。 開發階段開發階段4步驟步驟: 需求分析需求分析,設計設計,編碼編碼,測試測試。 軟件危機軟件危機:周期周期,質量質量,價格。價格。模塊獨立性模塊獨立性 內聚性內聚性:模塊內部模塊內部 耦合耦合性性:模塊之間模塊之間 高內高內聚低耦

4、合聚低耦合流程圖流程圖 數據數據流程圖流程圖(DFD):用于結構化用于結構化分析分析 數據字典：流程圖的核心（解釋作用）數據字典：流程圖的核心（解釋作用） 程序程序流程圖流程圖(PFD):用于結構化用于結構化設計設計測試和調試測試和調試 軟件測試軟件測試:發現錯誤發現錯誤 軟件調試軟件調試:發現并改正錯誤發現并改正錯誤 測試方法測試方法:黑黑盒測試和白盒測試盒測試和白盒測試 白白盒：覆蓋法盒：覆蓋法，基本路徑測試基本路徑測試 軟件測試軟件測試4步驟步驟: 單元測試單元測試,集成測試集成測試,驗收測試驗收測試,系統測試系統測試E-R圖圖 三要素三要素: 實體實體:矩形矩形 屬性屬性:橢圓橢圓 聯

5、系聯系:菱形菱形 聯系分類聯系分類:一對一一對一,一對多一對多,多對多多對多數據庫數據庫 數據庫核心數據庫核心:DBMS(數據庫管理系統數據庫管理系統) 數據庫系統數據庫系統,數據庫管理系統和數據庫關系。數據庫管理系統和數據庫關系。 數據庫設計數據庫設計4階段階段: 需求分析需求分析,概念設計概念設計,邏輯設計邏輯設計,物理設計。物理設計。 數據庫語言數據庫語言:定義語言定義語言,操縱語言操縱語言,控制語言。控制語言。 操縱操縱語言：增加，修改，刪除，查詢語言：增加，修改，刪除，查詢 數據庫模式數據庫模式:內模式（內模式（1個）個）,概念模式概念模式,外模式外模式（n個）。個）。 數據庫中數據的特點：獨立性，集成性，高共數據庫中數據的特點：獨立性，集成性，高共享性，低冗余性。享性，低冗余性。二維表二維表 二維表二維表(關系關系)組成組成: 二維二維表的行表的行:元組元組 二維表的列二維表的列:屬性；屬性； 主關鍵字和外關鍵字主關鍵字和外關鍵字 主主關鍵字：號關鍵字：號關系運算關系運算 兩張表兩張表(結構相同結構相同) 公共部分：交公共部分：交,內容集合：并內容集合：并,第一張表獨有第一張表獨有部分：差部分：差 兩兩張表張表(結構不同結構不同) 笛卡爾笛卡爾積（兩個完全不同的表