第一章：緒論

1.基本概念以及術語：

• 數據：信息的載體,是 描述客觀事物 屬性的數、字符及所有能輸入到計算機中并被計算機程序識别和處理的 符号的集合
• 數據對象：具有相同性質的數據元素的集合,是數據的一個子集
• 數據元素：數據的基本單位 ,通常作為個整體進行考慮和處理
• 數據項：構成數據元素的不可分割的 最小單位

數據包含數據對象，數據元素構成數據對象。

所有人的身份信息就可以作為數據對象，每一個人的身份信息就可以作為數據元素，身份信息的姓名、編号就可以作為數據項。

1.1數據

數據類型（集合 操作）

• 原子類型：值集合 操作（int、char、float等）
• 結構類型：結構的集合 操作（list、map、set等）
• 抽象數據類型ADT：數據對象 數據關系 操作（所有可以抽象出的模型）

1.2結構

結構： 數據不是孤立存在的，他們存在着某種關系，這種相互關系我們叫做 結構 。

1.3數據結構

數據結構 是相互之間存在一種或多種特定 關系 的 數據元素 的集合。

1.4數據結構三要素

• 邏輯結構
• 物理結構（存儲結構）
• 數據的運算

1.5邏輯結構

在這裡插入圖片描述

1.6物理結構（存儲結構）

在這裡插入圖片描述

1.7數據的運算

運算包括運算的 定義 和 實現 ，運算的定義針對 邏輯結構，運算的實現針對 存儲結構 。

在這裡插入圖片描述

1.8本節回顧

在這裡插入圖片描述

2.算法&算法評價

2.1算法

算法： 對特定問題求解的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作。

2.2算法特性

• 有窮性：一個算法必須在執行有窮步後結束，并且每步操作都在有窮時間内完成。
• 可行性：一個算法必須是可行的，算法中描述的操作是可以實現的。
• 确定性：算法中每一條指令、每一條語句都必須有确定的含義，同樣的輸入，必須要得到同樣的輸出。
• 輸入：一個算法必須要有零個或者多個輸入。
• 輸出：一個算法必須要有零個或者多個輸出。

2.2算法 VS 程序

算法（指導者）：解決問題的一個方法或者過程，考慮如何将輸入轉換成輸出，一個問題可以有很多個算法。

程序（實施者）：程序是某種設計語言對算法的具體實現。

有窮性：算法必須是有窮的，程序可以是無窮的。

正确性：算法必須是正确的，程序可以是錯誤的。

描述方法：算法可以用僞代碼、程序語言等描述，程序隻能用程序語言編寫并可以運行。

2.3算法效率的度量

//例如int sum=0;if(n!=0){ for(int i=1;i<=n;i ){ sum =i; }}如果n==0，T(n)=1=O(1),如果n!=0,T(n)=1 n=O(n)

在這裡插入圖片描述

基本運算頻度：最深層循環所執行的時間複雜度。

常見時間複雜度

在這裡插入圖片描述

O(1)<O(log~2~^n^)<O(n)<O(nlog~2~^n^)<O(n^2^)<O(n^3^)<O(2^n^)<O(n!)<O(n^n^)

2.4本節回顧

關于數據結構的知識，持續更新中，歡迎關注公衆号理木客

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部