軟件設(shè)計(jì)模式課程設(shè)計(jì)

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：11 大?。?6.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

已閱讀1頁(yè)，還剩10頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　2008級(jí)軟件設(shè)計(jì)模式課程設(shè)計(jì)　　（基于迭代器、適配器、策略模式的hashmap設(shè)計(jì)）　　目的及簡(jiǎn)要介紹　　大家都知道，C++為廣大愛(ài)好者提供了諸如Iterator、list等容器供大家使用，大大的方便了大家處理數(shù)據(jù)。這里，我們同樣為大家提供一個(gè)滿足ST

2、L要求的容器來(lái)供大家使用，讓大家在數(shù)據(jù)處理的過(guò)程中能更方便快捷。　　C++標(biāo)準(zhǔn)對(duì)容器提出了許多需求，只有滿足這些需求，才能算得上是STL容器。　　基本hashmap(散列表)：STL中的最大的疏忽嗎？在STL中，沒(méi)有定義hashmap容器，這里我們實(shí)現(xiàn)了。　　散列表在平均情況下可以提供常量時(shí)間的插入、刪除和查找。

3、散列表并不是將元素有序地存儲(chǔ)，而是把各元素散列(hash)或映射至某個(gè)桶(bucket)。只要所存儲(chǔ)的元素個(gè)數(shù)不比桶數(shù)大太多，插入、刪除和查找操作都能在常量時(shí)間內(nèi)運(yùn)行。　　Hashmap也存儲(chǔ)鍵/值對(duì)，它提供的操作與map幾乎一樣，這個(gè)hashmap實(shí)現(xiàn)使用鏈?zhǔn)缴⒘校ㄒ卜Q開(kāi)放散列），而且沒(méi)有提供諸如再散列等高級(jí)操作。　　程序?qū)崿F(xiàn)<

4、/b>　　Hashmap的訪問(wèn)操作：　　標(biāo)準(zhǔn)要求為鍵比較和值比較對(duì)象提供訪問(wèn)方法：　　Operator[]與STL中的map的原型相似。如果原來(lái)的hashmap中沒(méi)有該鍵對(duì)應(yīng)的值，則會(huì)插入一個(gè)，它會(huì)調(diào)用被映射的元素的默認(rèn)構(gòu)造函數(shù)進(jìn)行填充，并且反回這個(gè)值。<b&

5、gt;　　模板的分離編譯：　　在模板類的聲明文件(一般是.h文件)的最后添加一個(gè)include語(yǔ)句，將模板類的實(shí)現(xiàn)文件包含進(jìn)來(lái)，例如：　　#include “template_class_implement.cpp”　　將模板類的實(shí)現(xiàn)類文件從項(xiàng)目中移除(使工程中不含模板的實(shí)現(xiàn)文件 .cpp),

6、但并不從磁盤(pán)上移除，不改變其路徑。使它不能顯示的參與編譯。　　在聲明main函數(shù)的文件中包含要使用的模板類的聲明文件。　　設(shè)計(jì)模式　　相關(guān)內(nèi)容　　1、Hashmap應(yīng)當(dāng)允許客戶指定自己的散列函數(shù)和

7、桶數(shù)，而針對(duì)特定工作負(fù)載制定散列行為。另一方面，客戶如果沒(méi)有這種需求，或者沒(méi)有能力來(lái)編寫(xiě)一個(gè)好的散列函數(shù)及選擇桶數(shù)，也應(yīng)該能夠不做任何定制地直接使用容器。一種解決方案是允許客戶在hashmap構(gòu)造函數(shù)中提供散列函數(shù)和桶數(shù)，并為之提供默認(rèn)值。另外，把散列函數(shù)和桶數(shù)包裝在一個(gè)散列類中也是一種合理的做法:　　Hash()的實(shí)現(xiàn)要難一些，部分原因在于它必須應(yīng)用于任何類型的鍵，它要把鍵映射至某個(gè)mNumB

