計(jì)算機(jī)從解決數(shù)值計(jì)算問題到解決生活中的問題
現(xiàn)實(shí)生活中的問題涉及不同個(gè)體間的復(fù)雜聯(lián)系
需要在計(jì)算機(jī)程序中描述生活中個(gè)體間的聯(lián)系
數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計(jì)算程序問題中的操作對(duì)象以及它們之間的關(guān)系而不是研究復(fù)雜的算法

數(shù)據(jù)結(jié)構(gòu)

基本概念

數(shù)據(jù)：程序的操作對(duì)象，用于描述客觀事物

數(shù)據(jù)的特點(diǎn)：
-可以輸入到計(jì)算機(jī)
-可以被計(jì)算機(jī)程序處理

數(shù)據(jù)是一個(gè)抽象的概念，將其進(jìn)行分類后得到程序設(shè)計(jì)語言中的類型。如：int，float，char等等

數(shù)據(jù)元素：組成數(shù)據(jù)的基本單位
數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成
數(shù)據(jù)對(duì)象 – 性質(zhì)相同的數(shù)據(jù)元素的集合
e.g.

struct _MyTeacher //一種數(shù)據(jù)類型 {char name[32];char tile[32];int age;char addr[128]; };int main21() {struct _MyTeacher t1; //數(shù)據(jù)元素struct _MyTeacher tArray[30]; //數(shù)據(jù)對(duì)象memset(&t1, 0, sizeof(t1));strcpy(t1.name, "name"); //數(shù)據(jù)項(xiàng)strcpy(t1.addr, "addr"); //數(shù)據(jù)項(xiàng)strcpy(t1.tile, "addr"); //數(shù)據(jù)項(xiàng)t1.age = 1; }

數(shù)據(jù)元素之間不是獨(dú)立的，存在特定的關(guān)系，這些關(guān)系即結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的關(guān)系

數(shù)據(jù)的邏輯結(jié)構(gòu)

指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。邏輯結(jié)構(gòu)可細(xì)分為4類

數(shù)據(jù)的物理結(jié)構(gòu)

數(shù)據(jù)的運(yùn)算

算法

基本概念

算法是特定問題求解步驟的描述
在計(jì)算機(jī)中表現(xiàn)為指令的有限序列
算法是獨(dú)立存在的一種解決問題的方法和思想
對(duì)于算法而言，語言并不重要，重要的是思想

算法和數(shù)據(jù)結(jié)構(gòu)區(qū)別

數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系
高效的程序需要在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)和選擇算法

程序=數(shù)據(jù)結(jié)構(gòu)+算法

總結(jié)：
算法是為了解決實(shí)際問題而設(shè)計(jì)的
數(shù)據(jù)結(jié)構(gòu)是算法需要處理的問題載體
數(shù)據(jù)結(jié)構(gòu)與算法相輔相成

算法特性

• 輸入：算法具有0個(gè)或多個(gè)輸入
• 輸出：算法至少有1個(gè)或多個(gè)輸出
• 有窮性：算法在有限的步驟之后會(huì)自動(dòng)結(jié)束而不會(huì)無限循環(huán)
• 確定性：算法中的每一步都有確定的含義，不會(huì)出現(xiàn)二義性
• 可行性：算法的每一步都是可行的

算法效率的度量

• 事后統(tǒng)計(jì)法
  比較不同算法對(duì)同一組輸入數(shù)據(jù)的運(yùn)行處理時(shí)間
  缺陷

  • 為了獲得不同算法的運(yùn)行時(shí)間必須編寫相應(yīng)程序
  • 運(yùn)行時(shí)間嚴(yán)重依賴硬件以及運(yùn)行時(shí)的環(huán)境因素
  • 算法的測(cè)試數(shù)據(jù)的選取相當(dāng)困難
  • 事后統(tǒng)計(jì)法雖然直觀，但是實(shí)施困難且缺陷多

• 事前分析估算
  依據(jù)統(tǒng)計(jì)的方法對(duì)算法效率進(jìn)行估算
  影響算法效率的主要因素

  • 算法采用的策略和方法
  • 問題的輸入規(guī)模
  • 編譯器所產(chǎn)生的代碼
  • 計(jì)算機(jī)執(zhí)行速度

• 大O表示法
  算法效率嚴(yán)重依賴于操作(Operation)數(shù)量
  在判斷時(shí)首先關(guān)注操作數(shù)量的最高次項(xiàng)
  操作數(shù)量的估算可以作為時(shí)間復(fù)雜度的估算
  常見時(shí)間復(fù)雜度：
  
  關(guān)系
  

• 算法的空間復(fù)雜度
  算法的空間復(fù)雜度通過計(jì)算算法的存儲(chǔ)空間實(shí)現(xiàn)
  S(n) = O(f(n))
  其中，n為問題規(guī)模，f(n))為在問題規(guī)模為nn時(shí)所占用存儲(chǔ)空間的函數(shù)
  大O表示法同樣適用于算法的空間復(fù)雜度
  當(dāng)算法執(zhí)行時(shí)所需要的空間是常數(shù)時(shí)，空間復(fù)雜度為O(1)

空間與時(shí)間的策略

• 多數(shù)情況下，算法執(zhí)行時(shí)所用的時(shí)間更令人關(guān)注
• 如果有必要，可以通過增加空間復(fù)雜度來降低時(shí)間復(fù)雜度
• 同理，也可以通過增加時(shí)間復(fù)雜度來降低空間復(fù)雜度

轉(zhuǎn)載于:https://www.cnblogs.com/cj5785/p/10664712.html

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法-概念的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。