目錄

??????一、學習目標

二、數據結構

1.基本概念

線性關系：

非線性關系：

存儲形式

2. 算法分析

2.1 時間復雜度

2.2 空間復雜度

2.3 時空復雜度互換

總結

---

一、學習目標

• 了解數據結構的基本概念
• 了解算法的分析方法

? ? ? ??

二、數據結構

1.基本概念

數據結構是一門研究如何有效組織數據，并提高數據處理效率的學科。通過研究各種數據內部的邏輯關系，使用某種特定的存儲形式，并在此基礎上對數據實施各種操作（增刪改查），這些工作被稱為稱為廣義上的算法。

• 邏輯結構
  • 指數據之間的內在關系。通常有集合、線性表、樹、圖等常見的邏輯結構。
  • 邏輯結構是數據之間本身的屬性，跟我們怎么處理它們無關。

線性關系：

????????各個元素之間是一種一對一的關系，比如圖書館中的書架的書，除了首尾兩本書之外，其余的任意一本書的編號假設是N，都有且僅有一個直接前驅節點N-1，有且僅有一個直接后繼節點N+1。這種關系就是典型的線性邏輯。

非線性關系：

????????與上述線性關系的表述不同，如果各個元素之間不是嚴格一對一的關系，則被稱為非線性關系，比如家族中的各個成員、不同城市間的交通道路等，對于它們中間的某個元素，都可能有不止一個元素與之關聯。這種關系是典型的非線性邏輯。

• 存儲形式

  • 數據的存儲方式。比如順序存儲、鏈式存儲等。
  • 不同的存儲形式對最終數據的處理效率通常有很大的影響。
  • 邏輯結構與存儲形式并無必然聯系。

2. 算法分析

算法分析是指算法在正確的情況下，對其優劣的分析。一個好的算法通常是指：

1. 算法對應的程序所耗時間少
2. 算法對應的程序所耗存儲空間少
3. 算法結構性好、易讀、易移植和調試

????????數據結構與算法的本質任務，是提高程序的時間空間效率，簡單講就是讓程序的執行速度越快越好，所需內存空間越少越好。雖然在很多情況下，程序的時空特性是相互制約的，就像魚和熊掌不可兼得，但我們可以根據程序實際解決問題的側重點，去平衡時間和空間的對性能的消耗。

2.1 時間復雜度

????????一般而言，時間復雜度并不考察一段代碼運行所需要的絕對時間，因為不同的計算機的硬件參數不同，考察絕對時間沒有意義。時間復雜度一般指的是代碼的語句執行總次數，稱為語句頻度。比如：

void counting(int n)
{for(int i=0; i<n; i++){printf("本行語句將會出現n次\n");for(int j=0; j<n; j++){printf("本行語句將會出現n*n次\n");}}
}

????????不同算法的時間復雜度相差很大，如下圖所示，隨著所處理的問題規模的增大，不同時間復雜度的程序所需要的時間有天壤之別。

2.2 空間復雜度

????????空間復雜度的概念更簡單一點，就是一段程序運行時所需的內存字節量。

2.3 時空復雜度互換

????????一段程序的性能指標，既要運行快速，又要節省內存，而通常這兩者又是相互制約的，很難兼得。因此在實際解決問題時，會根據需要側重一方，犧牲另一方。

總結

????????本文簡述了數據結構的基本概念和算法分析，算是新副本的介紹，后續會寫數據結構的順序表、鏈表、隊列等關卡，并且附上實戰代碼。請大家拭目以待~

????????最后祝各位都可爬上C語巔峰，斬盡攔路小妖。

????????本文參考 粵嵌文哥 的部分課件，經過整理和修改后發布在C站。如有轉載，請聯系本人

? ?
?