清華大學(xué)嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)考研要點(diǎn)(精華版)

1、1、數(shù)據(jù)、數(shù)據(jù)(Data)：是客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素?cái)?shù)據(jù)元素(DataElement)：是數(shù)據(jù)的基本單位，在程序中通常作為一個(gè)整體來(lái)進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對(duì)象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集

2、。如字符集合C=‘A’’B’’C…。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是指相互之間具有：是指相互之間具有(存在存在)一定聯(lián)系一定聯(lián)系(關(guān)系關(guān)系)的數(shù)據(jù)元素的集合。元的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系素之間的相互聯(lián)系(關(guān)系關(guān)系)稱為邏輯結(jié)構(gòu)。稱為邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型，如圖13所示。①集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外，沒(méi)有其它關(guān)系。②線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。③樹

3、型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。2、順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的、順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的；鏈?zhǔn)浇Y(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒(méi)有要求。鏈?zhǔn)浇Y(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒(méi)有要求。數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，

4、而算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu)。結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu)。在C語(yǔ)言中，用一維數(shù)組表示順序存儲(chǔ)結(jié)構(gòu)；用結(jié)構(gòu)體類型表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。語(yǔ)言中，用一維數(shù)組表示順序存儲(chǔ)結(jié)構(gòu)；用結(jié)構(gòu)體類型表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、C語(yǔ)言中用帶指針的結(jié)構(gòu)體類型來(lái)描述語(yǔ)言中用帶指針的結(jié)構(gòu)體類型來(lái)描述typedefstructLnodeElemTypedata數(shù)據(jù)域，保存結(jié)點(diǎn)的值數(shù)據(jù)域，保存結(jié)點(diǎn)的值structLnodenext指針域指針域LNode結(jié)點(diǎn)

5、的類型結(jié)點(diǎn)的類型4、循環(huán)隊(duì)列為空：、循環(huán)隊(duì)列為空：front=rear。循環(huán)隊(duì)列滿：循環(huán)隊(duì)列滿：(rear1)%MAX_QUEUE_SIZE=front。5、性質(zhì)、性質(zhì)1：在非空二叉樹中，第：在非空二叉樹中，第i層上至多有層上至多有2i1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(i≧1)。性質(zhì)性質(zhì)2：深度為：深度為k的二叉樹至多有的二叉樹至多有2k1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（k≧1)。性質(zhì)性質(zhì)3：對(duì)任何一棵二叉樹，若其葉子結(jié)點(diǎn)數(shù)為：對(duì)任何一棵二叉樹，若其葉子結(jié)點(diǎn)數(shù)為n0，度

6、為，度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，則，則n0=n21。一棵深度為一棵深度為k且有且有2k1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹(FullBinaryTree)。完全二叉樹的特點(diǎn)：若完全二叉樹的深度為完全二叉樹的特點(diǎn)：若完全二叉樹的深度為k，則所有的葉子結(jié)點(diǎn)都出現(xiàn)在第，則所有的葉子結(jié)點(diǎn)都出現(xiàn)在第k層或?qū)踊騥1層。對(duì)于任一結(jié)點(diǎn)，如果其右子樹的最大層次為層。對(duì)于任一結(jié)點(diǎn)，如果其右子樹的最大層次為l，則其左子樹，則其左子樹8、

7、完全無(wú)向圖：、完全無(wú)向圖：對(duì)于無(wú)向圖，若圖中頂點(diǎn)數(shù)為n，用e表示邊的數(shù)目，則e?[0，n(n1)2]。具有n(n1)2條邊條邊的無(wú)向圖稱為完全無(wú)向圖。完全有向圖：完全有向圖：對(duì)于有向圖，若圖中頂點(diǎn)數(shù)為n，用e表示弧的數(shù)目，則e?[0，n(n1)]。具有n(n1)條邊的有向圖稱為完全有向圖。生成樹、生成森林：生成樹、生成森林：一個(gè)連通圖(無(wú)向圖)的生成樹是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)和只有足以構(gòu)成一棵樹的n1條邊條邊，稱為圖的

8、生成樹關(guān)于無(wú)向圖的生成樹的幾個(gè)結(jié)論：1)一棵有n個(gè)頂點(diǎn)的生成樹有且僅有n1條邊；2)如果一個(gè)圖有n個(gè)頂點(diǎn)和小于小于n1條邊條邊，則是非連通圖非連通圖；3)如果多于多于n1條邊條邊，則一定有環(huán)一定有環(huán)；4)有n1條邊的圖不一定是條邊的圖不一定是生成樹。9、最小生成樹、最小生成樹(MinimumSpanningTree)：帶權(quán)連通圖中代價(jià)最小的生成樹稱為最小生成：帶權(quán)連通圖中代價(jià)最小的生成樹稱為最小生成樹。樹。最小生成樹在實(shí)際中具有重要用途