、基本數(shù)據(jù)結(jié)構(gòu)與算法(編輯修改稿)
2024-08-28 17:22 本頁面
【文章內(nèi)容簡介】 隊列 ：限定僅在表的一端進(jìn)行插入，在另一端進(jìn)行刪除操作的線性表。是一種 先進(jìn)先出 （ FIFO，first in first out）的線性表。允許插入的的一端叫隊尾 ，允許刪除的一端則稱為 隊頭 。 下圖是隊列的示意圖： a1 a2 … an 出隊 入隊 隊頭 隊尾 由于隊列的隊頭和隊尾的位置是變化的，因而要設(shè)兩個指針和分別指示隊頭和隊尾元素在隊列中的位置，它們的初始值隊列初始化時均應(yīng)置為０。入隊時將新元素插入所指的位置，然后將加１。出隊時，刪去所指的元素，然后將加１并返回被刪元素。由此可見，當(dāng)頭尾指針相等時隊列為空。在非空隊列里，頭指針始終指向隊頭元素，而尾指針始終指向隊尾元素的下一位置。 ０ １ ２ ３ 0 1 2 3 Front rear a b c Front rear (a)隊列初始為空 （ b） A,B,C入隊 ０ １ ２ ３ ０ １ ２ ３ b c front rear front rear （ c) a出隊 (d) b,c出隊，隊為空 和棧類似，隊列中亦有上溢和下溢現(xiàn)象。此外，順序隊列中還存在 “ 假上溢 ” 現(xiàn)象。因為在入隊和出隊的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無法重新利用。因此，盡管隊列中實際的元素個數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，但也可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊操作。該現(xiàn)象稱為假上溢。 ?下列關(guān)于隊列的敘述中正確的是 ______。 A. 在隊列中只能插入數(shù)據(jù) B. 在隊列中只能刪除數(shù)據(jù) C. 隊列是先進(jìn)先出的線性表 D. 隊列是先進(jìn)后出的線性表 (C) ? 在實際應(yīng)用中，隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式。所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間。 在循環(huán)隊列中，用隊尾指針 rear指向隊列中的隊尾元素，用隊頭指針 front指向隊頭元素的前一個位置，因此，從隊頭指針 front指向的后一個位置直到隊尾指針 rear指向的位置之間所有的元素均為隊列中的元素。 ? 克服上述假上溢現(xiàn)象的方法 是將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲在其中的隊列稱為循環(huán)隊列（ Circular Queue)。在循環(huán)隊列中進(jìn)行出隊、入隊操作時，頭尾指針仍要加 1，朝前移動。只不過當(dāng)頭尾指針指向向量上界（ QueueSize1）時，其加 1操作的結(jié)果是指向向量的下界 0 ? 在實際使用循環(huán)隊列時，為了能區(qū)分隊滿還是隊列空，通常需要增加一個標(biāo)志 S： 隊列空，則 S=0， rear=front=m 隊列滿，則 S=1， rear=front=m 循環(huán)隊列主要有兩種基本運(yùn)算：入隊運(yùn)算和退隊運(yùn)算 入隊運(yùn)算指在循環(huán)隊列的隊尾加入一個新元素，首先rear=rear+1,當(dāng) rear=m+1時，置 rear=1,然后將新元素插入到隊尾指針指向的位置。當(dāng) S=1， rear=front,說明隊列已滿，不能進(jìn)行入隊運(yùn)算，稱為“上溢”。 退隊運(yùn)算指在循環(huán)隊列的隊頭位置退出一個元素并賦給指定的變量。首先 front=front+1,并當(dāng) front=m+1時，置front=1,然后將對頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊列為空 S=0，不能進(jìn)行退隊運(yùn)算，這種情況成為“下溢”。 ?十二 .線性單鏈表的 存儲結(jié)構(gòu) : 以鏈?zhǔn)浇Y(jié)構(gòu)存儲的線性表稱之為線性鏈表。缺點(diǎn)是不容易找到直接前趨。 ?頭指針只相當(dāng)于結(jié)點(diǎn)的指針域，頭結(jié)點(diǎn)即整個線性鏈表的第一個結(jié)點(diǎn)，它的數(shù)據(jù)域可以放數(shù)據(jù)元素，也可以放線性表的長度等附加信息，也可以不存儲任何信息。 十三 .線性鏈表的基本運(yùn)算 ?用鏈表表示線性表的優(yōu)點(diǎn)是 ______。 A. 便于插入和刪除操作 B. 數(shù)據(jù)元素的物理順序與邏輯順序相同 C. 花費(fèi)的存儲空間較順序存儲少 D. 便于隨機(jī)存取 (A) ?十四 .雙向鏈表的 存儲結(jié)構(gòu) ：在雙向鏈表的結(jié)點(diǎn)中有兩個指針域，其一指向直接后繼，另一指向直接前趨。 ?十五 .循環(huán)鏈表的存儲結(jié)構(gòu)及其基本運(yùn)算 是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)，它的特點(diǎn)是表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個鏈表形成一個環(huán)。因此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。 ?在 中，只要指出表中任何一個結(jié)點(diǎn)的位置，就可以從它出發(fā) 依次 訪問到表中其他所有結(jié)點(diǎn)。 A．線性單鏈表 B．雙向鏈表 C．線性鏈表 D．循環(huán)鏈表 這里的關(guān)鍵詞是“ 依次 ”， 線性單鏈表不能找到前面的節(jié)點(diǎn)。這題有 2個答案。 （ B， D） ?十六 .樹 ?一、樹的定義：樹是 n(n=0)個結(jié)點(diǎn)的有限集。在任
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1