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

1、數(shù)據(jù)：是對客觀事物的符號表示。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，也稱節(jié)點（node）或記錄（recd）。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)項：有獨立含義的數(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ù)元素之間除了“同屬于一個集合”的關(guān)系外，別無其他關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對一個的關(guān)系

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

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

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

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

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

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

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

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