軟件技術(shù)基礎(chǔ)-數(shù)據(jù)結(jié)構(gòu)(編輯修改稿)
2025-08-18 09:40 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 個(gè)環(huán)，構(gòu)成 單向循環(huán)鏈表 。 ?在雙鏈表中，將雙鏈表的最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)(帶頭結(jié)點(diǎn)的雙鏈表 )或第一個(gè)元素結(jié)點(diǎn) (不帶頭結(jié)點(diǎn)的雙鏈表 )鏈接起來(lái)，構(gòu)成 雙向循環(huán)鏈表 。 ③棧 ?棧是一種特殊的線性表，它的插入和刪除運(yùn)算 限制在表的一端進(jìn)行 。 ?通常稱(chēng)插入、刪除的一端為 “ 棧頂 ” ，另一端稱(chēng)為 “ 棧底 ” 。當(dāng)表中沒(méi)有元素時(shí)稱(chēng)為 “ 空棧 ” 。 ?棧中元素的插入和刪除只能在棧頂進(jìn)行，棧是一種 后進(jìn)先出表 (LIF0)。 舉例： 進(jìn)棧 與出 棧 ④隊(duì)列 ?隊(duì)列也是一種操作受限的線性表，允許在線性表的 一端進(jìn)行數(shù)據(jù)元素插入操作 ，而在 另一端進(jìn)行數(shù)據(jù)元素刪除操作 。 ?允許插入的一端稱(chēng)為隊(duì)尾，允許刪除的另一端稱(chēng)為隊(duì)頭。根據(jù)隊(duì)列的特點(diǎn)，隊(duì)列有兩個(gè)隊(duì)列指針，一個(gè)是隊(duì)頭指針 front,它總是指向隊(duì)頭元素的前一個(gè)位置；另一個(gè)是隊(duì)尾指針 rear， 它總是指向隊(duì)尾元素所在的存儲(chǔ)位置。 舉例： 入隊(duì)和出隊(duì) 舉例： 循環(huán)隊(duì)列的入隊(duì)和出隊(duì) ⑤數(shù)組 ?順序存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)是用一組連續(xù)的內(nèi)存單元來(lái)存儲(chǔ)數(shù)組的。它分為 行優(yōu)先順序存儲(chǔ) 和 按列優(yōu)先順序存儲(chǔ) 兩種。 ?一維數(shù)組本身就是順序表結(jié)構(gòu)，多維數(shù)組是一種特殊的線性結(jié)構(gòu)?；诙S數(shù)組應(yīng)用最為廣泛，像數(shù)學(xué)中的矩陣、生活中常見(jiàn)的報(bào)表都是二維數(shù)組。 ⑥串 ?串是一種數(shù)據(jù)元素固定為字符的線性表。 就數(shù)據(jù)結(jié)構(gòu)而言， 串歸屬于線性表數(shù)據(jù)結(jié)構(gòu) 。 ?線性表上的操作是針對(duì)線性表中的某個(gè)數(shù)據(jù)元素進(jìn)行，而串上的操作是針對(duì)串的整體或串的某一部分子串進(jìn)行。 ?串的基本操作包括：判串、求串長(zhǎng)、連接串、替換子串等。 三 .非線性結(jié)構(gòu) 非線性結(jié)構(gòu)的邏輯特征： 一個(gè)結(jié)點(diǎn)元素可能有多個(gè)直接前趨和多個(gè)直接后繼。 最主要的非線性結(jié)構(gòu)有樹(shù)結(jié)構(gòu)、二叉樹(shù)和圖結(jié)構(gòu)。 ?樹(shù)結(jié)構(gòu)是結(jié)點(diǎn)之間有分支、層次關(guān)系的結(jié)構(gòu)，類(lèi)似于自然界中的樹(shù)，也有樹(shù)根、樹(shù)葉及聯(lián)系它們的支干，它是一種倒生樹(shù)。 ?在樹(shù)中，一個(gè)結(jié)點(diǎn)元素簡(jiǎn)稱(chēng) “ 結(jié)點(diǎn) ” 。 ： 葉子： 沒(méi)有后繼的結(jié)點(diǎn) (或終端結(jié)點(diǎn) )。如圖結(jié)點(diǎn) D、 E、 F、 G、 H、 J。 分支結(jié)點(diǎn)： 非葉子結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn) (或非終端結(jié)點(diǎn) )。如圖結(jié)點(diǎn) A、 B、 C、 I。 結(jié)點(diǎn)的度： 一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目稱(chēng)為該結(jié)點(diǎn)的度。如圖結(jié)點(diǎn) B的度為 2；結(jié)點(diǎn) C的度為 3；結(jié)點(diǎn) D、 J的度為 0。 樹(shù)的度： 樹(shù)中各結(jié)點(diǎn)的度的最大值稱(chēng)為該樹(shù)的度。如圖所示樹(shù)的度為 3。 子結(jié)點(diǎn)： 某結(jié)點(diǎn)的子成為該結(jié)點(diǎn)的子結(jié)點(diǎn)。 父結(jié)點(diǎn)： 某結(jié)點(diǎn)的根，稱(chēng)該結(jié)點(diǎn)父結(jié)點(diǎn)。 兄弟： 具有同一父結(jié)點(diǎn)的子結(jié)點(diǎn)。 如， 結(jié)點(diǎn) C是結(jié)點(diǎn) G、 H、 I 的父結(jié)點(diǎn)； 結(jié)點(diǎn) G、 h、 I是結(jié)點(diǎn) C的子結(jié)點(diǎn)； 結(jié)點(diǎn) G、 H、 I 互為兄弟。 結(jié)點(diǎn)的層次： 根結(jié)點(diǎn)層次為 1，其他任何層次為父結(jié)點(diǎn)的層次加 1。 樹(shù)的深度： 結(jié)點(diǎn)的最大層次值就是樹(shù)的深度。圖中樹(shù)的深度為 4。 有序樹(shù)和無(wú)序樹(shù)： 若樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有序的，即交換某結(jié)點(diǎn)各子樹(shù)的相對(duì)位置，構(gòu)成不同的樹(shù)，稱(chēng)這棵樹(shù)為有序樹(shù)，反之則為無(wú)序樹(shù)。 森林： 森林是 n棵樹(shù)的集合 (n≥0) 。 任何一棵樹(shù)，刪去根結(jié)點(diǎn)，樹(shù)就變成丁森林。對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)來(lái)說(shuō)，其子樹(shù)的集合就是一個(gè)森林。 ?二叉樹(shù)結(jié)構(gòu)也是非線性結(jié)構(gòu)中重要的一類(lèi)，但二叉樹(shù)結(jié)構(gòu)不同于一般的樹(shù)結(jié)構(gòu)。 ?二叉樹(shù)是 n個(gè)結(jié)點(diǎn)的有限集合 (n≥0) ： 該集合可以是空 (即 n=0)， 即 “ 空二叉樹(shù) ” ；或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的被稱(chēng)為根的左子樹(shù)和右子樹(shù)組成。左子樹(shù)和右子樹(shù)分別又是一棵二叉樹(shù)。 ?二叉樹(shù)可以有五種基本形態(tài)。 [注意 ]一般樹(shù)至少有一個(gè)結(jié)點(diǎn)，而二叉樹(shù)可以空；二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)區(qū)分為左子樹(shù)和右子樹(shù)，而一般樹(shù)無(wú)此區(qū)分。 幾個(gè)特殊二叉樹(shù)的概念
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1