資料結構筆記——概述

資料結構——概述

——2017.12.21

一、線性表：

這個是為了解決單線存儲而出現的，數組就是最簡單粗暴的存儲方法。就是直接拉出一大塊資料存在那裡。數組的快速存取其實隻是一個副作用，因為所有的資料都在一起，可以直接算出來資料的位址。連結清單則是為了解決可以無線增長的需求的。因為找不到一大塊可以連續的存入資料，甚至也不知道程式可能使用的資料總量，是以就沒辦法劃分一塊資料來使用，劃小了不夠用，劃大了浪費。是以必須想辦法解決問題。最後采用的方法就是從入口開始，每一個資料塊不僅僅有資料，還會有指向下一個資料塊的線索，用來尋找下一個資料。這就是連結清單。所謂的雙向連結清單，隻是加了一個向前的線索的連結清單。隊列，棧，都是線性表的特殊形态。進行了操作上的限制。

二、樹：

樹是為了解決單一入口下的非線性關聯性的資料存儲或者排序這樣的功能而來的。

最常見的應用是程式設計時候的map，就是利用了二叉樹的可排序和可以快速插入并且保持序列完整的特性來建構鍵值資料對，來實作資料的插入增加以及快速查找的能力的。

還有做文法解析，文字處理等等很多場景也會用到樹。

三、圖：

圖其實就是把線性表進一步擴充，每個節點會有不止一個前置和字尾節點，而且前置和字尾的概念也不再明晰，變成了關聯節點。具體的應用主要是一些特殊的算法和圖形學上的一些使用。總之資料結構的前期學習要重了解。以倒推的方式，搞清楚每種資料結構産生的目标。多畫畫圖，思考一下，了解透徹以後。再去做練習題會事半功倍。