提示：文章寫完后，目錄可以自動(dòng)生成，如何生成可參考右邊的幫助文檔

文章目錄

• 前言
• 一、問題描述
• 二、問題描述
• • （1）選用的散列函數(shù)
  • （2）散列因子
  • （3）解決沖突的方法
• 三、實(shí)驗(yàn)結(jié)果及分析
• • （1）實(shí)驗(yàn)數(shù)據(jù)描述
  • （2）實(shí)驗(yàn)結(jié)果
  • （3）性能分析
• 四、實(shí)驗(yàn)總結(jié)
• 五、源代碼
• • （1）隨機(jī)生成電話號(hào)碼系統(tǒng)代碼
  • （2）電話號(hào)碼查詢系統(tǒng)代碼

---

前言

記錄下上學(xué)期的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)
本電話號(hào)碼查詢系統(tǒng)基于兩種散列方法和兩種解決沖突的方法實(shí)現(xiàn)

---

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

一、問題描述

設(shè)計(jì)散列表，實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)。設(shè)電話號(hào)碼簿長(zhǎng)度為n（0≤n≤10000），系統(tǒng)應(yīng)該實(shí)現(xiàn)如下工作：
⑴ 電話號(hào)碼簿保存在磁盤文件中，每一條電話號(hào)碼記錄包含數(shù)據(jù)項(xiàng)：編號(hào)（唯一），用戶名，通信地址，電話號(hào)碼（手機(jī)號(hào)）
⑵ 創(chuàng)建散列表：系統(tǒng)運(yùn)行時(shí)，讀取磁盤文件的電話號(hào)碼，構(gòu)建散列表，用于查詢。要求：自選散列函數(shù)(至少2種)，自選解決沖突的方法(至少2種)，分別以電話號(hào)碼和用戶名為關(guān)鍵字，建立散列表。
⑶ 查詢：根據(jù)輸入的用戶名，查找并顯示給定用戶的信息。
⑷ 性能分析：
① 計(jì)算并輸出不同散列函數(shù)、不同解決沖突方法的平均查找長(zhǎng)度。
② 通過改變散列因子、改變哈希函數(shù)等方式，改善平均查找長(zhǎng)度：通過數(shù)據(jù)表、柱形圖、折線圖等方式，記錄實(shí)驗(yàn)數(shù)據(jù)的變化情況，對(duì)影響平均查找長(zhǎng)度變化的原因進(jìn)行分析。

---

二、問題描述

（1）選用的散列函數(shù)

①除留余數(shù)法
分析：
ⅰ.以電話號(hào)碼為關(guān)鍵字時(shí)，將字符串類型的電話號(hào)碼轉(zhuǎn)換成long型數(shù)據(jù)，除以表長(zhǎng)，剩下的余數(shù)作為其在散列表中的地址，即pos值。
ⅱ.以姓名為關(guān)鍵字時(shí)，將字符串類型的姓名的每一位上的字母轉(zhuǎn)換成ascii碼，此時(shí)還是內(nèi)容為數(shù)字的字符串，再將字符串轉(zhuǎn)換成long型數(shù)據(jù)，除以表長(zhǎng)，剩下的余數(shù)作為其在散列表中的地址，即pos值。
②折疊法
分析：
ⅰ.以電話號(hào)碼為關(guān)鍵字時(shí)，將字符串類型的電話號(hào)碼，切割成四組數(shù)據(jù)，每組數(shù)據(jù)的個(gè)數(shù)為3 3 3 2，轉(zhuǎn)化成int型數(shù)據(jù)，取第一組數(shù)據(jù)和第三組數(shù)據(jù)、第二組和第四組的逆置數(shù)相加，得到的數(shù)據(jù)取后四位數(shù)，作為其在散列表中的地址，即pos值。
ⅱ.以姓名為關(guān)鍵字時(shí)，將字符串類型的姓名的每一位上的字母轉(zhuǎn)換成ascii碼，此時(shí)還是內(nèi)容為數(shù)字的字符串，再切割成四組數(shù)據(jù)，每組數(shù)據(jù)的個(gè)數(shù)為3 3 3 2，轉(zhuǎn)化成int型數(shù)據(jù)，取第一組數(shù)據(jù)和第三組數(shù)據(jù)、第二組和第四組的逆置數(shù)相加，得到的數(shù)據(jù)取后四位數(shù)，作為其在散列表中的地址，即pos值。

