單鏈表實驗報告正式版

1、單鏈表實驗報告正式版計算機與信息技術學院綜合性、設計性實驗報告專業(yè)：網(wǎng)絡工程年級/班級：大二 20212021學年第一學期課程名稱數(shù)據(jù)結構指導教師李四學號姓名16083240XX張三項目名稱單鏈表的基本操作實驗類型綜合性/設計性實驗時間實驗地點216機房一、實驗目的(1)熟悉順序表的創(chuàng)建、取值、查找、插入、刪除等算法，模塊化程序設計方法。二、實驗儀器或設備(1) 硬件設備：CPU為Pentium 4以上的計算機，內(nèi)存2G以上(2) 配置軟件：Microsoft Windows 7 與 VC+6.0三、總體設計(設計原理、設計方案及流程等) 設計原理：單鏈表屬于線性表，線性表的存儲結構的特點是：

2、用一組任意存儲單元存儲 線性表的數(shù)據(jù)元素，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。因此, 對于某個元素來說，不僅需要存儲其本身的信息，還需要存儲一個指示其直 接后繼的信息。設計方案：采用模塊化設計的方法，設計各個程序段，最終通過主函數(shù)實現(xiàn)各個程序段 的功能。設計時，需要考慮用戶輸入非法數(shù)值，所以要在程序中寫入說可以 處理非法數(shù)值的代碼。設計流程：1. 引入所需的頭文件；2. 定義狀態(tài)值；3. 寫入順序表的各種操作的代碼；寫入主函數(shù)，分別調(diào)用各個函數(shù)。在調(diào)用函數(shù)時，采用if結構進行判斷輸入值是否非法，從而執(zhí)行相應的程序四、實驗步驟(包括主要步驟、代碼分析等)#include<stdio

3、.h> / EOF(=AZ或 F6),NULL#in clude<stdlib.h> / srand( ) ,rand( ),exit (n)#in clude<malloc.h> / malloc( ),alloc( ),realloc()等#in clude<limits.h> / INT_MAX等#in clude<stri ng.h>#in clude<ctype.h>#in clude<math.h> / floor(),ceil( ),abs()#in clude<iostream.h> /

4、cout,ci n#in clude<time.h> / clock( ),CLK_TCK,clock_t#defi ne TRUE1#defi ne FALSE0#defi ne OK1#defi ne ERROR 0#defi ne INFEASIBLE -1#define OVERFLOW -2typedefint Status; / Status 是函數(shù)的類型 ,/其值是函數(shù)結果狀態(tài)代碼，如0K等typedefintElemType;typedefstructLNodeElemType data; /結點的數(shù)據(jù)域structLNode *next; / 結點的指針域LNod

