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