[其它課程]c2-線性表一-資料下載頁
2025-10-09 22:36本頁面
【正文】 動一個位置； ? 將要插入的元素寫到第 i個位置； ? 表長加 1。 ?注意事先應判斷 : ?插入位置 i是否合法 ? ?表是否已滿 ? 30 線性表的順序表示和實現(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 線性表的順序表示和實現(xiàn) ?插入操作 算法時間復雜度 ? 這里的問題規(guī)模是表的長度 n。 ? 插入算法的時間主要花費在結點后移的語句上， 該語句的執(zhí)行次數(shù)為 ni次，與插入節(jié)點所在位置 i 有關。 ?由此可看出，所需移動結點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關。 ?長度為 n的表中插入元素需移動元素的平均次數(shù) Eis=n/2 ?ListInsert_Sq的時間復雜度為 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 刪除順序表中某個指定的元素的示意圖如下： 線性表的順序表示和實現(xiàn) 33 線性表的順序表示和實現(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 長度為 n的表中刪除元素需移動元素的平均次數(shù) Edl=(n1)/2 ListDelete_Sq的時間復雜度為 O(n) 34 本講總結 ?線性結構的特點有哪些？ ?順序存儲的優(yōu)點有哪些？ ?順序表中下標與相對地址的關系？ ?在對順序表進行插入操作中應注意什么？ 35 實驗 ?用 C語言實現(xiàn)本講的算法 36
教學課件相關推薦
鄂ICP備17016276號-1