【正文】 個字串 S1 = ‘a1 a2 … an’， S2 = ‘b1b2 … bm’， 如果存在整數(shù) i，使得 bj = ai+j j = 1, 2, … , m 則稱 S2是 S1的子串 串名 串值 12 167。 棧 一、定義 二、特性 三、存儲 四、操作 27 167。 圖 一、定義 二、存儲 43 167。 圖 三、圖的遍歷 ?廣度優(yōu)先搜索 從圖Ｇ中某一頂點Ｖ 0出發(fā)，首先依次訪問Ｖ 0的鄰接的頂點Ｗ １ ，Ｗ ２ ， … ，Ｗ ｔ 。 樹 二、樹的遍歷 ? 遍歷：將樹節(jié)點放入一個線性序列的過程 ? 按深度的方向遍歷 ?先根次序 ?訪問頭一棵樹的根 ?在先根次序下遍歷頭一棵樹樹根的子樹 ?在先根次序下遍歷其他的樹 A B C G H F D E J I A B D E I J F C G H 39 167。 表 一、定義 ? 表是一組有序的數(shù)據(jù)元素 ? 每一數(shù)據(jù)元素包含一個或多個數(shù)據(jù)項 ? 每一數(shù)據(jù)元素與唯一的關鍵字相關聯(lián) 學號 姓名 性別 年齡 系別 19808801 趙仁 男 28 計算機系 19901023 錢廣 男 23 數(shù)學系 19701001 李惠 女 25 數(shù)學系 行：數(shù)據(jù)元素 關鍵字 23 167。 ? 它描述了數(shù)據(jù)在計算機中如何存儲、傳送、轉換。 4 什么是數(shù)據(jù)結構 ? 數(shù)據(jù)結構是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應，通過這組算法集合可以對數(shù)據(jù)結構中的數(shù)據(jù)進行某種操作。 數(shù)組 一、定義 二、表示 三、存儲方式 17 167。 隊列 一、定義 ? 隊列是一種操作受限的線性表 ? 對于隊列的插入在表的一端進行，刪除操作在表的另一端進行 ? 進行刪除的一端稱為隊列的頭，進行插入的一端稱為隊列的尾 ? 新來的成員總是加入到隊尾，每次離開的總是隊頭上的元素 (先進先出 ) 32 167。 圖 V2 V1 V3 V4 V1 V2 V3 V4 2 4 ? 3 ? 2 ? 3 ? V1 ? V2 V3 V4 1 3 ? 2 4 ? 1 ? 出邊表 入邊表 48 167。 ? 深度優(yōu)先搜索： ? 廣度優(yōu)先搜索： 49 167。 隊列 三、操作 ? enq(QU, X)：往隊列 QU中插入一個值為 X的表目 ? deq(QU)：從隊列 QU中刪除一個表目 ? front(QU, X)：把隊列 QU頭部表目的值讀到變量X中 ? qempty(QU)：判斷隊列是否為空 … ai ai+1 … aj aj+1 … 頭指針 尾指針 … ai ai+1 … aj 頭指針 尾指針 插入aj+1 刪除 ai 34 167。 18 167。因此，主要有三個方面的內容： ? 數(shù)據(jù)的邏輯結構 線性 (線性表，棧，隊列，向量， 字符串，多維數(shù)組，廣義表 )， 樹 ， 圖 ， 文件 數(shù)據(jù)結構主要研究什么？ 5 什么是數(shù)據(jù)結構 ? 數(shù)據(jù)的物理存儲結構 順序方法、索引方法、散列方法 ? 對數(shù)據(jù)的操作（或算法） 通常，算法的設計取決于數(shù)據(jù)的邏輯結構，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結構。