自考02331數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)(最終修訂)

1、1自考自考0233102331數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)(最終修訂最終修訂)第一章第一章概論概論1.瑞士計(jì)算機(jī)科學(xué)家沃思提出：算法數(shù)據(jù)結(jié)構(gòu)=程序。算法是對(duì)數(shù)據(jù)運(yùn)算的描述，而數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。由此可見(jiàn)，程序設(shè)計(jì)的實(shí)質(zhì)是針對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)一個(gè)好的算法，而好的算法在很大程度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。2.2.數(shù)據(jù)數(shù)據(jù)是信息的載體。數(shù)據(jù)元素?cái)?shù)據(jù)元素是數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)

2、組成，數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。3.3.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算①數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)分類數(shù)據(jù)的邏輯結(jié)構(gòu)分類:線

3、性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性表線性表是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。數(shù)組、廣義表、樹(shù)和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。②數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)，它依賴于計(jì)算機(jī)語(yǔ)言。③數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算。最常用的檢索、插入、刪除、更新、排序等。4.數(shù)據(jù)的四種基本存儲(chǔ)方法數(shù)據(jù)的四種基本存儲(chǔ)方法:順序存儲(chǔ)、鏈接存儲(chǔ)、索引存儲(chǔ)、散列存

4、儲(chǔ)（1）順序存儲(chǔ)：通常借助程序設(shè)計(jì)語(yǔ)言的數(shù)組數(shù)組描述。（2）鏈接存儲(chǔ)：通常借助于程序語(yǔ)言的指針來(lái)描述。（3）索引存儲(chǔ)：索引表由若干索引項(xiàng)組成。關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)元素的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的組合。（4）散列存儲(chǔ)：該方法的基本思想是：根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲(chǔ)地址。5.算法必須滿足5個(gè)準(zhǔn)則：輸入輸入，0個(gè)或多個(gè)數(shù)據(jù)作為輸入；輸出輸出，產(chǎn)生一個(gè)或多個(gè)輸出；有窮性有窮性，算法執(zhí)行有限步后結(jié)束；確定性確定性，每一條指令的含義都明確；可

5、行性可行性，算法是可行的。算法與程序的區(qū)別：程序必須依賴于計(jì)算機(jī)程序語(yǔ)言，而一個(gè)算法可用自然語(yǔ)言、計(jì)算機(jī)程序語(yǔ)言、數(shù)學(xué)語(yǔ)言或約定的符號(hào)語(yǔ)言來(lái)描述。目前常用的描述算法語(yǔ)言有兩類：類Pal和類C。6.評(píng)價(jià)算法的優(yōu)劣：算法的“正確性“是首先要考慮的。此外，主要考慮如下三點(diǎn)：①執(zhí)行算法所耗費(fèi)的時(shí)間，即時(shí)間復(fù)雜性；②執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，主要是輔助空間，即空間復(fù)雜性；③算法應(yīng)易于理解、易于編程，易于調(diào)試等，即可讀性和可操作性。以上幾點(diǎn)最主要的

6、是時(shí)間復(fù)雜性，時(shí)間復(fù)雜度常用漸進(jìn)時(shí)間復(fù)雜度表示。7.算法求解問(wèn)題的輸入量輸入量稱為問(wèn)題的規(guī)模用一個(gè)正整數(shù)n表示。8.常見(jiàn)的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階0(1)、對(duì)數(shù)階0(log2n)、線性階0(n)、線性對(duì)數(shù)階0(nlog2n)、平方階0(n2)立方階0(n3)、…、k次方階0(nk)、指數(shù)階0(2n)和階乘階0(n!)。9.一個(gè)算法的空間復(fù)雜度S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它是問(wèn)題規(guī)模n的函數(shù)它包括存儲(chǔ)算法本身所占

