線性表順序表鏈表順序表與鏈表的比較-展示頁(yè)
2024-10-29 11:38本頁(yè)面
【正文】 57 50 16 48 09 63 ?? 1 2 3 4 5 6 7 8 data 將 ai+1~an依次前移 正序移到 i~n1 長(zhǎng)度減１ i?1 且 i?n 1 2 3 4 5 6 7 8 data 25 34 57 50 刪除 x 16 48 09 63 ?? ? 線性表中元素的刪除 bool ListDelete ( SqList *amp。 Llength++。 j ) Ldata[j] = Ldata[j 1]。 for ( j = Llength。L, int i, Elemtype e ) { //在表中第 i 個(gè)位置插入新元素 x if (i 1|| i Llength +1|| Llength == MaxSize) return false。 else return i+1。 Ldata[i] != e ) i++。 while ( i Llength amp。 return true。 i Llength) return false。 } ? 提取 函數(shù)：在表中提取第 i 個(gè)元素的值 bool GetElem ( SqList *L, int i, ElemType e ) { if ( i 1 amp。 return(L)。L) { L= ( SqList * ) malloc( sizeof(SqList) )。 //終端結(jié)點(diǎn)在數(shù)組的位置 } SqList。 ? 可利用 一維數(shù)組 描述 存儲(chǔ)結(jié)構(gòu) a1 a2 a3 a4 a5 a6 1 2 3 4 5 6 data 順序表的連續(xù)存儲(chǔ)方式 c c c c c c c c c c LOC(ai) = LOC(a1)+(i1)*c LOC(ai) = LOC(ai1)+c, i 0 a, i = 1 a+(i1)*c a1 a2 a3 ai an 1 2 3 4 i n maxsize a 順序表 (SeqList)的定義 define MaxSize 10 //最大允許長(zhǎng)度 typedef struct { Elemtype data[MaxSize+1]。 不同的存儲(chǔ)方式，基本運(yùn)算的實(shí)現(xiàn)效益 也不同 167。 } } 在這些基本運(yùn)算的基礎(chǔ)上， 可以解決更復(fù)雜的問(wèn)題。i++) { GetElem(LB,i,e)。 for(i=1。 ListInsert(LC,i,e)。i=ListLength(LA )。LC) { InitList(LC)。 LA=（ 3， 6， 9， 2， 8） LB=（ 10， 3， 4， 9， 11） 首先將 LA中個(gè)元素放入 LC中， 依次處理 LB中每一個(gè)元素 bi ,i=1,2,3,…., 檢查 LA中是否存在 bi， 若無(wú)，則將 bi插入到 LC中。 } i++。 if (ex!=ey) j++。 j=i+1。 } 抽象數(shù)據(jù)類型線性表的定義 例：清除線性表 L中多余的重復(fù)元素 L=（ 2， 10， 2， 6， 9， 2， 6） 依次處理 ai i=1,2,3….. 掃描其后所有元素 aj j=i+1,i+2,….. ai=aj ai≠aj j=j+1 掃描下一個(gè) 刪除 aj ?j=j+1 Purge(List L) { i=1。L,i,amp。L,i,e)。 LocateElem(L,e)。 GetElem(L,i,amp。 ListEmpty(L)。 DestroyList(amp。 a1 a2 a3 a4 a5 a6 線 性 結(jié) 構(gòu) ADT List { 數(shù)據(jù)對(duì)象 : D={ai|1?i ? n, n ? 0, ai屬 Elemtype類型 數(shù)據(jù)關(guān)系 : R1={ ai ,ai+1 | ai ,ai+1 ?D, i=1,2, … ,n1} 基本運(yùn)算 : InitList(amp。 線性表的基本概念 線性表的邏輯結(jié)構(gòu) ? 除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè) 直接前驅(qū) 。? 線性表 ? 順序表 ? 鏈表 ? 順序表與鏈表的比較 ? 線性表 (Linear List) ? 定義 n（ ? 0） 個(gè)數(shù)據(jù)元素的有限序列，記作 L=（ a1, a2, …, an） ai 是表中數(shù)據(jù)元素， n 是表長(zhǎng)度。 n=0 是為空表 167。 ? 除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè) 直接后繼 。L)。L)。 ListLength(L): DispList(L)。e)。 ListInsert(amp。 ListDelete(amp。e)。 while(iListLength(L)) { GetElem(L, i, ex)。 while(j=ListLength(L) ) { GetElem(L, j, ey)。 else ListDelete(L, j, ey)。 } } 例：利用兩個(gè)線性表 LA和 LB分別表示 兩個(gè)集合 A和 B，求集合 C=AUB, 即將兩個(gè)集合的并集放在 LC中。 UnionList(List LA, List LB, List amp。 for (i=1。i++) { GetElem(LA,i,e)。 } lena=ListLenth(LA)。i= ListLength(LB )。 if(！ LocateElem(LA,e)) ListInsert(LC, ++lena, e )。 基本運(yùn)算的實(shí)現(xiàn)完全取決于存儲(chǔ)結(jié)構(gòu)。 線性表的順序存儲(chǔ)結(jié)構(gòu) ? 順序表 (Sequential List) ： 即把線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1