8、uckets桶。此函數(shù)使用了除留余數(shù)法來(lái)完成散列，即鍵所對(duì)應(yīng)的桶（號(hào)）是鍵對(duì)桶數(shù)取余后得到的一個(gè)整數(shù)值。　　遺憾的是，前面的方法無(wú)法應(yīng)用于string，因?yàn)椴煌膕tring對(duì)象可能包含相同的string值。因此相同的string值就可能散列到不同的桶中。這樣一來(lái)，可以想到，專門針對(duì)string提供DefaultHash類的一個(gè)部分特殊化。　　2、它支持

9、3個(gè)基本操作：插入、刪除、查找。　　比較器：hashmap允許客戶指定比較類型作為模板參數(shù)，并且能在構(gòu)造函數(shù)中傳遞該類的一個(gè)特定比較對(duì)象。Hashmap不會(huì)按鍵對(duì)元素排序，而是必須比較鍵的相等性。因此，它使用的是equal_to，比較對(duì)象只是用于檢測(cè)是否試圖向容器中插入重復(fù)鍵。　　散列器：允許客戶定義自己的類，以便構(gòu)造此類對(duì)象傳入構(gòu)造函數(shù)，此時(shí)必須明確如

10、何在構(gòu)造函數(shù)中指定該參數(shù)的類型。　　散列模板參數(shù)：使用 typedef 定義：　　鍵類型，值類型，比較類型，散列類型　　3、基本散列表結(jié)構(gòu)通常包括固定數(shù)目桶，每個(gè)桶可以存儲(chǔ)一個(gè)或多個(gè)元素。應(yīng)當(dāng)能夠基于一個(gè)bucket-id在常量時(shí)間內(nèi)訪問(wèn)桶。因此vector是對(duì)桶最為適合的容器。每個(gè)桶必須存儲(chǔ)一個(gè)元素列表，因此S

11、TL list可以用作桶類型。　　查找操作使用findElement幫助完成查找工作：findElement()首先使用散列對(duì)象將鍵散列至一個(gè)特定的桶。然后，在該桶中查找是否有元素的鍵與給定鍵匹配。所存儲(chǔ)的元素是鍵/值對(duì)，所以具體的比較會(huì)在元素第一個(gè)字段上進(jìn)行。構(gòu)造函數(shù)中指定的比較函數(shù)對(duì)象就是用于完成這個(gè)比較。List需要完成線性查找來(lái)尋找匹配的元素，因此可以使用find()算法而不是一個(gè)顯式的

12、for循環(huán)。　　Insert操作必須首先檢查hashmap中是否已經(jīng)存在此鍵的元素。如果沒(méi)有，會(huì)把元素插入到適當(dāng)?shù)耐爸械膌ist。需要說(shuō)明，findElement()會(huì)按引用返回散列到的那個(gè)桶，即在該桶中并沒(méi)有找到此鍵的元素。　　將hashmap作為容器　　有關(guān)typedef 的容器需求&

13、lt;p>　　作為容器必須提供的方法：　　編寫(xiě)一個(gè)迭代器：　　迭代器一般應(yīng)當(dāng)是一個(gè)看上去像智能指針的類，它要提供重載operator *和 operator ->，另外根據(jù)其特定行為還要提供其他一些操作。只要迭代器可以提供基本的迭代操作，應(yīng)該就能一切正常了。　　H

14、ashIterator類：　　每個(gè)HashIterator對(duì)象都是hashmap類的一特定貨柜的迭代器。為了提供這種一對(duì)一的映射，HashIterator還必須是一個(gè)類模板，要針對(duì)hashmap類的同樣參數(shù)模板化。　　Iterator_traits是一個(gè)類模板，它為各個(gè)迭代器類型定義了5個(gè)typedef。如果愿意，可以為你的新迭代器類型對(duì)其部分特殊化。還