（2）散列因子

散列表的散列因子定義為：α= 填入表中的元素個(gè)數(shù)/散列表的長(zhǎng)度。α是散列表裝滿程度的標(biāo)志因子。由于表長(zhǎng)是定值，α與元素個(gè)數(shù)成正比，所以，α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。
為了探究不同散列因子對(duì)平均查找長(zhǎng)度ASL的影響，在利用線性探測(cè)法解決沖突時(shí)，本實(shí)驗(yàn)中
擬取用 α 的值為 0.85、0.75、0.65、0.55；利用拉鏈法解決沖突時(shí)，本實(shí)驗(yàn)中 α 擬選用 1、1.2、
1.4、1.6。

（3）解決沖突的方法

①線性探測(cè)法
該方法的基本思想是，當(dāng)關(guān)鍵字key的哈希地址p出現(xiàn)沖突時(shí)，順序查看表中下一單元，以p為基礎(chǔ)產(chǎn)生另一個(gè)哈希地址p1,如果p1仍然沖突，再以p為基礎(chǔ)產(chǎn)生p2，……，直到找到一個(gè)不沖突的哈希地址pi，將相應(yīng)元素存入其中。沖突發(fā)生時(shí)，順序查看表中下一單元，，直到找出一個(gè)空單元或者查遍全表。
缺點(diǎn)：容易造成元素聚集，降低查找效率
②拉鏈法
該方法基本思想是將所有的哈希地址為i的元素構(gòu)成一個(gè)同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個(gè)單元中。
優(yōu)點(diǎn)：避免了動(dòng)態(tài)調(diào)整的開銷

---

三、實(shí)驗(yàn)結(jié)果及分析

（1）實(shí)驗(yàn)數(shù)據(jù)描述

1.數(shù)據(jù)集規(guī)模
本實(shí)驗(yàn)擬采用 10000 組聯(lián)系人記錄。每一行記錄一位聯(lián)系人的編號(hào)、姓名、地址、電話號(hào)碼。
文件存儲(chǔ)于FinalDataSet_10000.txt。文件存儲(chǔ)格式如圖 1 所示：

圖1 實(shí)驗(yàn)數(shù)據(jù)集內(nèi)容

2.數(shù)據(jù)集來源
本次實(shí)驗(yàn)的數(shù)據(jù)全部隨機(jī)生成。
數(shù)據(jù)內(nèi)容：
編號(hào)：1-10000，按順序輸出即可；
姓名：三個(gè)英文字母，字符串。隨機(jī)生成0-25的int型數(shù)據(jù)，再通過循環(huán)從char型字母表數(shù)組中利用下標(biāo)讀出并存儲(chǔ)到data數(shù)組的姓名域中去；
地址：長(zhǎng)度不等，字符串。這里使用的城市數(shù)據(jù)僅為20組，每組城市數(shù)據(jù)存儲(chǔ)在Country結(jié)構(gòu)體中，結(jié)構(gòu)體中有city[]，用于存放每組城市名稱，所有的城市數(shù)據(jù)存儲(chǔ)在Country類型的數(shù)組中。隨機(jī)生成0-20的int型數(shù)據(jù)，再通過循環(huán)從Country類型的數(shù)組中利用下標(biāo)讀出并存儲(chǔ)到data數(shù)組的地址域中去。
電話號(hào)碼：11位0-9的數(shù)據(jù)，字符串。根據(jù)一般電話號(hào)碼的規(guī)律，首位都是1，因此其他10位是隨機(jī)生成的。隨機(jī)生成0-9的int型數(shù)據(jù)，再通過循環(huán)從char型數(shù)字表數(shù)組中利用下標(biāo)讀出并存儲(chǔ)到data數(shù)組的電話號(hào)碼域中去；
3.磁盤文件存儲(chǔ)格式：.txt格式。

（2）實(shí)驗(yàn)結(jié)果

1.以電話號(hào)碼為關(guān)鍵字
①哈希函數(shù)為除留余數(shù)法，解決沖突的方法為線性探測(cè)法，查找成功，實(shí)驗(yàn)結(jié)果如圖2、3所示。

圖2 以電話號(hào)碼為關(guān)鍵字查找成功的實(shí)驗(yàn)結(jié)果

