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

數(shù)據(jù)結(jié)構(gòu)概念名詞解釋全套數(shù)據(jù)：是對客觀事物的符號表示。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，也稱節(jié)點(diǎn)（node）或記錄（record）。數(shù)據(jù)對象：是性質(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)系外，別無其他關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對一個(gè)的關(guān)系。樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對多個(gè)的關(guān)系。圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對多個(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ǔ)器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。算法：對特定問題求解步驟的一種描述。算法的五個(gè)重要特性：有窮性，確定性，可行性，輸入和輸出。算法設(shè)計(jì)的原則或要求：正確性，可讀性，健壯性，效率與低存儲(chǔ)量需求。衡量算法效率的方法：事后統(tǒng)計(jì)法和事前分析估算法。算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，則可記作：T(n)=O(f(n))，稱T(n)為算法的(漸近)時(shí)間復(fù)雜度算法運(yùn)行時(shí)間的衡量準(zhǔn)則：以基本操作在算法中重復(fù)執(zhí)行的次數(shù)。棧：限定僅在表尾進(jìn)行插入或刪除操作線性表。入棧：插入元素的操作；出棧：刪除棧頂元素的操作。隊(duì)列：只能在隊(duì)首進(jìn)行刪除、隊(duì)尾進(jìn)行插入的線性表。允許插入的一端叫隊(duì)尾，刪除的一端叫隊(duì)頭。串：由零個(gè)或多個(gè)字符組成的有限序列；空串：零個(gè)字符的串；長度：串中字符的數(shù)目；空串：零個(gè)字符的串；子串：；串中任意個(gè)連續(xù)的字符組成的子序列；位置：字符在序列中的序號；相等：串的值相等；空格串：由一個(gè)或多個(gè)空格組成的串，空格串的長度為串中空格字符的個(gè)數(shù)。存儲(chǔ)位置：LOC(i,j)=LOC(0,0)+(b2*i+j)L結(jié)點(diǎn):包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支；結(jié)點(diǎn)的度:結(jié)點(diǎn)擁有的子樹；樹的度:樹中所有結(jié)點(diǎn)的度的最大值；葉子結(jié)點(diǎn):度為零的結(jié)點(diǎn)；分支結(jié)點(diǎn):度大于零的結(jié)點(diǎn)樹的深度：樹中葉子結(jié)點(diǎn)所在的最大層次森林：m棵互不相交的樹的集合。二叉樹的性質(zhì)：性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)性質(zhì)2：深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)。（k≥1）性質(zhì)3:對任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1。性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為?log2n?+1。滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的

n

個(gè)結(jié)點(diǎn)和滿二叉樹中編號為

1

至

n

的結(jié)點(diǎn)一一對應(yīng)。路徑長度：路徑上分支的數(shù)目。樹的路徑長度：樹根到每個(gè)結(jié)點(diǎn)的路徑長度之和。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記作：WPL(T)=Swklk帶權(quán)路徑長度最小的二叉樹，稱為最優(yōu)樹二叉樹或赫夫曼樹。關(guān)鍵路徑：路徑長度最長的路徑。頂點(diǎn)：數(shù)據(jù)元素vi稱為頂點(diǎn)邊、?。篜(vi,vj)表示頂點(diǎn)vi和頂點(diǎn)vj之間的直接連線，在無向圖中稱為邊，在有向圖中稱為弧。任意兩個(gè)頂點(diǎn)構(gòu)成的偶對(vi,vj)∈E是無序的，該連線稱為邊。是有序的，該連線稱為弧。弧頭、弧尾：帶箭頭的一端稱為弧頭，不帶箭頭的一端稱為弧尾。頂點(diǎn)的度(TD)=出度(OD)+入度(ID)圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。排序的分類：按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過程中需對