自3數(shù)據(jù)結(jié)構(gòu)期中小結(jié)

1、數(shù)據(jù)結(jié)構(gòu)期中小結(jié)自3年級(jí)數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組集合S（D，R），其中D是結(jié)構(gòu)變量的非空有限集合，R是描述在D上的有限個(gè)關(guān)系的集合 KK1,K2,.,K10R=r1,r2r1=,r2=,一組元素集合一組關(guān)系集合關(guān)系r1描述關(guān)系r2描述2元關(guān)系的邏輯結(jié)構(gòu)圖示法 基本的數(shù)據(jù)邏輯結(jié)構(gòu)類型 數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示方法，我們稱為數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)；物理結(jié)構(gòu)是邏輯結(jié)構(gòu)的計(jì)算機(jī)存儲(chǔ)形式；物理結(jié)構(gòu)有四種基本的形式，見(jiàn)下圖所示，其中，索引結(jié)構(gòu)用于文件操作，散列結(jié)構(gòu)是對(duì)數(shù)據(jù)檢索時(shí)采用的一種形式。 線性表順序存儲(chǔ)結(jié)構(gòu)數(shù)組是一種順序存儲(chǔ)結(jié)構(gòu)，它用地址相鄰表達(dá)了邏輯相鄰的關(guān)系，數(shù)組在定義

2、中需要指定存儲(chǔ)空間；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用指針的指向表達(dá)數(shù)據(jù)結(jié)構(gòu)的邏輯上的前趨與后繼關(guān)系；選定數(shù)據(jù)結(jié)構(gòu)，包括數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)形式時(shí)，若主要考慮程序的靈活性，需要鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，若主要考慮空間節(jié)省，特別是限定的特殊操作時(shí)，可以考慮用順序存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)的選取形式，完全取決于要解決的問(wèn)題特點(diǎn)。如果在順序表中任一位置插入元素的概率相等，其平均移動(dòng)次數(shù)是： 在刪除i節(jié)點(diǎn)上元素時(shí)，需要順序移動(dòng)其后面的元素序列補(bǔ)充這個(gè)位置，在順序表中元素的移動(dòng)個(gè)數(shù)是j=n-i，所以，其平均移動(dòng)次數(shù)是： 鏈表鏈表是最基本的數(shù)據(jù)結(jié)構(gòu)形式，表達(dá)了C語(yǔ)言指針運(yùn)用特點(diǎn)，動(dòng)態(tài)生長(zhǎng)，邏輯簡(jiǎn)單，應(yīng)用靈活。單鏈表是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本

3、概念。線性鏈表主要問(wèn)題是平均檢索時(shí)間與規(guī)模n成正比，習(xí)慣稱之為時(shí)間開(kāi)銷是n的線性函數(shù)O（n），效率比較低，提高鏈表的檢索效率是各種程序設(shè)計(jì)方法的出發(fā)點(diǎn)。此外，因?yàn)橹羔樀撵`活性特點(diǎn)，它是解決特定的實(shí)際問(wèn)題場(chǎng)合下的最佳工具，因而指針概念要非常清楚，仔細(xì)分析題意，才能理清思路。通過(guò)對(duì)鏈表實(shí)際應(yīng)用形式的討論，單鏈表的復(fù)制，對(duì)稱表效率等，如果同學(xué)能基本理解，并完成了實(shí)驗(yàn)要求，那么在鏈表學(xué)習(xí)方面已經(jīng)相當(dāng)深入。 鏈表的特點(diǎn)是在存儲(chǔ)結(jié)構(gòu)上用指針表達(dá)了相鄰元素的邏輯關(guān)系，因此它的效率體現(xiàn)在插入與刪除方面很高，沒(méi)有順序表要移動(dòng)元素的問(wèn)題；但是，鏈?zhǔn)酱鎯?chǔ)是順序存取結(jié)構(gòu)的，設(shè)鏈表長(zhǎng)為n，單鏈表操作時(shí)每次訪問(wèn)、查找一個(gè)

4、元素必須從表頭開(kāi)始，如果查找任一元素的概率相等，其平均查找長(zhǎng)度是： 鏈表的時(shí)間開(kāi)銷是n的線性函數(shù)O（n）棧和隊(duì)列 隊(duì)和棧概念簡(jiǎn)單，但引申出來(lái)的實(shí)際問(wèn)題形式很多，棧是一個(gè)先進(jìn)后出的概念，隊(duì)是先進(jìn)先出的概念，棧注意的是算法程序設(shè)計(jì)問(wèn)題，隊(duì)更注意的是指針的運(yùn)用。 注意，數(shù)據(jù)結(jié)構(gòu)是用來(lái)解決程序設(shè)計(jì)問(wèn)題的。 棧和隊(duì)是解決問(wèn)題的一種數(shù)據(jù)結(jié)構(gòu)手段，實(shí)現(xiàn)棧、隊(duì)函數(shù)非常簡(jiǎn)單，因此，同學(xué)的主要問(wèn)題是對(duì)它們的運(yùn)用能力。循環(huán)隊(duì)問(wèn)題循環(huán)隊(duì)列結(jié)構(gòu)在課堂上仔細(xì)討論過(guò)。規(guī)定指針是順時(shí)針運(yùn)動(dòng)，一個(gè)邏輯上環(huán)形存儲(chǔ)器在物理上對(duì)應(yīng)的是順序存儲(chǔ)結(jié)構(gòu)。每當(dāng)指針front、rear達(dá)到存儲(chǔ)區(qū)尾部時(shí)就被調(diào)整到的存儲(chǔ)區(qū)頭部繼續(xù)，指針front、rear不能重疊，否則初始隊(duì)空與當(dāng)前隊(duì)滿無(wú)法判別，所以，一般說(shuō)隊(duì)頭指針與隊(duì)尾指針需要間隔一個(gè)空單元。 堆棧的邏輯結(jié)構(gòu) 循環(huán)隊(duì)列結(jié)構(gòu) 隊(duì)列邏輯結(jié)構(gòu) 這是最基本的非線性數(shù)據(jù)結(jié)構(gòu)，平衡情況下，它的檢索和插入效率都是O（log n）；我們主要討論了二叉排序樹(shù)，線索化樹(shù)，堆，哈夫曼樹(shù)；二叉排序樹(shù)根據(jù)左小右大的規(guī)則對(duì)數(shù)據(jù)分類；二叉樹(shù)是非線性結(jié)構(gòu)，程序設(shè)計(jì)比較復(fù)雜，因?yàn)楹芏鄬?shí)際問(wèn)題中遇到的數(shù)據(jù)關(guān)系都可以用二叉樹(shù)的形式描述，變種也多，所以，二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)中非