資料結構與演算法基礎知識

持續分享嵌入式技術，作業系統，演算法，c語言/python等，歡迎小友關注支援

資料結構介紹

“程式（Program）=資料結構（Data Structure）+演算法（Algorithm）”

資料結構是計算機專業中一門綜合性的基礎課程，它是介於數學，計算機硬體和計算機軟體的三者之間一門核心課程，同時，資料結構是設計資料庫，程式，作業系統，遊戲等等設計方面的重要基礎，是絕大多數計算機專業考研的指定科目，也是大公司面試時常考科目，同時，也是高中及大學的學科競賽中必備知識，優秀的資料結構和演算法，可見資料結構在計算機課程中的重要性。

計算機的演算法與資料結構密切相關，演算法無不依賴於資料結構，而資料結構也關係到演算法的效率，直接決定了一個程式的好壞。

資料結構，直白地理解，就是研究資料的儲存方式。

我們知道，資料儲存只有一個目的，即為了方便後期對資料的再利用，就如同我們使用陣列儲存

{1，2，3，4，5}

是為了後期取得它們的加和值，無緣由的資料儲存行為是對儲存空間的不負責任。

因此，資料在計算機儲存空間的存放，決不是胡亂的，這就要求我們選擇一種好的方式來儲存資料，而這也是資料結構的核心內容。

資料結構發展史

1) 起源：

1968年美國唐•歐•克努特教授開創了資料結構的最初體系，他所著的《計算機程式設計技巧》第一卷《基本演算法》是第一本較系統地闡述資料的邏輯結構和儲存結構語其操作的著作。我們一般認為本書開創了資料結構的系統概念。

70年代初，資料結構作為一門獨立的課程開始進入大學課堂。

資料結構的發展經歷三個階段：無結構階段，結構化階段和麵向物件階段（和程式發展的三個階段不謀而合了）

2) 無結構階段

40~60年代間，計算機的主要應用還沒有如此普及，當時計算機主要是針對科學計算，程式設計技術以機器語言和組合語言為主，程式處理的是存粹的數值，資料之間的關係主要是以來數學公式或者數學模型，此時資料結構概念並沒有明確形成。

3)結構化階段

60~80年代，計算機開始廣泛應用於非數值處理領域，資料表示成為程式設計的重要問題，人們認識到程式設計規範化的重要性，提出了程式結構模組化，並開始注意資料表示與操作的結構化。資料結構及抽象資料型別就是在這種情況下形成的，隨著資料規模的加大，程式的設計越來越依附於資料結構的設計，此時資料結構開始廣泛普及。

此間也有非常多的資料結構相關的文獻產出，最為著名的是圖靈獎獲得者沃斯的一個著名公式：程式=資料結構+演算法。

4)面向物件階段

80年代初期到現在，隨著計算機不斷普及，計算機效能以及需求不斷增加，面向物件的程式設計被逐步提出，在物件的世界中 ，程式設計中大大減少了重複設計的部分，資料結構在這個階段逐漸變得豐富，大量的封裝類出現，減少了程式設計者的負擔，資料結構因此變得更加友好。

何為演算法

計算1到100的和（1+2+3+……+100），大家在上學的時候經常遇到這種數學題吧，這種題最通俗的計算方式就是遍歷資料累加求和，c語言的表示如下所示：

#include int main（） { int ans=0，i； for（i=1；i<=100；i++）{ ans+=i； } printf（“%d”，ans）； return 0；}

然而我們都知道有個小學生高斯發現了一個更加簡單的計算方式，這種計算方法叫做等差數列，如果用c語言表示，程式碼如下所示：

#include int main（） {    int ans=（1+100）*100/2；    printf（“%d”，ans）；    return 0；}

相比第一份答案，我們進行了100次的運算，才得出我們想要的結果，而對於第二份答案，我們僅進行了1次運算就得到了想要的結果，而在實際中計算機的計算遠遠不止這點計算量，以此如果我們去計算1到1000000的和呢？

使用了等差數列還是一步算好，而這就是演算法的魅力。