數據結構+算法=程序設計

什么是數據結構

數據（data）：符號集合，處理對象。

數據元素（data element），由數據項（data item） 組成。

關鍵字（key）識別元素，主關鍵字（primary key） 唯一識別元素。

數據結構（data structure）指數據元素之間存在的關系。

包含以下三方面： 數據的邏輯結構 數據的存儲結構 數據操作

數據的邏輯結構

線性結構：數據元素只有一個前驅數據元素和一個后繼數據元素。

樹結構：每個數據元素只有一個前驅數據元素，可有零個或若干個后繼數據元素。

圖結構：每個數據元素可有零個或若干個前驅數據元素，零個或若干個后繼數據元素。

?數據的存儲結構

?順序存儲結構

鏈式存儲結構

?

數據操作

1.初始化。

2.判斷是否空狀態。

3.存取，指獲得、設置指定元素值。

4.統計數據元素個數。

5.遍歷（traverse），指按照某種次序訪問一個數據結構中的所有元素，并且每個數據元素只被訪問一次。遍歷一種數據結構，將得到一個所有數據元素的線性序列。

6.插入（insert）、刪除（remove）指定元素。

7.查找（search），指在數據結構中尋找滿足給定條件的數據元素。

8.排序（sort），指對數據元素按照指定關鍵字值的大小遞增（或遞減）次序重新排列。

數據類型與抽象數據類型?

?數據類型（data type）是指一個類型和定義在這個類型上的操作集合。

抽象數據類型（Abstract Data Type，ADT）是指一個邏輯概念上的類型和這個類型上的操作集合。

即，一種數據結構的抽象數據類型包括：

• 數據的邏輯結構
• 數據操作

?#復數抽象類型

ADT Complex

{ ? ?

double real, imag; ? ? ? ? ? ? //實部和虛部 ? ?

Complex(double real, double imag) ? ?

Complex add(Complex c) ? ? ? ?//加法 ? ?

Complex sub(Complex c) ? ? ? ?//減法

}

#集合的表示與實現

ADT Set<T> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //集合抽象數據類型

{ ? ?

數據：集合中的數據元素，數據元素的數據類型為T ? ?

操作： ? ?

boolean isEmpty(); ? ? ? ? ? //判斷集合是否為空 ? ?

int size (); ? ? ? ? ? ? ? ? ? ? ? ? ?//返回元素個數 ? ?

T search(T key) ? ? ? ? ? ? ? ? //返回查找到的關鍵字為key元素 ? ?

boolean contains(T key) ?//判斷是否包含關鍵字為key元素 ? ?

boolean add(T x) ? ? ? ? ? ? ?//增加元素x ? ?

T remove(T key) ? ? ? ? ? ? ? //刪除關鍵字為key元素 ? ?

void clear() ? ? ? ? ? ? ? ? ? ? ? ?//刪除所有元素 ? ?

String toString() ? ? ? ? ? ? ? //返回所有元素的描述字符串

#集合的抽象數據類型

?ADT Set<T> { ? ?

boolean equals(Object obj) ? //比較this與obj是否相等 ? ?

Object[] toArray() ? ? ? ? ? ? ? ? //返回包含所有元素的數組 ? ?

//以下方法描述集合運算，參數是另一個集合 ? ?

boolean containsAll(Set<?> set) ? ? ? ? ?//判斷是否子集 ? ?

boolean addAll(Set<? extends T> set) //集合并運算 ? ?

boolean removeAll(Set<?> set) ? ? ? ? ? ? //集合差 ? ?

boolean retainAll(Set<?> set) ? ? ? ? ? ? ? ?//僅保留那些也包含在set的元素，集合差

}

實現不同特性的集合?

①線性表表示可重復的無序集合，元素間具有前驅、后繼次序關系；不同元素的關鍵字可重復，采用序號能夠識別關鍵字重復的數據元素。

②排序線性表表示可重復的排序集合，元素按關鍵字大小次序排序。

③散列表表示不可重復的無序集合，元素關鍵字不重復，元素間沒有次序，不排序。

④二叉排序樹表示不可重復的排序集合，元素關鍵字不重復，元素按關鍵字升/降序排序。

?用java語言的接口描述抽象數據類型

?Java語言的接口（interface）是一組抽象方法、常量和內嵌類型的集合。

1.聲明接口

public interface Set<T> ?? ?//集合接口，T是泛型參數

2.聲明實現接口的類

public abstract class AbstractSet<T> implements Set<T> ? ? //抽象集合類，沒有實現所有抽象方法 public class HashSet<T> implements Set<T> ? ?//散列表類

3.接口是引用類型

Set<T> set = new HashSet<T>(); ?//接口對象引用實例

set.add(x) //運行時多態性，執行HashSet<T>類實現的add(x)方法

算法?

?一個算法（Algorithm）是一個有窮規則的集合，其規則確定一個解決某一特定類型問題的操作序列。

定義

• 有窮性
• 確定性
• 輸入
• 輸出
• 可行性

?算法設計目標

• ?正確性
• 可讀性
• 健壯性
• 高時間效率
• 高空間效率

?算法描述

?//在當前數據結構中，順序查找與key相等的元素（數據類型為T）；key提供查找條件的關鍵字

元素 search(T key) { ? ?

for (elem : 數據結構中的每個元素) ? //遍歷 ? ? ? ? ?

????????if (key與elem元素相等) ? ? ? ? ? ??? ?//由T類型約定兩個元素相等的比較規則

? ? ? ? ? ? ? ?查找成功，返回元素或元素位置;

查找不成功，返回查找不成功標記;

}

?算法與數據結構

?

?

?算法分析

?1.度量算法的時間效率

???????? 算法的時間效率指算法的執行時間隨問題規模的增長而增長的趨勢，通常采用時間復雜度來度量算法的時間效率。

????????????????????????T(n)=O(f(n))

1.一條簡單語句的時間復雜度是O(1)。

int count=0;

2.一個循環的時間復雜度是O(n)。

int n=8, count=0;

for (int i=1; i<=n; i++)

? ? count++; ? ? ? ? ? ? ? ? ? ?? ? ? ? ? //循環體執行n次

3.以下循環語句的時間復雜度是O(log_2 n)。

for (int i=1; i<=n; i*=2) ? ? ? ?//i按2的冪（1,2,4,8）遞增

? ? count++; ? ? ? ? ? ? ? ? ??? ? ? ? //循環體執行1+log2 n ?次

4.以下二重循環的時間復雜度為O(n^2)。

for (int i=1; i<=n; i++)

? ? for (int j=1; j<=n; j++)

5.以下二重循環的時間復雜度是O(n×log_2 n)

?for (int i=1; i<=n; i*=2) ? ? ? ?//循環log2n次

? ? ? for (int j=1; j<=n; j++) ? ? //循環n次

6.以下二重循環的時間復雜度是O(n)。

for (int i=1; i<=n; i*=2) ? ? ? ?//循環log2n次

? ? for (int j=1; j<=i; j++) ? ? ?//循環i次

? ? //循環次數

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

2.度量算法的空間效率

????????空間復雜度指算法在執行時為解決問題所需要的額外內存空間，不包括輸入數據所占用的存儲空間。

????????????????????????S(n)=O(f(n)) ?

結論：判斷一個算法的效率時，函數中的常數和其他次要項可以忽略，而更應該關注主項（最高項）的階數