1.1 基礎編程模型

1、算法：
我們用算法這個詞來描述了解決問題的步驟
2、使用Java編程語言編寫程序的原因：
（1）程序是對于算法精確、優雅和完全的描述
（2）可以通過運行程序來學習算法的各種性質
（3）可以在應用程序中直接使用這些算法
3、基礎編程模型：
我們把描述和實現算法所用到的語言特性、軟件庫和操作系統總稱為基礎編程模型

/*** 二分查找* @param index* @param list* @return*/public static int BinarySearch(int index , int[] list){int m = 0;int n = list.length -1 ;while (m < n ) {int mid = m+ (n-m)/2;if (index < mid) n = mid -1;else if (index > mid) m = mid+1;else return list[mid];}return -1;}

1.1.1 Java程序的基本結構

1、原始數據類型、語句、數組、靜態方法、字符串、標準輸入輸出、數據抽象

1.1.2 原始數據類型和表達式

1、基本數據類型：int、boolean、double、char
2、運算符：+ - * / …
3、表達式：Java使用的是中綴表達式。（一個字面量、一個運算符、一個字面量）

1.1.3 語句

1、語句：Java程序由語句組成的。語句可以通過創建和操作變量、對變量進行復制并控制這些操作的執行流程來描述運算。
2、聲明語句、賦值語句、條件語句、循環語句、調用和返回語句
3、break和continue的區別：
（1）break語句，立即從循環中退出
（2）continue語句，立即開始下一輪的循環

1.1.4 簡便記法

1、聲明并初始化、隱式賦值、單語句代碼塊、for語句

1.1.5 數組

1.1.6 靜態方法

1、遞歸（三種情況須符合）
（1）遞歸中總有方法第一條語句總是一個包含return的條件語句
（2）遞歸的調用總是去嘗試一個規模更小的子問題
（3）遞歸調用的父問題和嘗試解決的子問題之間不應該有交集

/*** 二分查找遞歸實現* @param index* @param list* @param beg* @param end* @return*/public static int BinarySearchByRecursion(int index, int[] list,int beg, int end) {if (beg > end) {return -1;}int mid = beg + (end - beg)/2;if (index > list[mid]) {return BinarySearchByRecursion(index,list,mid + 1, end);} else if (index < list[mid]) {return BinarySearchByRecursion(index,list,beg , mid - 1);} else {return index;}}

1.1.7 API

1.1.8 字符串

1.1.9 輸入輸出

1、標準的輸入輸出

Scanner in = new Scanner(System.in);System.out.println("請輸入第一個數 ：");int m = in.nextInt();System.out.println("請輸入第二個數 ：");int n = in.nextInt();

2、重定向和管道
（1）java xxx num rdm > xx.txt：將輸出的結果保存在 xx.txt中 ，終端窗口不會輸出任何內容，直接寫在了文件中
（2）java xxx < xx.txt：從文件中讀取數據
（3）管道：將一個程序的輸出重定向為另一個程序的輸入叫做管道
java xxx num rdm | xx.txt：將標準的輸入輸出指定為一個流

1.1.10 二分查找

1.2 數據抽象

1、數據類型指的是一組值和一組對這些值的操作的集合
2、對象：包含了某個數據類型值的實體
3、抽象數據類型：是一種能夠對使用者隱藏數據表示的數據類型

1.2.1 使用抽象數據類型

1、就是Java類
2、對象的三大重要特征：
（1）狀態：對象的狀態即數據類型中的值
（2）標識：對象的標識能夠將一個對象區別于另一個對象，對象的標識就是其在內存中的位置
（3）行為：對象的行為指的是數據類型的操作

1.2.2 抽象數據類型舉例

1.2.3 抽象數據類型的實現

創建一個對象

1.2.4 更多抽象數據類型的實現

1.2.5 數據類型的設計

