|
|
|
1.3.1 基本數(shù)據(jù)結(jié)構(gòu)與算法
1．算法的基本概念及特征 算法的概念是考試的重點(diǎn)，是指解題方案的準(zhǔn)確而完整的描述，它由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。 算法具有可行性、確定性、有窮性、擁有足夠的情報(bào)等特征。其中，確定性和有窮性是考試的重點(diǎn)。 算法的確定性，是指算法中的每一步驟都必須有明確定義，不允許有模棱兩可的解釋，也不允許有多義性。 算法的有窮性，是指算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能在執(zhí)行有限個(gè)步驟之后終止。 2．算法復(fù)雜度的概念和意義
一個(gè)算法質(zhì)量的好壞可從算法的時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面來(lái)衡量。算法的復(fù)雜度也是每次考試的重點(diǎn)，要注意明確有關(guān)概念。 算法的時(shí)間復(fù)雜度是指算法所需要的計(jì)算工作量；算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存 空間。
3．?dāng)?shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問(wèn)題： ① 數(shù)據(jù)集合中各元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。 ② 在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 ③ 對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。 要注意數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的區(qū)別與聯(lián)系。
4．線性結(jié)構(gòu)與非線性結(jié)構(gòu) 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各元素之間前后件關(guān)系的復(fù)雜程度，一般數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。要注意這兩種結(jié)構(gòu)的特征、它們之間的區(qū)別以及常見(jiàn)的有關(guān)結(jié)構(gòu)。 （1）線性結(jié)構(gòu)（或稱線性表）有以下主要特征： ① 有且只有一個(gè)根結(jié)點(diǎn)，它無(wú)前件。 ② 有且只有一個(gè)終結(jié)點(diǎn)，它無(wú)后件。 ③ 除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的長(zhǎng)度，當(dāng)結(jié)點(diǎn)個(gè)數(shù)為0時(shí)，該線性表為空表。 常見(jiàn)的線性結(jié)構(gòu)有：線性表、棧、隊(duì)列等。
（2）如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)，常見(jiàn)的非線性結(jié)構(gòu)有：樹(shù)、二叉樹(shù)、圖等。 5．線性表的順序存儲(chǔ)結(jié)構(gòu)（順序表）及其插入與刪除運(yùn)算 線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)。要注意掌握二者在存儲(chǔ)數(shù)據(jù)方面的方式與特點(diǎn)。 （1）線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)
① 線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的。 ② 線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。 由此可見(jiàn)，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面。 （2）線性表在順序存儲(chǔ)結(jié)構(gòu)下的插入與刪除運(yùn)算 線性表在順序存儲(chǔ)結(jié)構(gòu)下，若在第i（1?i?n，n為線性表中元素的個(gè)數(shù)）個(gè)位置上插入一個(gè)新元素，則首先從最后一個(gè)（即第n個(gè)）元素開(kāi)始，直到第i個(gè)元素之間共有n–i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)位置就被空出，然后將新元素插入到第i個(gè)位置。插入結(jié)束后，線性表的長(zhǎng)度增1。 顯然，在最好的情況下，插入位置在線性表的末尾進(jìn)行，即在第n個(gè)元素之后插入運(yùn)算，此時(shí)，不需要移動(dòng)表中的元素。而在最壞的情況下，插入位置在第1個(gè)元素上，此時(shí)需要移動(dòng)表中所有的元素。在平均情況下，要在線性表中插入一個(gè)新元素，需要移動(dòng)表中一半的元素。
同理，線性表在順序存儲(chǔ)結(jié)構(gòu)下的刪除運(yùn)算，也需要移動(dòng)表中的元素，只不過(guò)是向前移動(dòng)，在最好的情況下，刪除運(yùn)算在線性表的末尾進(jìn)行，即刪除第n個(gè)元素，此時(shí)，不需要移動(dòng)表中的元素。而在最壞的情況下，刪除位置在第1個(gè)元素上，此時(shí)需要移動(dòng)表中所有的元素。在平均情況下，要在線性表中刪除一個(gè)元素，需要移動(dòng)表中一半的元素。 線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，以及在順序存儲(chǔ)結(jié)構(gòu)下插入與刪除運(yùn)算的效率是考試的重點(diǎn)。
6．棧與隊(duì)列 要深刻領(lǐng)會(huì)二者的概念，以及對(duì)二者進(jìn)行插入、刪除運(yùn)算的特點(diǎn)，這是考試的重點(diǎn)。 棧實(shí)際上也是線性表，只不過(guò)是一種特殊的線性表。在這種特殊的線性表中，其插入與刪除運(yùn)算都只在線性表的一端進(jìn)行。即在這種線性表的結(jié)構(gòu)中，一端是封閉的，不允許進(jìn)行插入與刪除元素；另一端是開(kāi)口的，允許插入與刪除元素。允許插入與刪除運(yùn)算的一端稱為棧頂，而不允許插入與刪除運(yùn)算的一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。即棧是按照“先進(jìn)后出”（First In Last Out，F(xiàn)ILO）或“后進(jìn)先出”（Last In First Out，LIFO）的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進(jìn)后出”表或“后進(jìn)先出”表。由此可以看出，棧具有記憶作用。對(duì)棧常可以進(jìn)行進(jìn)棧、出棧、讀取棧頂元素的運(yùn)算。
隊(duì)列是指允許在一端進(jìn)行插入運(yùn)算、而在另一端進(jìn)行刪除運(yùn)算的線性表。允許插入運(yùn)算的一端稱為隊(duì)尾，通常用一個(gè)稱為隊(duì)尾指針的指針指向隊(duì)尾元素，即隊(duì)尾指針總是指向最后被插入的元素。允許刪除運(yùn)算的一端稱為隊(duì)頭，通常也用一個(gè)隊(duì)頭指針指向隊(duì)頭的元素。顯然，在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除，反之，最后插入的元素將最后才能被刪除。因此，隊(duì)列又稱為“先進(jìn)先出”（First In First Out，F(xiàn)IFO）或“后進(jìn)后出”（Last In Last Out，LILO）的線性表。對(duì)隊(duì)列可以進(jìn)行入隊(duì)、退隊(duì)運(yùn)算。
7．循環(huán)隊(duì)列 重點(diǎn)注意循環(huán)隊(duì)列的概念、存儲(chǔ)方式。 循環(huán)隊(duì)列是隊(duì)列順序存儲(chǔ)結(jié)構(gòu)的一種，它將m個(gè)物理上連續(xù)的存儲(chǔ)單元，在邏輯上形成一個(gè)環(huán)狀，供隊(duì)列循環(huán)使用。 具體來(lái)說(shuō)，在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，因此，從隊(duì)頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。
8．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（線性鏈表） （1）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其有關(guān)運(yùn)算 在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，一個(gè)元素用一個(gè)結(jié)點(diǎn)來(lái)存儲(chǔ)，每個(gè)結(jié)點(diǎn)含有兩個(gè)域，一個(gè)數(shù)據(jù)域用于存放數(shù)據(jù)元素值，一個(gè)指針域，用于存放指針，該指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件）。 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序（即存儲(chǔ)空間位置）與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。要特別注意，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)方式的不同。
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)又稱為線性鏈表。 對(duì)線性鏈表的運(yùn)算主要包括：查找指定元素、插入、刪除運(yùn)算等。不像順序存儲(chǔ)結(jié)構(gòu)那樣，對(duì)線性鏈表的插入與刪除運(yùn)算不需要移動(dòng)數(shù)據(jù)元素，而只需改變有關(guān)結(jié)點(diǎn)的指針即可。
|
|
發(fā)表留言請(qǐng)先登錄！
|