15、有一種做法，iterator_traits類模板的默認(rèn)實(shí)現(xiàn)只是把這5個(gè)typedef從迭代器類本身當(dāng)中取出。因此可以直接在迭代器類中定義這些typedef。事實(shí)上，C++中的iterator類模板，它會(huì)提供typedef。這樣只需指定迭迭代器類型和元素類型作為模板參數(shù)提供給iterator類模板HashIterator是一個(gè)雙向迭代器，所以可以指定bidirectional_iterator_tag作為迭代器類型。元素類型就是pair&

16、lt;const Key,T>　　可以不顯示地實(shí)現(xiàn)拷貝構(gòu)造函數(shù)和賦值操作符，因?yàn)槟J(rèn)的行為就是我們想要的。　　對(duì)于一個(gè)HashIterator自增會(huì)讓它指示容器中的“下一個(gè)”元素。這個(gè)方法首先讓list迭代器自新加增，然后檢查是否到達(dá)桶的末尾。倘若如此，就錄找hashmap中的下一個(gè)非控桶，因?yàn)橄乱粋€(gè)桶中可以沒(méi)有任何元素。如果沒(méi)有更多的非空桶，mI

17、t會(huì)設(shè)置為hashmap中最后一個(gè)桶的末尾迭代器，這是Hashmap的特殊“末尾”位置。應(yīng)當(dāng)記得，迭代器不必比啞指針更安全，所以對(duì)于已經(jīng)處在末尾的迭代器再自增等情況不必進(jìn)行錯(cuò)誤檢查。　　自減是自增的逆操作，它使迭代器指示容器中的“前一個(gè)”元素。不過(guò)，在此存在非對(duì)稱性，自減算法首先檢查底層list迭代器是否是當(dāng)前桶的開(kāi)始迭代器。如果不是就可以自減。否則，代碼要檢查當(dāng)前桶之前的第一個(gè)非空桶。如果找到

18、了這樣一個(gè)非空桶，list迭代器必須設(shè)置為指示桶中的最后一個(gè)元素，即對(duì)末尾迭代器減1。如果沒(méi)有找到非空桶，自減就是非法的，所以代碼的行為是未定義的。　　在實(shí)現(xiàn)中，increment()和decrement()都訪問(wèn)了hashmap類的protected成員。因此，hashmap類必HashIterator是一個(gè)friend類。　　Const迭代器：對(duì)元素

19、提供只讀訪問(wèn)。　　迭代器typedef和訪問(wèn)方法：　　Begin() end():如果散列表中沒(méi)有元素就可返回末尾迭代器。　　關(guān)聯(lián)容器的typedef需求：　　我們的實(shí)現(xiàn)還包括一個(gè)mapped_type 的typedef，因?yàn)閙ap容器就提供了這樣一個(gè)typedef。Va

20、lue_compare并沒(méi)有實(shí)現(xiàn)為一個(gè)typedef，而是作為一個(gè)嵌套類定義?？梢砸圆捎昧硗庖环N做法，此類可以是hashmap的一個(gè)friend類，但這個(gè)定義要遵循標(biāo)準(zhǔn)中所給出的map定義。Value_compare類的用途是對(duì)兩個(gè)元素的鍵調(diào)用比較函數(shù)。　　關(guān)聯(lián)容器的方法需求　　重載自增和自減操作：

21、;　　不帶參數(shù)的為前綴版本，帶int參數(shù)的為后綴版本　　源代碼　　//DefaultHash.h　　#ifndef DEFAULTHASH_H　　#define DEFAULTHASH_H

22、　　#include <string>　　#include <stdexcept>　　using namespace std;　　template<typename T>　　class DefaultHash</

23、p>　　{　　public:　　/** Default constructor */　　DefaultHash(int numBucket=101) throw (invalid_argument);</

24、p>　　int hash(const T& key) const;　　int numBuckets() const {return mNumBuckets;}　　/** Default destructor */　　virtual ~DefaultHash();</p&g

25、t;　　protected:　　int mNumBuckets;　　};　　template<>　　class DefaultHash<string><p&g

