數(shù)據(jù)結(jié)構(gòu)四川理工

1、 1.數(shù)據(jù)結(jié)構(gòu)基本概念 2. 數(shù)據(jù)元素、數(shù)據(jù)項、邏輯結(jié)構(gòu)、物理結(jié)構(gòu) 3.時間復(fù)雜度、空間復(fù)雜度、語句頻度等計算集合結(jié)構(gòu)：集合結(jié)構(gòu)： 僅同屬一個集合僅同屬一個集合線性結(jié)構(gòu)線性結(jié)構(gòu): 一對一（一對一（1:1) 樹樹 結(jié)結(jié) 構(gòu)構(gòu): 一對多（一對多（1:n) 圖圖 結(jié)結(jié) 構(gòu)構(gòu): 多對多多對多 (m:n)線線 性性邏輯結(jié)構(gòu)可細分為邏輯結(jié)構(gòu)可細分為4類：類：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它它與數(shù)據(jù)的存儲無關(guān)與數(shù)據(jù)的存儲無關(guān)，是，是獨立于計算機獨立于計算機的。的。解：解： 上述表達式可用圖形表示為：上述表達式可

2、用圖形表示為：b c a e f d此結(jié)構(gòu)為此結(jié)構(gòu)為線性線性的。的。例：例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。存儲結(jié)構(gòu)可分為存儲結(jié)構(gòu)可分為4大類：大類：例：例：復(fù)數(shù)復(fù)數(shù)3.02.3i 的兩種存儲方式：的兩種存儲方式：順序、鏈?zhǔn)?、索引、散列順序、鏈?zhǔn)?、索引、散?.303023.00300041503023.0030004152.3法法1：地址地址 內(nèi)容內(nèi)容法法2：地址地址 內(nèi)容內(nèi)容2字節(jié)字節(jié)數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)特別說明：如果無論算法規(guī)模怎樣變化，其執(zhí)行時間為一常數(shù)，則特別說明：如果無論算法規(guī)模

3、怎樣變化，其執(zhí)行時間為一常數(shù)，則該算法的時間復(fù)雜度為該算法的時間復(fù)雜度為o(1). 數(shù)據(jù)元素之間的關(guān)系是：數(shù)據(jù)元素之間的關(guān)系是： a ai-1i-1領(lǐng)先于領(lǐng)先于a ai i，a ai i領(lǐng)先于領(lǐng)先于a ai+1i+1。 稱稱a ai-1i-1是是a ai i的直接的直接前驅(qū)前驅(qū) 元素；元素；a ai+1i+1是是a ai i的直接的直接后繼后繼 元素。元素。 除除a a1 1外，每個元素有且僅有一個直接前驅(qū)元素，外，每個元素有且僅有一個直接前驅(qū)元素， 除除a an n外，每個元素有且僅有一個直接后繼元素。外，每個元素有且僅有一個直接后繼元素。 線性表中數(shù)據(jù)元素的個數(shù)線性表中數(shù)據(jù)元素的個數(shù)n(n

4、n(n=0)=0)稱為線性表的稱為線性表的長度長度， 當(dāng)當(dāng)n=0n=0時，稱為時，稱為空表空表。a1a2aian b b+k b+(i-1)k b+(n-1)k 特點：特點：存儲單元地址連續(xù)（需要一段連續(xù)空間）存儲單元地址連續(xù)（需要一段連續(xù)空間）邏輯上相鄰的數(shù)據(jù)元素其物理位置也相鄰邏輯上相鄰的數(shù)據(jù)元素其物理位置也相鄰存儲密度大（存儲密度大（100%100%）隨機存取隨機存取元素序號與存儲位置存在如下關(guān)系：元素序號與存儲位置存在如下關(guān)系：loc(ai) = loc(a1) + (i - 1) * d (1in) 線性表的線性表的順序存儲順序存儲指用指用一組地址連續(xù)的一組地址連續(xù)的存儲單元存儲單元

5、依次存儲線性表的數(shù)據(jù)元素。這稱為依次存儲線性表的數(shù)據(jù)元素。這稱為順序表順序表。算法思想算法思想： 進行合法性檢查，進行合法性檢查，1=1=i=n+1i=n+1； 判斷線性表是否已滿；判斷線性表是否已滿； 將第將第n n個至第個至第i i個元素逐一后移一個單元；個元素逐一后移一個單元； 在第在第i i個位置處插入新元素；個位置處插入新元素； 將表的長度加將表的長度加1 1。算法思想：算法思想： 進行合法性檢查，進行合法性檢查，i i是否滿足是否滿足1=1=i=ni=n； 判線性表是否已空，判線性表是否已空，l.lengthl.length=0=0； 將第將第i+1i+1至第至第n n個元素逐一向

