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