圖3 對(duì)應(yīng)在磁盤文件中的數(shù)據(jù)

②哈希函數(shù)為除留余數(shù)法，解決沖突的方法為拉鏈法，查找失敗，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 以電話號(hào)碼為關(guān)鍵字查找失敗的實(shí)驗(yàn)結(jié)果

2.以姓名為關(guān)鍵字
①哈希函數(shù)為除留余數(shù)法，解決沖突的方法為線性探測(cè)法，查找成功，實(shí)驗(yàn)結(jié)果如圖5、6所示。

圖5 以姓名為關(guān)鍵字查找成功的實(shí)驗(yàn)結(jié)果

圖6對(duì)應(yīng)在磁盤文件中的數(shù)據(jù)

②哈希函數(shù)為除留余數(shù)法，解決沖突的方法為拉鏈法，查找失敗，實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 以電話號(hào)碼為關(guān)鍵字查找失敗的實(shí)驗(yàn)結(jié)果

（3）性能分析

①分析填充因子和沖突方法與 ASL 的關(guān)系

表1 在不同的散列因子和解決沖突方法下，查找成功和查找失敗的ASL

圖8 在不同的散列因子和解決沖突的方法下，查找成功的ASL折線圖

圖9 在不同的散列因子和解決沖突的方法下，查找失敗的ASL折線圖

圖10 在線性檢測(cè)法下，不同的散列因子，查找成功和查找失敗的ASL折線圖

圖11 在拉鏈法下，不同的散列因子，查找成功和查找失敗的ASL折線圖

由表1和圖8-11可見，在采用相同的解決沖突的方法時(shí)，ASL隨散列因子增大而變大。當(dāng)解決沖突方法為線性探測(cè)法時(shí)，查找失敗比查找成功的ASL大，且增幅也隨散列因子增大而變大。但當(dāng)解決沖突方法為拉鏈法時(shí)，查找成功比查找失敗的ASL大，且增幅并不隨散列因子增大而改變。
②分析數(shù)據(jù)規(guī)模與 ASL 的關(guān)系

圖12 在散列因子為0.75時(shí)，不同的數(shù)據(jù)規(guī)模與ASL之間的折線圖

在散列因子α為0.75的情況下，進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)如圖12所示。顯然由圖可知，在相同的散列因子的情況下，隨著數(shù)據(jù)規(guī)模的增大，ASL并沒有明顯的變化，數(shù)據(jù)基本都浮動(dòng)在2.5上下。我認(rèn)為數(shù)據(jù)規(guī)模與ASL之間沒有直接的關(guān)系。

---

四、實(shí)驗(yàn)總結(jié)

在測(cè)試了不同的解決沖突辦法、不同的散列因子和不同的數(shù)據(jù)規(guī)模對(duì)ASL的影響后，我得到了以下的結(jié)論：
a．當(dāng)散列因子小于1時(shí)，解決沖突的方法可以選擇線性探測(cè)法。ASL隨著散列因子α的增大而增大，且增幅隨之變大。因此，當(dāng)解決沖突方法為線性探測(cè)法時(shí)，要慎重選擇散列因子α。散列因子α過大，平均查找長(zhǎng)度ASL過大，查找效果差；散列因子α過小，平均查找長(zhǎng)度ASL雖然會(huì)較小，但是需要的存儲(chǔ)空間隨之變大了，因此在設(shè)計(jì)解決沖突方法為線性探測(cè)法的散列表時(shí)，要選擇合適的散列因子α。
b．當(dāng)散列因子大于1時(shí)，解決沖突的方法可以選擇拉鏈法法。ASL隨著散列因子α的增大而增大，但增幅并不隨散列因子α的增大而改變，而是幾乎不變。因此，適當(dāng)選擇拉鏈法的散列因子，可以表現(xiàn)出良好的查找性能。
c．由圖表分析可得，解決沖突方式為拉鏈法受散列因子α的影響較小，解決沖突方式為線性探測(cè)法受散列因子α的影響較大。因此，拉鏈法更為穩(wěn)定，性能更好。
d．數(shù)據(jù)規(guī)模較小時(shí)，解決沖突方式采用線性探測(cè)法、拉鏈法，性能差別都不是很大，均能表現(xiàn)出良好的查找性能，但是當(dāng)數(shù)據(jù)規(guī)模變大的時(shí)候，采用線性探測(cè)法解決沖突的方法會(huì)使沖突增多，此時(shí)采用拉鏈法可以表現(xiàn)出更好的查找性能。
e．在實(shí)際操作的過程中，特別是在處理以姓名為關(guān)鍵字的時(shí)候，我發(fā)現(xiàn)有很多人的名字是重復(fù)的，這種情況在現(xiàn)實(shí)生活中也會(huì)存在，這也是沖突的其中一種方式，因此針對(duì)這種情況，我分不同的解決沖突方法進(jìn)行討論。
①線性探測(cè)法。當(dāng)發(fā)現(xiàn)關(guān)鍵字重復(fù)時(shí)，再次通過線性探測(cè)，在與之重復(fù)的關(guān)鍵字周圍尋找一個(gè)空表，將其填入，即可解決沖突，但要注意，要使用一個(gè)標(biāo)志flag來記錄某關(guān)鍵字重復(fù)的次數(shù)，借助該標(biāo)志flag在查詢關(guān)鍵字時(shí)方便找到所有重復(fù)的元素。
②拉鏈法。當(dāng)發(fā)現(xiàn)關(guān)鍵字重復(fù)時(shí)，直接將該節(jié)點(diǎn)插入散列表的與重復(fù)關(guān)鍵字相同的位置后的頭結(jié)點(diǎn)，即可解決沖突，但這個(gè)方法也需要使用一個(gè)標(biāo)志flag來記錄某關(guān)鍵字重復(fù)的次數(shù)，用來方便找到所有重復(fù)的元素。

