課程設(shè)計(jì)報(bào)告--數(shù)據(jù)哈希表應(yīng)用(編輯修改稿)
2025-02-14 23:25 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 archT::Insert(ElemTypeT e){//插入元素int s。if(count==size)2{ printf(表滿，不能插入!\n)。 return UNSUCCESS。}else{ s=Hash()。 int f。 f=Search(,s)。 if(f) //表中已有和 e的關(guān)鍵字相同的元素,不進(jìn)行插入操作 { printf(該元素已存在，不能插入!\n)。 return UNSUCCESS。 } else { HT[s].key=。 printf(插入成功!\n)。 count++。 return SUCCESS。 }}}本次課程設(shè)計(jì)采用的是除留余數(shù)法構(gòu)造了哈希表，除數(shù)的選擇很重要。如果選得不好，會(huì)造成很多沖突，浪費(fèi)時(shí)間和空間代價(jià)。例如，本次設(shè)計(jì)的哈希表最大長(zhǎng)度為 11，余數(shù)如果取得較小，會(huì)使得一部分元素容易形成堆積，平均搜索長(zhǎng)度變大，而且取余的時(shí)間也會(huì)更長(zhǎng)。本次設(shè)計(jì)處理沖突采用了線性探測(cè)再散列的辦法。相比起同時(shí)閉散列方法的二次探測(cè)再散列來(lái)說(shuō)，優(yōu)點(diǎn)在于功能簡(jiǎn)單易操作性；缺點(diǎn)是當(dāng)數(shù)據(jù)量逐漸加大時(shí)，前者的平均查找長(zhǎng)度會(huì)逐漸比后者大。六、總結(jié)哈希表作為一種存儲(chǔ)與查找的優(yōu)化方式，通過(guò)把關(guān)鍵碼值映射到數(shù)表3中一個(gè)位置來(lái)訪問(wèn)數(shù)據(jù)，以加快查找速度。在日常生活中，哈希函數(shù)的應(yīng)用也是隨處可見。當(dāng)今十分流行的 P2P 數(shù)據(jù)傳輸技術(shù)中一系列的壓縮、打包以及積分標(biāo)準(zhǔn)都應(yīng)用到了 hash 算法設(shè)置?？梢娎霉：瘮?shù)用途之廣。本次程序設(shè)計(jì)中利用“除留余數(shù)法”構(gòu)造哈希函數(shù)，并用“開放定址法”中的“線性探測(cè)再散列”方式處理沖突，選取較為簡(jiǎn)單的整型數(shù)字作為存儲(chǔ)數(shù)據(jù)。通過(guò)此次實(shí)驗(yàn)，我對(duì)哈希表抽象數(shù)據(jù)類型的定義以及構(gòu)造方法有了初步的認(rèn)識(shí)和了解，也為今后編寫更復(fù)雜的應(yīng)用程序提供了新的思想方法與實(shí)現(xiàn)基礎(chǔ)。七、附件（代碼、部分圖表）includedefine SUCCESS 1。define UNSUCCESS 0。define NULLKEY 1。define TableLength 13。define p 13。 // H(key)=key % p typedef int T。template class Tstruct ElemType{T key。//關(guān)鍵字}。template class Tclass LHSearch{private:ElemTypeT *HT。 //開放定址哈希表int count。 //當(dāng)前數(shù)據(jù)元素個(gè)數(shù)int size。 //哈希表長(zhǎng)度public:LHSearch()。 // ~LHSearch()。 //4 void InitHashTable(int n)。// int Hash(T key)。 //計(jì)算哈希地址void Collision(int amp。s)。//沖突,計(jì)算下一個(gè)地址int Search(T key,int amp。s)。//哈希查找int Insert(ElemTypeT e)。//元素插入int Delete(ElemTypeT e)。 //元素刪除void Display()。 //顯示哈希表}。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1