請牢記：程式=資料結構+演算法

1. 資料結構發展史

1) 起源：

1968年美國唐•歐•克努特教授開創了資料結構的最初體系；

他所著的《計算機程式設計技巧》第一卷《基本演算法》是第一本較系統地闡述資料的邏輯結構和儲存結構與其操作的著作。

資料結構的發展經歷三個階段：無結構階段，結構化階段和麵向物件階段。

2) 無結構階段

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

3)結構化階段

60~80年代，計算機開始廣泛應用於非數值處理領域，資料表示成為程式設計的重要問題，人們認識到程式設計規範化的重要性，提出了程式結構模組化，並開始注意資料表示與操作的結構化。

資料結構及抽象資料型別就是在這種情況下形成的，隨著資料規模的加大，程式的設計越來越依附於資料結構的設計，此時資料結構開始廣泛普及。

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

4)面向物件階段

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

2.何為演算法

請你回答一下如何使用計算機C語言程式設計計算1到100的和（1+2+3+……+100），相信大多數人會直接給出以下答案：

#include <stdio.h>in main() {    int ans=0,i;    for(i=1;i<=100;i++){        ans+=i;    }    printf("%d",ans);    return 0;}

這幾乎是計算機中最為簡單的程式了。

但是，這樣去完成這個功能真的好麼？早在300年前的小學生高斯在課堂上被老師要求去計算這個結果，在同班同學還在手推寫結果的時候，高斯早就已經做完了，他利用等差數列求和的演算法，輕易打敗了同班同學。

相關程式碼如下：

#include <stdio.h>int main() {    int ans=(1+100)*100/2;    printf("%d",ans);    return 0;}

相比第一份答案，我們進行了100次的運算，才得出我們想要的結果，而對於第二份答案，我們僅進行了1次運算就得到了想要的結果，而在實際中計算機的計算遠遠不止這點計算量，以此如果我們去計算1到1000000的和呢？使用了等差數列還是一步算好，而這就是演算法的魅力。

演算法基礎

1. 演算法的特性

1) 輸入輸出

演算法具有零個或者多個輸入，同時，演算法具有至少一個的輸出。

對於在螢幕上列印”Hello World”一樣，你可以不需要有任何的輸入，直接輸出得到結果即可，而對於一個沒有輸出的演算法，沒有任何意義。

2) 確定性

演算法的每一步都具有確定的含義，無二義性。任何條件下，演算法只有唯一的一條執行路徑，即對於相同的輸入只能得到相同的輸出。

請注意，如果演算法的目的是產生一個隨機數字，每一次執行產生了不同的結果，看上去好像違反了演算法確定性原則，但計算機產生隨機數亦是使用一種（或多種）演算法解決，以線性同餘產生隨機數為例，其利用了CPU時間的不同產生的不同的結果，當CPU的時間完全一樣的時候依舊會產生相同結果，只不過人類無法察覺到如此精確的時間區別。

3)有窮性

一個演算法總是需要（輸入合法的情況下）在有限的步驟結束，即每個演算法需要在有窮的時間內完成。

這是演算法與程式的最主要的區別，程式可以無限制迴圈的執行下去。對於此，你可以理解為一個演算法必須要有一個”邊界“，即使一個演算法需要計算機連續運算50年，但依舊是有窮的，只不過這個演算法意義已經不是很大了。

4)可行性

一個演算法是可以被執行的，即演算法中的每個操作都可以透過已經實現的基本運算執行有限的次數完成。

儘管在目前計算機解存在著沒有實現成功的極為複雜的演算法，但是並不能說的上是無法實現，只不過是受到現在的工具和人類的大腦限制了，這屬於理論研究的範圍。

2. 演算法設計要求

1) 正確性

正確性（Correctness）指的是該演算法能夠滿足預先指定的功能與效能的需求，即能夠得到正確答案。

其大致可以分為以下四點：

a)該演算法中不含任何語法錯誤。

b)程式對於幾組輸入資料能夠得到滿足需求的結果。

c)程式對於非法的輸入也能夠得到滿足需求說明的結果（如丟擲異常）。

d)程式對於精心挑選的嚴苛資料依舊能夠產生滿足需求的結果。

2)健壯性

健壯性（Robustness）指的是當輸入資料不合法時，演算法也能做出相關的處理，而不是產生不可預計的效果。

3)可讀性

可讀性（Readability）指的是演算法是可以閱讀，理解和交流的。

4)耗時低，佔用空間少

我們演算法與資料結構的研究的重點就是為了讓程式執行快，佔用空間低。

1. 基本概念和術語

1)資料

資料（Data）是資訊的載體，是可以被計算機識別，儲存並加工處理的描述客觀事物的資訊符號的總稱。資料不僅僅包括了整形，浮點數等數值型別，還包括了字元甚至聲音，影片，影象等非數值的型別。

2)資料元素

資料元素（Data Element）是描述資料的基本單位，也被稱為記錄。一個數據元素有若干個資料項組成。

如禽類，雞鴨都屬於禽類的資料元素。

3)資料項

資料項（Data Item）是描述資料的最小單位，其可以分為組合項和原子項：

a)組合項

如果資料元素可以再度分割，則每一個獨立處理單元就是資料項，資料元素就是資料項的集合。

b)原子項

如果資料元素不能再度分割，則每一個獨立處理的單元就是原子項。

如日期2019年4月25日就是一個組合項，其表示日期，但如果單獨拿25日這個資料出來觀測，這就是一個原子項，因為其不可以再分割。

4)資料物件

資料物件（Data Object）是性質相同的一類資料元素的集合，是資料的一個子集。資料物件可以是有限的，也可以是無限的。

5)資料結構

資料結構（Data Structures）主要是指資料和關係的集合，資料指的是計算機中需要處理的資料，而關係指的是這些資料相關的前後邏輯，這些邏輯與計算機儲存的位置無關，其主要包含以下四大邏輯結構。

2. 四大邏輯結構（Logic Structure）

1) 集合結構

集合結構（Set Structure）中所有資料元素除了同屬於一個集合外，並無其他關係。

如圖：

2) 線性結構

線性結構（Linear Structure）指的是資料元素之間存在“一對一的關係”

如圖:

3) 樹形結構

樹形結構（Tree Structure）指的是資料元素之間存在“一對多”的層次關係。

如圖：

4) 圖形結構

圖形結構（Graphic Structure，也稱：網狀結構）指的是資料元素之間存在“多對多的關係”（注：此時的“多對多”中的多表示，至少有一個）

圖示：

3.資料型別

1) 資料型別

資料型別（Data Type）是高階程式設計語言中的概念，是資料的取值範圍和對數進行操作的總和。資料型別規定了程式中物件的特性。程式中的每一個變數，常量或者表示式都屬於一種資料型別。

2) 抽象資料型別

抽象資料型別（Abstract Data Type，ADT）只是一個數學模型以及定義在模型上的一組操作。通常是對資料的抽象，定義了資料的取值範圍以及對資料操作的集合。

抽象資料型別的特徵是實現與操作分離，從而實現封裝。

資料結構與演算法是作為一名程式設計師必不可少的，既然你已經看到了這裡，說明你是一個對程式設計感興趣的人，那麼如何學習資料結構與演算法呢，不是去網上看個影片就會立馬懂，程式設計是個需要動手的事情。