本章的重點是了解數據結構的邏輯結構存儲結構數據的運算三方面的概念及相互關系難點是算法復雜度的分析方法
需要達到 <識記> 層次的基本概念和術語有數據數據元素數據項數據結構特別是數據結構的邏輯結構存儲結構及數據運算的含義及其相互關系數據結構的兩大類邏輯結構和四種常用的存儲表示方法
需要達到 <領會> 層次的內容有算法算法的時間復雜度和空間復雜度最壞的和平均時間復雜度等概念算法描述和算法分析的方法對一般的算法要能分析出時間復雜度
對於基本概念仔細看書就能夠理解這裡簡單提一下
數據就是指能夠被計算機識別存儲和加工處理的信息的載體
數據元素是數據的基本單位有時一個數據元素可以由若干個數據項組成數據項是具有獨立含義的最小標識單位如整數這個集合中這個數就可稱是一個數據元素又比如在一個數據庫(關系式數據庫)中一個記錄可稱為一個數據元素而這個元素中的某一字段就是一個數據項
數據結構的定義雖然沒有標准但是它包括以下三方面內容 邏輯結構存儲結構和對數據的操作 這一段比較重要我用自己的語言來說明一下大家看看是不是這樣
比如一個 表 ( 數據庫 )我們就稱它為一個數據結構它由很多 記錄 ( 數據元素 )組成每個元素又包括很多 字段 ( 數據項 )組成那麼這張表的邏輯結構是怎麼樣的呢? 我們分析數據結構都是從 結點 (其實也就是元素記錄頂點雖然在各種情況下所用名字不同但說的是同一個東東)之間的關系來分析的對於這個表中的任一個記錄(結點)它只有一個 直接前趨 只有一個 直接後繼 (前趨後繼就是前相鄰後相鄰的意思)整個表只有一個 開始結點 和一個 終端結點 那我們知道了這些關系就能明白這個表的邏輯結構了
而 存儲結構 則是指用 計算機語言 如何表示結點之間的這種關系如上面的表在計算機語言中描述為連續存放在一片內存單元中還是隨機的存放在內存中再用指針把它們鏈接在一起這兩種表示法就成為兩種不同的存儲結構( 注意在本課程裡我們只在高級語言的層次上討論存儲結構 )
第三個概念就是對 數據的運算 比如一張表格我們需要進行查找增加修改刪除記錄等工作而怎麼樣才能進行這樣的操作呢? 這也就是數據的運算它不僅僅是加減乘除這些算術運算了在數據結構中這些運算常常涉及算法問題
弄清了以上三個問題就可以弄清數據結構這個概念
通常我們就將數據的 邏輯結構 簡稱為 數據結構 數據的邏輯結構分兩大類 線性結構 和 非線性結構 (這兩個很容易理解)
數據的存儲方法有四種 順序存儲方法 鏈接存儲方法 索引存儲方法和散列存儲方法
下一個是 難點 問題就是算法的描述和分析主要是 算法復雜度 的分析方法及其運用
首先了解一下幾個概念一個是 時間復雜度 一個是 漸近時間復雜度 前者是某個算法的時間耗費它是該算法所求解問題 規模 n的函數而後者是指當問題規模趨向無窮大時該算法 時間復雜度的數量級
當我們評價一個算法的時間性能時主要標准就是 算法的漸近時間復雜度 因此 在算法分析時往往對兩者不予區分經常是將漸近時間復雜度T(n)=O(f(n)簡稱為時間復雜度其中的f(n)一般是算法中頻度最大的語句頻度
此外算法中語句的頻度 不僅與問題規模有關還與輸入實例中各元素的取值相關 但是我們總是考慮在最壞的情況下的時間復雜度以保證算法的運行時間不會比它更長
常見的時間復雜度按數量級遞增排列依次為 常數階O() 對數階O(logn) 線性階O(n) 線性對數階O(nlogn) 平方階O(n^)立方階O(n^) k次方階O(n^k) 指數階O(^n)
時間復雜度的分析計算請看書本上的例子然後我們通過做練習加以領會和鞏固
數 據 結 構 習 題 一
簡述下列概念數據數據元素數據類型數據結構邏輯結構存儲結構線性結構非線性結構
◆ 數據 指能夠被計算機識別存儲和加工處理的信息載體
◆ 數據元素 就是數據的基本單位在某些情況下數據元素也稱為元素結點頂點記錄數據元素有時可以由若干 數據項 組成
◆ 數據類型 是一個值的集合以及在這些值上定義的一組操作的總稱
◆ 數據結構 指的是數據之間的相互關系即數據的組織形式一般包括三個方面的內容:數據的 邏輯結構 存儲結構 和 數據的運算
◆ 邏輯結構 指各數據元素之間的邏輯關系
◆ 存儲結構 就是數據的邏輯結構用計算機語言的實現
◆ 線性結構 數據邏輯結構中的一類它的特征是若結構為非空集則該結構有且只有一個 開始結點 和一個 終端結點 並且所有結點都最多只有一個 直接前趨 和一個 直接後繼 線性表就是一個典型的線性結構
◆ 非線性結構 數據邏輯結構中的另一大類它的邏輯特征是一個結點可能有多個直接前趨和直接後繼
試舉一個數據結構的例子敘述其邏輯結構存儲結構運算三個方面的內容
◆ 例如有一張學生成績表記錄了一個班的學生各門課的成績按學生的姓名為一行記成的表這個表就是一個數據結構每個記錄(有姓名學號成績等字段)就是一個結點對於整個表來說只有一個開始結點(它的前面無記錄)和一個終端結點(它的後面無記錄)其他的結點則各有一個也只有一個直接前趨和直接後繼(它的前面和後面均有且只有一個記錄)這幾個關系就確定了這個表的邏輯結構
那麼我們怎樣把這個表中的數據存儲到計算機裡呢? 用高級語言如何表示各結點之間的關系呢? 是用一片連續的內存單元來存放這些記錄(如用數組表示)還是隨機存放各結點數據再用指針進行鏈接呢? 這就是存儲結構的問題我們都是從高級語言的層次來討論這個問題的(所以各位趕快學C語言吧)
最後我們有了這個表(數據結構)肯定要用它那麼就是要對這張表中的記錄進行查詢修改刪除等操作對這個表可以進行哪些操作以及如何實現這些操作就是數據的運算問題了
常用的存儲表示方法有哪幾種?
常用的存儲表示方法有四種:
◆ 順序存儲方法 它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元裡結點間的邏輯關系由存儲單元的鄰接關系來體現由此得到的存儲表示稱為 順序存儲結構
◆ 鏈接存儲方法 它不要求邏輯上相鄰的結點在物理位置上亦相鄰結點間的邏輯關系是由附加的指針字段表示的由此得到的存儲表示稱為 鏈式存儲結構
◆ 索引存儲方法 除建立存儲結點信息外還建立附加的索引表來標識結點的地址
◆ 散列存儲方法 就是根據結點的關鍵字直接計算出該結點的存儲地址
設三個函數fgh分別為 f(n)=n^+n^+ g(n)=n^+n^ h(n)=n^+nlgn 請判斷下列關系是否成立
() f(n)=O(g(n))
() g(n)=O(f(n))
() h(n)=O(n^)
() h(n)=O(nlgn)
◆ ()成立
◇ 這裡我們復習一下漸近時間復雜度的表示法 T(n)=O(f(n)) 這裡的O是數學符號它的嚴格定義是 若T(n)和f(n)是定義在正整數集合上的兩個函數則T(n)=O(f(n))表示存在正的常數C和 n 使得當n≥ n 時都滿足≤T(n)≤C·f(n) 用容易理解的話說就是 這兩個函數當整型自變量n趨向於無窮大時兩者的比值是一個不等於的常數 這麼一來就好計算了吧第()題中兩個函數的最高次項都是n^因此當n→∞時兩個函數的比值是一個常數所以這個關系式是成立的
◆ ()成立
◆ ()成立
◆ ()不成立
設有兩個算法在同一機器上運行其執行時間分別為n^和^n要使前者快於後者n至少要多大?
◆
◇ 最簡單最笨的辦法就是拿自然數去代呗假定n取為則前者的值是後者的值是小於前者那我們就加個用代入得前者為後者為已經比前者大但相差不多那我們再減個用代入得前者為後者為又比前者小了所以結果得出來就是n至少要是
設n為正整數利用大O記號將下列程序段的執行時間表示為n的函數
() i=; k=
while(i
{ k=k+*i;i++;
} ◆ T(n)=n
∴ T(n)=O(n)
◇ 這個函數是按線性階遞增的
() i=; k=;
do{
k=k+*i; i++;
}
while(i<> ◆ T(n)=n
∴ T(n)=O(n)
◇ 這也是線性階遞增的
() i=; j=;
while(i+j<=n)
{
if (i
else i++;
} ◆ T(n)=n/
∴ T(n)=O(n)
◇ 雖然時間函數是n/但其數量級仍是按線性階遞增的
() x=n; // n>
while (x>=(y+)*(y+))
y++; ◆ T(n)=n /
∴ T(n)=O(n / )
◇ 最壞的情況是y=那麼循環的次數是n / 次這是一個按平方根階遞增的函數
() x=; y=;
while(y>)
if(x>)
{x=x;y;}
else x++; ◆ T(n)=O()
◇ 這個程序看起<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23688.html