6、前移一個位置；個元素逐一向前移一個位置； 將表的長度減將表的長度減1 1。思考：如果要刪除指定位置開始的思考：如果要刪除指定位置開始的m個元素，個元素，如何實現(xiàn)？如何實現(xiàn)？數(shù)據(jù)域數(shù)據(jù)域指針域指針域datanext（a）鏈表結(jié)點結(jié)構(gòu)示意圖鏈表結(jié)點結(jié)構(gòu)示意圖datapriornextdata（b）（c）nextdata（d）priorpk=1a1 a2 ai an head pk=i單鏈表查找示意圖單鏈表查找示意圖a1 a2 ai an head 找到，返回p指向的結(jié)點的數(shù)據(jù)。問題：問題：i n呢？(a1, a2, , ai-1, e, ai, ai+1, , an)在元素在元素ai之前插入一個新

7、元素之前插入一個新元素e單鏈表上的實現(xiàn)示意圖單鏈表上的實現(xiàn)示意圖a1 ai an l ai-1 ai+1 基本步驟：基本步驟： 找到第找到第i-1個元素所在結(jié)點；個元素所在結(jié)點； 申請一個新結(jié)點申請一個新結(jié)點s并填入并填入e值；值； 修改修改s的指針域指向的指針域指向p的下一結(jié)點；的下一結(jié)點；p e s思考：第思考：第步步是否可交換？是否可交換？headai-1ai+1anaia1基本步驟：基本步驟：(1) 定位指針定位指針p指向結(jié)點指向結(jié)點ai-1 ;pe s(2) 建立新結(jié)點建立新結(jié)點s并賦并賦e ;(3) 修改修改s的的next指針域指向指針域指向p下一結(jié)點：下一結(jié)點：s-next =

8、p-next;(5) 修改修改p的的next指針域指向指針域指向s結(jié)點：結(jié)點：p-next = s;(6) 修改修改s下一結(jié)點的下一結(jié)點的prior指針域指向指針域指向s：s-next-prior = s;(4) 修改修改s的的prior指針域指向指針域指向p結(jié)點：結(jié)點：s-prior = p;問題問題：修改指針的步驟是否可隨意？修改指針的步驟是否可隨意？不帶頭結(jié)點？不帶頭結(jié)點？headai-1ai+1anaia1基本步驟：基本步驟：(1) 定位指針定位指針p指向結(jié)點指向結(jié)點ai;p(2) 修改修改p的前一結(jié)點的的前一結(jié)點的next指針域指向指針域指向p下一結(jié)點：下一結(jié)點：p-prior-ne

