數(shù)據(jù)結(jié)構(gòu)基本概念

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

1.數(shù)據(jù)：即信息的載體，是能夠輸入到計(jì)算機(jī)中并且能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和處理的符號(hào)總稱。

2.數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，又稱之為記錄（Record）。一般，數(shù)據(jù)元素由若干基本項(xiàng)（或稱字段、域、屬性）組成。

3.數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)元素及數(shù)據(jù)元素之間的相互關(guān)系，或組織數(shù)據(jù)的形式。

數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系

一、邏輯結(jié)構(gòu)：表示數(shù)據(jù)之間的抽象關(guān)系（如鄰接關(guān)系、從屬關(guān)系等），按每個(gè)元素可能具有的直接前趨數(shù)和直接后繼數(shù)將邏輯結(jié)構(gòu)分為“線性結(jié)構(gòu)”和“非線性結(jié)構(gòu)”兩大類。

1.特點(diǎn)：

只是描述數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的聯(lián)系規(guī)律。

是從具體問題中抽象出來的數(shù)學(xué)模型，是獨(dú)立于計(jì)算機(jī)存儲(chǔ)器的（與機(jī)器無關(guān)）。

2.邏輯結(jié)構(gòu)分類：集合，線性結(jié)構(gòu)，非線性結(jié)構(gòu)

1）線性結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有序（次序）集合。

　　集合中必存在唯一的一個(gè)"第一個(gè)元素"；

　　集合中必存在唯一的一個(gè)"最后的元素"；

　　除最后元素之外，其它數(shù)據(jù)元素均有唯一的"后繼"；

　　除第一元素之外，其它數(shù)據(jù)元素均有唯一的"前驅(qū)"。

2）樹形結(jié)構(gòu)（層次結(jié)構(gòu)）

樹形結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在著“一對(duì)多”的樹形關(guān)系的數(shù)據(jù)結(jié)構(gòu)，是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)數(shù)可以是一個(gè)也可以是多個(gè)。

3）圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）

圖是一種比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖結(jié)構(gòu)中任意兩個(gè)元素之間都可能有關(guān)系，也就是說這是一種多對(duì)多的關(guān)系。

4）其他結(jié)構(gòu)

除了以上幾種常見的邏輯結(jié)構(gòu)外，數(shù)據(jù)結(jié)構(gòu)中還包含其他的結(jié)構(gòu)，比如集合等。有時(shí)根據(jù)實(shí)際情況抽象的模型不止是簡(jiǎn)單的某一種，也可能擁有更多的特征。

二、存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在計(jì)算機(jī)中的具體實(shí)現(xiàn)方法，分為順序存儲(chǔ)方法、鏈接存儲(chǔ)方法、索引存儲(chǔ)方法、散列存儲(chǔ)方法。

1.特點(diǎn)：

是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映象（或表示）

存儲(chǔ)結(jié)構(gòu)是通過計(jì)算機(jī)程序來實(shí)現(xiàn)的，因而是依賴于具體的計(jì)算機(jī)語言的。

2.存儲(chǔ)結(jié)構(gòu)分類：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)

1）順序存儲(chǔ)（Sequential Storage）：將數(shù)據(jù)結(jié)構(gòu)中各元素按照其邏輯順序存放于存儲(chǔ)器一片連續(xù)的存儲(chǔ)空間中。

2）鏈?zhǔn)酱鎯?chǔ)（Linked Storage）：將數(shù)據(jù)結(jié)構(gòu)中各元素分布到存儲(chǔ)器的不同點(diǎn)，用記錄下一個(gè)結(jié)點(diǎn)位置的方式建立它們之間的聯(lián)系，由此得到的存儲(chǔ)結(jié)構(gòu)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

3）索引存儲(chǔ)（Indexed Storage）：在存儲(chǔ)數(shù)據(jù)的同時(shí)，建立一個(gè)附加的索引表，即索引存儲(chǔ)結(jié)構(gòu)=數(shù)據(jù)文件+索引表。

算法基本概念

1.定義：算法（Algorithm）是一個(gè)有窮規(guī)則（或語句、指令）的有序集合。它確定了解決某一問題的一個(gè)運(yùn)算序列。對(duì)于問題的初始輸入，通過算法有限步的運(yùn)行，產(chǎn)生一個(gè)或多個(gè)輸出。

數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān):

• 算法設(shè)計(jì): 取決于選定的邏輯結(jié)構(gòu)
• 算法實(shí)現(xiàn): 依賴于采用的存儲(chǔ)結(jié)構(gòu)

2.算法的特性

• 有窮性 —— 算法執(zhí)行的步驟（或規(guī)則）是有限的；
• 確定性 —— 每個(gè)計(jì)算步驟無二義性；
• 可行性 —— 每個(gè)計(jì)算步驟能夠在有限的時(shí)間內(nèi)完成；
• 輸入 ，輸出 —— 存在數(shù)據(jù)的輸入和出輸出

3.評(píng)價(jià)算法好壞的方法

• 正確性：運(yùn)行正確是一個(gè)算法的前提。
• 可讀性：容易理解、容易編程和調(diào)試、容易維護(hù)。
• 健壯性：考慮情況全面，不容以出現(xiàn)運(yùn)行錯(cuò)誤。
• 時(shí)間效率高：算法消耗的時(shí)間少。
• 儲(chǔ)存量低：占用較少的存儲(chǔ)空間。

時(shí)間復(fù)雜度計(jì)算

算法效率——用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來度量。“O”表示一個(gè)數(shù)量級(jí)的概念。根據(jù)算法中語句執(zhí)行的最大次數(shù)（頻度）來 估算一個(gè)算法執(zhí)行時(shí)間的數(shù)量級(jí)。

計(jì)算方法：

寫出程序中所有運(yùn)算語句執(zhí)行的次數(shù)，進(jìn)行加和
如果得到的結(jié)果是常量則時(shí)間復(fù)雜度為1
如果得到的結(jié)果中存在變量n則取n的最高次冪作為時(shí)間復(fù)雜度

下圖表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率。

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

總結(jié)

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

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