數(shù)據(jù)結(jié)構(gòu)是一種特殊的組織和存儲數(shù)據(jù)的方式,可以使我們可以更高效地對存儲的數(shù)據(jù)執(zhí)行操作。數(shù)據(jù)結(jié)構(gòu)在計算機科學(xué)和軟件工程領(lǐng)域具有廣泛而多樣的用途。 幾乎所有已開發(fā)的程序或軟件系統(tǒng)都使用數(shù)據(jù)結(jié)構(gòu)。此外,數(shù)據(jù)結(jié)構(gòu)屬于計算機科學(xué)和軟件工程的基礎(chǔ)。當(dāng)涉及軟件工程面試問題時,這是一個關(guān)鍵主題。因此,作為開發(fā)人員,我們必須對數(shù)據(jù)結(jié)構(gòu)有充分的了解。 在本文中,我將簡要解釋每個程序員必須知道的8種常用數(shù)據(jù)結(jié)構(gòu)。 一.數(shù)組陣列是固定大小的結(jié)構(gòu),其可以保持相同的數(shù)據(jù)類型的項目。它可以是整數(shù)數(shù)組,浮點數(shù)數(shù)組,字符串?dāng)?shù)組甚至數(shù)組數(shù)組(例如2維數(shù)組)。數(shù)組已建立索引,這意味著可以進(jìn)行隨機訪問。 圖1.數(shù)組基本術(shù)語的可視化 1.陣列運算
由于數(shù)組的大小是固定的,因此無法立即將元素插入到數(shù)組中以及從數(shù)組中刪除元素。如果要向數(shù)組中插入元素,則首先必須創(chuàng)建一個具有增大的大小(當(dāng)前大小+ 1)的新數(shù)組,復(fù)制現(xiàn)有元素并添加新元素。刪除大小減小的新數(shù)組的刪除操作也是如此。 2.數(shù)組的應(yīng)用
二.鏈表鏈表是一種順序結(jié)構(gòu),由一系列相互鏈接的線性順序項目組成。因此,您必須順序訪問數(shù)據(jù),并且無法進(jìn)行隨機訪問。鏈接列表提供了動態(tài)集的簡單而靈活的表示。 讓我們考慮以下有關(guān)鏈表的術(shù)語。您可以通過參考圖2來獲得一個清晰的主意。
圖2.鏈表基本術(shù)語的可視化 以下是可用的各種類型的鏈表。
1.鏈表操作
2.鏈表的應(yīng)用
三.堆棧堆棧是一個LIFO(后進(jìn)先出-放置在最后的元件可以在第一被訪問)可在許多編程語言來常見結(jié)構(gòu)。這種結(jié)構(gòu)之所以被稱為“堆疊”,是因為它類似于真實世界的堆疊-一組板。 圖片來源:pixabay 1.堆棧操作 下面給出了可以在堆棧上執(zhí)行的2個基本操作。請參考圖3,以更好地了解堆棧操作。
圖3.堆?;静僮鞯目梢暬?/p> 此外,為堆棧提供了以下附加功能,以檢查其狀態(tài)。
2.堆棧的應(yīng)用
四.隊列甲隊列是一個FIFO(先入先出-放置在第一元件可以在第一被訪問)可在許多編程語言來常見結(jié)構(gòu)。該結(jié)構(gòu)被稱為“隊列”,因為它類似于現(xiàn)實世界中的隊列-人們在隊列中等待。 圖片來源:pixabay 1.隊列操作 下面給出了可以在隊列上執(zhí)行的2個基本操作。請參考圖4,以更好地了解隊列操作。
圖4.隊列基本操作的可視化 2.隊列的應(yīng)用
五.哈希表哈希表是一種數(shù)據(jù)結(jié)構(gòu),其存儲有與之相關(guān)聯(lián)的鍵的值。此外,如果我們知道與值關(guān)聯(lián)的鍵,則它有效地支持查找。因此,無論數(shù)據(jù)大小如何,插入和搜索都非常有效。 當(dāng)存儲在表中時,直接尋址使用值和鍵之間的一對一映射。但是,當(dāng)存在大量鍵值對時,此方法存在問題。該表將具有很多記錄,并且非常龐大,鑒于典型計算機上的可用內(nèi)存,該表可能不切實際甚至無法存儲。為了避免這個問題,我們使用哈希表。 1.散列函數(shù) 使用一種稱為哈希函數(shù)(h)的特殊函數(shù)來克服上述直接尋址中的問題。 在直接訪問中,帶有密鑰k的值存儲在插槽k中。使用哈希函數(shù),我們可以計算出每個值都指向的表(插槽)的索引。使用給定鍵的哈希函數(shù)計算的值稱為哈希值,該值指示該值映射到的表的索引。
圖5.哈希函數(shù)的表示 考慮哈希函數(shù)h(k)= k%20,其中哈希表的大小為20。給定一組鍵,我們要計算每個鍵的哈希值,以確定索引應(yīng)在哈希表中的位置。考慮我們有以下鍵,即哈希和哈希表索引。
從上面給出的最后兩個示例中,我們可以看到,當(dāng)哈希函數(shù)為多個鍵生成相同的索引時,就會發(fā)生沖突。我們可以通過選擇合適的哈希函數(shù)h并使用鏈接和開放式尋址等技術(shù)來解決沖突。 2.哈希表的應(yīng)用
六.樹樹是進(jìn)行數(shù)據(jù)分層組織并連接在一起的分層結(jié)構(gòu)。此結(jié)構(gòu)與鏈接列表不同,而在鏈接列表中,項目以線性順序鏈接。 在過去的幾十年中,已經(jīng)開發(fā)出各種類型的樹,以適合某些應(yīng)用并滿足某些限制。一些示例是二叉搜索樹,B樹,挖掘,紅黑樹,展開樹,AVL樹和n元樹。 1.二叉搜索數(shù) 二叉搜索樹(BST),顧名思義,是一個二叉樹,其中數(shù)據(jù)在一個層次結(jié)構(gòu)組織。此數(shù)據(jù)結(jié)構(gòu)按排序順序存儲值,我們將在本教程中詳細(xì)研究這些值。 二叉搜索樹中的每個節(jié)點都包含以下屬性。
二叉搜索樹具有獨特的屬性,可將其與其他樹區(qū)分開。此屬性稱為binary-search-tree屬性。 令x為二叉搜索樹中的一個節(jié)點。
圖6.樹的基本術(shù)語的可視化。 2.樹的應(yīng)用
七.堆堆也是一種二叉樹,其中父節(jié)點相比,他們的孩子與他們的價值觀和相應(yīng)安排的一個特例。 讓我們看看如何表示堆。堆可以使用樹和數(shù)組來表示。圖7和8顯示了我們?nèi)绾问褂枚鏄浜蛿?shù)組來表示二叉堆。 圖7.堆的二叉樹表示 圖8.堆的數(shù)組表示 堆可以有2種類型。
堆的應(yīng)用
八.圖圖形是由一組有限的頂點或節(jié)點和一組邊緣連接這些頂點。 圖的順序是圖中的頂點數(shù)。圖的大小是圖中的邊數(shù)。 如果兩個節(jié)點通過同一邊彼此連接,則稱它們?yōu)?strong>相鄰節(jié)點。 1.有向圖 如果圖形G的所有邊緣都具有指示什么是起始頂點和什么是終止頂點的方向,則稱該圖形為有向圖。 我們說,(U,V)是事件的或葉頂點ü,是事發(fā)地或進(jìn)入頂點v。 自環(huán):從頂點到自身的邊。 2.無向圖 如果圖G的所有邊緣均無方向,則稱其為無向圖。它可以在兩個頂點之間以兩種方式傳播。 如果頂點未連接到圖中的任何其他節(jié)點,則稱該頂點為孤立的。 圖9.圖形術(shù)語的可視化 3.圖的應(yīng)用
|
|