數(shù)據(jù)結(jié)構(gòu)中的基本概念

1. 數(shù)據(jù)：數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示，所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)的總稱。如，整數(shù)、實(shí)數(shù)等都是數(shù)據(jù)。

2. 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，由數(shù)據(jù)項(xiàng)組成，如一本書為一數(shù)據(jù)元素，其中的作者，書名等信息為數(shù)據(jù)項(xiàng)。

3. 數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位，是數(shù)據(jù)記錄中最基本的，不可分的數(shù)據(jù)單位

4. 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象是性質(zhì)相同的的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

5. 數(shù)據(jù)結(jié)構(gòu)：指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，包括3方面的內(nèi)容：邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，對(duì)數(shù)據(jù)的運(yùn)算

6. 數(shù)據(jù)的邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)使對(duì)數(shù)據(jù)之間關(guān)系的描述，與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)?？煞譃?strong>線性結(jié)構(gòu)和非線性結(jié)構(gòu)

   • 線性結(jié)構(gòu)：一個(gè)數(shù)據(jù)元素有序的集合，有一下四個(gè)特征：
     集合中必須存在唯一一個(gè)“第一個(gè)元素”
     集合中必須存在唯一一個(gè)“最后一個(gè)元素”
     除最后一個(gè)元素外，其他數(shù)據(jù)元素均有唯一的“后繼”
     除第一個(gè)元素外，其他元素均有唯一的“前驅(qū)”
   • 非線性結(jié)構(gòu)：非線性結(jié)構(gòu)中的節(jié)點(diǎn)存在一對(duì)多的關(guān)系，可以劃分為樹形結(jié)構(gòu)和圖形結(jié)構(gòu)

7. 數(shù)據(jù)的物理結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)又稱為存儲(chǔ)結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的映像。數(shù)據(jù)結(jié)構(gòu)中有四種存儲(chǔ)方式：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)

   • 線性存儲(chǔ)結(jié)構(gòu)：該方法把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。
   • 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示
   • 索引存儲(chǔ)結(jié)構(gòu)：該方法通常在儲(chǔ)存結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表。索引項(xiàng)的一般形式是： (關(guān)鍵字、地址) 關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)
   • 散列存儲(chǔ)方法： 根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。

算法中的基本概念

1. 算法：由基本的運(yùn)算及運(yùn)算順序所構(gòu)成的完整解題步驟，或者看成按照要求設(shè)計(jì)好的有限的確切的計(jì)算序列。
   算法有以下特性：

   • 有窮性：一個(gè)算法必須保證執(zhí)行有限步后結(jié)束
   • 確切性：算法的每個(gè)步驟必須有確切的定義
   • 輸入：一個(gè)算法有0個(gè)或多個(gè)輸入
   • 輸出： 一個(gè)算法有一個(gè)或多個(gè)輸出
   • 可行性：算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行的操作步，即每個(gè)計(jì)算步都可以在有限時(shí)間內(nèi)完成（也稱之為有效性）

   算法的設(shè)計(jì)目標(biāo)：

   • 正確性：算法能夠正確的執(zhí)行預(yù)先規(guī)定的功能要求
   • 可讀性：要求算法易于人的理解
   • 健壯性：要求算法有很好的容錯(cuò)性，能夠?qū)Σ缓侠淼臄?shù)據(jù)進(jìn)行檢查
   • 高效率與低存儲(chǔ)量需求：即時(shí)間復(fù)雜度和空間復(fù)雜度

2. 時(shí)間復(fù)雜度：將算法中基本執(zhí)行的次數(shù)做為算法的時(shí)間復(fù)雜度
   ** T(n) = O(f(n)中增長(zhǎng)最快的項(xiàng)/此項(xiàng)的系數(shù))**
   常用的時(shí)間復(fù)雜度大小比較：
   O(1)≤O(log2n)≤O(n)≤O(nlog2n)≤O(n^2)≤O(n3)≤...≤O(n^k)≤O(2n)

3. 空間復(fù)雜度：一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度