點擊查看：2015年計算機二級公共基礎(chǔ)知識復(fù)習知識點匯總

　　順序表的刪除運算

　　在順序在存儲結(jié)構(gòu)的線性表中刪除一個元素。

　　注意：找到刪除的數(shù)據(jù)元素后，從該元素位置開始，將后面的元素一一向前移動，在移動完成后，線性表的長度減1

　　(1)刪除運算的邏輯描述

　　線性表的刪除運算是指將表的第i(1≤i≤n)個結(jié)點刪去，使長度為n的線性表

　　(a1，…，ai-1，ai，ai+1，…，an)

　　變成長度為n-1的線性表

　　(a1，…，ai-1，ai+1，…，an)

　　注意：

　　當要刪除元素的位置i不在表長范圍(即i<1或i>L->length)時，為非法位置，不能做正常的刪除操作

　　(2)順序表刪除操作過程

　　在順序表上實現(xiàn)刪除運算必須移動結(jié)點，才能反映出結(jié)點間的邏輯關(guān)系的變化。若i=n，則只要簡單地刪除終端結(jié)點，無須移動結(jié)點;若1≤i≤n-1，則必須將表中位置i+1，i+2，…，n的結(jié)點，依次前移到位置i，i+1，…，n-1上，以填補刪除操作造成的空缺。其刪除過程【參見動畫演示】

　　(3)具體算法描述

　　void DeleteList(SeqList *L,int i)

　　{//從L所指的順序表中刪除第i個結(jié)點ai

　　int j;

　　if(i<1||i>L->length)

　　Error("position error"); //非法位置

　　for(j=i;j<=L->length-1;j++)

　　L->data[j-1]=L->data[j]; //結(jié)點前移

　　L->length--; //表長減小

　　}

　　(4)算法分析

　�、俳Y(jié)點的移動次數(shù)由表長n和位置i決定：

　　i=n時，結(jié)點的移動次數(shù)為0，即為0(1)

　　i=1時，結(jié)點的移動次數(shù)為n-1，算法時間復(fù)雜度分別是0(n)

　　②移動結(jié)點的平均次數(shù)EDE(n)

　　其中：

　　刪除表中第i個位置結(jié)點的移動次數(shù)為n-i

　　pi表示刪除表中第i個位置上結(jié)點的概率。不失一般性，假設(shè)在表中任何合法位置(1≤i≤n)上的刪除結(jié)點的機會是均等的，則

　　p1=p2=…=pn=1/n

　　因此，在等概率插入的情況下，

　　順序表上做刪除運算，平均要移動表中約一半的結(jié)點，平均時間復(fù)雜度也是0(n)。

　　相關(guān)推薦：

　　2015計算機二級公共基礎(chǔ)知識精選選擇題專項練習

　　2015計算機二級《公共基礎(chǔ)知識》精選選擇題90道

　　2015年9月計算機等級考試各科目考前必做試題