数据结构学习笔记

第1章 緒論

1.1 數據結構

1.1.1 學習數據結構的必要性

《數據結構》這門課程的目的有三個.

1. 是講授常用的數據結構,這些數據結構形成了程序員基本數據結構工具箱.對於許多常見的問題,工具箱里的數據結構是理想的選擇;

2. 是講授常用的算法,這和數據結構一樣,是人們在長期實踐過程中的總結,程序員可以直接拿來或經過少許的修改就可以使用.可以通過算法訓練來提高程序設計水平;

3. 目的是通過程序設計的技能訓練促進程序員綜合能力的提高.

1.1.2 基本概念和術語

1. 數據：外部世界信息的載體,它能夠被計算機識別、存儲和加工處理,是計算機程序加工的原料;

2. 數據元素(Data Element)和數據項(Data Item)

數據元素：數據的基本單位,在計算機程序中通常被作為一個整體進行考慮和處理; 數據項：不可分割的、含有獨立意義的最小數據單位,數據項有時也稱為字段或域;

3. 數據對象(Data Object)：性質相同的數據元素的集合,是數據的一個子集;

4. 數據類型(Data Type):是高級程序設計語言中的概念,是數據的取值範圍和對數據進行操作的總和.

5. 數據結構(Data Structure):是相互之間存在一種或多種特定關係的數據元素的集合. 根據數據元素之間關係的不同特性,通常有4類基本數據結構:

(1)集合(Set)

(2)線性結構(Linear Structure)

(3)樹形結構(Tree Structure)

(4)圖狀結構(Graphic Structure)

數據結構包括數據的邏輯結構和物理結構.

數據的邏輯結構(Logic Structure):是從具體問題抽象出來的數學模型,是爲了討論問題的方便,與數據在計算機中的具體存儲沒有關係.

數據的物理結構(Physical Structure):又稱為存儲結構(Storage Structure),是數據在計算機中的表示(又叫映像)和存儲,包括數據元素的表示和存儲以及數據元素之間關係的表示和存儲.

數據的存儲結構包括:順序存儲結構和鏈式存儲結構兩種.

順序存儲結構(Sequence Storage Structure)是通過數據元素在計算機存儲器中的相對位置來表示出數據元素的邏輯關係,一版把邏輯上相鄰的數據元素存儲在屋裡位置相鄰的存儲單元中.

鏈式存儲結構(Linked Storage Structure)對邏輯上相鄰的數據元素不要求其存儲位置必須相鄰.鏈式存儲結構中的數據元素稱為節點(Node),在節點中附設地址域(Address Domain)來存儲于該節點相鄰的節點的地址來實現節點間的邏輯關係.

這個地址稱為引用(Reference),這個地址域被稱為引用域(Reference Domain).

1.2 算法

1.2.1 算法的特性

算法(Algorithm)是對某一特定類型的問題的求解步驟的一種描述,是指令的有限序列.一個算法應該具備以下5個特性:

1. 有窮性(Finite):一個算法總是在又窮步之後結束.

2. 確定性(Unambiguous):算法的每一個步驟都必須有確切的含義,即無二義,並且對於相同的輸出只能有相同的輸出.

3. 輸入(Input):

4. 輸出(Output):

5. 能行性(Realizability):算法中的每一步都可以通過已經實現的基本運算的有限次運行來實現.

1.2.2 算法的評價標準

評價一個算法優劣的主要標準如下:

1. 正確性(Correctness)

2. 可讀性(Readability)

3. 健壯性(Robustness)

4. 運行時間(Running Time)

5. 佔用空間(Storage Space):指算法在計算機上存儲所佔用的存儲空間,包括存儲算法本身所佔用的存儲空間、算法的輸入及輸出數據所佔用的存儲空間和算法在運行過程中臨時佔用的存儲空間.

通常把算法在運行過程中臨時佔用的存儲空間的大小叫算法的空間複雜度(Space Complexity).

1.2.3 算法的時間複雜度

