點(diǎn)擊查看：2015年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)復(fù)習(xí)知識(shí)點(diǎn)匯總

　　順序表的刪除運(yùn)算

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

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

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

　　線性表的刪除運(yùn)算是指將表的第i(1≤i≤n)個(gè)結(jié)點(diǎn)刪去，使長(zhǎng)度為n的線性表

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

　　變成長(zhǎng)度為n-1的線性表

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

　　注意：

　　當(dāng)要?jiǎng)h除元素的位置i不在表長(zhǎng)范圍(即i<1或i>L->length)時(shí)，為非法位置，不能做正常的刪除操作

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

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

　　(3)具體算法描述

　　void DeleteList(SeqList *L,int i)

　　{//從L所指的順序表中刪除第i個(gè)結(jié)點(diǎn)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é)點(diǎn)前移

　　L->length--; //表長(zhǎng)減小

　　}

　　(4)算法分析

　　①結(jié)點(diǎn)的移動(dòng)次數(shù)由表長(zhǎng)n和位置i決定：

　　i=n時(shí)，結(jié)點(diǎn)的移動(dòng)次數(shù)為0，即為0(1)

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

　�、谝苿�(dòng)結(jié)點(diǎn)的平均次數(shù)EDE(n)

　　其中：

　　刪除表中第i個(gè)位置結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i

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

　　p1=p2=…=pn=1/n

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

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

　　相關(guān)推薦：

　　2015計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)精選選擇題專項(xiàng)練習(xí)

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

　　2015年9月計(jì)算機(jī)等級(jí)考試各科目考前必做試題