訪問(wèn)【W(wǎng)RITE-BUG數(shù)字空間】_[內(nèi)附完整源碼和文檔]

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告--B樹(shù)

環(huán)境及工具

環(huán)境：C

工具：AnyivewCL

B 定義

一棵 m 階 B 樹(shù)(Balance Tree of order m), 或?yàn)榭諛?shù),或滿足下列的特性的 m 叉樹(shù)：(本次實(shí)驗(yàn)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))

(1)樹(shù)中每個(gè)結(jié)點(diǎn)最多含有 m 棵子樹(shù)。

(2)若根結(jié)點(diǎn)是非終端結(jié)點(diǎn),則至少有 2 棵子樹(shù)

(3)除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有「m/2 棵子樹(shù)。

(4)每個(gè)非終端結(jié)點(diǎn)中包含信息:(n,A,K1,A1,K2,A2,…,Kn,An)。其中：

①K(1≤i≤n)為關(guān)鍵字,且關(guān)鍵字按升序推入指針。

②A(0≤≤n)指向子樹(shù)的根結(jié)點(diǎn),A(i-1)指向子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均小于 Ki，且大于 K(i-1）。

③ 關(guān)鍵字的個(gè)數(shù) n 必須滿足「m/2-1≤n≤m-1。

(5)所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層,葉子結(jié)點(diǎn)不包含任何信息(可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn),實(shí)際上這些結(jié)點(diǎn)不存在,指向這些結(jié)點(diǎn)的指針為空。實(shí)際上,B 樹(shù)的結(jié)點(diǎn)還應(yīng)包含 n 個(gè)指向每個(gè)關(guān)鍵字相應(yīng)記錄的指針。這與應(yīng)用相關(guān),從略。

存儲(chǔ)結(jié)構(gòu)定義和宏定義

# define M 4 ?//B樹(shù)的階，本次實(shí)驗(yàn)設(shè)置為4 # define ?MAX M – 1 ? //每個(gè)節(jié)點(diǎn)存儲(chǔ)的最多關(guān)鍵字的數(shù)目 # define MIN M/2 ? //每個(gè)節(jié)點(diǎn)存儲(chǔ)的最少關(guān)鍵字的數(shù)目 # define N 14 ?//選取14個(gè)關(guān)鍵字的樹(shù)作為例子 # define ERROR 0 # define SUCCESS 1 # define TRUE 1 # define UNSUCCESS 0 # define OVERFLOW -1 # define FALSE -1 typedef int Status; typedef int KeyType;//關(guān)鍵字類(lèi)型為整形 typedef struct BTNode { ? ?int keynum; ? ? ? ? ? ? ? ? //當(dāng)前節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目 ? ?KeyType key[M + 1]; ? ? ? ? //關(guān)鍵字?jǐn)?shù)組，key[0]未用 ? ?struct BTNode parent; ? ? ?//雙親結(jié)點(diǎn)指針 ? ?struct BTNode ptr[M + 1]; ?//孩子節(jié)點(diǎn)指針數(shù)組 ? ?//Record recptr[M + 1]; ? ?//記錄指針向量，0號(hào)單元未用 } BTNode, BTree; ? ? ? ? ? ? ? //B樹(shù)的節(jié)點(diǎn)及指針類(lèi)型 //B樹(shù)查找的結(jié)果類(lèi)型 typedef struct { ? ?int tag; ? ? ? ? ? ? ? ? ? ?//1：查找成功，0：查找失敗 ? ?BTree pt; ? ? ? ? ? ? ? ? ?//指向找到的結(jié)果類(lèi)型 ? ?int index; ? ? ? ? ? ? ? ? //1 <= index <= M ?在節(jié)點(diǎn)中的關(guān)鍵字位序 } Result;