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

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

2、述線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述 在高級(jí)語言中，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用在高級(jí)語言中，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用 “ “結(jié)構(gòu)指針結(jié)構(gòu)指針”來來 描述，對(duì)于有些沒有結(jié)構(gòu)指針的高級(jí)語言，也就沒有描述，對(duì)于有些沒有結(jié)構(gòu)指針的高級(jí)語言，也就沒有 相應(yīng)的鏈?zhǔn)浇Y(jié)構(gòu)了。相應(yīng)的鏈?zhǔn)浇Y(jié)構(gòu)了。 data link E E）刪除某結(jié)點(diǎn)）刪除某結(jié)點(diǎn) if (p-link !=NULL) q=p-link ; p-link=q-link; free(q); / 刪除刪除p的后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn) b. b. 雙向鏈表雙向鏈表 在每個(gè)結(jié)點(diǎn)中設(shè)置兩個(gè)指針，一個(gè)指向后繼在每個(gè)結(jié)點(diǎn)中設(shè)置兩個(gè)指針，一個(gè)指向后繼, ,一個(gè)一個(gè) 指向前驅(qū)指向前驅(qū). .可直接確定一

3、個(gè)結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)，提可直接確定一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)，提 高效率。高效率。 a. a. 循環(huán)鏈表：首尾相接的鏈表。循環(huán)鏈表：首尾相接的鏈表。 將最后一個(gè)結(jié)點(diǎn)的空指針改為指向頭結(jié)點(diǎn)，從任一將最后一個(gè)結(jié)點(diǎn)的空指針改為指向頭結(jié)點(diǎn)，從任一 結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn)。結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn)。 操作與單鏈表基本一致操作與單鏈表基本一致, ,循環(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)樹：是帶權(quán)的路徑長(zhǎng)度最短的樹，常用于信息檢索；是帶權(quán)的路徑長(zhǎng)度最短的樹，常用于信息檢索； 路徑長(zhǎng)度：路徑長(zhǎng)度：從一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)之間經(jīng)過的分支數(shù)目稱從一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)之間經(jīng)過的分支數(shù)目稱 為這對(duì)結(jié)點(diǎn)間的路徑長(zhǎng)度；為這對(duì)結(jié)點(diǎn)間的路徑長(zhǎng)度； 樹的路徑長(zhǎng)度：樹的路徑長(zhǎng)度：從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和，用從樹根到每一結(jié)點(diǎn)

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