26、t;　　{　　public:　　DefaultHash(int numBuckets=101) throw (invalid_argument);　　int hash(const string& key) const;</p

27、>　　int numBuckets() const {return mNumBuckets;}　　protected:　　int mNumBuckets;　　};　　#include "Defau

28、ltHash.cpp"　　#endif // DEFAULTHASH_H　　//HashIterator.h　　#ifndef HASHITERATOR_H　　#define HASHITERATOR_H　　#inclu

29、de <vector>　　#include <list>　　#include <iterator>　　using namespace std;　　//前向引用聲明<p&

30、gt;　　template <typename Key,typename T,typename Compare,typename Hash>　　class hashmap;　　/**　　* \class HashIterator<p&

31、gt;　　* \tparam Key 鍵類型　　* \tparam T 要映射的類型　　* \tparam Compare 比較器　　* \tparam Hash hash函數(shù)　　* \extends std::iterator&

32、lt;b>　　*/　　template <typename Key,typename T,typename Compare,typename Hash>　　class HashIterator:public std::iterator<std::bidirectional_iterator_tag,pair&l

33、t;const Key,T> >　　{　　friend class hashmap<Key, T, Compare, Hash>;/*! a friend class*/　　public:&

34、lt;p>　　HashIterator();/**< Default constructor */　　HashIterator(int bucket,typename list<pair<const Key,T> >::iterator listIt,　　const hashmap<Key,T,Compare,H

35、ash>* inHashmap);/**< overload constructor */　　pair<const Key,T>& operator*() const; /**< an overload operator *.Details.*/　　pair<const Key,T>* operator

36、->() const;/**< an overload operator ->.Details.*/　　HashIterator<Key,T,Compare,Hash>& operator++();　　const HashIterator<Key,T,Compare,Hash> operator++(in

37、t);　　HashIterator<Key,T,Compare,Hash>& operator--();　　const HashIterator<Key,T,Compare,Hash> operator--(int);　　bool operator==(const HashIter

38、ator& rhs) const;　　bool operator!=(const HashIterator& rhs) const;　　~HashIterator();　　protected:　　int mBucket;<p&

39、gt;　　typename list<pair<const Key,T> >::iterator mIt;　　const hashmap<Key,T,Compare,Hash>* mHashmap;　　void increment();　　void decrement();&l

40、t;/p>　　};　　#include "HashIterator.cpp"　　#endif // HASHITERATOR_H　　//hashmap.h　　#ifndef HASHMA

41、P_H　　#define HASHMAP_H　　#include "DefaultHash.h"　　#include <list>　　#include <vector>　　#includ

42、e <stdexcept>　　#include "HashIterator.h"　　using namespace std;　　template <typename Key,typename T,typename Compare,typename Hash></p

43、>　　class HashIterator;　　/**　　* \class hashmap　　* \tparam <Key>{鍵類型}　　* \tparam <T> {要映射的類型}

44、　　* \tparam <Compare> {比較器}　　* \tparam <Hash> {hash函數(shù)}　　* \extends std::iterator　　*/

