解析來自某大佬
分析： 差別概念平均成功查找次數和平均不成功查找次數。 平均成功查找次數=每個關鍵詞比較次數之和÷關鍵詞的個數
平均不成功查找次數=每個位置不成功時的比較次數之和÷表長（所謂每個位置不成功時的比較次數就是在除餘位置内，每個位置到第一個為空的比較次數，比如此題表長為11，散列函數為Key%11，除餘的是11，那麼除餘位置就是0—10；如果表長為15，但散列函數為Key%13，那麼除餘位置就是0—12）
明确概念後做題： 連續插入散列值相同的4個元素，我們就假設它的散列值都為0，那麼插入後的位置：
資料結構作業21複習 其中位置0到第一個為空的位置4的比較次數為5，其餘的位置以此類推。 平均不成功查找次數=（5+4+3+2+1+1+1+1+1+1+1）÷
11 = 21/11 故選D
2-12
設數字 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 在大小為10的散清單中根據散列函數 h(X)=X%10得到的下标對應為 {1, 3, 4, 9, 5, 0, 2}。那麼繼續用散列函數 “h(X)=X%表長”實施再散列并用線性探測法解決沖突後，它們的下标變為：
(3分)
A.1, 12, 17, 0, 13, 8, 14
B.11, 3, 13, 19, 4, 0, 9
C.1, 3, 4, 9, 5, 0, 2
D.1, 12, 9, 13, 20, 19, 11
再散列就是，把表長變為兩倍即20，取最近的素數23。然後分别取餘就可以了，其實到第三個就可以選出答案了。
6-1 分離連結法的删除操作函數 (20分)
試實作分離連結法的删除操作函數。
函數接口定義：
其中HashTable是分離連結散清單，定義如下：
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
typedef struct TblNode *HashTable; /* 散清單類型 */
struct TblNode { /* 散清單結點定義 */
int TableSize; /* 表的最大長度 */
List Heads; /* 指向連結清單頭結點的數組 */
};
函數Delete應根據裁判定義的散列函數
Hash( Key, H->TableSize )
從散清單H中查到Key的位置并删除之，然後輸出一行文字：
Key is deleted from list Heads[i]
，其中
Key
是傳入的被删除的關鍵詞，i是Key所在的連結清單的編号；最後傳回
true
。如果
Key
不存在，則傳回
false
。
裁判測試程式樣例：
#include <stdio.h>
#include <string.h>
#define KEYLENGTH 15 /* 關鍵詞字元串的最大長度 */
typedef char ElementType[KEYLENGTH+1]; /* 關鍵詞類型用字元串 */
typedef int Index; /* 散列位址類型 */
typedef enum {false, true} bool;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
typedef struct TblNode *HashTable; /* 散清單類型 */
struct TblNode { /* 散清單結點定義 */
int TableSize; /* 表的最大長度 */
List Heads; /* 指向連結清單頭結點的數組 */
};
Index Hash( ElementType Key, int TableSize )
{
return (Key[0]-'a')%TableSize;
}
HashTable BuildTable(); /* 裁判實作，細節不表 */
bool Delete( HashTable H, ElementType Key );
int main()
{
HashTable H;
ElementType Key;
H = BuildTable();
scanf("%s", Key);
if (Delete(H, Key) == false)
printf("ERROR: %s is not found\n", Key);
if (Delete(H, Key) == true)
printf("Are you kidding me?\n");
return 0;
}
/* 你的代碼将被嵌在這裡 */
輸入樣例1：散清單如下圖
able
輸出樣例1：
輸入樣例2：散清單如樣例1圖
date
輸出樣例2：
ERROR: date is not found
bool Delete(HashTable H,ElementType Key)
{
Index i;
i=Hash(Key,H->TableSize);
if(H->Heads[i].Next==NULL) return false;
Position p,temp;
p=H->Heads[i].Next;
//當未到達表尾，且未找到時
while(strcmp(p->Data,Key)!=0&&p)//需要比對的關鍵字為字元串
{
temp=p;
p=p->Next;
}
if(strcmp(p->Data,Key)==0)
{
printf("%s is deleted from list Heads[%d]\n",Key,i);
temp=p->Next;
free(p);
return true;
}
else return false;
}
6-2 哈希表的建立及查找(線性探查法) (10分)
實作哈希表建立及查找算法，哈希函數使用除餘法，用線性探測法處理沖突。
函數接口定義：
void CreateHash(HashTable HT[],int n); //輸入不大于m的n個不為0（0表示空值）的數，用線性探查法解決沖突構造散清單
int SearchHash(HashTable HT[],int key); //輸入一個值key，在散清單中查找key位置
其中
HT
表示哈希表，
n
表示記錄數，
key
要查找的關鍵字
裁判測試程式樣例：
#include<iostream>
using namespace std;
#define m 16
#define NULLKEY 0 //單元為空的标記
struct HashTable{
int key;
};
void CreateHash(HashTable HT[],int n);
int SearchHash(HashTable HT[],int key);
int main()
{ int value,key;
int result;
int i,j,n;
HashTable HT[m];
for(i=0;i<m;i++)
HT[i].key=0;
cin >> n;
if(n>m) return 0;
CreateHash(HT,n);
cin >> key;
result=SearchHash(HT,key);
if(result!=-1)
cout << "search success，The key is located in "<< result+1;
else
cout << "search failed";
return 0;
}
/* 請在這裡填寫答案 */
輸入樣例：
12
19 14 23 1 68 20 84 27 55 11 10 79
55
輸出樣例：
輸出拓撲序列。
void CreateHash(HashTable HT[],int n)//輸入不大于m的n個不為0（0表示空值）的數，用線性探查法解決沖突構造散清單
{
int i,e,t;
for(i=0;i<n;i++)
{
cin>>e;
t=e%13;
while(1)
{
if(HT[t].key==0)
{
HT[t].key=e;break;
}
else
{
t++;
}
}
}
}
int SearchHash(HashTable HT[],int key) //輸入一個值key，在散清單中查找key位置
{
int i,t;
for(i=0;i<=m;i++)
{
t=key%13;
while(HT[t].key!=0)
{
if(HT[t].key==key)
{
return t;
}
else
{
t++;
}
}
}
return -1;
}