數(shù)據(jù)結(jié)構(gòu)概念名詞解釋大全

1、數(shù)據(jù)：是對(duì)客觀事物的符號(hào)表示。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，也稱節(jié)點(diǎn)（node）或記錄（recd）。數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)項(xiàng)：有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域(field)。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，別無(wú)其他關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系

2、。樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。邏輯結(jié)構(gòu)：抽象反映數(shù)據(jù)元素之間的邏輯關(guān)系。（算法設(shè)計(jì)）物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。（算法實(shí)現(xiàn)）存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)：借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。算法：對(duì)特定問(wèn)題求解步驟的一種描述。算法的五個(gè)重要特性：有

3、窮性，確定性，可行性，輸入和輸出。算法設(shè)計(jì)的原則或要求：正確性，可讀性，健壯性，效率與低存儲(chǔ)量需求。衡量算法效率的方法：事后統(tǒng)計(jì)法和事前分析估算法。算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作：T(n)=O(f(n))，稱T(n)為算法的(漸近)時(shí)間復(fù)雜度算法運(yùn)行時(shí)間的衡量準(zhǔn)則：以基本操作在算法中重復(fù)執(zhí)行的次數(shù)。棧：限定僅在表尾進(jìn)行插入或刪除操作線性表。入棧：插入元素的操作；出棧：刪除棧頂元素的操作。隊(duì)列：只能在隊(duì)首進(jìn)行刪除、隊(duì)

4、尾進(jìn)行插入的線性表。允許插入的一端叫隊(duì)尾，刪除的一端叫隊(duì)頭。串：由零個(gè)或多個(gè)字符組成的有限序列；空串：零個(gè)字符的串；長(zhǎng)度：串中字符的數(shù)目；空串：零個(gè)字符的串；子串：；串中任意個(gè)連續(xù)的字符組成的子序列；位置：字符在序列中的序號(hào)；相等：串的值相等；空格串：由一個(gè)或多個(gè)空格組成的串，空格串的長(zhǎng)度為串中空格字符的個(gè)數(shù)。存儲(chǔ)位置：LOC(ij)=LOC(00)(b2ij)L結(jié)點(diǎn):包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支；結(jié)點(diǎn)的度:結(jié)點(diǎn)擁有的子樹(shù)；樹(shù)

5、的度:樹(shù)中所有結(jié)點(diǎn)的度的最大值；葉子結(jié)點(diǎn):度為零的結(jié)點(diǎn)；分支結(jié)點(diǎn):度大于零的結(jié)點(diǎn)樹(shù)的深度：樹(shù)中葉子結(jié)點(diǎn)所在的最大層次森林：m棵互不相交的樹(shù)的集合。二叉樹(shù)的性質(zhì)：二叉樹(shù)的性質(zhì)：性質(zhì)1：在二叉樹(shù)的第i層上至多有2i1個(gè)結(jié)點(diǎn)。(i≥1)性質(zhì)2：深度為k的二叉樹(shù)上至多含2k1個(gè)結(jié)點(diǎn)。（k≥1）性質(zhì)3:對(duì)任何一棵二叉樹(shù)，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n21。性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為?log2n?

6、1。滿二叉樹(shù)：指的是深度為k且含有2k1個(gè)結(jié)點(diǎn)的二叉樹(shù)。完全二叉樹(shù)：樹(shù)中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。路徑長(zhǎng)度：路徑上分支的數(shù)目。樹(shù)的路徑長(zhǎng)度：樹(shù)根到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記作：WPL(T)=?wklk帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，稱為最優(yōu)樹(shù)二叉樹(shù)或赫夫曼樹(shù)。2、假設(shè)x是一個(gè)結(jié)點(diǎn)，T1，T2，…，Tk是k株互不相交的樹(shù)，我們可以構(gòu)造一株新樹(shù)：令x為根，并有k條邊

7、由x指向樹(shù)T1，T2，…，Tk。這些邊也叫做分支，T1，T2，…，Tk稱作根x的樹(shù)之子樹(shù)。二叉樹(shù)：二叉樹(shù)：有限個(gè)結(jié)點(diǎn)的集合，這個(gè)集合或者是空集，或者是由一個(gè)根結(jié)點(diǎn)和兩株互不相交的二叉樹(shù)組成，其中一株叫根的做左子樹(shù)，另一棵叫做根的右子樹(shù)。滿二叉樹(shù)：滿二叉樹(shù)：深度為k且有2k－1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。完全二叉樹(shù)：完全二叉樹(shù)：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)，稱之為完全

8、二叉樹(shù)。線索二叉樹(shù)：線索二叉樹(shù)：若結(jié)點(diǎn)p有左孩子，則plchild指向其左孩子結(jié)點(diǎn)，否則令其指向其（中序）前驅(qū)。若結(jié)點(diǎn)p有右孩子，則prchild指向其右孩子結(jié)點(diǎn)，否則令其指向其（中序）后繼。堆：堆：如果一棵完全二叉樹(shù)的任意一個(gè)非終端結(jié)點(diǎn)的元素都不小于其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)（如果有的話）的元素，則稱此完全二叉樹(shù)為最大堆。同樣，如果一棵完全二叉樹(shù)的任意一個(gè)非終端結(jié)點(diǎn)的元素都不大于其左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)（如果有的話）的元素，則稱此完全二

9、叉樹(shù)為最小堆。選擇樹(shù)：選擇樹(shù)：一棵選擇樹(shù)是一棵二叉樹(shù)，其中每一個(gè)結(jié)點(diǎn)都代表該結(jié)點(diǎn)兩個(gè)兒子中的較小者。這樣，樹(shù)的根結(jié)點(diǎn)就表示樹(shù)中最小元素的結(jié)點(diǎn)。二叉排序樹(shù)：二叉排序樹(shù)：二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：1、若它的左子樹(shù)非空，則左子樹(shù)上的所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值。2、若它的右子樹(shù)非空，則右子樹(shù)上的所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值。3、它的左右子樹(shù)分別為二叉排序樹(shù)。圖：圖：一個(gè)圖G=（V，E）是一個(gè)由非空的有