[院校資料]第二章-線(xiàn)性表-展示頁(yè)
2024-10-25 23:56本頁(yè)面
【正文】 ? ListEmpty(L) ? 初始條件 :線(xiàn)性表 L已經(jīng)存在 。L) ? 初始條件 :線(xiàn)性表 L已經(jīng)存在 。 ? 操作結(jié)果 :銷(xiāo)毀線(xiàn)性表 L。 ? DestroyList(amp。 ?… } ADT List ? InitList(amp。L,i,amp。L,i,e)。L)。L)。第二章 線(xiàn)性表 陳羽中 線(xiàn)性表 ? 線(xiàn)性表的類(lèi)型定義 ? 線(xiàn)性表的順序表示與實(shí)現(xiàn) ? 線(xiàn)性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) ? 線(xiàn)性鏈表 ? 循環(huán)鏈表 ? 雙向鏈表 線(xiàn)性表 ? 線(xiàn)性結(jié)構(gòu)的特點(diǎn) ? 存在唯一的”第一個(gè)”數(shù)據(jù)元素 ? 存在唯一的”最后一個(gè)”數(shù)據(jù)元素 ? 除第一個(gè)外 ,每個(gè)數(shù)據(jù)元素均有且只有一個(gè)前驅(qū)元素 ? 除最后一個(gè)外 ,每個(gè)數(shù)據(jù)元素均有且只有一個(gè)后繼元素。 線(xiàn)性表的類(lèi)型定義 ? 線(xiàn)性表舉例 : ? 字母表 (A,B,C,…,X,Y,Z) ? 數(shù)據(jù)序列 (6,17,28,50,92,188) ? n個(gè)元素的線(xiàn)性表 : ? (a1, a2 ,…, ai, ai+1, …, an) 第一個(gè)元素 (沒(méi)有前驅(qū) ) 第 i個(gè)元素 (有唯一的前驅(qū) 和唯一的后繼 ) 最后一個(gè)元素 (沒(méi)有后繼 ) 線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型 (ADT) ADT List{ ? 數(shù)據(jù)對(duì)象 D={ai|a屬于 Elemset,(i=1,2,…,n, n≥0)} ? 數(shù)據(jù)關(guān)系 R1={＜ ai1,ai＞ |ai1,ai屬于 D,(i=2,3,…,n)} ? 基本操作： ?InitList(amp。 ?DestroyList(amp。 ?ListInsert(amp。 ?ListDelete(amp。e)。L) ? 操作結(jié)果 :構(gòu)造一個(gè)空的線(xiàn)性表 L。L) ? 初始條件 :線(xiàn)性表 L已經(jīng)存在 。 ? ClearList(amp。 ? 操作結(jié)果 :將線(xiàn)性表 L重置為空表 。 ? 操作結(jié)果 :若線(xiàn)性表 L為空表 ， 則返回 TURE。 基本操作 (一 ) 基本操作 (二 ) ? ListLength(L) ? 初始條件 :線(xiàn)性表 L已經(jīng)存在 。e) ? 初始條件 :線(xiàn)性表 L已經(jīng)存在 ,1=i=ListLength(L)。 ? LocateElem(L,e,pare()) ? 初始條件 :線(xiàn)性表 L已經(jīng)存在 ,pare()是數(shù)據(jù)元素判定函數(shù)。若這樣的數(shù)據(jù)元素不存在則返回值為 0。pre_e) ? 初始條件 : 線(xiàn)性表 L已經(jīng)存在 。 pre_e無(wú)意義 。next_e) ? 初始條件 : 線(xiàn)性表 L已經(jīng)存在。 基本操作 (三 ) ? ListInsert(amp。 ? 操作結(jié)果 : 在 L的第 i個(gè)位置之前插入新的數(shù)據(jù)元素 e,L的長(zhǎng)度加一。L,i,amp。 ? 操作結(jié)果 : 刪除 L的第 i個(gè)數(shù)據(jù)元素 ,并用 e返回其值 , L的長(zhǎng)度減一。L, visited()) ? 初始條件 :線(xiàn)性表已經(jīng)存在 ? 操作結(jié)果：依次對(duì) L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit() 線(xiàn)性表的合并 例 1 線(xiàn)性表的合并 , La = La∪ Lb void union(List amp。 Lb_len = ListLength(Lb)。 i=Lb_len。 if(!LocateElem(La,e,equal)) ListInsert(La,++La_len,e)。 例 2 非遞減線(xiàn)性表 La,Lb的合并 例 2：已知非遞減線(xiàn)性表 La,Lb,將所有 La和 Lb中的數(shù)據(jù)元素歸并到 Lc中 , 使 Lc 的數(shù)據(jù)元素也是非遞減的 . 如： La=3,5,8,11),Lb=(2,6,8,9,11,15,20) 合并結(jié)果 :Lc=(2,3,5,6,8,8,9,11,11,15,20) void MergeList(List La, List Lb, List amp。 InitList(amp。 i=j=1。 La_len = ListLength(La)。 While ((i=La_len)amp。(j=Lb_len)){ GetElem(La,i,a)。 if(a=b){ ListInsert(Lc, ++k,a)。 } else { ListInsert(Lc, ++k, b)。} } } 例 2 代碼 例 2 代碼 (續(xù) ) while (i=La_len) { GetElem(La,i++,a)。 } while (j=Lb_len) { GetElem(Lb,j++,b)。 } 例 3 例 3:試寫(xiě)一算法 ,清除表中重復(fù)的元素 . 如 :表中元素為 :a b a c d b a b d,則執(zhí)行完該算法后，表中的元素為 a c d void ListPurge ( LIST L) void ListPurge( LIST L ){ int i,j。 while( i = ListLength(L)){ j=i+1。 while( j= ListLength(L){ GetElem(L,j,y)。 else j=j+1。 } } ? 線(xiàn)性表 (a1,a2,…,ai,ai+1,…,an)的順序表示 :用一組地址連續(xù)的存貯單元依次存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素 ? Loc(ai+1) = Loc(ai)+ι ? Loc(ai) = Loc(a1)+(i1)*ι ? 設(shè) ι為每個(gè)數(shù)據(jù)元素所需的存儲(chǔ)大小 線(xiàn)性表的順序表示與實(shí)現(xiàn) (物理結(jié)構(gòu) ) 線(xiàn)性表的順序表示 存儲(chǔ)地址 內(nèi)存狀態(tài) 位序b a1 1b+ ι a2 2…… ……b+(i1)* ι ai i……b+(n1)* ι an nb: 為 a1數(shù)據(jù)元素的存儲(chǔ)地址 ι:為每個(gè)數(shù)據(jù)元素所需的存儲(chǔ)大小 typedef struct { ElemType*elem。 int listsize。 Status InitList_Sq(SqList amp。 if (!) return(OVERFLOW)。 =LIST_INIT_SIZE。 } Status ListInsert_Sq(Sqlistamp。 if(i1 || i+1) return ERROR。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1