瑞士計算機科學家Niklaus Wirth在1976年寫了一本書,名為《算法+數據結構=編程》。 40多年后,這個等式仍被奉為真理。這就是為什么在面試過程中,需要考察軟件工程師對數據結構的理解。 幾乎所有的問題都需要面試者對數據結構有深刻的理解。無論你是初入職場的新兵(剛從大學或者編程培訓班畢業(yè)),還是擁有幾十年經驗的職場老鳥。 有些面試題會明確提及某種數據結構,例如,“給定一個二叉樹?!倍硪恍﹦t隱含在面試題中,例如,“我們希望記錄每個作者相關的書籍數量?!?/span> 即便是對于一些非常基礎的工作來說,學習數據結構也是必須的。那么,就讓我們先從一些基本概念開始入手。 簡單地說,數據結構是以某種特定的布局方式存儲數據的容器。這種“布局方式”決定了數據結構對于某些操作是高效的,而對于其他操作則是低效的。首先我們需要理解各種數據結構,才能在處理實際問題時選取最合適的數據結構。 數據是計算機科學當中最關鍵的實體,而數據結構則可以將數據以某種組織形式存儲,因此,數據結構的價值不言而喻。 無論你以何種方式解決何種問題,你都需要處理數據——無論是涉及員工薪水、股票價格、購物清單,還是只是簡單的電話簿問題。 數據需要根據不同的場景,按照特定的格式進行存儲。有很多數據結構能夠滿足以不同格式存儲數據的需求。 首先列出一些最常見的數據結構,我們將逐一說明: · 數組 數組是最簡單、也是使用最廣泛的數據結構。棧、隊列等其他數據結構均由數組演變而來。下圖是一個包含元素(1,2,3和4)的簡單數組,數組長度為4。 每個數據元素都關聯一個正數值,我們稱之為索引,它表明數組中每個元素所在的位置。大部分語言將初始索引定義為零。
· 一維數組(如上所示)
· Insert——在指定索引位置插入一個元素
· 尋找數組中第二小的元素 著名的撤銷操作幾乎遍布任意一個應用。但你有沒有思考過它是如何工作的呢?這個問題的解決思路是按照將最后的狀態(tài)排列在先的順序,在內存中存儲歷史工作狀態(tài)(當然,它會受限于一定的數量)。這沒辦法用數組實現。但有了棧,這就變得非常方便了。 可以把棧想象成一列垂直堆放的書。為了拿到中間的書,你需要移除放置在這上面的所有書。這就是LIFO(后進先出)的工作原理。 下圖是包含三個數據元素(1,2和3)的棧,其中頂部的3將被最先移除:
· Push——在頂部插入一個元素
· 使用棧計算后綴表達式 與棧相似,隊列是另一種順序存儲元素的線性數據結構。棧與隊列的最大差別在于棧是LIFO(后進先出),而隊列是FIFO,即先進先出。 一個完美的隊列現實例子:售票亭排隊隊伍。如果有新人加入,他需要到隊尾去排隊,而非隊首——排在前面的人會先拿到票,然后離開隊伍。 下圖是包含四個元素(1,2,3和4)的隊列,其中在頂部的1將被最先移除: 移除先入隊的元素、插入新元素
· Enqueue()?——?在隊列尾部插入元素
· 使用隊列表示棧 鏈表是另一個重要的線性數據結構,乍一看可能有點像數組,但在內存分配、內部結構以及數據插入和刪除的基本操作方面均有所不同。 鏈表就像一個節(jié)點鏈,其中每個節(jié)點包含著數據和指向后續(xù)節(jié)點的指針。 鏈表還包含一個頭指針,它指向鏈表的第一個元素,但當列表為空時,它指向null或無具體內容。 鏈表一般用于實現文件系統(tǒng)、哈希表和鄰接表。 這是鏈表內部結構的展示:
· 單鏈表(單向)
· InsertAtEnd - 在鏈表的末尾插入指定元素
· 反轉鏈表 圖是一組以網絡形式相互連接的節(jié)點。節(jié)點也稱為頂點。 一對節(jié)點(x,y)稱為邊(edge),表示頂點x連接到頂點y。邊可以包含權重/成本,顯示從頂點x到y(tǒng)所需的成本。
· 無向圖
· 鄰接矩陣
· 廣度優(yōu)先搜索
· 實現廣度和深度優(yōu)先搜索 樹形結構是一種層級式的數據結構,由頂點(節(jié)點)和連接它們的邊組成。 樹類似于圖,但區(qū)分樹和圖的重要特征是樹中不存在環(huán)路。 樹形結構被廣泛應用于人工智能和復雜算法,它可以提供解決問題的有效存儲機制。
· Root - 根節(jié)點
· N元樹 其中,二叉樹和二叉搜索樹是最常用的樹。
· 求二叉樹的高度 字典樹,也稱為“前綴樹”,是一種特殊的樹狀數據結構,對于解決字符串相關問題非常有效。它能夠提供快速檢索,主要用于搜索字典中的單詞,在搜索引擎中自動提供建議,甚至被用于IP的路由。 以下是在字典樹中存儲三個單詞“top”,“so”和“their”的例子: 這些單詞以頂部到底部的方式存儲,其中綠色節(jié)點“p”,“s”和“r”分別表示“top”,“thus”和“theirs”的底部。
· 計算字典樹中的總單詞數 哈希法(Hashing)是一個用于唯一標識對象并將每個對象存儲在一些預先計算的唯一索引(稱為“鍵(key)”)中的過程。因此,對象以鍵值對的形式存儲,這些鍵值對的集合被稱為“字典”。可以使用鍵搜索每個對象。基于哈希法有很多不同的數據結構,但最常用的數據結構是哈希表。 哈希表通常使用數組實現。
· 哈希函數 下圖為如何在數組中映射哈希鍵值對的說明。該數組的索引是通過哈希函數計算的。
· 在數組中查找對稱鍵值對 以上是在編程面試之前你應該知曉的八大數據結構。 來源:網絡大數據 |
|