數(shù)據(jù)結(jié)構(gòu)a第06章(已修改)
2025-08-05 17:38 本頁(yè)面
【正文】 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 數(shù)據(jù)結(jié)構(gòu) Data Structures in C++ 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 第 6章 集合和搜索 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 基本概念 順序搜索 二分搜索 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 基本概念 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 集合和搜索的概念 在數(shù)學(xué)上， 集合 是不同對(duì)象的無(wú)序匯集 ，集合的對(duì)象稱為元素或成員，每個(gè)元素僅出現(xiàn)一次。 多重集 是元素的無(wú)序匯集，其中，每個(gè)元素可出現(xiàn)一次或多次。例如， 多重集 {1, 1, 2, 3} 與 {1, 2, 3, 1}相同，但與 {1, 2, 3}不同。 通常用大括號(hào)表示 無(wú)序集 。 一個(gè) 有序集 是元素的匯集，其中，每個(gè)元素可以出現(xiàn)一次或多次，并且它們的出現(xiàn)次序是重要的（如同向量一樣）。通常用圓括號(hào)表示有序集，例如，（ 2， 1， 3）。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 集合結(jié)構(gòu) （簡(jiǎn)稱集合）作為一種數(shù)據(jù)結(jié)構(gòu)，我們將它視為同類型數(shù)據(jù)元素的 匯集 。集合的數(shù)據(jù)元素之間除了 “ 同屬于一個(gè)集合 ”的聯(lián)系之外沒(méi)有其它關(guān)系。一般地，我們假定所討論的集合不包含相同元素。數(shù)據(jù)結(jié)構(gòu)意義上的集合通常是動(dòng)態(tài)的，在集合中可以插入和刪除元素，因而被稱為 動(dòng)態(tài)集 。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 元素類型 template class K,class D struct E { operator K ()const { return key。} K key。 D data。 }。 其中， K和 D是用戶定義的數(shù)據(jù)類型， K被稱為關(guān)鍵字類型， key是關(guān)鍵字，我們要求類型 K是 C/C++語(yǔ)言允許的，可以比較大小的類型。除關(guān)鍵字外的其它數(shù)據(jù)項(xiàng)歸入 data域部分， D可以是簡(jiǎn)單類型，也可以是結(jié)構(gòu)類型。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 關(guān)鍵字 是用以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)。 若此關(guān)鍵字可以惟一標(biāo)識(shí)一個(gè)元素，則稱此關(guān)鍵字 為主關(guān)鍵字 。集合中，不同數(shù)據(jù)元素有不同的主關(guān)鍵字值。 稱可用以識(shí)別若干數(shù)據(jù)元素的關(guān)鍵字為 次關(guān)鍵字 。當(dāng)數(shù)據(jù)元素是初等數(shù)據(jù)類型時(shí)，其關(guān)鍵字值即數(shù)據(jù)元素值。 在本章討論中，若非特殊說(shuō)明，都假定被搜索的關(guān)鍵字為 主關(guān)鍵字 。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 搜索 ：根據(jù)給定的某個(gè)值 ， 在表中確定一個(gè)關(guān)鍵字值等于給定值的數(shù)據(jù)元素 ， 若表中存在這樣的元素 ， 則稱 搜索成功 ， 搜索結(jié)果可以返回整個(gè)數(shù)據(jù)元素 ， 也可指示該元素在表中的地址 。 哈，找到了！ 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 搜索 ：根據(jù)給定的某個(gè)值 ， 在表中確定一個(gè)關(guān)鍵字值等于給定值的數(shù)據(jù)元素 ， 若表中不存在關(guān)鍵字值等于給定值的元素 ， 則稱 搜索不成功 （ 也稱 搜索失敗 ） 。 噢！還是沒(méi)找到！ 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 搜索算法分類 搜索算法可以按元素是否全部在內(nèi)存分為： 內(nèi)搜索 和外搜索 。 我們將對(duì)表的搜索稱為 內(nèi)搜索 ， 而對(duì)文件的搜索稱為 外搜索 。 如果一個(gè)搜索算法只是單純搜索一個(gè)元素 ， 稱為 靜態(tài)搜索 ， 如果在搜索不成功時(shí) ， 需將被搜索的元素插入表中 ， 這樣的搜索被稱為 動(dòng)態(tài)搜索 ， 這種將搜索和插入結(jié)合起來(lái)的算法常稱為 符號(hào)表算法 ， 被編譯程序用于構(gòu)造標(biāo)識(shí)符表 。 搜索算法還可以根據(jù)算法中是否以關(guān)鍵字值間的比較為基礎(chǔ) ， 或由關(guān)鍵字值直接計(jì)算元素地址 ， 分為 基于關(guān)鍵字比較的搜索 和 基于計(jì)算地址的搜索 ， 本章和第 9章的搜索屬于前者 ， 第 10章的散列表搜索屬于后者 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 動(dòng)態(tài)集 ADT ADT DynamicSe
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1