dijkstra堆優(yōu)化及set用法(已修改)
2025-10-10 21:43 本頁(yè)面
【正文】 Dijkstra堆優(yōu)化及 set用法 主講： wangfangbob Email:. Set功能 ? Set，顧名思義，就是集合的意思 ? 它支持插入，刪除，查找，首元素，末元素等操作，就像一個(gè)集合一樣． ? 而且所有的操作都是在嚴(yán)格 logn時(shí)間之內(nèi)完成，效率非常高．對(duì)于動(dòng)態(tài)維護(hù)可以說(shuō)是很理想的選擇 ? Set是一個(gè)有序的容器，里面的元素都是排好序的 Set實(shí)現(xiàn)簡(jiǎn)介 ? Set的實(shí)現(xiàn)是通過(guò) ２ 叉排序樹(shù)來(lái)實(shí)現(xiàn)，就是將所有的元素用一個(gè)樹(shù)來(lái)存儲(chǔ)，根元素大于左子樹(shù)的元素，小于右子樹(shù)的元素，所有的操作都是基于這個(gè)樹(shù)，通過(guò)判斷元素的大小來(lái)選擇對(duì)左子樹(shù)操作還是右子樹(shù)操作，這樣操作數(shù)量和樹(shù)的層數(shù)成正比． ? 這樣樹(shù)就有可能退化成一條線，所以 Set用一種平衡的 ２ 叉排序樹(shù)－－紅黑樹(shù)實(shí)現(xiàn)． Set對(duì)元素的要求 ? Set中的元素可以是任意類型的，但是由于需要排序，所以元素必須有一個(gè)序，即大小的比較關(guān)系，比如整數(shù)可以用＜比較． ? 比較關(guān)系是有要求的，必須和實(shí)數(shù)的＜類似，下面說(shuō)明對(duì)比較關(guān)系＜的要求 ? １ ．如果 a b, b c 則有 a c，即比較關(guān)系必須滿足傳遞性 ? ２ ． a b和 b c不能同時(shí)成立 ? 如果元素類型有比較關(guān)系，并且比較關(guān)系滿足以上 ２ 個(gè)條件，那么這個(gè)類型的元素就可以作為 Set中的元素來(lái)存儲(chǔ) 自定義元素類型 Set代碼 ? includeset typedef struct { 定義類型 } ss(類型名 )。 ? bool operator( const ss amp。a, const ss amp。b ) { 定義比較關(guān)系 (必須滿足上一頁(yè) ２ 個(gè)要求 )} (運(yùn)算符重載，重載 ) ? setss base。 ( 創(chuàng)建一個(gè)元素類型是 ss,名字是 base的 set ) ? 注：定義了＜，＝＝和＞以及＞＝，＜＝就都確定了，STL的比較關(guān)系都是用＜來(lái)確定的，所以必須通過(guò)定義＜ －－“嚴(yán)格弱小于”來(lái)確定比較關(guān)系 Set的操作 ? 以 base為例說(shuō)明 Set的操作 () 清空 base ( a ) 插入元素 a ( a ) 刪除元素 a,如果 a是迭代器 ,就刪除迭代器指向的元素( a ) 順序查找 =a的第一個(gè)元素 ,返回迭代器 ( a
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1