數據結構-手機號碼查詢系統(tǒng)方案

PAGE.學習幫手.數據結構-手機號碼查詢系統(tǒng)方案.學習幫手.報告編號：第5組綜合課程設計報告手機號碼查詢系統(tǒng)指導教師：所在系：電子工程系所學專業(yè)：計算機科學與技術年級：2012級數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第1頁。2014年6數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第1頁。目錄1、課程設計目的和要求 11.1設計目的 11.2設計要求 12、課程設計的主要工作 12.1需求分析 13、課程基本設計說明 13.1概要設計和數據結構選擇 13.2程序具體設計 23.3程序流程圖 24、程序詳細設計 44.1創(chuàng)建 44.2對哈希函數的定義 44.3哈希查找 54.4主函數 65、程序運行結果界面 86、課程設計總結 127、參考文獻 138、附錄 13數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第2頁。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第2頁。摘要本文主要介紹了手機號碼查詢系統(tǒng)，實現(xiàn)對用戶手機號碼、用戶名以及地址的添加、查詢、存儲。程序主要以手機號碼和姓名為關鍵字建立哈希表，并實現(xiàn)查找功能。其中，以手機號為關鍵字建立哈希表時采用線性探測法解決沖突、以姓名為關鍵字建立哈希表時用拉鏈法解決沖突，成功通過設計哈希表實現(xiàn)對用戶的手機號碼、姓名、地址顯示、查詢等功能。通過課程設計,鞏固和加深對結構體、哈希表等理論知識的理解，掌握現(xiàn)實復雜的分析建模和解決方法,掌握包括問題描述、系統(tǒng)分析、設計建模、代碼實現(xiàn)、結果分析等的方法；提高利用計算機分析解決綜合性實際問題的基本能力；鍛煉個人的動手能力，歷練自身素質；提高大家的合作能力。關鍵字：哈希表線性探測法鏈地址法數據結構數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第3頁。1、課程設計目的和要求1.1設計目的本題目最主要的的是設計散列函數，本程序需要設計兩個散列函數才能解決問題，程序需要分別為以號碼和用戶名為關鍵字建立哈希表。所以要分別以用戶名、號碼為關鍵字建立兩個散列函數。1.2設計要求（1）每個記錄有下列數據項：手機號碼、用戶名、地址；（2）從鍵盤輸入各記錄，分別以手機號碼和用戶名為關鍵字建立哈希表（哈希函數自選）；（3）以手機號為關鍵字建立哈希表時采用線性探測法解決沖突、以姓名為關鍵字建立哈希表時用拉鏈法解決沖突；（4）查找并顯示給定手機號碼的記錄；數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第4頁。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第4頁。2、課程設計的主要工作2.1需求分析本題目最主要的要求是設計散列函數，需要設計兩個散列函數才能解決問題。程序需要分別為以號碼和用戶名為關鍵字建立哈希表。所以要分別以用戶名為關鍵字建立哈希表時采用拉鏈法解決沖突、以手機號碼為關鍵字時采用線性探測法解決沖突，具體思路為：（1）對于以號碼為關鍵字的散列函數，是將十一個數字全部相加，然后對20求余。得到的數作為地址。對于以用戶名為關鍵字的散列函數，是將所有字母的ASCLL碼值相加，然后對20求余。（2）要添加用戶信息，以號碼為關鍵字的添加函數即要有實現(xiàn)添加功能的函數，以用戶名為關鍵字的添加函數即要有實現(xiàn)添加結點功能的函數，所以要設計一個必須包括一個輸入結點信息、添加結點的函數；（3）要實現(xiàn)查找函數，則必須包括查找的函數；另外還有一個必不可少的就是運行之后要有一個主菜單，即要設計一個主函數（main()）。（4）測試數據的選擇，程序完成后要對程序進行編譯調試，執(zhí)行后要選擇數據進行測試；3、課程基本設計說明3.1概要設計和數據結構選擇本設計涉及到的數據結構為：哈希表。要求輸入號碼、用戶名、地址三個信息，并要求分別以號碼和用戶名為關鍵字進行查找，所以本問題要用到兩個哈希函數，進行哈希查找。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第5頁。（1）在鏈地址法中，每個結點對應一個鏈表結點，它由三個域組成，而由于該程序需要分別用電話號碼和用戶名為關鍵字建立哈希表，所以該鏈表結點它是由四個域組成，鏈地數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第5頁。name[20]num[20]address[30]next其中name[20]和num[20]是分別為以號碼和用戶名為關鍵字域，存放關鍵字（key）；address[30]的數據域，用來存儲用戶的地址。Next指針是用來指向下一個結點的地址。（2）在線性探測法中，先輸入關鍵字，根據計算哈希地址的函數，求得哈希地址。根據哈希地址找到哈希地址對應的關鍵字，看哈希地址對應的關鍵字是否與所查找的關鍵字相同。若不同，則將哈希地址加一，直到找到關鍵字為止。3.2程序具體設計本系統(tǒng)分為六個個模塊，分別是主函數，增加用戶、查找記錄、號碼顯示、姓名顯示。下面就每個功能進行詳細說明：（1）主函數：設計用戶登錄界面（包括增加、顯示、查詢、退出）。（2）增添用戶：選擇增加用戶數量，再輸入對應數量的用戶姓名，住址，號碼（3）查找記錄：分為按姓名查詢和按號碼查詢，并分別調用自己的輸入法。按姓名查詢是以姓名為關鍵字的哈希表的查找函數計算哈希地址，并進行判斷，當查找的關鍵字與利用該關鍵字求得的哈希地址一致時輸出該用戶所有信息，否則繼續(xù)查找，直至找到。號碼查詢是以手機號碼為關鍵字的哈希表的查找函數計算哈希地址，并進行判斷，如果元素不在該位置，將元素后移再判斷遇到空格表示該元素不存在，最后返回查找到的哈希地址。（4）姓名顯示：以姓名為關鍵字的哈希函數計算姓名中每個字符的ASCII碼值相加姓名為關鍵字創(chuàng)建哈希表計算哈希地址，采用拉鏈法解決沖突。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第6頁。（5）號碼顯示：以手機號碼為關鍵字的哈希函數計算號碼中每個字符的ASCII碼值相加，號碼為關鍵字創(chuàng)建哈希表并計算哈希地址，采用線性探測法數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第6頁。3.3程序流程圖數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第7頁。（1）本程序設計是運用哈希表來解決問題，其中運用了許多數組和鏈表中的基本操作，運用C語言程序編寫程序，創(chuàng)建哈希表，以及哈希函數的實現(xiàn)等基本功能，同時運用除留余數求得哈希地址，線性探測法以及拉鏈法解決沖突，在程序設計成功的基礎上，進一步深化理解哈希表的作用和實現(xiàn)原理。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第7頁。開開始Menu（）主菜單輸入選擇選擇1按號碼查找輸入按姓名查找輸入輸出結果輸出結果選擇2選擇3選擇4選擇5選擇5按號碼顯示號碼散列結果按姓名顯示退出系統(tǒng)return0按號碼查找按姓名查找姓名散列結果號碼散列結果結束添加用戶姓名散列結果Main()初始化數組并為其動態(tài)分配內存空間初始化散列鏈表并為其動態(tài)分配內存空間數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第8頁。圖3-3程序基本流程圖 數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第8頁。4、程序詳細設計4.1創(chuàng)建************************程序部分源代碼*************************創(chuàng)建數組typedefstruct{ charname[20];charaddress[30];charnum[20];}Record;RecordInf[M];RecordH[M];創(chuàng)建結點structnode{charname[20];charaddress[30];charnum[20];node*next;};node**nam;數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第9頁。typedefnode*mingzi數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第9頁。4.2對哈希函數的定義本程序要設計兩個hash（）函數，分別對應電話號碼和用戶名。本設計中對散列函數選擇的是除留余數法，即對關鍵字進行模運算，將運算結果所得的余數作為關鍵字（或結點）的存儲地址，即H（key）=keymodp,本設計中p取19,然后將計算出來的數作為哈希地址賦給key。具體方法如下：以號碼為關鍵字建立哈希函數hash(charnum[20)。以用戶名為關鍵字建立哈希函數hash2(charname[20])。利用強制類型轉換，將用戶名的每一個字母的ASCLL碼值相加并且除以19后的余數。將計算出來的數作為該結點的地址賦給key2。************************程序部分源代碼*************************inthash(charnum[20]){ inti=0; intb=0; while(num[i]!='\0') {b=b+num[i];i++;} b=b%19; return(b);}voidhash2(charname[20]) {數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第10頁。inti=1;數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第10頁。key2=(int)name[0];while(name[i]!=NULL) {key2+=(int)name[i];i++;}key2=key2%19;}4.3哈希查找想要實現(xiàn)查找功能，同樣需要兩個查找函數，無論以用戶名還是以號碼為關鍵字，首先，都需要利用hash函數來計算出地址。再通過比對，如果是以號碼為關鍵字，比較其號碼是否相同，如果相同則輸出所有信息，如果以用戶名為關鍵字，則比較用戶名是否相同，如果相同則輸出該結點的所有信息。如果找不到與之對應相同的，則輸出“無此記錄”。************************程序部分源代碼*************************intfind(RecordH[],charnum[20]){ intw,key=0;key=hash(num);while(strcmp(num,H[key].num)!=0) { 數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第11頁。 key++;數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第11頁。 if(strcmp(H[key].num,NULLKEY)==0) { printf("查找號碼不存在\n"); return-1; break; } }returnkey;}voidfind2(charname[20]){ hash2(name);node*q=nam[key2]->next;while(q!=NULL) { if(strcmp(name,q->name)==0)break;q=q->next; }if(q) printf("\t用戶名:\t%s\n\t地址:%s\n\t號碼:%s\n",q->name,q->address,q->num);數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第12頁。elseprintf("無此記錄\n");數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第12頁。}4.4主函數本程序需要創(chuàng)建一個主菜單和一個主函數，主菜單便于用戶的使用，主函數中，包括所有功能對應的數值，使之和主菜單相對應。************************程序部分源代碼*************************intmenu_select(){ intc; do{system("cls");printf("**************************\n");printf("**************************\n");printf("*****手機號碼查詢系統(tǒng)****\n");printf("*1.增添用戶*\n");printf("*2.按號碼顯示*\n"); printf("*3.按姓名顯示*\n");printf("*4.按號碼查找*\n");printf("*5.按姓名查找*\n");printf("*6.結束程序*\n");printf("**************************\n");printf("請選擇您要運行的選項按(1-6):");數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第13頁。scanf("%d",&c);數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第13頁。getchar(); }while(c<1||c>6); return(c);}菜單函數主要有以下功能：1.增添用戶2.按號碼顯示 3.按姓名顯示4.按號碼查找5.按姓名查找6.結束程序至此，就解決了哈希表的設計與實現(xiàn)算法可能出現(xiàn)的各種問題，那么根據以上思路以及對問題的分析和對出現(xiàn)情況的解決則可以寫出源程序。5、程序運行結果界面1）菜單主界面數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第14頁。2）新增用戶界面數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第14頁。3）按號碼查詢輸入界面4）按號碼顯示界面數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第15頁。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第15頁。5）按號碼查詢數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第16頁。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第16頁。6）按姓名查詢輸入界面7）按姓名顯示界面數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第17頁。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第17頁。8）按姓名查詢界面數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第18頁。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第18頁。9）退出界面6、課程設計總結1、語法錯誤及修改：程序是分塊寫的,調試時可以使用分步調試的方式進行,以便能查找看程序是在哪出錯了。本算法使用了鏈表結構和鏈地址法解決沖突的問題，在以姓名為關鍵字的哈希表中要注意涉及ASCLL碼的類型轉換，要注意輸出不能是“%d”，否則不能輸出結果。編寫程序時要多注意程序中各種指針的使用，還有各類變量的定義，函數的使用。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第19頁。2、邏輯問題修改和調整：鏈表結構方法雖然方便了運行，但是增加了對算法過程的認識難度。在本程序中每一個函數中都需要涉及到指針的操作。所以需要仔細分析函數中的指針指向。在插入結點，查找結點時尤為突出。對于主菜單和主函數的對應，一定要一致，這樣才能保證運行時不會出錯。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第19頁。3、時間，空間性能分析：散列法本質上是一種通過關鍵字直接計算存儲地址的方法。在理想情況下，散列函數可以把結點均勻地分布到散列表中，不發(fā)生沖突，則查找過程無需比較，其時間復雜度O（n）=1。散列法的查找性能取決于3個因素：散列函數、沖突處理方法和填充因子。采用鏈地址法，可以從根本上杜絕“二次聚集”的發(fā)生，從而提高散列表的均勻度，提高查找性能，不過也會“浪費”一部分散列表的空間。當散列函數和沖突處理辦法固定時，散列法的查找性能就取決于散列表的填充因子。填充因子a=表中已有的結點數/表的長度。填充因子a標志表的添滿程度。很顯然，a越小則發(fā)生沖突的機會就越??；反之，a越大沖突的機會就越大，查找的性能也就越低。哈希表鏈地址法查找成功的平均查找長度SNc=1+a/2。鏈地址法查找不成功的平均查找長度Un滿足：Unc=a+e-a.由以上可以看出，散列表的平均查找長度是填充因子的函數，和散列表的長度沒有關系，因此在實際應用中，我們應該選擇一個適當的填充因子，以便把平均查找長度控制在一個盡量小的范圍內。4、人員分工：組長王敏編寫有關增加的函數和創(chuàng)建哈希表的函數，整個程序的運行及調試工作。組員韋蕾項目報告匯總和修改組員張雪妮編寫有關顯示的函數組員楊丹編寫有關查詢的函數和計算哈希地址的函數組員熊佳惠編寫菜單和主函數所有組員在編寫過程中都認真負責，體現(xiàn)了團隊精神，每個人都有明確的分工，都參加了項目報告的撰寫，達到了預期團隊合作的效果。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第20頁。5、通過這次課程設計,我們大家鞏固和加深了對哈希表等理論知識的理解；提高利用計算機分析解決綜合性實際問題的基本能力；鍛煉個人的動手能力，歷練自身素質；提高大家的合作能力。掌握實現(xiàn)復雜問題的分析建模和解決方法；也提高了對書寫報告的規(guī)范性數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第20頁。7、參考文獻[1]嚴蔚敏.數據結構（C語言版）.北京：清華大學出版社，2007版.[2]譚浩強、張基溫編著.《C語言程序設計教程》(第3版).北京：高等教育出版社，2006年[3]李春葆，數據結構題集.北京：清華大學出版社，1992年2月第一版。8、附錄程序代碼如下：#include<stdio.h>#include<string.h>#include<stdlib.h>#defineM20#defineNULLKEY"\0"#defineNULL0#defineINFEASIBLE-1typedefstruct{ charname[20];charaddress[30];charnum[20];}Record;RecordInf[M];//定義輔助數組為全局變量RecordH[M];//定義哈希表為全局變量unsignedintkey2;structnode//建結點每個結點包括用戶姓名、地址、電話號碼、以及指向下一個結點的指針數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第21頁。{數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第21頁。charname[20];charaddress[30];charnum[20];node*next;};typedefnode*mingzi;//typedef可以為一個已有的數據類型聲明多個別名，這里為該類型聲明了一個指針node**nam;intmenu_select()/*菜單函數*/{ intc; do{system("cls");/*運行前清屏*/printf("**************************\n");printf("*****手機號碼查詢系統(tǒng)****\n");printf("*1.增添用戶*\n");printf("*2.按號碼顯示*\n"); printf("*3.按姓名顯示*\n");printf("*4.按號碼查找*\n");printf("*5.按姓名查找*\n");printf("*6.結束程序*\n");printf("**************************\n");printf("請選擇您要運行的選項按(1-6):");數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第22頁。scanf("%d",&c);/*讀入選擇*/數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第22頁。getchar(); }while(c<1||c>6); return(c);/*返回選擇*/}inti=0;intadd()//增加用戶{ printf("請輸入名字\n"); scanf("%s",Inf[i].name); printf("請輸入地址\n"); scanf("%s",Inf[i].address); printf("請輸入號碼\n");scanf("%s",Inf[i].num); i++; returni;}inthash(charnum[20])//以號碼為關鍵字的哈希函數{ inti=0,b=0; while(num[i]!='\0')//計算手機號碼中每個字符的ASCII碼值相加 { b=b+num[i]; i++;//哈希地址 }數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第23頁。 b=b%19;//除留余法求數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第23頁。 return(b);}voidinput(RecordInf[M],intm,RecordH[M])//以手機號碼為關鍵字創(chuàng)建哈希表{ intj,key=0; for(j=0;j<m;j++) { key=hash(Inf[j].num);//計算哈希地址 while(1) { if(strcmp(H[key].num,NULLKEY)==0)//判斷該位置是否為空，為空就把輔助數組中的元素存到該位置 { strcpy(H[key].name,Inf[j].name); strcpy(H[key].num,Inf[j].num); strcpy(H[key].address,Inf[j].address); break; } else key++;//如果不為空，采用線性探測法，將元素后移,解決沖突 } }}數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第24頁。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第24頁。voidlist(RecordH[M])//以手機號碼為關鍵字的哈希表的輸出函數{ inti; for(i=0;i<20;i++) { if(strcmp(H[i].num,"\0")!=0) { printf("\t用戶名:%s\n\t地址:%s\n\t號碼:%s\n",H[i].name,H[i].address,H[i].num); } }}intfind(RecordH[],charnum[20])//以手機號碼為關鍵字的哈希表的查找函數{ intkey=0;key=hash(num);//計算哈希地址while(strcmp(num,H[key].num)!=0)//如果元素不在該位置，將元素后移再判斷 { key++; if(strcmp(H[key].num,NULLKEY)==0)//遇到空格表示該元素不存在 { printf("查找號碼不存在\n"); return-1;數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第25頁。 break;數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第25頁。 } }returnkey;//返回查找到的哈希地址}node*input2()//輸入節(jié)點信息，建立結點，并將結點的next指針指空{ node*temp;temp=newnode;//new的功能是動態(tài)分配內存，語法形式：new類型名T（初值列表temp->next=NULL;printf("請輸入姓名:\n");scanf("%s",temp->name);printf("輸入地址：\n");scanf("%s",temp->address);printf("輸入電話：\n");scanf("%s",temp->num);returntemp;//對于指針類型返回的是地址}voidhash2(charname[20])//哈希函數以用戶名為關鍵字建立哈希函數 //利用強制類型轉換，將用戶名的每一個字母的ASCLL碼值相加并且除以20后的余數{ inti=1;key2=(int)name[0];數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第26頁。while(name[i]!=NULL) { key2+=(int)name[i];i++; }key2=key2%19;}voidcreate()//新建節(jié)點{ inti;nam=newmingzi[20];//動態(tài)創(chuàng)建對象數組for(i=0;i<20;i++) { nam[i]=newnode;nam[i]->next=NULL; }}intapend()//添加節(jié)點{ node*newname;newname=input2();newname->next=NULL;hash2(newname->name);//利用哈希函數計算出對應關鍵字的存儲地址數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第27頁。newname->next=nam[key2]->next;//利用用戶名為關鍵字插入,采用頭插入法數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第27頁。nam[key2]->next=newname;//是采用鏈地址法，拉鏈法處理沖突的散列表結構return0;}voidlist2()//按姓名顯示哈希表{ inti;node*p;for(i=0;i<20;i++) {p=nam[i]->next;while(p) { printf("\t用戶名:\t%s\n\t地址:%s\n\t號碼:%s\n",p->name,p->address,p->num);p=p->next; } }}voidfind2(charname[20])//在以用戶名為關鍵字的哈希表中查找用戶信息{ hash2(name);node*q=nam[key2]->next;while(q!=NULL) {數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第28頁。 if(strcmp(name,q->name)==0)數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第28頁。break;q=q->next; }if(q) printf("\t用戶名:\t%s\n\t地址:%s\n\t號碼:%s\n",q->name,q->address,q->num);elseprintf("無此記錄\n");}intmenu()/*菜單函數*/{ intc; do{system("cls");/*運行前清屏*/printf("**************************\n");printf("*******輸入方式選擇*******\n");printf("*1.按號碼查詢輸入*\n");printf("*2.按姓名查詢輸入*\n");printf("**************************\n");printf("請選擇您要運行的選項按(1-2):");scanf("%d",&c);/*讀入選擇*/getchar(); }while(c<1||c>2); return(c);/*返回選擇*/}數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第29頁。數據結構-手機號碼查詢系統(tǒng)方案全文共34頁，當前為第29頁。voidmain()//主函數{ charname[20],num[20]; intm,n,j,w,k; create(); while(1) { switch(menu