03-常用數(shù)據(jù)結(jié)構(gòu)及其應用

1、1 江蘇大學電氣信息工程學院江蘇大學電氣信息工程學院 電子信息工程系電子信息工程系 登錄號： 書名： 作者名： 分類號： 出版單位： 出版時間： 價格： 書目卡片 按作者名按作者名 H BCD EFG A HGFE Loc(Loc(元素元素i)i) = Lo + = Lo +（i-1) i-1) * * m m 式中，式中，LoLo為第一個元素地為第一個元素地 址，址，m m為一個元素占用空間為一個元素占用空間 的大小。的大小。 順序存儲結(jié)構(gòu)即將數(shù)據(jù)結(jié)順序存儲結(jié)構(gòu)即將數(shù)據(jù)結(jié) 構(gòu)的數(shù)據(jù)元素存放在一組構(gòu)的數(shù)據(jù)元素存放在一組 地址連續(xù)的存儲單元中。地址連續(xù)的存儲單元中。 5、 線性表鏈式存儲結(jié)構(gòu)的描

2、述線性表鏈式存儲結(jié)構(gòu)的描述 在高級語言中，鏈式存儲結(jié)構(gòu)用在高級語言中，鏈式存儲結(jié)構(gòu)用 “ “結(jié)構(gòu)指針結(jié)構(gòu)指針”來來 描述，對于有些沒有結(jié)構(gòu)指針的高級語言，也就沒有描述，對于有些沒有結(jié)構(gòu)指針的高級語言，也就沒有 相應的鏈式結(jié)構(gòu)了。相應的鏈式結(jié)構(gòu)了。 data link E E）刪除某結(jié)點）刪除某結(jié)點 if (p-link !=NULL) q=p-link ; p-link=q-link; free(q); / 刪除刪除p的后繼結(jié)點的后繼結(jié)點 b. b. 雙向鏈表雙向鏈表 在每個結(jié)點中設置兩個指針，一個指向后繼在每個結(jié)點中設置兩個指針，一個指向后繼, ,一個一個 指向前驅(qū)指向前驅(qū). .可直接確定一

3、個結(jié)點的前驅(qū)和后繼結(jié)點，提可直接確定一個結(jié)點的前驅(qū)和后繼結(jié)點，提 高效率。高效率。 a. a. 循環(huán)鏈表：首尾相接的鏈表。循環(huán)鏈表：首尾相接的鏈表。 將最后一個結(jié)點的空指針改為指向頭結(jié)點，從任一將最后一個結(jié)點的空指針改為指向頭結(jié)點，從任一 結(jié)點出發(fā)均可找到其它結(jié)點。結(jié)點出發(fā)均可找到其它結(jié)點。 操作與單鏈表基本一致操作與單鏈表基本一致, ,循環(huán)條件不同循環(huán)條件不同 l單鏈表單鏈表p p或或p-link=NULLp-link=NULL； l循環(huán)鏈表循環(huán)鏈表p p或或p-link=hp-link=h； top top bottom top bottombottom top 1 2 3 4 5 6 7

4、 anan-1 a3a2a1 特殊矩陣：值相同元素或非零元素的分布具有一定規(guī)律。特殊矩陣：值相同元素或非零元素的分布具有一定規(guī)律。 1 1）下三角陣）下三角陣 Loc(aij) = Loc(a11) + 2 * (i-1) + (j-1) *S 2/1 2 11) 1( 2 3/2 3 121) 1( 3 1 1) 1( lim n n nk kn k n n nk kn k nk kn k A B CD EF 4 23 1 567 8910 11 12 C D L R A D B C T1 T2 T3 Pre流程 中序、后序算法 creat(T-R-R) B A creat(T-L) cre

5、at(T-R-R) B creat(T-L) B creat(T-R-R) D = D - - C + + creat(T-L) creat(T-R-R) C # D = creat(T-L) C + 1 1、哈夫曼樹、哈夫曼樹 （HuffmanHuffman) ) 最優(yōu)樹：最優(yōu)樹：是帶權的路徑長度最短的樹，常用于信息檢索；是帶權的路徑長度最短的樹，常用于信息檢索； 路徑長度：路徑長度：從一個結(jié)點到另一結(jié)點之間經(jīng)過的分支數(shù)目稱從一個結(jié)點到另一結(jié)點之間經(jīng)過的分支數(shù)目稱 為這對結(jié)點間的路徑長度；為這對結(jié)點間的路徑長度； 樹的路徑長度：樹的路徑長度：從樹根到每一結(jié)點的路徑長度之和，用從樹根到每一結(jié)點

6、的路徑長度之和，用PLPL 表示；表示； 結(jié)點帶權的路徑長度：結(jié)點帶權的路徑長度：為從該結(jié)點到樹根之間的路徑長度為從該結(jié)點到樹根之間的路徑長度 與結(jié)點上權的乘積。與結(jié)點上權的乘積。 樹的帶權路徑長度：樹的帶權路徑長度：為樹中葉子結(jié)點帶權路徑長度之和。為樹中葉子結(jié)點帶權路徑長度之和。 記作：記作： 其中：其中：W Wk k為樹中每個葉子結(jié)點的權；為樹中每個葉子結(jié)點的權； L Lk k為每個葉子結(jié)點到根的路徑長度。為每個葉子結(jié)點到根的路徑長度。 WPLWPL最小的二叉樹就稱作最小的二叉樹就稱作最優(yōu)二叉樹最優(yōu)二叉樹或或哈夫曼樹哈夫曼樹。 18 a cd babcd ab a 輸入輸入10000個個 數(shù)據(jù)，則