7、的存儲(chǔ)空間、算法的輸入輸出數(shù)據(jù)所占的存儲(chǔ)空間和算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間。第二章第二章線性表線性表1.數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。2.只要確定了線性表存儲(chǔ)的起始位置，線性表中任意一個(gè)元素都可隨機(jī)存取，所以順序表是一種隨機(jī)存取結(jié)構(gòu)。3.常見(jiàn)的線性表的基本運(yùn)算:(1)置空表InitList（L）構(gòu)造一個(gè)空的線性表L。(2)求表長(zhǎng)ListLength（L）求線性表L中的結(jié)點(diǎn)個(gè)數(shù)，即求表長(zhǎng)。(3

8、)GetNode（L，i）取線性表L中的第i個(gè)元素。(4)LocateNode（L，x）在L中查找第一個(gè)值為x的元素，并返回該元素在L中的位置。若L中沒(méi)有元素的值為x，則返回0值。(5)List（L，i，x）在線性表L的第i個(gè)元素之前插入一個(gè)值為x的新元素，表L的長(zhǎng)度加1。(6)List（L，i）刪除線性表L的第i個(gè)元素，刪除后表L的長(zhǎng)度減1。4.順序存儲(chǔ)方法：把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里的方法。順序表

9、（SequentialList）：用順序存儲(chǔ)方法存儲(chǔ)的線性表稱為順序表。順序表順序表是一種隨機(jī)存取結(jié)構(gòu)隨機(jī)存取結(jié)構(gòu)順序表的特點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰。3r=srnext=NULL終端結(jié)點(diǎn)的指針域置空，或空表的頭結(jié)點(diǎn)指針域置空以上三個(gè)算法的時(shí)間復(fù)雜度均為以上三個(gè)算法的時(shí)間復(fù)雜度均為O(n)O(n)。8.單鏈表上的查找：（帶頭結(jié)點(diǎn)）（1）按結(jié)點(diǎn)序號(hào)查找：序號(hào)為0的是頭結(jié)點(diǎn)。算法：p=headj=0從頭結(jié)點(diǎn)開(kāi)始掃描while(pn

10、extjif(i==j)returnp找到了第i個(gè)結(jié)點(diǎn)elsereturnNULL當(dāng)i0時(shí)，找不到第i個(gè)結(jié)點(diǎn)時(shí)間復(fù)雜度：在等概率假設(shè)下，平均時(shí)間復(fù)雜度為：為時(shí)間復(fù)雜度：在等概率假設(shè)下，平均時(shí)間復(fù)雜度為：為n2=O(n)n2=O(n)（2）按結(jié)點(diǎn)值查找：具體算法：ListNodep=headnext從開(kāi)始結(jié)點(diǎn)比較。表非空，p初始值指向開(kāi)始結(jié)點(diǎn)while(p掃描下一結(jié)點(diǎn)returnp若p=NULL，則查找失敗，否則p指向值為key的結(jié)點(diǎn)時(shí)間

11、復(fù)雜度為：時(shí)間復(fù)雜度為：O(n)O(n)9.插入運(yùn)算：插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai1與ai之間。s=(ListNode)malloc(sizeof(ListNode))②sdata=x③snext=pnext④pnext=s⑤算法的時(shí)間主要耗費(fèi)在查找結(jié)點(diǎn)上，故時(shí)間復(fù)雜度亦為O(n)。10.刪除運(yùn)算刪除運(yùn)算r=pnext②使r指向被刪除的結(jié)點(diǎn)aipnext=rnext③將ai從鏈上摘下free(r)

12、④釋放結(jié)點(diǎn)ai的空間給存儲(chǔ)池算法的時(shí)間復(fù)雜度也是O（n）.p指向被刪除的前一個(gè)結(jié)點(diǎn)。鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。11.單循環(huán)鏈表—在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開(kāi)始結(jié)點(diǎn)即可。判斷空鏈表的條件是head==headnext12.僅設(shè)尾指針的單循環(huán)鏈表僅設(shè)尾指針的單循環(huán)鏈表:用尾指針rear表示的單循環(huán)鏈表對(duì)開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an查找時(shí)間都是O(1)。而表的操作常常是在表的首尾位置上