第2章線性表及其順序存儲-資料下載頁
2025-07-20 09:21本頁面
【正文】 …, ki1, ki+1, …, kn1} 刪除過程的圖示見下圖 ： k i k0 k1 k i1 k n1 k0 k1 k i1 k n1 k i+1 前移結(jié)束位置 前移開始位置 刪除前 刪除后 k i+1 21 刪除操作的具體實現(xiàn)見算法 /?????????????????????????????????????????????????????/ /? 函數(shù)功能 :刪除順序表中第 position位置的結(jié)點 ?/ /? 函數(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é)點 22 要刪除順序表中的第 i個結(jié)點 ， 則需要稱動 （ ni1）個元素 ， 設(shè)刪除表中第 i個結(jié)點的概率為 qi， 且在表中每一個位置刪除的概率相等 ， 即： q0=q1=…=qn1=1/n 則在一個長度為 n的順序表中刪除一個結(jié)點的平均移動次數(shù)為： 212)1(1)1(1)1( 1010?????????? ?? ????nnnninninqninii在一個長為 n的順序表中刪除一個元素平均需要移動表中大約一半的元素。該算法的時間復(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分裂成兩個線性表 L2與 L3， L2由表中所奇數(shù)組成， L3由所有偶數(shù)組成。 順序表上的一些其它常見算法 （ 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號-1