45、　　template<typename Key,typename T,typename Compare=std::equal_to<Key>,　　typename Hash=DefaultHash<Key> >　　class hashmap　　{</b&

46、gt;　　public:　　/**　　* \var typedef Key key_type　　* \brief 鍵類型　　*/<

47、/b>　　typedef Key key_type;　　/**　　* \var typedef T mapped_type　　* \brief 被映射的元素類型　　*/

48、　　typedef T mapped_type;　　/**　　* \var typedef pair<const Key,T> value_type　　* \brief 值類型&

49、lt;p>　　*/　　typedef pair<const Key,T> value_type;　　/**　　* \var typedef pair<const Key,T> reference</p&

50、gt;　　* \brief 值的引用類型　　*/　　typedef pair<const Key,T>& reference;　　/**　　* \var

51、typedef pair<const Key,T> const_reference　　* \brief 只讀的值的引用類型　　*/　　typedef const pair<const Key,T>& const_reference;</p

52、>　　/**　　* \var typedef size_t size_type　　* \brief 元素的大小類型　　*/　　typedef size_t size_t

53、ype;　　/**　　* \var typedef ptrdiff_t difference_type　　* \brief 元素的指針運(yùn)算結(jié)果類型　　*/

54、　　typedef ptrdiff_t difference_type;　　/**　　* \var typedef HashIterator<Key,T,Compare,Hash> iterator　　* \brief 元素的迭代器類型&l

55、t;p>　　*/　　typedef HashIterator<Key,T,Compare,Hash> iterator;　　typedef HashIterator<Key,T,Compare,Hash> const_iterator;<b

56、>　　/**　　* \class value_compare　　* \extends binary_function　　* \brief 用于比較兩個(gè)value_type的類　　* 關(guān)聯(lián)容器需要定義這個(gè)類

57、　　*/　　class value_compare:public binary_function<value_type,value_type,bool>　　{　　friend class hashmap<Key,T,Co

58、mpare,Hash>;　　public:　　bool operator()(const value_type& x,const value_type& y)const　　{

59、　　return comp(x.first,y.first);　　}　　protected:　　Compare comp;　　value_compare(Compare c):comp(c){}

60、;　　};　　friend class HashIterator<Key, T, Compare, Hash>;　　iterator begin();　　iterator end();　　const_iterator be

61、gin() const;　　const_iterator end() const;　　typedef Compare key_compare;　　/**< brief overload constructor*/　　explicit hashmap(const Co

62、mpare& com=Compare(),const Hash& hash=Hash())　　throw (invalid_argument);　　/**< a template method as constructor */　　template<class InputIterato

63、r>　　hashmap(InputIterator first,InputIterator last,　　const Compare& comp=Compare(),const Hash& hash=Hash())　　throw (invalid_argument);

64、　　/**< deconstructor */　　~hashmap();　　/**< copy constructor */　　hashmap(const hashmap<Key,T,Compare,Hash>& src);

65、;　　/**< assignment operator */　　hashmap<Key,T,Compare,Hash>& operator=(　　const hashmap<Key,T,Compare,Hash>& rhs);　　/**size method*/<

66、;/p>　　bool empty() const;　　size_type size() const;　　size_type max_size() const;　　/** element operations */　　T& operato

67、r[](const key_type& x);　　pair<iterator,bool> insert(const value_type& x);　　iterator insert(iterator position,const value_type& x);　　templat

68、e<class InputIterator>　　void insert(InputIterator first,InputIterator last);　　void erase(iterator position);　　size_type erase(const key_type& x);&l

69、t;/p>　　void erase(iterator first,iterator last);　　/**< other modify methods */　　void swap(hashmap<Key,T,Compare,Hash>& hashIn);　　v

70、oid clear();　　/**< access method for STL conformity*/　　key_compare key_comp() const;　　value_compare value_comp() const;　　/**< Look

71、up Methods*/　　iterator find(const key_type& x);　　const_iterator find(const key_type& x) const;　　size_type count(const key_type& x) const;</p&g

72、t;　　protected:　　typename list<pair<const Key,T> >::iterator　　findElement(const key_type& x,int& bucket) const;　　typedef list&l

73、t;value_type> ListType;　　vector<ListType>* mElems;　　int mSize;　　Compare mComp;　　Hash mHash;　　};&l

74、t;/b>　　#include "hashmap.cpp"　　#endif // HASHMAP_H　　問(wèn)題分析　　總結(jié)<

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

軟件設(shè)計(jì)模式課程設(shè)計(jì)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

軟件設(shè)計(jì)模式課程設(shè)計(jì)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載