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