[其它課程]c2-線性表一-資料下載頁(yè)
2025-10-09 22:36本頁(yè)面
【正文】 動(dòng)一個(gè)位置； ? 將要插入的元素寫到第 i個(gè)位置； ? 表長(zhǎng)加 1。 ?注意事先應(yīng)判斷 : ?插入位置 i是否合法 ? ?表是否已滿 ? 30 線性表的順序表示和實(shí)現(xiàn) ?算法 24 Status ListInsert_Sq(SqList *L， int i ， ElemType e){ if(i1||i+1) return ERROR。 if(=){ newbase=(ElemType *)realloc (, (+LISTINCREMENT)* sizeof(ElemType))。 If(! newbase) exit(OVERFLOW)。 = newbase。 +=LISTINCREMENT。 } q= amp。([i1])。 for(p= amp。([])。p=q。p) *(p+1)=*p。 *q=e。 ++。 return OK。 }//ListInsert_Sq 31 線性表的順序表示和實(shí)現(xiàn) ?插入操作 算法時(shí)間復(fù)雜度 ? 這里的問題規(guī)模是表的長(zhǎng)度 n。 ? 插入算法的時(shí)間主要花費(fèi)在結(jié)點(diǎn)后移的語(yǔ)句上， 該語(yǔ)句的執(zhí)行次數(shù)為 ni次，與插入節(jié)點(diǎn)所在位置 i 有關(guān)。 ?由此可看出，所需移動(dòng)結(jié)點(diǎn)的次數(shù)不僅依賴于表的長(zhǎng)度，而且還與插入位置有關(guān)。 ?長(zhǎng)度為 n的表中插入元素需移動(dòng)元素的平均次數(shù) Eis=n/2 ?ListInsert_Sq的時(shí)間復(fù)雜度為 O(n) 32 1 2 3 4 5 6 7 8 9 12 13 21 24 25 28 30 42 77 1 2 3 4 5 6 7 8 12 13 21 24 28 30 42 77 刪除順序表中某個(gè)指定的元素的示意圖如下： 線性表的順序表示和實(shí)現(xiàn) 33 線性表的順序表示和實(shí)現(xiàn) ?線性表的刪除操作 Status ListDelete_Sq(SqList *L， int i ， ElemType amp。 e) { if((i1)||(i)) return ERROR。 p= amp。 ([i1])。 e= *p。 q=+。 for(++p。p=q。++p) *(p1)= *p。 。 return OK。 }//ListDelete_Sq 長(zhǎng)度為 n的表中刪除元素需移動(dòng)元素的平均次數(shù) Edl=(n1)/2 ListDelete_Sq的時(shí)間復(fù)雜度為 O(n) 34 本講總結(jié) ?線性結(jié)構(gòu)的特點(diǎn)有哪些？ ?順序存儲(chǔ)的優(yōu)點(diǎn)有哪些？ ?順序表中下標(biāo)與相對(duì)地址的關(guān)系？ ?在對(duì)順序表進(jìn)行插入操作中應(yīng)注意什么？ 35 實(shí)驗(yàn) ?用 C語(yǔ)言實(shí)現(xiàn)本講的算法 36
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1