關(guān)于數(shù)據(jù)結(jié)構(gòu)基本概念的介紹

1、數(shù)據(jù)（Data）

---- 是對(duì)信息的一種符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。

2、數(shù)據(jù)元素（Data Element）

---- 是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。

? ? ? 數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。

3、數(shù)據(jù)對(duì)象（Data Object）

---- 是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

4、數(shù)據(jù)結(jié)構(gòu)（Data Structure）

---- 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

? ? ? 數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：

-- 1）集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合（一種類型）外，別無其它關(guān)系。各個(gè)數(shù)據(jù)元素是“平等”的。

-- 2）線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。

-- 3）樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。

-- 4）圖形結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲(chǔ)結(jié)構(gòu)。（數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)映像稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。）

數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)形式有四種：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)。

順序存儲(chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。

5、算法：是對(duì)特定問題求解步驟的一種描述。

---- 算法是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。

算法具有以下五個(gè)特性：

-- 1）有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。

-- 2）確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。

-- 3）可行性：一個(gè)算法是可行的。即算法描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。

-- 4）輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。

-- 5）輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。

---- 算法設(shè)計(jì)的要求：評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn)：

-- 1）正確性（Correctness）算法應(yīng)滿足具體問題的需求。

-- 2）可讀性（Readability）算法應(yīng)該好讀，以有利于閱讀者對(duì)程序的理解。

-- 3）健壯性（Robustness）算法應(yīng)具有容錯(cuò)處理功能。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。

-- 4）時(shí)間效率高和存儲(chǔ)量低。時(shí)間效率指的是算法的執(zhí)行時(shí)間，執(zhí)行時(shí)間長(zhǎng)的效率低。

存儲(chǔ)量需求指的是算法在執(zhí)行過程中需要的最大存儲(chǔ)空間，主要指算法運(yùn)行程序時(shí)所占用的內(nèi)存或外部硬盤存儲(chǔ)空間。

---- 算法效率的度量方法：事后統(tǒng)計(jì)方法和事前分析估算方法

-- 事后統(tǒng)計(jì)方法：這種方法主要是通過設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而

確定算法效率的高低。（依賴計(jì)算機(jī)硬件和軟件等環(huán)境因素）

-- 事前分析估算方法：在計(jì)算機(jī)程序編制前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。

---- 函數(shù)的漸近增長(zhǎng)：給定兩個(gè)函數(shù)f(n)和g(n)，如果存在一個(gè)整數(shù)N，使得對(duì)于所有的n>N,f(n)總是比g(n)大，那么，我們說f(n)的增長(zhǎng)

漸近快于g(n)。

---- 算法時(shí)間復(fù)雜度：在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)T（n）是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T（n）隨n的變化情況并確定T(n)

的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，記作：T（n）= O（f（n））。它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)

率和f(n)的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度。其中f(n)是問題規(guī)模n的某個(gè)函數(shù)。

用大寫O()來體現(xiàn)算法時(shí)間復(fù)雜度的記法，稱之為大O記法。一般情況下，隨著n的增大，T(n)增長(zhǎng)最慢的算法為最優(yōu)算法。

---- 推導(dǎo)大O階方法：

-- 1）用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。

-- 2）在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。

-- 3）如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。得到的結(jié)果就是大O階。

---- 常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

O(1): 常數(shù)階，O(logn): 對(duì)數(shù)階，O(n): 線性階，O(n^2): 平方階等。

6、描述頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）的區(qū)別？

答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。

首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié)點(diǎn)是在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，其指針域指向首元

結(jié)點(diǎn)，其作用主要是為了方便對(duì)鏈表的操作。它可以對(duì)空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。