嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)為主的筆記-吐血推薦(編輯修改稿)
2025-10-04 12:42 本頁面
【文章內(nèi)容簡介】 FreeBSD、Sun公司的Solaris、IBM的AIX），就用一個學(xué)期開設(shè)《數(shù)據(jù)結(jié)構(gòu)和算法》課程（在這之前，用一個學(xué)期開設(shè)《C++程序設(shè)計》課程）。 現(xiàn)行的中學(xué)相關(guān)的計算機教程或者是關(guān)于怎樣使用Windows操作系統(tǒng)及其工具、或者是有關(guān)辦公軟件的使用，或者是打字教程。計算機對他們始終有一種神秘感，也許是理論導(dǎo)向吧，因為不可能每個人將來都成為計算機專業(yè)人員。 作為一個中學(xué)生，在學(xué)完C/C++以后，關(guān)鍵的問題是怎樣熟練地應(yīng)用和鞏固。本網(wǎng)站希望能夠結(jié)合《數(shù)據(jù)結(jié)構(gòu)》和相關(guān)的數(shù)、理、化知識來鞏固C/C++。其實《數(shù)據(jù)結(jié)構(gòu)》并不難?？梢哉f，數(shù)據(jù)結(jié)構(gòu)貫穿于我們的數(shù)學(xué)課程之中，只是思考問題方法的不同。在大學(xué)的《數(shù)據(jù)結(jié)構(gòu)》教程中，很多生僻的詞語、晦澀難懂的語句，連大學(xué)生就感到望而生畏。本網(wǎng)站將集合小學(xué)和中學(xué)的數(shù)學(xué)、物理、化學(xué)教材，深入淺出地講解這門課程。希望不但能夠?qū)W(xué)習(xí)電腦有所幫助，更希望能夠?qū)?shù)理化的學(xué)習(xí)起到一個促進(jìn)作用。 在學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》之前，要求學(xué)生有C/C++基礎(chǔ)?？梢赃@樣說，C/C++是其他程序設(shè)計語言的基礎(chǔ)。掌握了C/C++，學(xué)習(xí)其他語言就會易如反掌。例如，微軟的MFC類庫基于C++；ATL基于C++中的模板類；Java語言基于C++思想，其編程風(fēng)格與C++差別很??；C++ Builder又是基于C++；Delphi中的有關(guān)對象的概念與C++中的對象幾乎完全一致。C++相比其他語言具有與計算機硬件集合緊密、代碼效率高，這是Java語言和其他高級語言所無法比擬的。這樣，C/C++對于學(xué)習(xí)計算機系統(tǒng)結(jié)構(gòu)有很大的好處。 第一章：概論(包括習(xí)題與答案及要點) 本章的重點是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)的運算三方面的概念及相互關(guān)系，難點是算法復(fù)雜度的分析方法。 需要達(dá)到識記層次的基本概念和術(shù)語有：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)。特別是數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運算的含義及其相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯結(jié)構(gòu)和四種常用的存儲表示方法。 需要達(dá)到領(lǐng)會層次的內(nèi)容有算法、算法的時間復(fù)雜度和空間復(fù)雜度、最壞的和平均時間復(fù)雜度等概念，算法描述和算法分析的方法、對一般的算法要能分析出時間復(fù)雜度。 對于基本概念，仔細(xì)看書就能夠理解，這里簡單提一下： 數(shù)據(jù)就是指能夠被計算機識別、存儲和加工處理的信息的載體。 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有時一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。如整數(shù)這個集合中，(關(guān)系式數(shù)據(jù)庫)中，一個記錄可稱為一個數(shù)據(jù)元素，而這個元素中的某一字段就是一個數(shù)據(jù)項。 數(shù)據(jù)結(jié)構(gòu)的定義雖然沒有標(biāo)準(zhǔn)，但是它包括以下三方面內(nèi)容：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、和對數(shù)據(jù)的操作。這一段比較重要，我用自己的語言來說明一下，大家看看是不是這樣。 比如一個表(數(shù)據(jù)庫)，我們就稱它為一個數(shù)據(jù)結(jié)構(gòu)，它由很多記錄(數(shù)據(jù)元素)組成，每個元素又包括很多字段(數(shù)據(jù)項)組成。那么這張表的邏輯結(jié)構(gòu)是怎么樣的呢? 我們分析數(shù)據(jù)結(jié)構(gòu)都是從結(jié)點(其實也就是元素、記錄、頂點，雖然在各種情況下所用名字不同，但說的是同一個東東)之間的關(guān)系來分析的，對于這個表中的任一個記錄(結(jié)點)，它只有一個直接前趨，只有一個直接后繼(前趨后繼就是前相鄰后相鄰的意思)，整個表只有一個開始結(jié)點和一個終端結(jié)點，那我們知道了這些關(guān)系就能明白這個表的邏輯結(jié)構(gòu)了。 而存儲結(jié)構(gòu)則是指用計算機語言如何表示結(jié)點之間的這種關(guān)系。如上面的表，在計算機語言中描述為連續(xù)存放在一片內(nèi)存單元中，還是隨機的存放在內(nèi)存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲結(jié)構(gòu)。(注意，在本課程里，我們只在高級語言的層次上討論存儲結(jié)構(gòu)。) 第三個概念就是對數(shù)據(jù)的運算，比如一張表格，我們需要進(jìn)行查找，增加，修改，刪除記錄等工作，而怎么樣才能進(jìn)行這樣的操作呢? 這也就是數(shù)據(jù)的運算，它不僅僅是加減乘除這些算術(shù)運算了，在數(shù)據(jù)結(jié)構(gòu)中，這些運算常常涉及算法問題。 弄清了以上三個問題，就可以弄清數(shù)據(jù)結(jié)構(gòu)這個概念。 通常我們就將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu) (這兩個很容易理解) 數(shù)據(jù)的存儲方法有四種：順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。 下一個是難點問題，就是算法的描述和分析，主要是算法復(fù)雜度的分析方法及其運用。 首先了解一下幾個概念。一個是時間復(fù)雜度，一個是漸近時間復(fù)雜度。前者是某個算法的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)，而后者是指當(dāng)問題規(guī)模趨向無窮大時，該算法時間復(fù)雜度的數(shù)量級。 當(dāng)我們評價一個算法的時間性能時，主要標(biāo)準(zhǔn)就是算法的漸近時間復(fù)雜度，因此，在算法分析時，往往對兩者不予區(qū)分，經(jīng)常是將漸近時間復(fù)雜度T(n)=O(f(n)簡稱為時間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語句頻度。 此外，算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實例中各元素的取值相關(guān)。但是我們總是考慮在最壞的情況下的時間復(fù)雜度。以保證算法的運行時間不會比它更長。 常見的時間復(fù)雜度，按數(shù)量級遞增排列依次為：常數(shù)階O(1)、對數(shù)階O(log2n)、線性階O(n)、線性對數(shù)階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、k次方階O(n^k)、指數(shù)階O(2^n)。 時間復(fù)雜度的分析計算請看書本上的例子，然后我們通過做練習(xí)加以領(lǐng)會和鞏固。 數(shù)據(jù)結(jié)構(gòu)習(xí)題一 簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1