數據結構
- 緒論
1、數據 是客觀事物的符號表示,在計算機學科中指所有能夠被輸入到計算機中並被計算機程序處理的字符總稱。
2、數據元素 是數據的基本單位,也稱數據結構節點或記錄
3、數據項 是數據不可分割的最小單位,也稱字段、屬性
4、數據結構:是相互之間存在一種或多種特定關係的數據元素組成的集合
結構的4中形式: ①集合 ②線性結構 ③樹形結構 ④圖狀或網狀結構
數據結構+算法=程序
程序+文檔=軟件
什麼是算法?
1、算法是計算機程序對特定問題求解步驟的一種描述
2、算法的五個特性:①有窮性 ②確定性 ③可行性 ④輸入 ⑤輸出
3、算法效率度量:
絕對執行時間:算法在就硬件上的實際執行時間
相對執行時間:算法的漸近時間複雜度,又稱時間複雜度
T(n)=O( f(n) ) n:問題的規模 f(n):算法中基本操作被重複執行的次數 O:只取f(n)的最高數量級
例: T(n)=O(3n^3+2n^2+5n+10)=O(3n^3)=O(n^3)
存儲空間需求:算法的存儲空間需求的度量用空間複雜度表示:
S(n)=O( g(n) ) g(n):存儲空間的大小
T(n)和S(n)關係: T(n)越小,S(n)越大
- 線型表:
1、定義:線性表由n個數據元素a0,a1,···,an-1組成的有限長序列