資料結構簡介


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

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

基本術語

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

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

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

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

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

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

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

為什麼需要資料結構

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

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

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

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

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

資料結構的優點

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

資料結構分類

1. 線性資料結構

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

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

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

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

age[0], age[1], age[2], age[3],.... age[98], age[99]
  • 連結串列:連結串列是一種線性資料結構,用於維護記憶體中的列表。 它可以看作儲存在非連續記憶體位置的節點集合。連結串列中的每個節點都包含指向其相鄰節點的指標。

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

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

2. 非線性資料結構

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

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

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

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

資料結構的操作

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

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

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

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

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

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


以下是糾正/補充內容:

資料結構 下面的 圖 標題錯了 陣列結構應改為資料結構  提交時間:2019-09-05