J數(shù)據(jù)結(jié)構(gòu)與算法概論

一、基本概念

數(shù)據(jù)：描述客觀事物的數(shù)、字符以及能輸入計算機(jī)中并被計算機(jī)處理的符號集合

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位。有時一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(也稱為字段、域、屬性)組成。

數(shù)據(jù)對象：是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

數(shù)據(jù)項：是具有獨立含義的最小標(biāo)識單位

數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。結(jié)構(gòu)指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式，結(jié)構(gòu)中的數(shù)據(jù)元素稱為結(jié)點。

二、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

傳統(tǒng)上，我們把數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

邏輯結(jié)構(gòu)：數(shù)據(jù)對象中數(shù)據(jù)元素之間的邏輯(或抽象)關(guān)系。

①集合結(jié)構(gòu)：數(shù)據(jù)元素除了同屬于一個集合外，他們之間沒有其他不三不四的關(guān)系。

集合結(jié)構(gòu).png

②線性結(jié)構(gòu)：數(shù)據(jù)元素之間是一對一的關(guān)系。

線性結(jié)構(gòu).png

③樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在一種一對多的層次關(guān)系。

樹形結(jié)構(gòu).png

④圖形結(jié)構(gòu)：數(shù)據(jù)元素時多對多的關(guān)系。

圖形結(jié)構(gòu).png

物理結(jié)構(gòu)(存儲結(jié)構(gòu))：數(shù)據(jù)元素及其關(guān)系在計算機(jī)內(nèi)的存儲方式。

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

順序存儲.png

②鏈?zhǔn)酱鎯Γ菏前褦?shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。

鏈?zhǔn)酱鎯?png

很顯然，這樣說的話鏈?zhǔn)酱鎯Y(jié)構(gòu)的數(shù)據(jù)元素存儲關(guān)系并不能反映其邏輯關(guān)系，因此需要用一個指針存放數(shù)據(jù)元素的地址，這樣子通過地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置。

③索引存儲：通常是在存儲信息的同時，還建立附加的索引表。表中的索引項一般形式是：(關(guān)鍵字，地址)。關(guān)鍵字是能唯一標(biāo)識一個元素的一個數(shù)據(jù)項或多個數(shù)據(jù)項的組合。

④散列存儲：基本思想是根據(jù)元素的關(guān)鍵字直接計算出該元素的存儲地址。

三、算法

實現(xiàn)：1+2+…+99+100

方式一：

int i, sum = 0, n = 100;for(i=1; i = n; i++)

{

sum = sum + i;

}printf(“%d”, sum);

方式二：

int i, sum = 0, n = 100;

sum = (1+n)*n/2;printf(“%d”, sum);

1.什么是算法

算法是解決特定問題求解步驟的描述，在計算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作。

2.算法的五個基本特性

①輸入：算法具有零個或多個輸入。

②輸出：算法至少有一個或多個輸出。輸出的形式可以是打印形式輸出，也可以是返回一個值或多個值等。

③有窮性：指算法在執(zhí)行有限的步驟之后，自動結(jié)束而不會出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內(nèi)完成。

④確定性：

算法的每一個步驟都具有確定的含義，不會出現(xiàn)二義性。

算法在一定條件下，只有一條執(zhí)行路徑，相同的輸入只能有唯一的輸出結(jié)果。

算法的每個步驟都應(yīng)該被精確定義而無歧義。

⑤可行性：算法的每一步都必須是可行的，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成。

3.算法設(shè)計的要求

①正確性：算法的正確性是指算法至少應(yīng)該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需求、能夠得到問題的正確答案。

②可讀性：算法設(shè)計另一目的是為了便于閱讀、理解和交流。

③健壯性：當(dāng)輸入數(shù)據(jù)不合法時，算法也能做出相關(guān)處理，而不是產(chǎn)生異常、崩潰或莫名其妙的結(jié)果。

④時間效率高和存儲量低：好算法應(yīng)該具備時間效率高和存儲量低的特點。所以在設(shè)計算法的時候我們應(yīng)該盡量思考這兩方面的問題!