1. 數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系

數(shù)據(jù)結(jié)構(gòu)是一門研究組織數(shù)據(jù)方式的學(xué)科，有了編程語(yǔ)言也就有了數(shù)據(jù)結(jié)構(gòu)，學(xué)好數(shù)據(jù)結(jié)構(gòu)可以編寫出更加漂亮更加有效率的代碼。

學(xué)好數(shù)據(jù)結(jié)構(gòu)就要多多考慮如何將生活中遇到的問(wèn)題，用程序去實(shí)現(xiàn)解決。

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)，換言之，想要學(xué)好算法，需要把數(shù)據(jù)結(jié)構(gòu)學(xué)到位。

2. 幾個(gè)實(shí)際編程中遇到的問(wèn)題

問(wèn)題一：

    public static void main(String[] args) {
        String str = "Java, Java, hello, world!";
        String newStr = str.replace("Java", "hahaha");
        System.out.println("newStr = " + newStr);
    }

問(wèn)題：試寫出用單鏈表表示的字符串類以及字符串結(jié)點(diǎn)類的定義，并依次實(shí)現(xiàn)它的構(gòu)造函數(shù)、計(jì)算串長(zhǎng)度、串賦值、判斷串相等、求子串、兩串相連、求子串在串中的位置等7個(gè)成員函數(shù)。

問(wèn)題二：
五子棋程序，判斷游戲的輸贏，并完成存盤退出和讀盤繼續(xù)上局功能。

-- 棋盤映射成二維數(shù)組 ，棋盤很大，可以使用稀疏數(shù)組來(lái)節(jié)省空間。

問(wèn)題三：
約瑟夫問(wèn)題(丟手帕問(wèn)題)
編號(hào)1到n的小朋友坐一圈，約定編號(hào)為k(1 <= k <= n)的人從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人出列，它的下一位又從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列，依此類推，直到所有人出列為止，求出隊(duì)編號(hào)的序列。

-- 用一個(gè)不帶頭節(jié)點(diǎn)的循環(huán)鏈表來(lái)處理Josephu問(wèn)題：先構(gòu)成一個(gè)有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表(單向環(huán)形鏈表)，然后由k結(jié)點(diǎn)從1開(kāi)始計(jì)數(shù)，計(jì)到m時(shí)刪除對(duì)應(yīng)的結(jié)點(diǎn)，然后從被刪除的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)又從1開(kāi)始計(jì)數(shù)，直到最后一個(gè)結(jié)點(diǎn)被刪除。

修路問(wèn)題 -- 最小生成樹 + 普利姆算法)
最短路徑 -- 圖 + 佛洛依德算法
漢諾塔 -- 分治算法
八皇后問(wèn)題 -- 回溯算法

有些問(wèn)題，數(shù)據(jù)結(jié)構(gòu)就可以解決，因?yàn)閷?duì)應(yīng)的算法比較簡(jiǎn)單，有些問(wèn)題就需要很復(fù)雜的算法加上數(shù)據(jù)結(jié)構(gòu)才能解決。

3. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)

線性結(jié)構(gòu)有兩種存儲(chǔ)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu)(數(shù)組)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(鏈表)。

線性結(jié)構(gòu)：數(shù)組、隊(duì)列、鏈表、棧，元素之間一對(duì)一
非線性結(jié)構(gòu)：二維數(shù)組、多維數(shù)組、廣義表、樹、圖