【文章內(nèi)容簡(jiǎn)介】 ? 時(shí)間與空間是一對(duì)矛盾。要節(jié)約空間往往就要消耗較多時(shí)間，反之亦然，而目前由于計(jì)算機(jī)硬件的發(fā)展，一般都有足夠的內(nèi)存空間，因此在分析中著重考慮時(shí)間的因素。 算法與分析技術(shù)初步 35 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 ? 理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、算法等基本概念。 ? 掌握頻度、時(shí)間復(fù)雜度的計(jì)算。 ? 了解空間復(fù)雜度。 小結(jié) 36 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 線 性 表 線性表的定義和運(yùn)算 順序存儲(chǔ)線性表 線性鏈表 向量和鏈表的比較 小結(jié) 作業(yè) 37 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 線性表的定義和運(yùn)算 1. 線性表的概念 2. 線性表的邏輯結(jié)構(gòu)是 n個(gè)數(shù)據(jù)元素的有限序列 : L=(a1, a2 ,...， an) L為線性表， ai(i=1,...， n)是屬于某數(shù)據(jù)對(duì) 象的元素， n為線性表的長(zhǎng)度 (n≥0) ， n=0的表稱為空表。 2. 線性表的定義 L=（ D， R） }2,{ 11 niDaaaaR iiii ?????? ??38 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 3. 線性表的結(jié)構(gòu)特點(diǎn) ? 表中的數(shù)據(jù)元素為同一數(shù)據(jù)類型 ? 數(shù)據(jù)元素之間是線性關(guān)系 ? 每個(gè)元素 有且只有一個(gè)前趨元素 (第一個(gè)元素除外 )，每個(gè)元素 有且只有一個(gè)后繼元素 (最后一個(gè)元素除外 ) 線性表的定義和運(yùn)算 39 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 4. 有序表與無(wú)序表的概念 若線性表中的數(shù)據(jù)元素相互之間可以比較，且ai≥ai+1 ， i=2， 3， ...， n（ 或 ai≤ai+1 ， i=1，2， ...， n1），則稱該線性表為 有序表 ，否則稱為 無(wú)序表 。 5. 線性表的基本運(yùn)算 插入、刪除、查找、排序等。 (按位置、按值 ) 線性表的定義和運(yùn)算 40 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 順序存儲(chǔ)線性表 （ 順序表 ） 一、順序存儲(chǔ)結(jié)構(gòu) ? 用一組地址連續(xù)的存儲(chǔ)單元存放線性表的數(shù)據(jù)元素（也稱為向量式存儲(chǔ)結(jié)構(gòu)） ? 該結(jié)構(gòu)用高級(jí)語(yǔ)言中的一維數(shù)組類型表示 。 例如：可用一維數(shù)組 A[n]來(lái)存儲(chǔ)線性表： （ a1, a2 ,...， an）。 ? 地址計(jì)算： addr(ai)=addr(a1)+(i1)*L ? 特點(diǎn)：隨機(jī)存儲(chǔ)結(jié)構(gòu) (查找方便 )。 41 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 例： a1 a2 a3 a4 a5 a6 … 2024H 2024H …… 2024H addr(a4) = addr(a1) + (i1) L = 2024H+(41) 1=2024H 順序存儲(chǔ)線性表 42 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 二、順序存儲(chǔ)結(jié)構(gòu)的插入與刪除 1)概念： 有線性表 (a1,a2 ,...， an)， 長(zhǎng)度為 n， 要在第i1與第 i個(gè)元素之間插入一個(gè)新元素。使得線性表變?yōu)椋?(a1,a2 ,... ai1,x, ai,...,an), 長(zhǎng)度為 n+1。 2)插入過(guò)程： 將 ai至 an依次后移一個(gè)位置 (共移動(dòng) ni+1個(gè)元素 )，然后將新元素插入在第 i個(gè)位置上 (合法位置：1=i=n+1)。 請(qǐng)參見(jiàn) 教材 27頁(yè)圖 23所示。 順序存儲(chǔ)線性表 43 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 3)算法描述 int InsertList(L[m],n,i,x) //形式參數(shù) { if (i1 || in+1) return(0)。 //位置非法 for (j=n。j=i。j) L[j+1]=L[j]。 //移動(dòng)元素 L[i]=x。 //插入元素 n++。 //長(zhǎng)度加 1 return(1)。 //執(zhí)行成功，返回 } 順序存儲(chǔ)線性表 44 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 2. 刪除 1）概念： 刪除第 i個(gè)位置上的元素，使線性表的長(zhǎng)度由 n變?yōu)?n1。 2）刪除過(guò)程： ai+1～ an依次前移一個(gè)位置 (共移動(dòng) ni個(gè)元素 ) 。 (合法位置： 1=i=n)參見(jiàn) 教材 27頁(yè)圖 24所示。 順序存儲(chǔ)線性表 45 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 3）算法描述 int DeleteList(L[m],n,i) { if (i1 || in) return(0)。 //參數(shù)不合法 for (j=i。j=n1。j++) L[j]=L[j+1]。 //前移 n。 //表長(zhǎng)減 1 return(1)。 } 順序存儲(chǔ)線性表 46 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 3. 運(yùn)算的時(shí)間分析 ? 在插入和刪除運(yùn)算中，時(shí)間主要消耗在移動(dòng)元素上。 ? 設(shè) pi－在第 i個(gè)元素前插入一個(gè)元素的概率，則在長(zhǎng)度為 n的線性表中插入一個(gè)元素所需的平均移動(dòng)次數(shù)為： 順序存儲(chǔ)線性表 47 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 在等概率情況下， pi=1/(n+1)， 則有： ? 同理，刪除時(shí)有： 在等概率情況下， qi=1/n， 則有： 問(wèn)題：順序表插入、刪除的時(shí)間復(fù)雜度？ O(n) 順序存儲(chǔ)線性表 48 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 ： ? 優(yōu)點(diǎn)：存儲(chǔ)效率高、查找方便。 ? 缺點(diǎn)： 1)插入刪除代價(jià)高 (插入或刪除一個(gè)元素，平均需要移動(dòng)表中一半的元素 ),僅適用于不經(jīng)常進(jìn)行插入和刪除運(yùn)算以及表中元素相對(duì)穩(wěn)定的場(chǎng)合 。 2)要求連續(xù)存儲(chǔ)區(qū)，管理不靈活，元素刪除后不能釋放空間。 順序存儲(chǔ)線性表 49 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 三、順序存儲(chǔ)結(jié)構(gòu)的應(yīng)用舉例 將兩個(gè)有序順序表 A（ 有 m個(gè)元素）和 B（ 有 n個(gè)元素），合并為一個(gè)有序線性表 C。 順序存儲(chǔ)線性表 50 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 解 ： LINK (A, m, B, n, C) { i=0。 j=0。 t=0。 k=0。 while (im jn) //掃描 A和 B， 將當(dāng)前較小者賦給 C { if (A[i] B[j]) C[k++]=A[i++]。 else if (A[i] B[j]) C[k++]=B[j++]。 else { C[k++]=B[j++]。 //相等者只保存一個(gè) i++。 } } if ( i= =m) //B未完，將 B余下的元素賦給 C for (t=j。 tn。 t++) C[k++]=B[t]。 if ( j= =n) //A未完，將 A余下的元素賦給 C for (t=i。 tm。 t++) C[k++]=A[t]。 return k。 } 順序存儲(chǔ)線性表 51 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 線性鏈表 一、問(wèn)題的提出 ? 順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn) 1）插入和刪除時(shí)需移動(dòng)大量的元素； 2） 要求存放元素的存儲(chǔ)單元連續(xù)； 3）有時(shí)會(huì)造成空間浪費(fèi)或溢出； 4）表的容量不易擴(kuò)充（個(gè)數(shù)固定）。 52 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 二、線性鏈表的邏輯結(jié)構(gòu) 1. 邏輯結(jié)構(gòu) a1 a2 a3 a4 ^ head ^ ? 每個(gè)結(jié)點(diǎn)有兩個(gè)字段： data－ 數(shù)據(jù)域，存放結(jié)點(diǎn)值 next－ 指針域，存放后繼結(jié)點(diǎn)的地址 data next ? 頭指針： head （ 指向鏈表的第一個(gè)結(jié)點(diǎn)） ? 鏈表可以為空： head NULL ?字段值的獲?。?data(a1) 。 next(a1) 。（ C語(yǔ)言： a1data。a1next。） 線性鏈表 53 合肥工業(yè)大學(xué) 計(jì)算機(jī)信息學(xué)院軟件所 二、線性鏈表的邏輯結(jié)構(gòu) 2. 線性鏈表的特點(diǎn) ? 存儲(chǔ)單元不要求連續(xù)，插入和刪除方便； ? 要求較多的存儲(chǔ)空間（存放指針域）。 a2 1008 data next data next a1 1002 data next a4 nil a3 1007 1000 1001 1002 1003 1004 100