自學專業(yè)考試數據結構重點總結分析02331(2014整理)

1、.自考數據結構重點（自考數據結構重點（20142014整理）整理）第一章第一章概論概論1.瑞士計算機科學家沃思提出：算法數據結構=程序。算法是對數據運算的描述，而數據結構包括邏輯結構和存儲結構。由此可見，程序設計的實質是針對實際問題選擇一種好的數據結構和設計一個好的算法，而好的算法在很大程度上取決于描述實際問題的數據結構。2.2.數據數據是信息的載體。數據元素數據元素是數據的基本單位。一個數據元素可以由若干個數據項數據項組成，數據項數據

2、項是具有獨立含義的最小標識單位。數據對象數據對象是具有相同性質的數據元素的集合。3.3.數據結構數據結構指的是數據元素之間的相互關系，即數據的組織形式。數據結構一般包括以下三方面內容：數據的邏輯結構、數據的存儲結構、數據的運算數據結構一般包括以下三方面內容：數據的邏輯結構、數據的存儲結構、數據的運算①數據的邏輯結構是從邏輯關系上描述數據，與數據元素的存儲結構無關，是獨立于計算機的。數據的邏輯結構分類數據的邏輯結構分類:線性結構和非線性結

3、構②數據元素及其關系在計算機內的存儲方式，稱為數據的存儲結構（物理結構）數據的存儲結構（物理結構）。數據的存儲結構是邏輯結構用計算機語言的實現，它依賴于計算機語言。③數據的運算數據的運算。最常用的檢索、插入、刪除、更新、排序等。4.數據的四種基本存儲方法數據的四種基本存儲方法:順序存儲、鏈接存儲、索引存儲、散列存儲（1）順序存儲：通常借助程序設計語言的數組數組描述。（2）鏈接存儲：通常借助于程序語言的指針來描述。（3）索引存儲：索引表由

4、若干索引項組成。關鍵字是能唯一標識一個元素的一個或多個數據項的組合。（4）散列存儲：該方法的基本思想是：根據元素的關鍵字直接計算出該元素的存儲地址。5.算法必須滿足5個準則：輸入輸入，0個或多個數據作為輸入；輸出輸出，產生一個或多個輸出；有窮性有窮性，算法執(zhí)行有限步后結束；確定性確定性，每一條指令的含義都明確；可行性可行性，算法是可行的。算法與程序的區(qū)別：程序必須依賴于計算機程序語言，而一個算法可用自然語言、計算機程序語言、數學語言或約

5、定的符號語言來描述。目前常用的描述算法語言有兩類：類Pal和類C。6.評價算法的優(yōu)劣：算法的“正確性“是首先要考慮的。此外，主要考慮如下三點：①執(zhí)行算法所耗費的時間，即時間復雜性；②執(zhí)行算法所耗費的存儲空間，主要是輔助空間，即空間復雜性；③算法應易于理解、易于編程，易于調試等，即可讀性和可操作性。以上幾點最主要的是時間復雜性，時間復雜度常用漸進時間復雜度表示。7.算法求解問題的輸入量輸入量稱為問題的規(guī)模用一個正整數n表示。8.常見的時間

6、復雜度按數量級遞增排列依次為：常數階0(1)、對數階0(log2n)、線性階0(n)、線性對數階0(nlog2n)、平方階0(n2)立方階0(n3)、…、k次方階0(nk)、指數階0(2n)和階乘階0(n!)。9.一個算法的空間復雜度S(n)定義為該算法所耗費的存儲空間，它是問題規(guī)模n的函數它包括存儲算法本身所占的存儲空間、算法的輸入輸出數據所占的存儲空間和算法在運行過程中臨時占用的存儲空間。第二章第二章線性表線性表1.數據的運算是定義

7、在邏輯結構上的，而運算的具體實現是在存儲結構上進行的。2.只要確定了線性表存儲的起始位置，線性表中任意一個元素都可隨機存取，所以順序表是一種隨機存取結構。3.常見的線性表的基本運算:(1)置空表InitList（L）構造一個空的線性表L。(2)求表長ListLength（L）求線性表L中的結點個數，即求表長。(3)GetNode（L，i）取線性表L中的第i個元素。(4)LocateNode（L，x）在L中查找第一個值為x的元素，并返回該

8、元素在L中的位置。若L中沒有元素的值為x，則返回0值。(5)List（L，i，x）在線性表L的第i個元素之前插入一個值為x的新元素，表L的長度加1。(6)List（L，i）刪除線性表L的第i個元素，刪除后表L的長度減1。4.順序存儲方法：把線性表的數據元素按邏輯次序依次存放在一組地址連續(xù)的存儲單元里的方法。順序表（SequentialList）：用順序存儲方法存儲的線性表稱為順序表。順序表順序表是一種隨機存取結構隨機存取結構順序表的.r

9、next=sr=srnext=NULL終端結點的指針域置空，或空表的頭結點指針域置空以上三個算法的時間復雜度均為以上三個算法的時間復雜度均為O(n)O(n)。8.單鏈表上的查找：（帶頭結點）（1）按結點序號查找：序號為0的是頭結點。算法：p=headj=0從頭結點開始掃描while(pnextjif(i==j)returnp找到了第i個結點elsereturnNULL當i0時，找不到第i個結點時間復雜度：在等概率假設下，平均時間復雜度為

10、：為時間復雜度：在等概率假設下，平均時間復雜度為：為n2=O(n)n2=O(n)（2）按結點值查找：具體算法：ListNodep=headnext從開始結點比較。表非空，p初始值指向開始結點while(p掃描下一結點returnp若p=NULL，則查找失敗，否則p指向值為key的結點時間復雜度為：時間復雜度為：O(n)O(n)9.插入運算：插入運算是將值為x的新結點插入到表的第i個結點的位置上，即插入到ai1與ai之間。s=(ListN

11、ode)malloc(sizeof(ListNode))②sdata=x③snext=pnext④pnext=s⑤算法的時間主要耗費在查找結點上，故時間復雜度亦為O(n)。10.刪除運算刪除運算r=pnext②使r指向被刪除的結點aipnext=rnext③將ai從鏈上摘下free(r)④釋放結點ai的空間給存儲池算法的時間復雜度也是O（n）。p指向被刪除的前一個結點。鏈表上實現的插入和刪除運算，無須移動結點，僅需修改指針。11.單循環(huán)