2014年計算機二級公共基礎(chǔ)知識總結(jié)第一章(3)

　　查看匯總：2014年計算機二級公共基礎(chǔ)知識總結(jié)匯總

　　1.3棧及線性鏈表

　　考點5 棧及其基本運算

　　考試鏈接：

　　考點5在筆試考試中，是一個必考的內(nèi)容，在筆試考試中出現(xiàn)的幾率為100%，主要是以選擇的形式出現(xiàn)，分值為2分，此考點為重點掌握內(nèi)容，讀者應(yīng)該掌握棧的運算 。

　　1.棧的基本概念

　　棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元素時稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的元素;棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。棧是按照"先進后出"或"后進先出"的原則組織數(shù)據(jù)的。

　　2.棧的順序存儲及其運算

　　用一維數(shù)組S(1∶m)作為棧的順序存儲空間，其中m為最大容量。

　　在棧的順序存儲空間S(1∶m)中，S(bottom)為棧底元素，S(top)為棧頂元素。top=0表示�？�;top=m表示棧滿。

　　棧的基本運算有三種：入棧、退棧與讀棧頂元素。

　　(1)入棧運算：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂指針加一(即top加1)，然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明棧空間已滿，不可能再進行入棧操作。這種情況稱為棧"上溢"錯誤。

　　(2)退棧運算：退棧是指取出棧頂元素并賦給一個指定的變量。首先將棧頂元素(棧頂指針指向的元素)賦給一個指定的變量，然后將棧頂指針減一(即top減1)。當(dāng)棧頂指針為0時，說明棧空，不可進行退棧操作。這種情況稱為棧的"下溢"錯誤。

　　(3)讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變量。這個運算不刪除棧頂元素，只是將它賦給一個變量，因此棧頂指針不會改變。當(dāng)棧頂指針為0時，說明�？眨x不到棧頂元素。

　　小技巧：棧是按照"先進后出"或"后進先出"的原則組織數(shù)據(jù)，但是出棧方式有多種選擇，在考題中經(jīng)常考查各種不同的出棧方式。

　　考點6 線性鏈表的基本概念

　　考試鏈接：

　　考點6在筆試考試中出現(xiàn)的幾率為30%，主要是以選擇的形式出現(xiàn)，分值為2分，此考點為識記內(nèi)容。重點識記結(jié)點的組成。

　　在鏈?zhǔn)酱鎯Ψ绞街�，要求每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域，另一部分用于存放指針，稱為指針域。其中指針用于指向該結(jié)點的前一個或后一個結(jié)點(即前件或后件)。

　　鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。

　　(1)線性鏈表

　　線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。

　　在某些應(yīng)用中，對線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針，用以指向其前件結(jié)點;另一個稱為右指針，用以指向其后件結(jié)點。這樣的表稱為雙向鏈表。

　　(2)帶鏈的棧

　　棧也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結(jié)點，這種帶鏈的棧稱為可利用棧。

　　疑難解答：在鏈?zhǔn)浇Y(jié)構(gòu)中，存儲空間位置關(guān)系與邏輯關(guān)系是什么?

　　在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。

　　相關(guān)推薦：

　　計算機等級考試合格標(biāo)準(zhǔn)

　　2014年計算機等考上機六大注意事項

　　考試吧：2014年3月計算機等考真題及答案解析專題