概念:
數(shù)據(jù)結(jié)構(gòu)是一種存儲和組織數(shù)據(jù)的方法，可以有效地使用它。
數(shù)據(jù)結(jié)構(gòu)是任何程序或軟件的構(gòu)建塊(基礎(chǔ)塊)。
術(shù)語:
就數(shù)據(jù)結(jié)構(gòu)而言，使用以下術(shù)語:
- 數(shù)據(jù)：數(shù)據(jù)可以定義為基本值或值集合，例如，學(xué)生的姓名和ID，成績等就是學(xué)生的數(shù)據(jù)。
- 組項：具有從屬數(shù)據(jù)項的數(shù)據(jù)項稱為組項，例如，學(xué)生的姓名由名字和姓氏組成。
- 記錄：記錄可以定義為各種數(shù)據(jù)項的集合，例如，如果以學(xué)生實體為例，那么學(xué)生的名稱，地址，課程和標(biāo)記可以組合在一起形成學(xué)生的記錄。
- 文件：文件是一種類型實體的各種記錄的集合，例如，如果類中有60名員工，則相關(guān)文件中將有20條記錄，其中每條記錄包含有關(guān)每個員工的數(shù)據(jù)。
- 屬性和實體：實體表示某些對象的類。它包含各種屬性。每個屬性表示該實體的特定屬性。
- 字段：字段是表示實體屬性的單個基本信息單元。
用途:
隨著應(yīng)用程序變得越來越復(fù)雜，數(shù)據(jù)量日益增加，可能會出現(xiàn)以下問題：
- 處理器速度：要處理非常大的數(shù)據(jù)，需要高速處理，但隨著數(shù)據(jù)逐日增長到每個實體數(shù)十億個文件，處理器可能無法處理大量數(shù)據(jù)。
- 數(shù)據(jù)搜索：假設(shè)商店的庫存大小是100860個商品，如果應(yīng)用程序需要搜索某一特定商品，則每次需要遍歷100860個商品，這會導(dǎo)致搜索過程變慢。
- 大量請求：如果成千上萬的用戶在Web服務(wù)器上同時搜索數(shù)據(jù)，在此過程中可能在短時會有一個非常大請求而導(dǎo)致服務(wù)器處理不了。
為了解決上述問題，使用數(shù)據(jù)結(jié)構(gòu)。組織數(shù)據(jù)以形成數(shù)據(jù)結(jié)構(gòu)，使得不需要搜索所有項目并且可以立即搜索所需數(shù)據(jù)。
分類:
操作:
遍歷：每個數(shù)據(jù)結(jié)構(gòu)都包含一組數(shù)據(jù)元素。遍歷數(shù)據(jù)結(jié)構(gòu)表示訪問數(shù)據(jù)結(jié)構(gòu)的每個元素，以便執(zhí)行某些特定操作，如搜索或排序。示例 ：如果需要計算學(xué)生在6個不同科目中獲得的分?jǐn)?shù)的平均值，需要遍歷完整的分?jǐn)?shù)數(shù)組并計算總和，然后將總分?jǐn)?shù)除以科目數(shù)，即6， 最后得到平均值。
插入：插入是在任何位置將元素添加到數(shù)據(jù)結(jié)構(gòu)的過程。如果數(shù)據(jù)結(jié)構(gòu)的大小是n，那么只能在n-1個數(shù)據(jù)元素之間插入元素。
刪除：從數(shù)據(jù)結(jié)構(gòu)中刪除元素的過程稱為刪除。 可以在任何隨機(jī)位置刪除數(shù)據(jù)結(jié)構(gòu)中的元素。如果要從空數(shù)據(jù)結(jié)構(gòu)中刪除元素，則會發(fā)生下溢。
搜索：在數(shù)據(jù)結(jié)構(gòu)中查找元素位置的過程稱為搜索。 有兩種算法可以執(zhí)行搜索，即線性搜索和二進(jìn)制搜索。
排序：按特定順序排列數(shù)據(jù)結(jié)構(gòu)的過程稱為排序。 有許多算法可用于執(zhí)行排序，例如，插入排序，選擇排序，冒泡排序等。
合并：當(dāng)兩個列表分別為大小為M和N的列表A和列表B時，相似類型的元素，連接產(chǎn)生第三個列表，列表C的大小(M + N)，則此過程稱為合并。
數(shù)據(jù)結(jié)構(gòu)分類
1.線性數(shù)據(jù)結(jié)構(gòu)
如果數(shù)據(jù)結(jié)構(gòu)的所有元素按線性順序排列，則稱為線性數(shù)據(jù)結(jié)構(gòu)。
在線性數(shù)據(jù)結(jié)構(gòu)中，元素以非分層方式存儲，除了第一個和最后一個元素，它的每個元素具有后繼元素和前導(dǎo)元素。
線性數(shù)據(jù)結(jié)構(gòu)的類型有：數(shù)組;鏈表;堆棧;隊列
- 數(shù)組：數(shù)組是類似數(shù)據(jù)項的集合,每個數(shù)據(jù)項稱為數(shù)組的元素。元素的數(shù)據(jù)類型可以是任何有效的數(shù)據(jù)類型，如char,int,float或者double。數(shù)組的元素共享相同的變量名，但是每個元素都有一個不同的索引號，這些索引號也稱為下標(biāo)。數(shù)組可以是一維的，二維的或者多維的。
- 鏈表：鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，用于維護(hù)內(nèi)存中的列表。它可以看作存儲在非連續(xù)內(nèi)存位置的節(jié)點(diǎn)集合。鏈表中每個節(jié)點(diǎn)都包含指向其相鄰節(jié)點(diǎn)的指針。
- 隊列：隊列是一個線性列表，它的元素只能在一端插入（添加），也被稱為后端，而只在另一端出隊（刪除），也被稱為前端。
- 堆棧：堆棧是一個線性列表，其中只允許在一端插入和刪除，稱為頂部。堆棧是一種抽象的數(shù)據(jù)類型（ADT），可以在大多數(shù)編程語言中實現(xiàn)。它被命名為堆棧，因為它的行為類似于真實世界的的堆棧，例如，成堆的板塊或卡片組等，只能在最頂面操作。
2.非線性數(shù)據(jù)結(jié)構(gòu)
非線性數(shù)據(jù)結(jié)構(gòu)不形成序列，即每個項目或元素以非線性排列與兩個或更多個其他項目連接。 數(shù)據(jù)元素不按順序結(jié)構(gòu)排列。
非線性數(shù)據(jù)結(jié)構(gòu)的類型有：樹；圖
- 樹：樹是多級數(shù)據(jù)結(jié)構(gòu)，其元素之間具有層次關(guān)系，樹的元素也稱為節(jié)點(diǎn)。層次中最底層的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)，而最頂層節(jié)點(diǎn)稱為根節(jié)點(diǎn)。 每個節(jié)點(diǎn)都包含指向相鄰節(jié)點(diǎn)的指針。
樹數(shù)據(jù)結(jié)構(gòu)基于節(jié)點(diǎn)之間的父子關(guān)系。 除了葉節(jié)點(diǎn)之外，樹中的每個節(jié)點(diǎn)可以具有多個子節(jié)點(diǎn)，而除了根節(jié)點(diǎn)之外，每個節(jié)點(diǎn)可以具有最多一個父節(jié)點(diǎn)。
樹可以分為許多類別：
無序樹：樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間沒有順序關(guān)系，這種樹稱為無序樹,也稱為自由樹;
有序樹：樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系，這種樹稱為有序樹；
-
二叉樹：每個節(jié)點(diǎn)最多含有兩個子樹的樹稱為二叉樹；二叉樹又分為
- 完全二叉樹：對于深度為K的，有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為K的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時稱之為完全二叉樹。
- 滿二叉樹：一個二叉樹，如果每一個層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是(2^k) -1 ，則它就是滿二叉樹。
- 霍夫曼樹：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹；
- 圖：圖可以定義為由稱為邊緣的鏈接連接的元素集(由頂點(diǎn)表示)的圖表示。 圖不同于樹，圖可以有循環(huán)而樹不能具有循環(huán)。
數(shù)據(jù)結(jié)構(gòu)優(yōu)缺點(diǎn)匯總
