數(shù)據(jù)結(jié)構(gòu)實驗9哈希查找

,.1、 實驗?zāi)康模?)復(fù)習(xí)順序查找、二分查找、分塊查找的基本算法及適用場合；謝謝閱讀（2)掌握哈希查找的基本方法及適用場合，并能在解決實際問題時靈活應(yīng)用；感謝閱讀（3)鞏固在散列查找時解決沖突的方法及特點。2、 實驗內(nèi)容（1)哈希表查找的實現(xiàn)（用線性探測法解決沖突）；（2)能對哈希表進行插入和查找。3、 實驗要求（1)分析算法思想，利用C（C++）語言完成程序設(shè)計。精品文檔放心下載（2)上機調(diào)試通過實驗程序。（3)輸入數(shù)據(jù)，進行哈希插入和查找。（4)給出具體的算法分析，包括時間復(fù)雜度和空間復(fù)雜度等。精品文檔放心下載（5)撰寫實驗報告。4、 實驗步驟與源程序⑴實驗步驟本程序共設(shè)計了五個函數(shù)來實現(xiàn)建表，顯示，查找，插入，刪除這幾個主要功能，然后設(shè)計主感謝閱讀函數(shù)，串接程序，并進行調(diào)試，測試實驗結(jié)果。⑵源代碼#include<dos.h>#include<conio.h>#include<math.h>#include<stdio.h>,.#include<stdlib.h>#defineMAXSIZE12 //哈希表的最大容量，與所采用的哈希函數(shù)有關(guān)感謝閱讀enumBOOL{False,True};enumHAVEORNOT{NULLKEY,HAVEKEY,DELKEY};//哈希表元素的三種狀態(tài)，沒有記錄、有記精品文檔放心下載錄、有過記錄但已被刪除typedefstruct{ intelem[MAXSIZE];HAVEORNOTelemflag[MAXSIZE];感謝閱讀

//定義哈希表的結(jié)構(gòu)//數(shù)據(jù)元素體//元素狀態(tài)標志，沒有記錄、有記錄、有過記錄但已被刪除intcount;

//哈希表中當(dāng)前元素的個數(shù)}HashTable;typedefstruct{ intkeynum;

//記錄的數(shù)據(jù)域，只有關(guān)鍵字一項}Record;voidInitialHash(HashTable&);感謝閱讀voidPrintHash(HashTable);精品文檔放心下載BOOLSearchHash(HashTable,int,int&);精品文檔放心下載BOOLInsertHash(HashTable&,Record);感謝閱讀BOOLDeleteHash(HashTable&,Record);謝謝閱讀

//初始化哈希表//顯示哈希表中的所有元素//在哈希表中查找元素//在哈希表中插入元素//在哈希表中刪除元素,.intHash(int); //哈希函數(shù)voidmain(){ HashTableH; //聲明哈希表Hcharch,j='y';intposition,n,k;RecordR;BOOLtemp;InitialHash(H);while(j!='n'){printf("\n\t 哈 希 查 找 ");printf("\n\t**************************************");感謝閱讀printf("\n\t* 1-----建 表 *");感謝閱讀printf("\n\t* 2-----顯 示 *");精品文檔放心下載printf("\n\t* 3-----查 找 *");精品文檔放心下載printf("\n\t* 4-----插 入 *");精品文檔放心下載printf("\n\t* 5-----刪 除 *");謝謝閱讀printf("\n\t* 0-----退 出 *");謝謝閱讀printf("\n\t**************************************");謝謝閱讀,.printf("\n\n\t請輸入菜單號：");scanf("%c",&ch); //輸入操作選項精品文檔放心下載switch(ch){case'1':printf("\n請輸入元素個數(shù)(<10):");謝謝閱讀scanf("%d",&n);printf("\n");for(k=0;k<n;k++){ printf("請輸入第%3d個整數(shù):",k+1);精品文檔放心下載scanf("%d",&R.keynum); //輸入要插入的記錄感謝閱讀temp=InsertHash(H,R);};break;case'2':if(H.count) //哈希表不空謝謝閱讀PrintHash(H);elseprintf("\n散列表為空表!\n");break;case'3':if(!H.count),.printf("\n散列表為空表!\n");

//哈希表空else{ printf("\n請你輸入要查找元素(int):");精品文檔放心下載scanf("%d",&R.keynum);

