資料結構簡介

資料結構可以定義為資料元素組，它提供了在計算機中儲存和組織資料的有效方法，以便可以有效地使用它。 資料結構的一些範例是：陣列，連結串列，堆疊，佇列等。資料結構廣泛用於電腦科學的幾乎每個方面，即作業系統，編譯器設計，人工智慧，圖形等等。

資料結構是許多電腦科學演算法的主要部分，因為它們使程式員能夠以有效的方式處理資料。 它在提高軟體或程式的效能方面發揮著重要作用，因為軟體的主要功能是盡可能快地儲存和檢索使用者的資料。

基本術語

資料結構是任何程式或軟體的構建塊(基礎塊)。為程式選擇適當的資料結構對於程式員來說是最困難的任務。就資料結構而言，使用以下術語 -

資料：資料可以定義為基本值或值集合，例如，學生的姓名和ID，成績等就是學生的資料。

組項：具有從屬資料項的資料項稱為組項，例如，學生的姓名由名字和姓氏組成。

記錄：記錄可以定義為各種資料項的集合，例如，如果以學生實體為例，那麼學生的名稱，地址，課程和標記可以組合在一起形成學生的記錄。

檔案：檔案是一種型別實體的各種記錄的集合，例如，如果類中有60名員工，則相關檔案中將有20條記錄，其中每條記錄包含有關每個員工的資料。

屬性和實體：實體表示某些物件的類。它包含各種屬性。每個屬性表示該實體的特定屬性。

欄位：欄位是表示實體屬性的單個基本資訊單元。

為什麼需要資料結構

隨著應用程式變得越來越複雜，資料量日益增加，可能會出現以下問題：

• 處理器速度：要處理非常大的資料，需要高速處理，但隨著資料逐日增長到每個實體數十億個檔案，處理器可能無法處理大量資料。

• 資料搜尋：假設商店的庫存大小是100860個商品，如果應用程式需要搜尋某一特定商品，則每次需要遍歷100860個商品，這會導致搜尋過程變慢。

• 大量請求：如果成千上萬的使用者在Web伺服器上同時搜尋資料，在此過程中可能在短時會有一個非常大請求而導致伺服器處理不了。

為了解決上述問題，使用資料結構。組織資料以形成資料結構，使得不需要搜尋所有專案並且可以立即搜尋所需資料。

資料結構的優點

• 效率：程式的效率取決於資料結構的選擇。 例如：假設有一些資料，需要執行搜尋特定記錄。 在這種情況下，如果在陣列中組織資料，則需要逐個元素地搜尋。 因此，在這裡使用陣列可能效率不高。 有更好的資料結構可以使搜尋過程像有序陣列，二進位制搜尋樹或雜湊表一樣高效。
• 可重用性：資料結構是可重用的，即當實現了特定的資料結構，就可以在其他地方使用它。也將資料結構的實現編譯到不同用戶端使用的程式庫中。
• 抽象：資料結構由ADT指定，它提供抽象級別。 用戶端程式僅通過介面使用資料結構，而不涉及實現細節。

資料結構分類

1. 線性資料結構

如果資料結構的所有元素按線性順序排列，則稱為線性資料結構。 線上性資料結構中，元素以非分層方式儲存，除了第一個和最後一個元素，它的每個元素具有後繼元素和前導元素。

線性資料結構的型別如下：

• 陣列：陣列是類似資料項的集合，每個資料項稱為陣列的元素。 元素的資料型別可以是任何有效的資料型別，如char，int，float或double。
  陣列的元素共用相同的變數名，但每個元素都帶有一個不同的索引號，這些索引號也稱為下標。 陣列可以是一維的，二維的或多維的。

範例：陣列age的各個元素是：

age[0], age[1], age[2], age[3],.... age[98], age[99]

• 連結串列：連結串列是一種線性資料結構，用於維護記憶體中的列表。 它可以看作儲存在非連續記憶體位置的節點集合。連結串列中的每個節點都包含指向其相鄰節點的指標。

• 堆疊 ：堆疊是一個線性列表，其中只允許在一端插入和刪除，稱為頂部。
  堆疊是一種抽象資料型別(ADT)，可以在大多數程式設計語言中實現。 它被命名為堆疊，因為它的行為類似於真實世界的堆疊，例如：成堆的板塊或卡片組等，只能在最頂面上操作。

• 佇列：佇列是一個線性列表，它的元素只能在一端插入(新增)，也被稱為後端，而只在另一端出隊(刪除)，也被稱為前端。

2. 非線性資料結構

非線性資料結構不形成序列，即每個專案或元素以非線性排列與兩個或更多個其他專案連線。 資料元素不按順序結構排列。

非線性資料結構的型別如下：

• 樹：樹是多級資料結構，其元素之間具有層次關係，樹的元素也稱為節點。層次中最底層的節點稱為葉節點，而最頂層節點稱為根節點。 每個節點都包含指向相鄰節點的指標。
  樹資料結構基於節點之間的父子關係。 除了葉節點之外，樹中的每個節點可以具有多個子節點，而除了根節點之外，每個節點可以具有最多一個父節點。 樹可以分為許多類別，本教學在稍後章節中將對此進行討論。

• 圖：圖可以定義為由稱為邊緣的連結連線的元素集(由頂點表示)的圖表示。 圖不同於樹，圖可以有迴圈而樹不能具有迴圈。

資料結構的操作

• 遍歷：每個資料結構都包含一組資料元素。遍歷資料結構表示存取資料結構的每個元素，以便執行某些特定操作，如搜尋或排序。範例 ：如果需要計算學生在6個不同科目中獲得的分數的平均值，需要遍歷完整的分數陣列併計算總和，然後將總分數除以科目數，即6， 最後得到平均值。

• 插入：插入是在任何位置將元素新增到資料結構的過程。如果資料結構的大小是n，那麼只能在n-1個資料元素之間插入元素。

• 刪除：從資料結構中刪除元素的過程稱為刪除。 可以在任何隨機位置刪除資料結構中的元素。如果要從空資料結構中刪除元素，則會發生下溢。

• 搜尋：在資料結構中查詢元素位置的過程稱為搜尋。 有兩種演算法可以執行搜尋，即線性搜尋和二進位制搜尋。在本教學後面討論這兩種搜尋演算法。

• 排序：按特定順序排列資料結構的過程稱為排序。 有許多演算法可用於執行排序，例如，插入排序，選擇排序，氣泡排序等。

• 合併：當兩個列表分別為大小為M和N的列表A和列表B時，相似型別的元素，連線產生第三個列表，列表C的大小(M + N)，則此過程稱為合併。

以下是糾正/補充內容：