《哈希表》课程设计报告(2)

int CurrentSize,TableSize; //当前深度以及表的容量 string ht[DefaultSize]; //哈希表存储数组 int info[DefaultSize]; //状态数组

int FindPos(int key,string value) const; //散列函数：计算初始的散列地址

的属性（Active,Empty,Delected） }

/**使用线性探测法搜索 **/

int HashTable::FindPos(int key,string value) const{

//搜索一个散列表中关键码与key匹配的元素，搜索成功，则函数返回改元素的位置 //否则返回插入点（如果有足够空间的话）

for(int i=0;i<TableSize;i++) {

ht[i] = ' '; info[i] = Empty; }

int address= key % divitor;

数据结构散列表(哈希表)课程设计报告及源代码

//找到

do{

if(info[j]==Empty||info[j]==Deleted||(info[j]==Active&&ht[j]==value)){t1++;return j;}

else { j=(j+1) % TableSize; t1++; } //当做循环表处

理，找出下一个空地址

}while (j != address);

return j; //转一圈回到起点，表已满，失败

} //t1在这个函数体里面增加的量δt1为某一元素探查的次数

bool HashTable::Search(int key,string value){

//使用线性探测在哈希表ht（每个地址容纳一个元素）中搜索word。如果word在表中存在，

//则函数返回true，并用引用参数value返回找到的元素；如果word不在表中，则返回false。 }

int Calculate(string s){

//key计算函数：word前5个字符的ASCII码 + 单词长度 //不足5个字符的word，用所有字符的ASCII码 + 单词长度

int k=0,len; len=s.length(); if(len<5){

for(unsigned int i=0;i<s.length();i++) k+=(int)s[i]; }

int temp=t1;

int i = FindPos(key,value);

if(value == ht[i]) {cout<<"此单词在 "<<i<<" 位置";t1=temp;return true;} else {t1=temp;return false;}

数据结构散列表(哈希表)课程设计报告及源代码

}

k+=len; return k;

for(int i=0;i<=4;i++) k+=(int)s[i]; }

int HashTable::Insert(string value){

//在ht表中搜索value。若找到则不再插入；若未找到，但表已满，也不再插入，并返回false。

//若找到的位置标志是Empty或Deleted,不论是表是否已满都插入，返回true。 }

bool HashTable::Remove(int key ,string value){

//在ht表中删除元素word,若表中找不到word,或虽然找到word，但它已经逻辑删除过

int key = Calculate(value); //计算函数：抽取关键码 int i = FindPos(key,value); //地址计算 int flag=0; do{

if(info[i] != Active){ //该地址未被存放，存放新元素

ht[i] = value; info[i] = Active; getInfo(i); CurrentSize++; flag = 1; break; }

if(info[i] == Active && ht[i] == value)

{ cout<<"表中已有此元素，不用在插入！"<<endl; flag = -1;t1--;break;} if(info[i] == Active && ht[i] !=value) i++;

}while(i<TableSize);

if(i>=TableSize) { cout<<"表已满，不能插入！"<<endl; t1--;} return flag;

数据结构散列表(哈希表)课程设计报告及源代码

//则返回false，否则在表中删除元素word,返回true，并在引用参数value中得到它

int temp=t1;

int i = FindPos(key,value);

if(info[i] == Active && ht[i] == value){ //找到要删元素，且是活动元素 }

else { cout<<"找不到这个元素或者这个元素已经被删除过。"<<endl;t1=temp;return

info[i] = Deleted; CurrentSize--; //做删除标志，并不是真正的物理删除 cout<<"元素已被删除"<<endl; getInfo(i);

t1=t1-2*(t1-temp); //t1-temp为这个元素的探查次数（δt1） return true; //删除成功

false; } //删除失败,t1不变 }

void HashTable::makeEmpty(){ }

void getSize(HashTable HT){ }

void HashTable::getInfo(int a){

if(HT.CurrentSize>=0 && HT.TableSize>=0){ }

cout<<"CurrentSize: "<<HT.CurrentSize<<endl; cout<<"TableSize: "<<HT.TableSize<<endl;

for(int i=0;i<TableSize;i++) { ht[i] = " ";info[i] = Empty;} CurrentSize = 0; t1=0;

cout<<"散列表已被置空"<<endl;

数据结构散列表(哈希表)课程设计报告及源代码

}

cout<<"HT["<<a<<"]= ";

cout<<" "<<ht[a]<<"\t"; //HT[a]=value if(info[a] == Empty) cout<<"Empty"<<endl; if(info[a] == Active){ cout<<"Active"<<" ";

cout<<"key: "<<Calculate(ht[a])<<endl;} if(info[a] == Deleted) cout<<"Deleted"<<endl;

void ASL(HashTable HT){

int i=0,j=0;

t2=0; //重置t2

do{ i=j; //外层循环控制数组的下标

do{

if([i] != Active) {t2++;break;} //没有活动的元素，表明可以

插入，使用了一次查找次数，t+1

else {t2++;i++;} } //找不到空地址，t自加

while(i<HT.TableSize); j++ ;} //内存循环结束，j自加，进行下一个

元素的计算

while(j<HT.TableSize); cout<<"ASLsucc:"<<t1<<"/"<<HT.CurrentSize<<"\t";

cout<<"ASLunsucc:"<<t2<<"/"<<HT.TableSize<<endl; //最后t的值是所有元素查找不

成功次数的总和 }

②．主程序hash_main.cpp #include <string> #include "HashTable.h"

数据结构散列表(哈希表)课程设计报告及源代码

HashTable HT(29,DefaultSize); // 此处还可以用try...catch语句来捕捉初始化时产生的未知错误

string word; // 输入的单词

void function(){

cout<<"接下来你想要做什么？"<<endl;

cout<<&quo …… 此处隐藏：2443字，全部文档内容请下载后查看。喜欢就下载吧 ……