考點(diǎn)9 順序表的刪除運(yùn)算
線性表的刪除運(yùn)算是指將表的第i(1≤i≤n)個結(jié)點(diǎn)刪除，使長度為n的線性表：
(a1，…，ai-1，ai，ai+1，…，an)
變成長度為n-l的線性表
(a1，…，ai-1，ai+1，…，an)
該算法的時間分析與插入算法相似，結(jié)點(diǎn)的移動次數(shù)也是由表長n和位置i決定。若i=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動結(jié)點(diǎn)；若i=1，則前移語句將循環(huán)執(zhí)行n一1次，需移動表中除開始結(jié)點(diǎn)外的所有結(jié)點(diǎn)。這兩種情況下算法的時間復(fù)雜度分別為O(1)和O(n)。
刪除算法的平均性能分析與插入算法相似。在長度為n的線性表中刪除一個結(jié)點(diǎn)，令Ede(n)表示所需移動結(jié)點(diǎn)的平均次數(shù)，刪除表中第i個結(jié)點(diǎn)的移動次數(shù)為n-i，故
式子中，pi表示刪除表中第i個結(jié)點(diǎn)的概率。在等概率的假設(shè)下，
p1=p2=p3=…=pn=1/n
由此可得：
即在順序表上做刪除運(yùn)算，平均要移動表中約一半的結(jié)點(diǎn)，平均時間復(fù)雜度也是O(n)。
1.4 棧和隊(duì)列
考點(diǎn)10 棧及其基本運(yùn)算
1什么是棧
棧實(shí)際也是線性表，只不過是一種特殊的線性表。棧(Stack)是只能在表的一端進(jìn)行插入和刪除運(yùn)算配線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧(棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。
假設(shè)棧S=(al，a2，a3，…，an)，則a1，稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，…，an的次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為先進(jìn)后出表(FILO，F(xiàn)irst In Last Out)，或“后進(jìn)先出”表(LIFO，Last In First Out)，如圖1-7所示。
2棧的順序存儲及其運(yùn)算
(l)入棧運(yùn)算：入棧運(yùn)算是指在棧頂位置插入一個新元素。首先將棧頂指針加一(即top加1)，然后將元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明?？臻g已滿，不可能再進(jìn)行入棧操作。這種情況稱為棧“上溢”錯誤。如圖1-8所示。
(2)退棧運(yùn)算：退棧是指取出棧頂元素并賦給一個指定的變量。首先將棧頂元素(棧頂指針指向的元素)賦給一個指定的變量，然后將棧頂指針減一(即t叩減1)。當(dāng)棧頂指針為。時，說明?？?，不可進(jìn)行退棧操作。這種情況稱為棧的“下溢”錯誤。 (3)讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變量。這個運(yùn)算不刪除棧頂元素，只是將它賦給一個變量，因此棧頂指針不會改變。當(dāng)棧頂指針為0時，說明?？?，讀不到棧頂元素。
考點(diǎn)11 隊(duì)列及其基本運(yùn)算
1什么是隊(duì)列
隊(duì)列(queue)是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)，
當(dāng)隊(duì)列中沒有元素時稱為空隊(duì)列。在空隊(duì)列中依次加入元素a1，a2，…，an之后，a1是隊(duì)頭元素，an是隊(duì)尾元素。顯然退出隊(duì)列的次序也只能是a1，a2，…，an也就是說隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。因此隊(duì)列亦稱作先進(jìn)先出(FIFO，F(xiàn)irst In First Out)的線性表，或后進(jìn)后出(LILO，Last In Last Out)的線性表。往隊(duì)列隊(duì)尾插入一個元素稱為入隊(duì)運(yùn)算，從隊(duì)列的排頭刪除一個元素稱為退隊(duì)運(yùn)算，如圖1-10所示。
一個隊(duì)列幣。刪除個兒素后的隊(duì)列間插入元素E后的隊(duì)列
2循環(huán)隊(duì)列及其運(yùn)算
在實(shí)際應(yīng)用中，隊(duì)列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間
在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個位置。因此，從排頭指針front指向的后一個位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。
可以將向量空間想象為一個首尾相接的圓環(huán)，如圖1-12所示，并稱這種向量為循環(huán)向量，存儲在其中的隊(duì)列稱為循環(huán)隊(duì)列( Cireular Queue)。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時，頭尾指針仍要加1，朝前移動。只不過當(dāng)頭尾指針指向向量上界(Queuesize-l)時，其加1操作的結(jié)果是指向向量的下界0。
由于入隊(duì)時尾指針向前追趕頭指針，出隊(duì)時頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時頭尾指針均相等。因此，我們無法通過front=rear來判斷隊(duì)列“空”還是“滿”。
在實(shí)際使用循環(huán)隊(duì)列時，為了能區(qū)分隊(duì)列滿還是隊(duì)列空，通常還需增加一個標(biāo)志、，、值的定義如下：當(dāng)s=0時表示隊(duì)列空；當(dāng)s=1時表示隊(duì)列非空。
(l)入隊(duì)運(yùn)算
入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個新元素。首先將隊(duì)尾指針進(jìn)一(即rear=rear+1)，并當(dāng)rear=m+l時置rear=1；然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)循環(huán)隊(duì)列非空(s=l)且隊(duì)尾指針等于隊(duì)頭指針時，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，這種情況稱為“上溢”。
線性表的刪除運(yùn)算是指將表的第i(1≤i≤n)個結(jié)點(diǎn)刪除，使長度為n的線性表：
(a1，…，ai-1，ai，ai+1，…，an)
變成長度為n-l的線性表
(a1，…，ai-1，ai+1，…，an)
該算法的時間分析與插入算法相似，結(jié)點(diǎn)的移動次數(shù)也是由表長n和位置i決定。若i=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動結(jié)點(diǎn)；若i=1，則前移語句將循環(huán)執(zhí)行n一1次，需移動表中除開始結(jié)點(diǎn)外的所有結(jié)點(diǎn)。這兩種情況下算法的時間復(fù)雜度分別為O(1)和O(n)。
刪除算法的平均性能分析與插入算法相似。在長度為n的線性表中刪除一個結(jié)點(diǎn)，令Ede(n)表示所需移動結(jié)點(diǎn)的平均次數(shù)，刪除表中第i個結(jié)點(diǎn)的移動次數(shù)為n-i，故
式子中，pi表示刪除表中第i個結(jié)點(diǎn)的概率。在等概率的假設(shè)下，
p1=p2=p3=…=pn=1/n
由此可得：
即在順序表上做刪除運(yùn)算，平均要移動表中約一半的結(jié)點(diǎn)，平均時間復(fù)雜度也是O(n)。
1.4 棧和隊(duì)列
考點(diǎn)10 棧及其基本運(yùn)算
1什么是棧
棧實(shí)際也是線性表，只不過是一種特殊的線性表。棧(Stack)是只能在表的一端進(jìn)行插入和刪除運(yùn)算配線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧(棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。
假設(shè)棧S=(al，a2，a3，…，an)，則a1，稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，…，an的次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為先進(jìn)后出表(FILO，F(xiàn)irst In Last Out)，或“后進(jìn)先出”表(LIFO，Last In First Out)，如圖1-7所示。
2棧的順序存儲及其運(yùn)算
(l)入棧運(yùn)算：入棧運(yùn)算是指在棧頂位置插入一個新元素。首先將棧頂指針加一(即top加1)，然后將元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明?？臻g已滿，不可能再進(jìn)行入棧操作。這種情況稱為棧“上溢”錯誤。如圖1-8所示。
(2)退棧運(yùn)算：退棧是指取出棧頂元素并賦給一個指定的變量。首先將棧頂元素(棧頂指針指向的元素)賦給一個指定的變量，然后將棧頂指針減一(即t叩減1)。當(dāng)棧頂指針為。時，說明?？?，不可進(jìn)行退棧操作。這種情況稱為棧的“下溢”錯誤。 (3)讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變量。這個運(yùn)算不刪除棧頂元素，只是將它賦給一個變量，因此棧頂指針不會改變。當(dāng)棧頂指針為0時，說明?？?，讀不到棧頂元素。
考點(diǎn)11 隊(duì)列及其基本運(yùn)算
1什么是隊(duì)列
隊(duì)列(queue)是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)，
當(dāng)隊(duì)列中沒有元素時稱為空隊(duì)列。在空隊(duì)列中依次加入元素a1，a2，…，an之后，a1是隊(duì)頭元素，an是隊(duì)尾元素。顯然退出隊(duì)列的次序也只能是a1，a2，…，an也就是說隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。因此隊(duì)列亦稱作先進(jìn)先出(FIFO，F(xiàn)irst In First Out)的線性表，或后進(jìn)后出(LILO，Last In Last Out)的線性表。往隊(duì)列隊(duì)尾插入一個元素稱為入隊(duì)運(yùn)算，從隊(duì)列的排頭刪除一個元素稱為退隊(duì)運(yùn)算，如圖1-10所示。
一個隊(duì)列幣。刪除個兒素后的隊(duì)列間插入元素E后的隊(duì)列
2循環(huán)隊(duì)列及其運(yùn)算
在實(shí)際應(yīng)用中，隊(duì)列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間
在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個位置。因此，從排頭指針front指向的后一個位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。
可以將向量空間想象為一個首尾相接的圓環(huán)，如圖1-12所示，并稱這種向量為循環(huán)向量，存儲在其中的隊(duì)列稱為循環(huán)隊(duì)列( Cireular Queue)。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時，頭尾指針仍要加1，朝前移動。只不過當(dāng)頭尾指針指向向量上界(Queuesize-l)時，其加1操作的結(jié)果是指向向量的下界0。
由于入隊(duì)時尾指針向前追趕頭指針，出隊(duì)時頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時頭尾指針均相等。因此，我們無法通過front=rear來判斷隊(duì)列“空”還是“滿”。
在實(shí)際使用循環(huán)隊(duì)列時，為了能區(qū)分隊(duì)列滿還是隊(duì)列空，通常還需增加一個標(biāo)志、，、值的定義如下：當(dāng)s=0時表示隊(duì)列空；當(dāng)s=1時表示隊(duì)列非空。
(l)入隊(duì)運(yùn)算
入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個新元素。首先將隊(duì)尾指針進(jìn)一(即rear=rear+1)，并當(dāng)rear=m+l時置rear=1；然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)循環(huán)隊(duì)列非空(s=l)且隊(duì)尾指針等于隊(duì)頭指針時，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，這種情況稱為“上溢”。