---

五、源代碼

（1）隨機(jī)生成電話號(hào)碼系統(tǒng)代碼

#include <stdio.h> #include <time.h> #include <stdlib.h> #include <string.h>#define N 10000 //元素最大個(gè)數(shù) typedef struct {int no; //編號(hào)char name[3];//名字char address[10];//地址char tel[12];//電話號(hào)碼 } NODE; typedef struct {char data[10]; } Country; Country country[10];void creatfile(NODE data[], int *n);//創(chuàng)建磁盤文件f:\resource.dat int isTelRepeated(char tel[]);void initCountry();int main() {NODE DATA[N];int n;creatfile(DATA, &n);return 0; }void creatfile(NODE data[], int *n) {FILE *fp;int i, key, flag;int temp_n;char temp_tel[11];unsigned seed;*n = N;char num[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};char alphabet[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g','h', 'i', 'j', 'k', 'l', 'm', 'n','o', 'p', 'q', 'r', 's', 't','u', 'v', 'w', 'x', 'y', 'z'};//字母表/*char ALPHABET[26] = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H', 'I', 'J', 'K', 'L', 'M', 'N','O', 'P', 'Q', 'R', 'S', 'T','U', 'V', 'W', 'X', 'Y', 'Z'};//字母表*/initCountry();if ((fp = fopen("/Users/xiaoyee/Desktop/數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)作業(yè)/實(shí)驗(yàn)報(bào)告/電話號(hào)碼查詢系統(tǒng)/1/TelDataSet_10000.txt", "w")) == NULL) {printf("can't open the file!\n");exit(0);}seed = time(NULL);srand(seed); //設(shè)置隨機(jī)種子for (i = 0; i < *n;i++) {for (int k = 0; k < 3; k++) {key = rand() % 26;data[i].name[k] = alphabet[key];}data[i].name[3] = '\0';}for (i = 0; i < *n;i++) {key = rand() % 20;for (int k = 0; k < 10; k++) {data[i].address[k] = country[key].data[k];}}for (i = 0; i < *n;) {temp_tel[0] = '1';for (int k = 1; k < 11; k++) {key = rand() % 10;temp_tel[k] = num[key];}temp_tel[11] = '\0';//寫一個(gè)整數(shù)到磁盤文件flag = 1;if (isTelRepeated(temp_tel)) {flag = 0;break;}if (flag) {for (int k = 0; k < 11; k++) {data[i].tel[k] = temp_tel[k];}i++;}}for (i = 0; i < *n; i++) {fprintf(fp, "%d ", i + 1); //寫一個(gè)整數(shù)到磁盤文件fprintf(fp, "%s ", data[i].name); //寫一個(gè)整數(shù)到磁盤文件fprintf(fp, "%s ", data[i].address); //寫一個(gè)整數(shù)到磁盤文件fprintf(fp, "%s\n", data[i].tel); //寫一個(gè)整數(shù)到磁盤文件}fclose(fp); }void initCountry() {FILE *fp;char temp[10];if ((fp = fopen("/Users/xiaoyee/Desktop/數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)作業(yè)/實(shí)驗(yàn)報(bào)告/電話號(hào)碼查詢系統(tǒng)/1/Country_data.txt", "r")) == NULL) {printf("can't open the file!\n");exit(0);}for (int i = 0; i < 20; i++) {fscanf(fp, "%s", temp);for (int j = 0; j < 10; j++) {country[i].data[j] = temp[j];}} }int isTelRepeated(char tel[]) {FILE *fp;char temp_tel[11];if ((fp = fopen("/Users/xiaoyee/Desktop/數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)作業(yè)/實(shí)驗(yàn)報(bào)告/電話號(hào)碼查詢系統(tǒng)/1/TelDataSet_10000.txt", "r")) == NULL) {printf("can't open the file!\n");exit(0);}for (int i = 1; i <= N; i++) {fscanf(fp, "%s", temp_tel);if (strcmp(tel, temp_tel) == 0) {return 1;}}return 0; }

