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