9、xt = p-next;(3) 修改修改p的下一結(jié)點的的下一結(jié)點的prior指針域指向指針域指向p前一結(jié)點：前一結(jié)點：p -next -prior = p-prior;(4) 釋放結(jié)點釋放結(jié)點p。出隊列入隊列a1 a2 . an隊頭隊尾算法時間復(fù)雜度算法時間復(fù)雜度?o(n*m)，其中，其中n、m分別為主串和子串長度分別為主串和子串長度vloc(aloc(aijij)=loc(a)=loc(a1111)+(i-1)+(i-1)* *n+j-1n+j-1* *d d對稱矩陣對稱矩陣數(shù)組數(shù)組bai,jan,na1,1a2,1a2,2a3,11234km下標(biāo)下標(biāo)a1,1 a1,2 a1,na2,1 a

10、2,2 a2,n ai,j an,1 an,2 an,na1,1a2,1 a2,2 ai,j an,1 an,2 an,n k = ? m = ?結(jié)論：一棵樹的各結(jié)點的度之和，等于該樹的分支數(shù)目。結(jié)論：一棵樹的各結(jié)點的度之和，等于該樹的分支數(shù)目。重點說明：對于前4個性質(zhì)，要求能推廣到多叉樹。dlr根結(jié)點根結(jié)點根的根的左子樹左子樹根的根的右子樹右子樹 lchild ltag data rtag rchild 若結(jié)點有左子樹，則左鏈域若結(jié)點有左子樹，則左鏈域lchildlchild指示其左孩子指示其左孩子（ltag=0ltag=0）；否則，令左鏈域指示其前驅(qū)（）；否則，令左鏈域指示其前驅(qū)（ltag

11、=1ltag=1）；）； 若結(jié)點有右子樹，則右鏈域若結(jié)點有右子樹，則右鏈域rchildrchild指示其右孩子指示其右孩子（rtag=0rtag=0）；否則，令右鏈域指示其后繼（）；否則，令右鏈域指示其后繼（rtag=1rtag=1）；）；a ac cb bd d a a b b c c d d=i i i i j j k k l l=j jk kl li ic cb bh hg gf fe ed dk kl lm mbdfcklmeghi結(jié)論：從根開始，沿右指針前進，結(jié)結(jié)論：從根開始，沿右指針前進，結(jié)點個數(shù)對應(yīng)原森林中樹的數(shù)目。點個數(shù)對應(yīng)原森林中樹的數(shù)目。赫夫曼編碼赫夫曼編碼abcdefgh

12、0.050.290.070.080.140.230.030.11agcdhefb最優(yōu)二叉樹01000000111111a: 0010b: 11c: 1010d: 1011e: 100f: 01 g: 0011h: 000abcdefgh設(shè)圖設(shè)圖g=（v，e）有）有n個頂點，則個頂點，則g的鄰接矩陣定義為的鄰接矩陣定義為n階方陣階方陣a。其中：其中：ai，j= 1 若（若（ vivi，vjvj）或）或 vievje，i ij j 0 其它其它 0 1 1 0 a1 0 0 0 0 0 0 0 1 1 0 0 0g2 0 1 0 1 0 a2 1 0 1 0 1 0 1 0 1 1 1 0 1 0

13、 0 0 1 1 0 0g1 td(vi)=od(vi)+id(vi) n n = ai,j+ai,j+aj,iaj,i j j= =1 j=11 j=1 n n td(vi)=ai,j=ai,j=aj,iaj,i j j=1 =1 j j=1=1 2534154353341221212345g2 234143121234深到底深到底回退回退深到底深到底v1v2v4v8v5（v2v8均已訪問）均已訪問）深到底深到底v3v6v7回退回退訪問訪問v1v2v3v4v5v6v7v8初始化：第1步：第2步：第3步：第4步：2第5步：頂點加入序列：v1，v3，v6，v4，v2，v5頂點逐個加入頂點逐個加入

14、2112345查找結(jié)果查找結(jié)果:靜態(tài)查找表靜態(tài)查找表動態(tài)查找表動態(tài)查找表有序表的查找有序表的查找查找表中記錄按關(guān)鍵字有序排列的表查找表中記錄按關(guān)鍵字有序排列的表. 即即: st.elemi.key=st.elemi+1.key i=1,2,n-1要求要求: 查找表為有序表查找表為有序表;查找過程查找過程: 先確定待查記錄范圍先確定待查記錄范圍; 然后逐步縮小范圍然后逐步縮小范圍; 直到直到: 查找成功或不成功查找成功或不成功.折半查找算法折半查找算法 int search_bin(sstable st,keytype key); low=1; high=st.length; while( lo

15、w=high) mid=(low+high)/ 2; if(eq( key,st.elemmid.key)return mid; else if(lt(key,st.elemmid.key) high=mid-1; else low=mid+1; return 0;/search_bin折半查找算法（遞歸實現(xiàn)）折半查找算法（遞歸實現(xiàn)） int search_bin(sstable st,int low,int high,keytype key); if( low=high) mid=(low+high)/ 2; if(eq( key,st.elemmid.key)return mid; els

16、e if(lt(key,st.elemmid.key) return search_bin(st,low,mid-1,key) ; else return search_bin(st, mid+1,high,key) ; else return 0;/search_bin 6855198420231011 0 1 2 3 4 5 6 7 8 9101112681920231114hash表表012755107984溢出表溢出表順序查找順序查找初始關(guān)鍵字：初始關(guān)鍵字： 4949，3838，6565，9797，7676，1313，2727，4949 pivot key 4949jji1 1次交換后：次交換后： 2727，3838，6565，9797，7676，1313， ，4949 iji2 2次交換后：次交換后：2727，3838， ，9797，7676，1313，6565，4949 ijj3 3次交換后：次交換后：2727，3838，1313，9797，7676， ，6565，4949 iji4 4次交換后：次交換后：2727，3838，1313， ，7676，9797，6565，4949 jij一趟完成后：一趟完成后：2727，3838，1313，4