（2）電話號(hào)碼查詢系統(tǒng)代碼

#include <stdio.h> #include <stdlib.h> #include <string.h>#define NIL -1 //定義初始值 #define M 13333 //表長(zhǎng) #define N 10000 //關(guān)鍵字個(gè)數(shù) // α=0.75typedef long keytype; //散列表結(jié)點(diǎn)類型 typedef struct {int no; //編號(hào)char *name;//名字char *address;//地址char *tel;//電話號(hào)碼 } NODE;typedef struct pos {keytype pos;int flag;struct pos *next; } POS;//初始化哈希表，將姓名和電話號(hào)碼初始化！ void init(POS *table);int increment(int i);//某種探測(cè)方法int HASH_1(keytype key, int i);//將某鍵值轉(zhuǎn)換成位置 //在散列表中搜索指定的鍵值 int search_tel(POS *table, char *tel, int *pos);//在散列表中搜索指定的鍵值 int search_name(POS *table, char *name, int *pos);//pos返回鍵值的位置 //將一個(gè)關(guān)鍵字添加到哈希表中（以電話號(hào)碼為關(guān)鍵字） void insert_tel(POS *table_tel, int no, char *name);//將一個(gè)關(guān)鍵字添加到哈希表中（以姓名為關(guān)鍵字） void insert_name(POS *table_name, int no, char *tel);//void insert_pos(POS *table_name, int i, int pos);//創(chuàng)建哈希表（以電話號(hào)碼為關(guān)鍵字） void creat(NODE *htable);//將姓名轉(zhuǎn)化為數(shù)字 long converse_name(char *name);//輸出想要搜索的關(guān)鍵字的相關(guān)信息 void prn(NODE *htable, int no);//輸出哈希表 void prnnn(NODE *htable, POS *table_name, int pos);//成功查找的ASL float success_ASL();//失敗查找的ASL float fail_ASL(); //******************************************************* //除留余數(shù)法作為散列函數(shù)，線性探測(cè)法解決沖突 //*******************************************************void menu();//******************************************************** //主函數(shù) //******************************************************** NODE htable[N];//定義結(jié)點(diǎn)表 POS table_tel[M];//定義哈希表(以電話號(hào)碼為關(guān)鍵字) POS table_name[M];//定義哈希表(以姓名為關(guān)鍵字) int main() {int op;//菜單選擇int i;int pos;char *tel;char *name;init(table_tel); //哈希表初始化init(table_name); //哈希表初始化creat(htable);menu();scanf("%d", &op);printf("----------------------------------------------\n");while (op != 3) {switch (op) {case 1: {tel = (char *) malloc(sizeof(char));printf("請(qǐng)輸入你想要查詢的電話號(hào)碼:");scanf("%s", tel);i = search_tel(table_tel, tel, &pos);if (i) { //搜索指定鍵值printf("找到該電話號(hào)碼！！！\n");printf("成功查找的平均查找長(zhǎng)度ASL:%f\n", success_ASL());prn(htable, table_tel[pos].pos);//table_tel[pos].pos=no} else {printf("未找到該電話號(hào)碼！！！\n");printf("失敗查找的平均查找長(zhǎng)度ASL:%f\n", fail_ASL());}}break;case 2: {//?name = (char *) malloc(sizeof(char));printf("請(qǐng)輸入你想要查詢的姓名:");scanf("%s", name);i = search_name(table_name, name, &pos);//在散列表中查找被插入的鍵值if (i) { //搜索指定鍵值printf("找到該姓名！！！\n");printf("成功查找的平均查找長(zhǎng)度ASL:%f\n", success_ASL());if (table_name[pos].flag != 1)prnnn(htable, table_name, pos);elseprn(htable, table_name[pos].pos);//table_name[pos].pos=no} else {printf("未找到該姓名！！！\n");printf("失敗查找的平均查找長(zhǎng)度ASL:%f\n", fail_ASL());}}break;case 3:exit(0);default: {printf("您輸入的操作不合法，請(qǐng)重新輸入！\n");fflush(stdin);//防止不斷從緩沖區(qū)取數(shù)，造成循環(huán)break;}}printf("\n");menu();scanf("%d", &op);}return 0; }//******************************************************** //初始化哈希表 //******************************************************** void init(POS *table) {POS *p = table;for (; p < table + M; p++) {p->pos = NIL;//初始化表元素的鍵值p->flag = 0;p->next = NULL;} } //******************************************************** //開放定址的哈希函數(shù):折疊法 //構(gòu)造哈希函數(shù) //********************************************************//******************************************************** //開放定址的哈希函數(shù):除留余數(shù)法 //構(gòu)造哈希函數(shù) //******************************************************** int increment(int i) //某種探測(cè)方法 {return i; //增量為i }int HASH_1(keytype key, int i) //將某鍵值轉(zhuǎn)換成位置 {return ((int) (key % M) + increment(i)) % M; //線性探測(cè) }//******************************************************** //在散列表中搜索指定的鍵值 //pos返回鍵值的位置 //******************************************************** int search_tel(POS *table_tel, char *tel, int *pos) {int i = 0;long s;do {s = atol(tel);//字符串電話號(hào)碼轉(zhuǎn)換為long型數(shù)據(jù)*pos = HASH_1(s, i);//開放定址的散列函數(shù)if (table_tel[*pos].pos == NIL)return 0; //表未滿，沒找到if (strcmp(htable[table_tel[*pos].pos].tel, tel) == 0) return *pos; //找到} while (++i < M);return -1; //表滿，沒找到 }//將姓名轉(zhuǎn)化為數(shù)字 long converse_name(char *name) {long temp = 0;int i = 10000;while (*name != '\0') {temp += ((*name - 'a') * i);i /= 100;name++;}return temp; }int search_name(POS *table_name, char *name, int *pos) {int i = 0;long k;k = converse_name(name);do {*pos = HASH_1(k, i);//開放定址的散列函數(shù)if (table_name[*pos].pos == NIL)return 0; //表未滿，沒找到if (strcmp(htable[table_name[*pos].pos].name, name) == 0) return *pos; //找到} while (++i < M);return -1; //表滿，沒找到 }//******************************************************** //將一個(gè)關(guān)鍵字添加到哈希表中 //******************************************************** void insert_tel(POS *table_tel, int no, char *tel) {//將一個(gè)關(guān)鍵字添加到哈希表中int i;int pos;i = search_tel(table_tel, tel, &pos); //在散列表中查找被插入的鍵值if (i == 0) { //表不滿，該結(jié)點(diǎn)不存在table_tel[pos].pos = no;} else if (i == -1)printf("表滿,無法插入!\n");else printf("關(guān)鍵字重復(fù)，無法插入!\n"); }void insert_name(POS *table_name, int no, char *name) {int i, pos;int t = 1;long k;i = search_name(table_name, name, &pos); //在散列表中查找被插入的鍵值if (i == 0) { //表不滿，該結(jié)點(diǎn)不存在table_name[pos].pos = no;table_name[pos].flag = 1;} else if (i == -1)printf("表滿,無法插入!\n");else {k = converse_name(name);table_name[i].flag++;//重復(fù)的次數(shù)+1do {pos = HASH_1(k, t);//開放定址的散列函數(shù)if (table_name[pos].flag == 0) {table_name[pos].pos = no;table_name[pos].flag = 1;//insert_pos(table_name, i, pos);break;}} while (++t < M);// printf("關(guān)鍵字重復(fù)，無法插入!\n");} } /* void insert_pos(POS *table_name, int i, int position) {Pos p;p = table_name[i].next;while (p != NULL)p = p->next;p->next = &table_name[position];printf(p->next->flag); }*///******************************************************** //從磁盤文件中讀入數(shù)據(jù)，并存入結(jié)點(diǎn)表中 //******************************************************** void creat(NODE *htable) {FILE *fp;int no;char *name;char *address;char *tel;if (M < N) {printf("散列因子>1,結(jié)點(diǎn)個(gè)數(shù)超過表長(zhǎng),無法創(chuàng)建!\n");return;}if ((fp = fopen("/Users/xiaoyee/Desktop/數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)作業(yè)/實(shí)驗(yàn)報(bào)告/電話號(hào)碼查詢系統(tǒng)/1/FinalDataSet_10000.txt", "r")) == NULL) {printf("can't open the file!!");exit(0);}while (!(feof(fp))) {name = (char *) malloc(sizeof(char));address = (char *) malloc(sizeof(char));tel = (char *) malloc(sizeof(char));//非常重要！！！fscanf(fp, "%d", &no);fscanf(fp, "%s", name);fscanf(fp, "%s", address);fscanf(fp, "%s", tel);htable[no].no = no;htable[no].name = name;htable[no].address = address;htable[no].tel = tel; //找到開放位置,將鍵值加入insert_tel(table_tel, no, tel);insert_name(table_name, no, name);}fclose(fp); }//******************************************************** //輸出哈希表 //******************************************************** void prn(NODE *htable, int no) {printf("編號(hào)：%d\t", htable[no].no);printf("姓名：%s\t", htable[no].name);printf("城市：%s\t", htable[no].address);printf("城市：%s\n", htable[no].tel);printf("\n"); }//輸出哈希表 void prnnn(NODE *htable, POS *table_name, int pos) {int no = 0;int i = pos;POS *p;p = (POS *) malloc(sizeof(POS));//令p為table_name[i],即重復(fù)元素值相同的第一個(gè)元素p->pos = table_name[pos].pos;p->flag = table_name[pos].flag;p->next = table_name[pos].next;printf("查詢到該姓名在該電話號(hào)碼查詢系統(tǒng)中重復(fù)!\n");printf("現(xiàn)將所有是該姓名的人查詢?nèi)缦?#xff1a;\n");for (int k = 0; k < table_name[pos].flag;) {if (strcmp(htable[table_name[pos].pos].name, htable[table_name[i].pos].name) == 0) {no = table_name[i].pos;printf("編號(hào)：%d\t", htable[no].no);printf("姓名：%s\t", htable[no].name);printf("城市：%s\t", htable[no].address);printf("城市：%s\n", htable[no].tel);k++;}i++;} }//成功查找的ASL float success_ASL() {float i = 1 - (1.0 * N) / M;return (1 + 1 / i) / 2; }//失敗查找的ASL float fail_ASL() {float a = (1.0 * N) / M;float i = 1 - a;return (1 + 1 / (i * i)) / 2; }/*void prnnn(NODE *htable) {NODE *p = htable;for (; p < htable + M; p++)if (p->tel != NIL) {printf("編號(hào)：%d\t", p->no);printf("姓名：%s\t", p->name);printf("城市：%s\t", p->address);printf("電話號(hào)碼：%ld\t", p->tel);//如果某地址不開放,則輸出相應(yīng)的鍵值}printf("\n"); }*/void menu() {printf("----------------------------------------------\n");printf("*************歡迎使用電話號(hào)碼查詢系統(tǒng)*************\n");printf("----------------------------------------------\n");printf("請(qǐng)選擇你想要進(jìn)行的查詢：");printf(" 1.以電話號(hào)碼為關(guān)鍵字進(jìn)行查詢\n");printf("\t\t\t\t 2.以姓名為關(guān)鍵字進(jìn)行查詢\n");printf("\t\t\t\t 3.退出\n");printf("----------------------------------------------\n");printf("請(qǐng)選擇你想要進(jìn)行的操作：");

總結(jié)

以上是生活随笔為你收集整理的数据结构实验：电话号码查询系统的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。