1、封裝
2、設計API
3、算法與抽象數據類型
4、接口繼承
5、toString()
6、內存管理
7、斷言：
斷言是一條需要在程序的某處確認為true的布爾表達式。如果表達式的值為false，程序將會終止并報告出一條出錯的信息。

assert index >= 0; // 斷言

1.3 背包、隊列、棧

1、不同點在于刪除或者訪問對象的順序不同

1.3.1 泛型

1、泛型：集合類的抽象數據類型的一個關鍵特性是我們應該可以用他們存儲任意類型的數據
2、自動裝箱：
自動將一個原始數據類型轉換為一個封裝數據類型被稱為自動裝箱。
自動將一個封裝的數據類型轉換為一個原始數據類型稱為自動拆箱。

Stack<Integer> stack = new Stack<Integer> (); stack.push(17); // 自動裝箱（int -> Integer） int i = stack.pop(); // 自動拆箱（Integer -> int）

3、可迭代的集合類型
4、背包：
背包是一種不支持從中刪除元素的集合數據類型-目的就是幫助用例收集元素并迭代遍歷所有收集到的元素
5、先進先出隊列
6、下壓棧（后進、先出）
7、雙棧算術表達式求值算法：
（1）將操作數壓入操作數棧
（2）將運算符壓入運算符棧
（3）忽略左括號
（4）在遇到右括號時，彈出一個運算符，彈出所需數量的操作數，并將運算符和操作數的結果壓入操作數棧

1.3.2 集合數據類型的實現

1、定容棧：
（1）一個用于保存棧中的元素的數組a[]，和另一個用于保存棧中的元素數量的整數N。
（2）刪除一個元素需要將N減1并返回a[N]
（3）添加一個元素，將a[N]設置為新元素并將N加1
2、對象游離：
Java的垃圾收集策略是回收所有無法被訪問的對象的內存。在我們對pop()的實現中，被彈出的元素的引用依然存在于數組中-他永遠無法被訪問了，但Java的垃圾收集器沒法知道這一點，除非該引用被覆蓋。即使用例已經不再需要這個元素了，數組中的引用依然可以讓他繼續存在。這種情況稱為游離。
避免對象游離很容易，只需要將被彈出的數組元素的值設置為null即可，這將覆蓋無用的引用并使系統可以在用例使用完被彈出的元素后回收他的內存

1.3.3 鏈表

1、鏈表： 是一種遞歸的數據結構，它或者為空，或者是指一個節點node的引用，該節點含有一個泛型的元素和一個指向另一條鏈表的引用

/*** 使用嵌套類來定義結點的抽象數據類型*/private class Node {Item item;Node next;}

2、構造鏈表
3、在表頭插入結點
4、從表頭刪除結點
5、從表尾插入結點

1.4 算法分析

1.4.1 科學方法

1、用來研究理解自然世界的方法對于研究計算機程序的運行時間同樣有效

1.4.2 觀察

1.4.3 數學模型

1、一個程序運行的總時間主要和兩點有關系：
（1）執行每條語句的耗時
（2）執行每條語句的頻率

1.4.4 增長數量級分類

1、常數級別
2、對數級別
3、線性級別
4、線性對數級別
5、平方級別
6、立方級別
7、指數級別

1.4.5 設計更快的算法

1.4.6 倍率實驗

1.4.7 注意事項

1、大常數
2、非決定性的內循環
3、指令時間
4、系統因素
5、不分伯仲
6、對輸入的強烈依賴
7、多個問題參量

1.4.8 處理對于輸入的依賴

1、輸入模型
2、對最壞情況下的性能的保證
3、隨機化算法
4、操作序列
5、均攤分析

1.4.9 內存

1、對象
2、鏈表
3、數組
4、字符串對象
5、字符串的值和子字符串

1.4.10 展望

1、良好的性能是非常重要的，速度極慢的程序和不正確的程序一樣無用。

1.5 案例研究：union-find算法

總結

以上是生活随笔為你收集整理的算法4-第一章基础的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。