第2章線性表及其順序存儲(chǔ)-資料下載頁(yè)
2025-07-20 09:21本頁(yè)面
【正文】 …, ki1, ki+1, …, kn1} 刪除過(guò)程的圖示見(jiàn)下圖 ： k i k0 k1 k i1 k n1 k0 k1 k i1 k n1 k i+1 前移結(jié)束位置 前移開(kāi)始位置 刪除前 刪除后 k i+1 21 刪除操作的具體實(shí)現(xiàn)見(jiàn)算法 /?????????????????????????????????????????????????????/ /? 函數(shù)功能 :刪除順序表中第 position位置的結(jié)點(diǎn) ?/ /? 函數(shù)參數(shù) :指向 sequence_list型變量的指針變量 slt ?/ /? int型變量 position ?/ /? 函數(shù)返回值 :空 文件名 :,函數(shù)名 :dele() ?/ /?????????????????????????????????????????????????????/ void dele(sequence_list ?slt,int position) { int i。 if(sltsize==0) {printf(\n順序表是空的 !)。exit(1)。} if(position0||position=sltsize) {printf(\n指定的刪除位置不存在 !)。exit(1)。} for(i=position。isltsize1。i++) slta[i]=slta[i+1]。 sltsize。 } 算法 刪除順序表中第 position位置的結(jié)點(diǎn) 22 要?jiǎng)h除順序表中的第 i個(gè)結(jié)點(diǎn) ， 則需要稱動(dòng) （ ni1）個(gè)元素 ， 設(shè)刪除表中第 i個(gè)結(jié)點(diǎn)的概率為 qi， 且在表中每一個(gè)位置刪除的概率相等 ， 即： q0=q1=…=qn1=1/n 則在一個(gè)長(zhǎng)度為 n的順序表中刪除一個(gè)結(jié)點(diǎn)的平均移動(dòng)次數(shù)為： 212)1(1)1(1)1( 1010?????????? ?? ????nnnninninqninii在一個(gè)長(zhǎng)為 n的順序表中刪除一個(gè)元素平均需要移動(dòng)表中大約一半的元素。該算法的時(shí)間復(fù)雜度為 O（ n） 23 （ 1） void verge(sequence_list l) 將順序表 L就地轉(zhuǎn)置 ， 即借助于 O（ 1） 的輔助空間 。 （ 2） void sprit(sequence_lsit *l1,sequence_list *l2, sequence_list *l3) [略 ] 將有序順序表 L1分裂成兩個(gè)線性表 L2與 L3， L2由表中所奇數(shù)組成， L3由所有偶數(shù)組成。 順序表上的一些其它常見(jiàn)算法 （ 3） void merge(sequence_lsit *l1,sequence_list *l2, sequence_list *l3) 將有序順序表 L1與 L2合并成有序順序表 L3。 24 作業(yè) ? P33\ void reverse(Sequence_list *slt) ? void insert_order(Sequence_list *slt, datatype x) ?下次上課課前交
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1