5、e,*LinkList; /LinkList為指向結構體 LNode 的指針類型/ 初始化單鏈表算法步驟：1. 生成新結點作為頭結點，用頭指針 L 指向頭結點。2. 頭結點的指針域置空。Status InitList_L(LinkList &L)L=new LNode;/ 生成新結點作為頭結點，用頭指針L 指向頭結點；L->next=NULL;/ 頭結點的指針域置空return 0K;/ 單鏈表的取值算法步驟：1. 用指針 P 指首元結點，用 j 做計數(shù)器初值賦為 1.2. 從首元結點開始依次順著鏈域 next 向下訪問，只要指向當前結點的指針 p 不為空(NULL,并且沒有到達

6、序號為i的結點，則循環(huán)執(zhí)行以下操作：P指向下一結點；計數(shù)器 j 相應加 1；3. 退出循環(huán)時，如果指針p為空，或者計數(shù)器j大于i ,說明指定的序號i值不合法(i 大于表長n或i小于等于0)，取值失敗返回ERROR否則取值成功，此時j=i時，p所指的 結點就是要找的第 i 個結點，用參數(shù) e 保存當前結點的數(shù)據(jù)域，返回 0K。Status GetElem_L(LinkList L, inti, ElemType &e)LinkList p;int j;p=L->next;j=1;while(p&&j<i)p=p->next;+j;if(!p|j>i

7、) return ERROR;e=p->data;return OK;/ 單鏈表的按值查找 算法步驟：1. 用指針 p 指首元結點。2. 從首元結點開始依次順著鏈域 next 向下查找， 只要指向當前結點的指針 p 不為空， 并且p所指結點的數(shù)據(jù)域不等于給定值e,則循環(huán)執(zhí)行以下操作：p指向下一個結點。3. 返回 p 。若查找成功,p 此時即為結點的地址值,若查找失敗, p 的值即為 NULL。intLocateElem_L(LinkListL,ElemType e)LinkList p;int j;p=L->next;j=1;while(p&&p->data!

8、=e)p=p->next;j+;if(p) return j;else return 0;/ 單鏈表的插入算法步驟：1. 查找結點 ai-1 并由指針 p 指向該結點。2. 生成一個新結點 *s 。3. 將新結點 *s 的數(shù)據(jù)域置為 e。4. 將新結點 *s 的指針域指向結點 ai 。5. 將結點 *p 的指針域指向新結點 *s 。Status ListInsert_L(LinkList &L,inti,ElemType e)LinkList p=L,s;int j=0;while(p&&(j<i-1) p=p->next;+j;if(!p|j>

9、i-1)return ERROR; s=new LNode;s->data=e;s->next=p->next;p->next=s;return OK;/ 單鏈表的刪除1. 查找結點 ai-1 并由指針 p 指向該結點。2. 臨時保存待刪除結點ai的地址在q中，以備釋放。3. 將結點*p的指針域指向ai的直接后繼結點。4. 釋放結點 ai 的空間。Status ListDelete_L(L in kList & L,i nti)LinkList p=L,q;int j=0;while(p->next)&&(j<i-1)p=p->

10、next;+j;if(!p->next)|(j>i-1)return ERROR;q=p->next; p->next=q->next; delete q;return OK;/ 單鏈表的輸出 算法步驟：1. 將指針 p 指向 L 的 next 域。2. 輸出 p 指針的數(shù)據(jù)。3. 將指針 p 后移。4. 循環(huán)第 2,3 步，直到 p 指針為空( NULL)。voidListPrint_L(LinkList L)LinkList p;p=L->next;doprintf("%5d",p->data);p=p->next;whi

11、le(p);void main() inti,n,e; LinkList L; if(InitList_L(L); printf(" 單鏈表創(chuàng)建成功！ n"); printf(" 請輸入您要輸入的數(shù)據(jù)個數(shù) n:n"); scanf("%d",&n);printf(" 請輸入您要輸入的數(shù)據(jù)： n"); for(i=1;i<=n;i+) scanf("%d",&e); ListInsert_L(L,i,e);printf(" 當前單鏈表的內(nèi)容為： n");

12、ListPrint_L(L);printf("n");：n");printf(" 請輸入您要插入的數(shù)據(jù) e 及其位置 i ，使用空格鍵隔開 scanf("%d %d",&e,&i);if(ListInsert_L(L,i,e)printf(" 當前單鏈表的內(nèi)容為： n"); ListPrint_L(L); elseprintf("i 值越界！ n"); printf("n"); printf(" 請輸入您要取的數(shù)據(jù)序號： n"); scan

13、f("%d",&i);if(GetElem_L(L,i,e)printf(”第4位數(shù)據(jù)的值為：dn",i,e);elseprintf("i 值越界！ n");printf(" 請輸入要查找的數(shù)據(jù)值： n"); scanf("%d",&e);if(!LocateElem_L(L,e)printf(" 查無此值 !n");elseprintf(”數(shù)據(jù) 4在 d號位置 n",e,LocateElem_L(L,e);prin tf("請輸入要刪除的數(shù)據(jù)的序號

14、：n");scan f("%d", &i);if(ListDelete_L(L,i)printf("刪除后單鏈表的內(nèi)容為：n");ListPri nt_L(L);elseprin tf("輸入有誤！");prin tf("n ”);五、結果分析與總結1ifi輸人疫螯博扎的就肅十就皿盡佢輸人的菽據(jù)：1314192S芻st塑莊氧的內(nèi)塔負、1314192$ 托悄確人您要桶人的豺Kk賈菖也苜1*使用空稱傳喝幵：61 4當前單璉喪的內(nèi)容為，1314 西 6L 制 75謂瑜人卷萎愍的牡矗申號t據(jù)的值t|!輸人聲査找的數(shù)

15、攆IE：75益惘巧在6號位置詛柿陸的議棉的帶號18H殆后單壘表的內(nèi)客為二1314196175Prfas mv key tc cwitlnw中-白度五筆悽扎崔半；圖1結果分析：如圖1所示，輸入正確數(shù)據(jù)時，程序各個功能執(zhí)行正常。設置輸入數(shù)據(jù)個數(shù)為5, 可以輸入5個數(shù)據(jù)，按回車后，可以顯示我們當前單鏈表中的數(shù)據(jù)內(nèi)容。 繼續(xù)輸 入下一指令：輸入要插入的數(shù)據(jù)及位置，使用空格鍵隔開，回車后，可以看到已 經(jīng)成功插入。繼續(xù)輸入所取的數(shù)據(jù)序號，可以查找該數(shù)據(jù)的值。輸入要查找的數(shù) 據(jù)，可以返回該數(shù)據(jù)的位置。輸入要刪除的數(shù)據(jù)，可以返回刪除該元素后的單鏈 表的內(nèi)容?？偨Y：在單鏈表中，對數(shù)據(jù)元素 ai 來說，除了存儲其

16、本身的信息之外，還需存儲一個 指示其直接后繼的信息。這兩部分信息組成數(shù)據(jù)元素 ai 的存儲映像，稱為結點 它包括兩個域； 其中存儲數(shù)據(jù)元素的域稱為數(shù)據(jù)域； 存儲直接后繼的域稱為指針 域。教師簽名：年 月 日實習報告題目：設計一個哈希表，完成相應的建表和查表程序班級： 1503013 姓名：李睿元 學號： 完成日期：、需求分析1. 假設人名為中國人名的漢語拼音形式；2. 待填入哈希表的姓名共有 30 個，去平均查找長度的上限為 2；3. 哈希函數(shù)用除留余數(shù)法構造，用偽隨機探測再散列法處理沖突；4. 取讀者周圍較熟悉的 30 個人的姓名。、概要設計1. 抽象數(shù)據(jù)類型的定義：（1）人名數(shù)據(jù)表：typ

17、edef struct Nodechar name20;int key;Node,NodeListMAX;（2）哈希表：typedef struct hashtablechar* name;int key;int conflict_time;HashTablehashlen;（3）變量：#define P 61/ 隨機數(shù)值#define MAX 30/ 人數(shù)#define hashlen 61/ 哈希表長2. 主要函數(shù)的實現(xiàn)：（ 1）哈希函數(shù)：int Hash（int key）（2）關鍵字獲得：int GetKey（char str）（3）文件流中讀取姓名：void GetName(NodeL

18、ist &L,int i,FILE* fp)(4) 哈希表的初始化： void InitialHashTable(HashTable &ht) ( 5)偽隨機探測序列的生成： void CreatConfilctArray(int n) (6)哈希表的生成： void CreatHashTable(HashTable &ht,NodeList L,int* n) ( 7)哈希表的查詢：void SearchHashTable(HashTable ht,int* n,char get_name)三、詳細設計#include <stdio.h>#include

19、<stdlib.h>#include <string.h>#define P 61/ 隨機數(shù)值#define MAX 30/ 人數(shù)#define hashlen 61/ 哈希表長typedef struct Nodechar name20;int key;Node,NodeListMAX;typedef struct hashtablechar* name;int key;int conflict_time;HashTablehashlen;int Hash(int key)return key%P;int GetKey(char str)int t=0;char *s

20、=str;while(*s)t += *s;s+;return t;void GetName(NodeList &L,int i,FILE* fp)/*printf(" 請以拼音形式輸入第 %d 個姓名 :",i); scanf("%s",L);Li.key=GetKey(L); */ fscanf(fp,"%s",L);Li.key=GetKey(L);/printf("n");void InitialHashTable(HashTable &ht)

21、int n=0; while(n<hashlen) htn.conflict_time=0; =NULL;htn.key=0;n+;void CreatConfilctArray(int n)/n=(int*)malloc(50*sizeof(int);int i=0,j=0;while(i<50)ni=rand()%(hashlen+1); for(;j<i;j+)if(ni=nj)j=0;ni=rand()%(hashlen+1);continue;i+;void CreatHashTable(HashTable &ht,NodeList L,in

22、t* n)/CreatConfilctArray(n);int i=0;int t; while(i<MAX)t=Hash(Li.key);if(htt.conflict_time=0)=L;htt.conflict_time+;htt.key=Li.key;printf(" 姓名： %s key 值： %d 表內(nèi)存儲位置： %dn",L,Li.key,t); elseint m=0;int d=(t+nm)%hashlen;while(htd.conflict_time!=0)htd.conflict_time+;m+;d=(

23、t+nm)%hashlen;=L;htd.conflict_time+;htd.key=Li.key;printf(" 姓名： %s key 值： %d 表內(nèi)存儲位置： %dn",L,Li.key,d); i+;void SearchHashTable(HashTable ht,int* n,char get_name)/printf(" 請輸入要查詢的姓名： ");/char get_name20;int p=-1;int s_time=1;/scanf("%s",get_name);int

24、h,k;int t;k=GetKey(get_name);t=h=Hash(k);while(1)/*if(hth.conflict_time=0&&hth.key!=k)printf(" 表中未找到無此人！ n");break;else if(hth.key=k)printf(" 已找到 %s ，表內(nèi)存儲位置： %dn",get_name,h);break;elsep+;h=np;*/if(=NULL)printf(" 表中未找到無此人！ n");break;else if(strcmp(hth.na

25、me,get_name)=0)printf(” 已找到 s，表內(nèi)存儲位置：d,查找次數(shù)：dn",get_name,h,s_time);break;elsep+;h=(t+np)%hashlen;s_time+;int main()/printf(" 請輸入建表所需的三十個人名！ n");int i,j;NodeList L;HashTable ht;InitialHashTable(ht);char get_name20=0;int rand_n50; CreatConfilctArray(rand_n);FILE* fp; fp=fopen("name

26、.txt","r");for(i=0;i<30;i+)GetName(L,i,fp);fclose(fp);CreatHashTable(ht,L,rand_n); printf("n");printf(" 哈希表建表完成 ");printf("n");while(1) get_name20=0;printf(" 請輸入要查找的人名 (輸入“ * ”表示結束程序 ):"); scanf("%s",get_name);printf(" 關鍵字： %d

27、",GetKey(get_name); if(strcmp(get_name,"*")=0) break;SearchHashTable(ht,rand_n,get_name); return 0;四、調(diào)試分析1. 哈希表可以在理想情況下不經(jīng)過任何比較，一次存取就能得到所查記錄；2除留余數(shù)法對于 p的選擇很重要，經(jīng)過分析后的選擇是p為小于等于m的最大素數(shù),最終選擇了 61；3.偽隨機探測再散列相較于線性探測再散列或二次探測再散能有效的防止二次堆積。五、用戶手冊1. 本程序的運行環(huán)境為Windows操作系統(tǒng)，執(zhí)行文件為hashtable.exe;2. 本程序的輸入的

28、名字存儲在name.txt文件中； nimte' X卻回網(wǎng)垃你©迂口加軻81州kt *01 iEkijfing3hijgLri：=VlJAIwisubin.dalasidashlliobaiyu-yuL -wfjJigEL：=jcbaiL-icihelLuJLrSlUWQj-njhfiah6.jwha hauy«iulJi flhdohm-jazhautO£Uihahua Lang abaci hukun3. 程序進入后已經(jīng)完成哈希表的構建并進行展示，用戶只需進行相應的查找；禹shta b I c > oxo 口 X姓名；rnujiahmo key值

29、：他表內(nèi)存儲位直；53 姓名huyazhQU keyfi； M3羔內(nèi)存儲位置；39 姓各taosijl ktytf ： 7f5表內(nèi)存佶位置：23 姓名:hahu iey7®: 422表內(nèi)存福位置=56 妲名：along keyfS： 529為為#儲住置：41 弓生占:tn.:一匕: 403表內(nèi)存儲位置 37 矩名：hukun Keytt； 555論為存?zhèn)蛭恢茫?7 夬咯vaugkun key值t 7G3獲內(nèi)存儲位置I 2 如名niwei k刖值：650表再看楠位置一 20 雄名：hacjie kmy值：生議內(nèi)看槁位置；14哈希我建表完 成 請榆入要查找的貝名（WA翼表示結束程序）:w

30、anun 關饉字1 763匕找Slwangkun.衣肉存楮檢瓷2,査挨次藪:9 請輸人宴査找曲人名（輸入"*林”表示結東程序）曲亦讓 關薩字：624 E找到hafljie.表內(nèi)存?zhèn)蛭恢?1也：i找次數(shù)7 諳揄入慕査找的人名（輸入“怦二表示結耒程序）：1利Ei 年裨字：filfi 1=找到1利常i.表內(nèi)存儲侍詈：6.杳找也數(shù)：1 活揄號晉廿的人名（輸入 林"表示結束程序）:hahahaha 艮黔：804夫中未找到無此人！請輸入要查找的人名（輸入S林”裘示結耒程序）:如Process exited after 15* 06 seconds with return value 0

31、祐按莊煮毎推續(xù).六、測試數(shù)據(jù)1.挑選表中已有的十個姓名進行測試(xiaoli,zhua ngshua ngshua ng,laobai,lujia,xiaohei,huyazhou,abao,haojie,taosiji,wa ngkun )iS3lshta bl e. axe XJ皓希表建表完成請輸入要査找的人名（輜入“5林"表示結束程序）:處血i 快縫字；646已找到xiaoli,表內(nèi)存?zhèn)蛭?； 36,査扌好次教：丄 情揃入要查找的人芻帥入"*十羔示結耒程.序）:zhuangshuangshuang 年犍字：19邨己找SJ zhusngshuangshuang,表內(nèi)存儲

32、住置：54*奩棧次數(shù);1 請輸入要查找的人名（輸入表示結東程序）:13心 關龜宇：010匚找到laabal,表內(nèi)梓儲伍晝=6,查般扶數(shù) 諳輸入要查找的人名（輸人S+"表示結東程序）：lujla 關鍵宇：533己找到gjis表內(nèi)時借位置；45,查找橫數(shù)訂 $青輸入要查找的人名（輸入“怦嚴表示結束程序）：訪8說 feiiT. 743 E找SJxiachci,妄內(nèi)希楮信瓷11,查煮歡數(shù)：1 請輸人更查找色人名綸人表示結束程序）:huyahou 罠睡字 S92 tLhcuyazhoti,表內(nèi)存儲檢置=2山查找次數(shù)：1 馬輸入要查找的人名（輸入恤甘”裘示結耒程序）: abac 爆齡，403 E

33、找鈿bg 表內(nèi)存儲位置.37,査找初擻：1 請輸入更査找的人名（輸入林"表示結束程序）rhaojie 丟讎字：624 ESSJhaojie表內(nèi)初留位覚14,沓我次數(shù):1 惰輸入套査找的人名（輸入"伽汁裏示結東程序）：訟曲i 關魂宅：此匕L,找至Itaosi ii,去內(nèi)牡桔和首：23,"找怎対：1 請輸人蘿杳找的人名（論入嗨+*"美示結耒稈序）:wanakun 關饉字：763已找Skangkun,轟內(nèi)存借住置：2（杳我決敵;9 請輸入更查找的人名（輸入吟林"表示結束程序）:卅'rocess exited after 37. 49 seco

34、nds with return value 0與上方的哈希表進行對比完全匹配。性名：mlong kwyd： 52E存慵位置：41fct名:abao .<ey： 403表內(nèi)存儲樓置：37： hukun keytt： 555 羔|為存儘位暨：47 堆名vangk'jn keytf ： 763 表內(nèi)存fStol： 2 姓名！ veiwei tey®： &50辰內(nèi)存儲位萱：20 姓名：hddjin Zy值：624蔻內(nèi)薦儲位置：14哈希表建表気成 請輸入要查找的人名輸入廠表示結耒程序）；xiaoli 悚健646 E找到就譏丘，表內(nèi)冇越位置：36.查找次數(shù);1 請輸入夏查找

35、的人色（輸入叫*"乘F結: zhtianshuangshuang 關健寧；1945 E）f3J zhju&nssh-jangshuan,裘內(nèi)存儲位置；E4,查棧次數(shù) 請輸入要査找的人名（輸入“壯尹表示結耒程序）ll.obai 雜字，616 E找封山此応，表內(nèi)存儲位童.務查我真數(shù)：1 惰輸入要査找的人名輸入S*"表示結克程序）： lujia 底麻立532匕找到luji at表內(nèi)審樹iZ甕45,査找橫數(shù)訂 諳輸入要査找的人名（輸入“*鮎"裘示結東程序）：泊価珀 艮蜒字：743已找到xiaohei,裘內(nèi)右櫓位置：11*査戕次數(shù)：1 信輸入慕杳找的人名（輸入嗨&q

36、uot;'恚示結束稈庫）zhuyazhou 戻每宅I 393 L.找封huyazhou*表慶1右游方曽：3氏杳挨次數(shù);1 請輸入妾查找的人名（輸入&林"表示結束程序）:abao 關鍵字：403已找到abao,表內(nèi)存焉位置：37,查班農(nóng)數(shù):1 請輸入要查找的人名（輸入"*'聿示結束程序）:辰可ie 關鍵字：624已找到haojie,表內(nèi)薦儲位晝；14.查袈次數(shù);1請輸入要查找的人名（輸人“枠忙錄示結束程序）；Uoijishta bl a. &ko- X姓名:&on呂kg/fi： 52孕存儘位宜：41姓若！ abao <eyB： 4

37、03表內(nèi)存?zhèn)湮槐w土 37 姓名:hukun址叭值=555衣伕）存儲（15： 47 姓名：wangle in key： 7總宇:內(nèi)#儲俚置；2 處容；veiwei teyfi； &5Q表內(nèi)存儲位萱20 姓名；Laojie key®； &24表內(nèi)存fit位養(yǎng)：14哈希表建表冗成諳輸入曼査找的人名（輸入“枠”裘示結耒程JT） iacli 天融?。?46 E找到xiaoll,表內(nèi)存?zhèn)蛭粫?36,查枚次數(shù)：1 請揃要查找的£（輸入"*'羔不結束程庫）:shuangshuangshiJing 關讎矣I 1045已K5J zhuangahuangchui

38、ng,表內(nèi)存借吃置；54，查找次數(shù);1 請輸入更查找的人名（輸入表示結束程序）處比M 吳健字，616匚找到均北乩表內(nèi)存儲位星氐查找歡熱1 諳輸入要查找的人名（輸入嗨+嚴裏示結耒程庠）：luj在 蕪讎字：日鵡E找到inji裘內(nèi)存儲位置：軒，査找績數(shù)訂 請揄人要査找的人名（輸人林"表示結束程序）:xiachei 工讎字:743匕找Sllxiaohei.養(yǎng)肉存祜位置i 11.査我枕數(shù)：1 請輸入慕查找的人名（輸入“*桝"恚示結東程序）:huyazhou 關融字=S93已找到huyazhoLi,恚內(nèi)右幡殳直；39,査莪次數(shù)：1 請輸入醫(yī)查找購人名（輸入“林汁恚示結束程序）；區(qū)匚 關

39、齡| 403已找到abao,表內(nèi)存命位貫：3人査我涵;1 清輸扎更亙”的丿名埼卅廠吏活束程刊:加工讓 關饉字：624已找Ijhaojie,表內(nèi)帚位晝：14,查磁次數(shù):1 請輸人要查找的人名（輸入"*'表示結東程并）:t遇i五 2. 選擇5個沒有在表中的名字進行查表操作:(lovetia nqi,tianjiejie,jiwa ng,beij in g,heheda )右名名名名名名名4塵甌雄姓姓繪炷>ytaosi ji key fl： 755 表內(nèi)仔儲位直：23 hahu jceyfi： 422表內(nèi)存?zhèn)蛉蕴J:5b along key©： 529羔為存儲位疊：4

40、1 abao kerjS： 403表內(nèi)存儲位置：37 hukun key值：555羔I為存儲位置：47 vangkun key£： 763表內(nèi)存儲位置：2 weiwei key®： 650表內(nèi)存儲位置：20 haojie key®： 624表內(nèi)存儲位置:14哈希表建表元成二二幢輸入更瑩找的人名（輸入“卅/裘示結束程序艮鍵字，1024 中未找到無此人！陪輸入要査找的人名（輸入“林/表示結耒程序）：tiar.ji9jne 民鍵宇.1052奏中木找到無此人！青揄入要奩找的人名（輸入“*護表示結克程序）：jiwanS 性鍵字，640裘中未找到元此人！陸揄入要査找的人名（輸

41、入"*"表示結東程序）:beijing 民鍵字：728表中未找到元此人！借輸入夢杳找的人名（輸入“*林”耒示結束稈序）：heheda 快鍵字：607表中未找到無此人！ 愴輸入要直找的人名（輸入“*”表示結束程序）:林*Process exited after 22. 06 seconds with return value 0 青按任意鍵絕續(xù) HUNANUNIVERSIT Y課程實習報告題 目： 哈希表學生姓名 唐鵬學生學號 202108080216專業(yè)班級物聯(lián)2班指導老師吳帆完成日期2021年4月2日一、需求分析：1. 本程序來自于圖書館靠書名來檢索想要查找的書問題。2.

42、 本程序要求:(1)根據(jù)輸入建立圖書名稱表，米用創(chuàng)建散列表實現(xiàn)(2)建散列表后，如果想要查找的數(shù)據(jù)在散列表中輸出yes否則輸 出no。二哈希表簡介結構中存在關鍵字和 K相等的記錄，則必定存儲在 f(K)的位置上。由此，不需比較便可直 接取得所查記錄。這個對應關系 f稱為散列函數(shù)(Hash function )，按這個思想建立的表為 散列表。*對不同的關鍵字可能得到同一散列地址，即keyl豐key2，而f(key1)=f(key2 )，這種現(xiàn)象稱沖突。具有相同函數(shù)值的關鍵字對該散列函數(shù) 來說稱做同義詞。*綜上所述，根據(jù) 散列函數(shù)H(key )和處理沖突的方法將一組 關鍵字映象到一個有限的連續(xù) 的

43、地址集(區(qū)間)上，并以關鍵字在地址集中的象” 作為這條記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。這個現(xiàn)象也叫散列桶，在散列桶中，只能通過順序的方式來查找，一般只需要查找三次就可以找到。科學家計算過，當負載因子(load factor)不超過75%，查找效率最高。*若對于關鍵字集合中的任一個關鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)(Un iform Hash function )，這就是使關鍵字經(jīng)過散列函數(shù)得到一個隨機的地址”從而減少沖突。程序設計流程程序思想(一) 哈希函數(shù)unsign

44、ed int hash_BKDE(char *str) 生成映射地址，成為散列表的 編號。(二) 哈希表HashTable:HashTable()通過數(shù)組儲存元素(三) 插入函數(shù)void HashTable:insert(char*c)插入字符串，先計算要插入字符串 生成的映射地址，然后在相應的地址插入，如果沒有空位查找空位插入。(四) 查找函數(shù)bool HashTable:find(char*c)進行查找，先計算要生成字符串的地 址，再到散列表中進行查找比較。(五) 主函數(shù)main ()1) 輸入：輸入散列表內(nèi)容和要查找的數(shù)據(jù)個數(shù)和數(shù)據(jù)2）輸出模塊：散列表查找的結果。3）建散列表并查找：建立

45、散列表并遞歸查找 流程圖插入 inserted三.實驗源程序：#in clude<iostream>#i nclude<cstdlib>#in clude<ctime>using n amespace std;un sig ned int hash_BKDE(char *str)哈希函數(shù)，題目給出 _初始種子 seed 可取 31 131 1313 13131 131313 etc. un sig ned int seed = 131;un sig ned int hash = 0;while (*str)hash = hash * seed + (*str

46、+);return (hash & 0x7FFFFFFF);double k=(double)(rand()%999)/1000;/隨機生成小數(shù)隨機數(shù) 0<k<1unsigned int hash_rand(unsignedint value) /value<2A32 ，將轉化地址轉化為 seeddouble a=k*value;double n=(a-(int)a)*64;/取小數(shù)部分與 2A5 相乘unsigned int seed=(int)n;return seed;unsigned int Hash(char*str) /生成最終的地址映射即計算散列地址位置

47、return hash_rand(hash_BKDE(str);class HashTable/哈希表類public:HashTable();HashTable();void insert(char*c);bool find(char*c);private:char*Arr;/二維數(shù)組用于保存字符串書名int ArrSize;/散列表單元個數(shù)在此為 2A15=32768;HashTable:HashTable()ArrSize=32768;Arr=new char*64;for(int i=0;i<64;i+)Arri=new char100;Arri=NULL;HashTable:HashTable()for(int i=0;i<64;i+)deleteArri;delete Arr;void HashTable:i