//輸入待查記錄的關(guān)鍵字temp=SearchHash(H,R.keynum,position);精品文檔放心下載//temp=True:記錄查找成功；temp=False:沒有找到待查記錄謝謝閱讀if(temp)printf("\n查找成功該元素位置是%d\n",position);精品文檔放心下載elseprintf("\n本散列表沒有該元素!\n");精品文檔放心下載}break;case'4':if(H.count==MAXSIZE)謝謝閱讀

//哈希表已滿{printf("\n散列表已經(jīng)滿!\n");break; }printf("\n請輸入要插入元素(int):");感謝閱讀scanf("%d",&R.keynum);

//輸入要插入的記錄temp=InsertHash(H,R);//temp=True:記錄插入成功；temp=False:已存在關(guān)鍵字相同的記錄精品文檔放心下載,.if(temp)printf("\n元素插入成功!\n");elseprintf("\n元素插入失敗，相同元素本散列表已經(jīng)存在!\n");感謝閱讀break;case'5':printf("\n請你輸入要刪除元素(int):");精品文檔放心下載scanf("%d",&R.keynum); //輸入要刪除記錄的關(guān)鍵字精品文檔放心下載temp=DeleteHash(H,R);//temp=True:記錄刪除成功；temp=False:待刪記錄不存在感謝閱讀if(temp)printf("\n刪除成功!\n");elseprintf("\n刪除元素不在散列表中!\n");謝謝閱讀break;default:j='n';}}printf("\n\t歡迎再次使用本程序，再見!\n");精品文檔放心下載},.voidInitialHash(HashTable&H)謝謝閱讀{

//哈希表初始化inti;H.count=0;for(i=0;i<MAXSIZE;i++)H.elemflag[i]=NULLKEY;}voidPrintHash(HashTableH)謝謝閱讀{置

//顯示哈希表所有元素及其所在位inti;for(i=0;i<MAXSIZE;i++)

//顯示哈希表中記錄所在位置printf("%-4d",i);printf("\n");for(i=0;i<MAXSIZE;i++)

//顯示哈希表中記錄值if(H.elemflag[i]==HAVEKEY)感謝閱讀printf("%-4d",H.elem[i]);,.elseprintf("%4c",'');printf("\ncount:%d\n",H.count);感謝閱讀

//顯示哈希表當(dāng)前記錄數(shù)}BOOLSearchHash(HashTableH,intk,int&p)精品文檔放心下載{ //在開放定址哈希表H中查找關(guān)鍵字為k的數(shù)據(jù)元素，若查找成功，以p指示精品文檔放心下載//待查數(shù)據(jù)元素在表中的位置，并返回True；否則，以p指示插入位置，并返回False感謝閱讀intp1;p1=p=Hash(k);while(H.elemflag[p]==HAVEKEY&&k!=H.elem[p])感謝閱讀

//求得哈希地址//該位置中填有記錄并且關(guān)鍵字不相等{ p++;

//沖突處理方法：線性探測再散列if(p>=MAXSIZE)p=p%MAXSIZE;

//循環(huán)搜索if(p==p1)returnFalse;

//整個表已搜索完，沒有找到待查元素}if(k==H.elem[p]&&H.elemflag[p]==HAVEKEY)謝謝閱讀

//查找成功，p指示待查元素位,.置returnTrue;elsereturnFalse; //查找不成功}BOOLInsertHash(HashTable&H,Recorde)謝謝閱讀{ //查找不成功時插入元素e到開放定址哈希表H中，并返回True，否則返回False謝謝閱讀intp;if(SearchHash(H,e.keynum,p)) //表中已有與e有相同關(guān)鍵字的元謝謝閱讀素returnFalse;else{ H.elemflag[p]=HAVEKEY; //設(shè)置標志為HAVEKEY，表示該感謝閱讀位置已有記錄H.elem[p]=e.keynum; //插入記錄精品文檔放心下載H.count++; //哈希表當(dāng)前長度加一returnTrue;}},.BOOLDeleteHash(HashTable&H,Recorde)謝謝閱讀{//在查找成功時刪除待刪元素e，并返回True，否則返回False謝謝閱讀intp;if(!SearchHash(H,e.keynum,p)) //表中不存在待刪元素謝謝閱讀returnFalse;else{ H.elemflag[p]=DELKEY; //設(shè)置標志為DELKEY，表明該元素謝謝閱讀已被刪除H.count--; //哈希表當(dāng)前長度減一returnTrue;}}intHash(intkn){ return(kn%11); } //哈希函數(shù)：H(key)=keyMOD11謝謝閱讀5、