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