【正文】 2022年 1月 4日星期二 第 1頁(yè) 線性表 2022年 1月 4日星期二 第 2頁(yè) 【 學(xué)習(xí)目標(biāo) 】 1. 了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類(lèi)不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱(chēng)為順序表，用后者表示的線性表簡(jiǎn)稱(chēng)為鏈表。 2. 熟練掌握這兩類(lèi)存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。 3. 能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。 4. 結(jié)合線性表類(lèi)型的定義增強(qiáng)對(duì)抽象數(shù)據(jù)類(lèi)型的理解。 2022年 1月 4日星期二 第 3頁(yè) 【 重點(diǎn)和難點(diǎn) 】 鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針 p 和結(jié)點(diǎn) *p 之間的對(duì)應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的不同所指以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。 【 知識(shí)點(diǎn) 】 線性表、順序表、鏈表、有序表 2022年 1月 4日星期二 第 4頁(yè) 線性結(jié)構(gòu)的 基本特征 為 : 1．集合中必存在唯一的一個(gè) “第一元素” ； 2．集合中必存在唯一的一個(gè) “最后元素” ； 3．除最后元素在外，均有 唯一的后繼 ； 4．除第一元素之外，均有 唯一的前驅(qū) 。 線性結(jié)構(gòu) 是 一個(gè)數(shù)據(jù)元素的 有序（次序）集 線性表 是一種最簡(jiǎn)單的 線性結(jié)構(gòu) 2022年 1月 4日星期二 第 5頁(yè) 1 線性表的類(lèi)型定義 3 線性表類(lèi)型的實(shí)現(xiàn) ? 鏈?zhǔn)接诚? 4 一元多項(xiàng)式的表示 2 線性表類(lèi)型的實(shí)現(xiàn) ? 順序映象 2022年 1月 4日星期二 第 6頁(yè) 線性表的類(lèi)型定義 2022年 1月 4日星期二 第 7頁(yè) ? 定義：一個(gè)線性表是具有相同類(lèi)型的 n（ n≧ 0）個(gè)數(shù)據(jù)元素的有限序列， 通常記為： ? ?ni aaaaa i ???? 11 i,21 a, ??例 英文字母表（ A,B,C,…..Z) 例 學(xué)號(hào) 姓名 年齡 001 張三 18 002 李四 19 …… …… …… 數(shù)據(jù)元素 ? 特征： ? i為元素的序號(hào) ? 元素個(gè)數(shù) n—表長(zhǎng)度， n=0空表 ? 1in時(shí) –ai的直接 前驅(qū) 是 ai1， a1無(wú)直接前驅(qū) –ai的直接 后繼 是 ai+1， an無(wú)直接后繼 1 線性表的定義 2022年 1月 4日星期二 第 8頁(yè) 數(shù)據(jù)對(duì)象 ： D＝ { ai | ai ∈ D0, i=1,2,...,n, n≥0 } {稱(chēng) n 為線性表的 表長(zhǎng) 。 稱(chēng) n=0 時(shí)的線性表為 空表 。 } 數(shù)據(jù)關(guān)系 ： R＝ { ai1 ,ai |ai1 ,ai∈ D, i=2,...,n } {設(shè)線性表為 (a1， a2, . . . ， ai， . . . ， an), 稱(chēng) i 為 ai 在線性表中的 位序 。 } 2022年 1月 4日星期二 線性表的基本運(yùn)算 ?置空表 setnull(L)：將線性表 L置為空表 。 ?求長(zhǎng)度 length(L)：計(jì)算線性表 L中數(shù)據(jù)元素的個(gè)數(shù) 。 ?取元素 get(L,i)：取出線性表 L中第 i個(gè)數(shù)據(jù)元素；要求i≤length(L)。 ?取前趨 prior(L,x)：取出線性表 L中值為 x的元素的前趨元素；要求 x的位序大于 1。 ?取后繼 next(L,x)：取出線性表 L中值為 x的元素的后繼元素；要求 x的位序小于 length(L)。 ?定位序 locate(L,x)：確定元素 x在線性表 L中的位置 ，并給出位置序號(hào)；若 L中無(wú) x返回 0。 2022年 1月 4日星期二 線性表的基本運(yùn)算（續(xù)） ?插入 insert(L,x,i)：在線性表 L中第 i個(gè)位置上插入值為 x的新元素 ， 使表長(zhǎng)增 1；要求 1≤i≤length(L)+1。 ?刪除 delete(L,i)：刪除線性表 L中的第 i個(gè)元素 ， 使表長(zhǎng)減 1；要求 1≤i≤length(L)。 2022年 1月 4日星期二 第 11頁(yè) 利用上述定義的 線性表 可以實(shí)現(xiàn)其它更復(fù)雜的操作 例 22 例 21 2022年 1月 4日星期二 第 12頁(yè) 求兩個(gè)集合的并，即 A=A∪ B 例 21 2022年 1月 4日星期二 第 13頁(yè) 要求對(duì)線性表作如下操作： 擴(kuò)大線性表 LA，將 存在于線性表LB 中 而 不存在于線性表 LA 中 的數(shù)據(jù)元素 插入到線性表 LA 中 去。 上述問(wèn)題可演繹為： 2022年 1月 4日星期二 第 14頁(yè) 1． 從線性表 LB中依次察看每個(gè)數(shù)據(jù)元素 。 2． 依值在線性表 LA中進(jìn)行查訪 。 3． 若不存在，則插入之。 get (LB, i)→ e locate (LA, e) insert(LA, n+1, e) 操作步驟： 2022年 1月 4日星期二 第 15頁(yè) e =get(Lb, i)。 // 取 Lb中第 i個(gè)數(shù)據(jù)元素賦給 e if (!locate (La, e) ) insert(La, ++La_len, e)。 // La中不存在和 e 相同的數(shù)據(jù)元素，則插入之 void union(La, Lb) { La_len = length(La)。 // 求線性表的長(zhǎng)度 Lb_len = length(Lb)。 for (i = 1。 i = Lb_len。 i++) { } } // union 2022年 1月 4日星期二 第 16頁(yè) 已知 一個(gè) 非純集合 B，試 構(gòu)造 一個(gè)純集合 A， 使 A中只包含 B 中所有值各不相 同的數(shù)據(jù)元素 。 仍選用 線性表 表示集合。 例 22 2022年 1月 4日星期二 第 17頁(yè) 集合 B 集合 A 從集合 B 取出物件放入集合 A 要求集合 A中 同樣物件不能有兩件以上 因此， 算法的策略應(yīng)該和例 21相同 2022年 1月 4日星期二 第 18頁(yè) void union(List amp。La, List Lb) { La_len=length(La)。 Lb_len=length(Lb)。 } // union e=get(Lb, i)。 // 取 Lb中第 i 個(gè)數(shù)據(jù)元素賦給 e if (!locate(La, e) ) insert(La, ++La_len, e)。 // La中不存在和 e 相同的數(shù)據(jù)元素，則插入之 for (i = 1。 i = Lb_len。 i++) { } setnull(La)。 // 構(gòu)造 (空的 )線性表 LA 2022年 1月 4日星期二 第 19頁(yè) 若線性表中的數(shù)據(jù)元素相互之間可以 比較 ，并且數(shù)據(jù)元素在線性表中 依值非遞減或非遞增有序 排列，即 ai≥a i1 或 ai≤a i1(i = 2,3,… , n)，則稱(chēng)該線性表為 有序表 (Ordered List)。 我們?cè)賮?lái)看看 有序表 表示的集合。 2022年 1月 4日星期二 第 20頁(yè) 例如 ： LA=(3,5,8,11) LB=(2,6,8,9,11,15,20) 對(duì)集合 LA和 LB 而言， 值相同的數(shù)據(jù)元素必定相鄰。 要求生成一個(gè)新表 LC，使 LC中的數(shù)據(jù)元素仍按值非遞減有有序排列。 2022年 1月 4日星期二 第 21頁(yè) void MergeList(List La, List Lb, List amp。Lc) { // 本算法將非遞減的有序表 La 和 Lb 歸并為 Lc } // merge_list while ((i = La_len) amp。amp。 (j = Lb_len)) { // La 和 Lb 均不空 } while (i=La_len) // 若 La 不空 while (j=Lb_len) // 若 Lb 不空 setnull(Lc)。 // 構(gòu)造空的線性表 Lc i = j = 1。 k = 0。 La_len = length(La)。 Lb_len = length(Lb)。 例 23 2022年 1月 4日星期二 第 22頁(yè) while (i = La_len) { // 當(dāng) La不空時(shí) ai= get(La, i++)。 insert(Lc, ++k, ai)。 } // 插入 La 表中剩余元素 while (j = Lb_len) { // 當(dāng) Lb不空時(shí) bj= get(Lb, j++)。 insert(Lc, ++k, bj)。 } // 插入 Lb 表中剩余元素 While( (i = La_len)amp。amp。 (j = Lb_len)) { // 當(dāng) La,Lb都不空時(shí) ai =get(La, i)。 bj= get(Lb, j)。 if(ai=bj){insert(Lc, ++k, ai)。++i。} else{insert(Lc, ++k, bj)。++j} } 2022年 1月 4日星期二 第 23頁(yè) 2022年 1月 4日星期二 第 24頁(yè) 用一組 地址連續(xù) 的存儲(chǔ)單元 依次存放 線性表中的數(shù)據(jù)元素 a1 a2 … ai1 ai … an 線性表的 起始地址 稱(chēng)作線性表的 基地址 2022年 1月 4日星期二 第 25頁(yè) ? 元素地址計(jì)算方法： –LOC(ai)=LOC(a1)+(i1)*d 1≦ i≦ n ? 特點(diǎn)： –邏輯上相鄰 —物理地址相鄰 –隨機(jī)存取 ? 實(shí)現(xiàn)： 可用 C語(yǔ)言的一維數(shù)組