數據結構與算法

數據結構(英語:data structure)是計算機中存儲、組織數據的方式。

數據結構是一種具有一定邏輯關係,在計算機中應用某種存儲結構,並且封裝了相應操作的數據元素集合。它包含三方麵的內容,邏輯關係、存儲關係及操作。

不同種類的數據結構適合於不同種類的應用,而部分甚至專門用於特定的作業任務。例如,計算機網絡依賴於路由表運作,B 樹高度適用於數據庫的封裝。

本教程將介紹基礎的數據結構和算法分析,源碼部分參考 https://github.com/liuyubobobo/Play-with-Algorithms


為什麼要學習數據結構和算法?

隨著應用程序變得越來越複雜和數據越來越豐富,幾百萬、幾十億甚至幾百億的數據就會出現,而對這麼大對數據進行搜索、插入或者排序等的操作就越來越慢,數據結構就是用來解決這些問題的。

閱讀本教程前,您需要了解的知識?


在您開始閱讀本教程之前,您必須具備基本的 Java 編程的概念。如果您還不了解這些概念,那麼建議您先閱讀我們的 Java 教程


常見的數據結構

  • 棧(Stack):棧是一種特殊的線性表,它隻能在一個表的一個固定端進行數據結點的插入和刪除操作。
  • 隊列(Queue):隊列和棧類似,也是一種特殊的線性表。和棧不同的是,隊列隻允許在表的一端進行插入操作,而在另一端進行刪除操作。
  • 數組(Array):數組是一種聚合數據類型,它是將具有相同類型的若幹變量有序地組織在一起的集合。
  • 鏈表(Linked List):鏈表是一種數據元素按照鏈式存儲結構進行存儲的數據結構,這種存儲結構具有在物理上存在非連續的特點。
  • 樹(Tree):樹是典型的非線性結構,它是包括,2 個結點的有窮集合 K。
  • 圖(Graph):圖是另一種非線性數據結構。在圖結構中,數據結點一般稱為頂點,而邊是頂點的有序偶對。
  • 堆(Heap):堆是一種特殊的樹形數據結構,一般討論的堆都是二叉堆。
  • 散列表(Hash table):散列表源自於散列函數(Hash function),其思想是如果在結構中存在關鍵字和T相等的記錄,那麼必定在F(T)的存儲位置可以找到該記錄,這樣就可以不用進行比較操作而直接取得所查記錄。

常用算法

數據結構研究的內容:就是如何按一定的邏輯結構,把數據組織起來,並選擇適當的存儲表示方法把邏輯結構組織好的數據存儲到計算機的存儲器裏。算法研究的目的是為了更有效的處理數據,提高數據運算效率。數據的運算是定義在數據的邏輯結構上,但運算的具體實現要在存儲結構上進行。一般有以下幾種常用運算:

  • 檢索:檢索就是在數據結構裏查找滿足一定條件的節點。一般是給定一個某字段的值,找具有該字段值的節點。
  • 插入:往數據結構中增加新的節點。
  • 刪除:把指定的結點從數據結構中去掉。
  • 更新:改變指定節點的一個或多個字段的值。
  • 排序:把節點按某種指定的順序重新排列。例如遞增或遞減。