數(shù)據(jù)結(jié)構(gòu)課件線(xiàn)性表(已修改)
2025-08-02 21:19 本頁(yè)面
【正文】 第 2章 線(xiàn)性表 線(xiàn)性表的類(lèi)型定義 線(xiàn)性表的順序表示和實(shí)現(xiàn) 線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 一元多項(xiàng)式的表示及相加 線(xiàn)性表的類(lèi)型定義 ? 線(xiàn)性結(jié)構(gòu)的特點(diǎn)： 在數(shù)據(jù)元素的非空有限集中， 1）有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)； 2）有且僅有一個(gè)終端結(jié)點(diǎn)；3）除第一個(gè)結(jié)點(diǎn)外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)前驅(qū)； 4）除最后一個(gè)結(jié)點(diǎn)外，集合中的每個(gè)數(shù)據(jù)元素均有且只有一個(gè)后繼。 ? 線(xiàn)性序列：線(xiàn)性結(jié)構(gòu)中的所有結(jié)點(diǎn)按其關(guān)系可以排成一個(gè)序列，記為 (a1,…,ai,ai+1,…an) 線(xiàn)性表的類(lèi)型定義 1. 線(xiàn)性表 1）線(xiàn)性表是 n(n ≥0)個(gè)數(shù)據(jù)元素的有限序列。 2）線(xiàn)性表是一種最常用且最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。 含有 n個(gè)數(shù)據(jù)元素的線(xiàn)性表是一個(gè)數(shù)據(jù)結(jié)構(gòu)： List = (D,R) 其中： D = {ai | ai∈ D0,i=1,2,…n,n≥0} R = {N}, N = { ai1 , ai | ai1 , ai ∈ D0 , i = 2,3,…n} D0 為某個(gè)數(shù)據(jù)對(duì)象 ——數(shù)據(jù)的子集 ? 特性：均勻性，有序性（線(xiàn)性序列關(guān)系） 線(xiàn)性表的類(lèi)型定義 1. 線(xiàn)性表 3）線(xiàn)性表的長(zhǎng)度及空表 ? 線(xiàn)性表中數(shù)據(jù)元素的個(gè)數(shù) n（ n≥0）定義為線(xiàn)性表的長(zhǎng)度 ? 當(dāng)線(xiàn)性表的長(zhǎng)度為 0 時(shí)，稱(chēng)為空表。 ? ai 是第 i個(gè)數(shù)據(jù)元素，稱(chēng) i為 ai 在線(xiàn)性表中的位序。 2. 線(xiàn)性表的基本操作 p19~p20 1） InitList(amp。L) 初始化，構(gòu)造一個(gè)空的線(xiàn)性表 2） ListLength(L) 求長(zhǎng)度 ,返回線(xiàn)性表中數(shù)據(jù)元素個(gè)數(shù) 3） GetElem(L,i,amp。e) 取表 L中第 i個(gè)數(shù)據(jù)元素賦值給 e 4） LocateElem(L,e) 按值查找，若表中存在一個(gè)或多個(gè)值為 e的結(jié)點(diǎn)，返回第一個(gè)找到的數(shù)據(jù)元素的位序，否則返回一個(gè)特殊值。 5） ListInsert(amp。L,i,e) 在 L中第 i個(gè)位置前插入新的數(shù)據(jù)元素 e，表長(zhǎng)加 1。 6） ListDelete(amp。L,i,e) 刪除表中第 i個(gè)數(shù)據(jù)元素，e返回其值，表長(zhǎng)減 1。 線(xiàn)性表的基本操作舉例 ? 例 21 求 A = A ∪ B P20算法 ?時(shí)間復(fù)雜度： LocateElem()執(zhí)行次數(shù) O(ListLength(A)*ListLength(B)) ? 例 22 合并 LA 和 LB 到 LC中 P2021算法 ?時(shí)間復(fù)雜度： ListInsert()執(zhí)行次數(shù)O(ListLength(LA)+ListLength(LB)) 線(xiàn)性表的順序表示和實(shí)現(xiàn) — 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu) 1）在計(jì)算機(jī)內(nèi)存中用一組地址連續(xù)的存儲(chǔ)單元依次 存儲(chǔ)線(xiàn)性表中的各個(gè)數(shù)據(jù)元素。 2）假設(shè)線(xiàn)性表的每個(gè)元素需占用 L個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的起始存儲(chǔ)位置，則線(xiàn)性表中第 i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置Loc(ai+1)和第 i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置 Loc(ai)之間滿(mǎn)足下列關(guān)系： Loc(ai+1) = Loc(ai) + L 一般來(lái)說(shuō)，線(xiàn)性表的第 i個(gè)元素 ai的存儲(chǔ)位置為： Loc(ai) = Loc(a1) + (i1)*L 其中 Loc(a1)是線(xiàn)性表的第一個(gè)數(shù)據(jù)元素 a1的存儲(chǔ)位置，通常稱(chēng)作線(xiàn)性表的 起始位置 或 基地址 。 — 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu) 3）線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)示意圖 ——p22圖 ? 用“物理位置”相鄰來(lái)表示線(xiàn)性表中數(shù)據(jù)元素之間的邏輯關(guān)系。 ? 根據(jù)線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，只要確定了存儲(chǔ)線(xiàn)性表的起始位置，線(xiàn)性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以，線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種 隨機(jī)存取 的存儲(chǔ)結(jié)構(gòu)。 define LIST_MAX_LENTH 100/或者 N/或者是一 個(gè) 常數(shù) typedef struct ElemType { int *elem。 //存儲(chǔ)空間的基址 int length。 //當(dāng)前的長(zhǎng)度 } SqList。 SqList L。 ? C語(yǔ)言中 靜 態(tài)分配描述 p22 ?求置空表 Status ClearList( amp。L ) { L. length=0。 return OK。 } ? C語(yǔ)言中 靜 態(tài)分配描述 p22 ?求長(zhǎng)度 Status List length( SqList L ) { length= L. length。 return OK。 } ? C語(yǔ)言中 靜 態(tài)分配描述 p22 ?初始化 Status InitList_ SqList( SqList L ) { =(*int) malloc(LIST_MAX_LENGTH *sizeof(int) )。 if(!) exit(Overflow) 。 L. length=0。 return OK。 } ? C語(yǔ)言中 靜 態(tài)分配描述 p22 2. 順序表的描述 1) C語(yǔ)言中 動(dòng) 態(tài)分配描述 p22 define LIST_INIT_SIZE 100 define LISTINCREMENT 10 typedef struct { ElemType *elem。 int length。 int listsize。 }SqList。 SqList L。 ? 說(shuō)明： elem數(shù)組指針指向線(xiàn)性表的基地址； length指示線(xiàn)性表的當(dāng)前長(zhǎng)度； listsize指示順序表當(dāng)前分配的存儲(chǔ)空間大小。當(dāng)空間不足時(shí)，再分
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1