一個算法的時間複雜度(Time Complexity)是指該算法的運行時間與問題規模的對應關係.一個算法是由控制結構和原操作構成的,其執行的時間取決於二者的綜合效果.爲了便於比較同意問題的不同算法,通常把算法中基本操作重複執行的次數(頻度)作為算法的時間複雜度.算法中的基本操作一般是指算法中最深層循環內的語句.因此,算法中基本操作語句的頻度是問題規模n的某個函數f(n),記做:T(n)=o(f(n)).

1.4.2 泛型編程

第2章 線性表

線性表是線性結構的抽象(Abstract),線性結構的特點是結構中的數據元素之間存在一對一的線性關係.

2.1 線性表的邏輯結構

線性表(List)是由n(n≥0)個相同類型的數據元素構成的有限序列.

2.2 順序表

在計算機內,保存線性表最簡單、最自然的方式,就是把裱中的元素一個接一個地放進順序的存儲單元,這就是線性表的順序存儲(Sequence Storage).

線性表的順序存儲是指在內存中用一塊連續的空間依次存放線性表的數據元素,用這種方式存儲的線性表叫順序表(Sequence List).

2.3 單鏈表

線性表的另外一種存儲結構---鏈式存儲(Linked Storage),這樣的線性表叫鏈表(Linked List)

2.3.1 單鏈表的定義

鏈表是用一組任意的存儲單元來存儲線性表中的數據元素(這組存儲單元可以是連續的,也可以使不連續的).那麼,怎麼表示兩個數據元素邏輯上的相鄰關係呢?即如何表示數據元素之間的線性關係呢?為此,在存儲數據元素時,除了存儲數據元素本身的信息外,還要存儲與它相鄰的數據元素的存儲地址信息.這兩部份信息組成該數據元素的存儲映像(Image),稱為節點(Node).把存儲數據元素本身信息的域叫節點的數據域(Data Domain),把存儲與它相鄰的數據元素的存儲地址信息的域叫節點的引用域(Reference Domain).因此,線性表通過每個節點的引用域形成了一根”鏈條”,這就是”鏈表”名稱的由來.

如果結點的引用域只存儲該節點的直接後繼結點的存儲地址,則該鏈表叫單鏈表(Singly

next.

2.4 其他鏈表

2.4.1 雙向鏈表

2.4.2 循環鏈表

第3章 棧和隊列

棧和隊列也是線性結構,線性表、棧和隊列這三種數據結構的數據元素以及數據元素間的邏輯關係完全相同.

3.1 棧

棧(Stack)是操作限定在表的尾端進行的線性表.

3.1.2 棧的存儲和運算實現

1. 順序棧

用一片連續的存儲空間來存儲棧中的數據元素,這樣的棧稱為順序棧(Sequence Stack).

2. 鏈棧

棧的另外一種存儲方式是鏈式存儲,這樣的棧稱為鏈棧(Linked Stack).鏈棧通常用單鏈表來表示,它的實現是單鏈表的簡化.

3.2 隊列

3.2.1 隊列的定義及基本運算

隊列(Queue)是插入操作限定在表的尾部而其他操作限定在表的頭部進行的線性表.把進行

插入操作的表位稱為隊尾(Rear),把進行其他操作的頭部稱為對頭(Front).檔隊列中沒有數據元素時成為空隊列(Empty Queue).

3.2.2 隊列的存儲和運算實現

1. 順序隊列:用一片連續的存儲空間來存儲隊列中的數據元素,這樣的隊列稱為順序隊列(Sequence Queue).

解決假溢出的方法是將順序隊列看成是首尾相接的循環結構,頭尾指示器的關係不變,這種隊列叫循環順序隊列(Circular Sequence Queue)

2. 鏈隊列:隊列的另外一種存儲方式是鏈式存儲,這樣的隊列稱為鏈式隊列(Linked Queue).

第4章 串和數組

4.1 串

字符串簡稱串,是一種特殊的線性表,其特殊性在於串中的數據元素是一個個的字符.

4.1.1 串的基本概念

4.1.2 串的存儲及類定義

由於串中的字符都是連續存儲的,而在C#中串具有恒定不變的特性,即字符串一經創建,就不能將 …… 此处隐藏：22778字，全部文档内容请下载后查看。喜欢就下载吧 ……