发布时间 : 星期三 文章数据结构习题解析第10章更新完毕开始阅读6e123bed0975f46527d3e18c
10-14 设有150个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ 设?是散列表的装载因子，则有
11ASL?(1?) succ21??【解答】
已知要存储的记录数为n = 150，查找成功的平均查找长度为ASLsucc ? 2，则有ASLsucc 1?1?n150221???? 2，解得 ? ?。又有? = =?? ，则 m ? 225。 ?2?1??mm33
10-15 若设散列表的大小为m，利用散列函数计算出的散列地址为h = hash(x)。 (1) 试证明：如果二次探查的顺序为(h + q2), (h + (q-1)2), …, (h+1), h, (h-1), …, (h-q2)，其中， q = (m-1)/2。因此在相继被探查的两个桶之间地址相减所得的差取模(%m)的结果为 m-2, m-4, m-6, …, 5, 3, 1, 1, 3, 5, …, m-6, m-4, m-2 (2) 编写一个算法，使用课文中讨论的散列函数h(x)和二次探查解决冲突的方法，按给定值x来搜索一个大小为m的散列表。如果x不在表中，则将它插入到表中。 【解答】
(1) 将探查序列分两部分讨论：
(h + q2), (h + (q-1)2), …, (h+1), h 和 (h-1), (h-22), …, (h-q2)。
对于前一部分，设其通项为h + ( q – d )2, d = 0, 1, …, q，则相邻两个桶之间地址相减所得的差取模：
( h + (q – (d -1) )2 – ( h + (q – d )2 ) ) % m = ( (q – (d -1 ) )2 – (q – d )2 ) % m = (2*q -2*d +1) % m = ( m – 2*d ) % m. ( 代换 q = (m-1)/2 ) 代入 d = 1, 2, …, q，则可得到探查序列如下： m-2, m-4, m-6, …, 5, 3, 1。 ( m – 2*q = m – 2* (m-1)/2 = 1 ) 对于后一部分，其通项为h – ( q – d )2, d = q, q+1, …, 2q，则相邻两个桶之间地址相减所得的差取模： ( h – ( q – d )2 – ( h – ( q – (d+1) )2 ) ) % m = ( ( q – (d+1)2 – (q – d )2 ) % m
= ( 2*d – 2*q +1) % m = ( 2*d – m + 2) % m ( 代换 q = (m-1)/2 ) 代入 d = q, q+1, …, 2q-1，则可得到 2*d–m+2 = 2*q – m +2 = m – 1 – m +2 = 1, 2*d–m+2 = 2*q + 2 – m +2 = m – 1 + 2 – m +2 = 3, ……,
2*d–m+2 = 2*(2*q-1) – m +2 = 2*(m–1–1) – m + 2 = 2*m – 4 – m +2 = m – 2。〖证毕〗 (2) 编写算法
下面是使用二次探查法处理溢出时的散列表类的声明。
7
template
enum KindOfEntry { Active, Empty, Deleted }; ~HashTable ( ) { delete [ ] ht; } int Find ( const Type & x ); private:
struct HashEntry {
//散列表的表项定义
//表项分类 (活动 / 空 / 删) //析构函数 //在散列表中搜索x
//判散列表空否，空则返回1
HashTable ( ) : TableSize ( DefaultSize ) { AllocateHt ( ); CurrentSize = 0; } //构造函数 const HashTable & operator = ( const HashTable & ht2 ); //重载函数：表赋值
//散列表类的定义
int IsEmpty ( ) { return !CurrentSize ? 1 : 0; }
217
Type Element; KindOfEntry info;
//表项的数据, 即表项的关键码 //三种状态: Active, Empty, Deleted //表项构造函数
HashEntry ( ) : info (Empty ) { } };
enum { DefualtSize = 31; } HashEntry *ht; int TableSize; int CurrentSize;
HashEntry ( const Type &E, KindOfEntry i = Empty ) : Element (E), info (i) { }
//散列表存储数组
//数组长度，是满足4k+3的质数，k是整数 //已占据散列地址数目
//为散列表分配存储空间; //散列函数
void AllocateHt ( ) { ht = new HashEntry[TableSize ]; } int FindPos ( const Type & x ); };
template
return *this; }
template
//返回目标散列表结构指针
delete [ ] ht; TableSize = ht2.TableSize; AllocateHt ( ); //重新分配目标散列表存储空间 for ( int i = 0; i < TableSize; i++ ) ht[i] = ht2.ht[i]; CurrentSize = ht2.CurrentSize;
//从源散列表向目标散列表传送
//传送当前表项个数
//共有函数： 找下一散列位置的函数 int i = 0, q = ( TableSize -1 ) / 2, h0; int CurrentPos = h0 = HashPos ( x );
// i为探查次数
//利用散列函数计算x的散列地址 /搜索是否要求表项
}
if ( ht[CurrentPos].info == Active && ht[CurrentPos].Element == x ) return CurrentPos; else {
ht[CurrentPos].info = Active; ht[CurrentPos].Element = x; if ( ++CurrentSize < TableSize / 2 ) return CurrentPos;
//当前已有项数加1, 不超过表长的一半返回
218
//插入x
//返回桶号
if ( i <= q ) {
//求“下一个”桶
//实现取模
CurrentPos = h0 + (q - i ) * ( q - i );
while ( CurrentPos >= TableSize ) CurrentPos -= TableSize; } else {
CurrentPos = h0 - ( i -q ) * ( i - q );
while ( CurrentPos < 0 ) CurrentPos += TableSize; } i++;
//实现取模
while ( ht[CurrentPos].info != Empty && ht[CurrentPos].Element != x ) {
HashEntry *Oldht = ht; CurrentSize = 0;
//分裂空间处理: 保存原来的散列表
int OldTableSize = TableSize;
TableSize = NextPrime ( 2 * OldTableSize ); //原表大小的2倍，取质数 Allocateht ( );
//建立新的二倍大小的空表 //原来的元素重新散列到新表中 //递归调用
for ( i = 0; i < OldTableSize; i++) if ( Oldht[i].info == Active ) {
Find ( Oldht[i].Element );
if ( Oldht[i].Element == x ) CurrentPos = i;
}
} }
delete [ ] Oldht; return CurrentPos;
求下一个大于参数表中所给正整数N的质数的算法。
int IsPrime ( int N ) { }
//测试N是否质数
//若N能分解为两个整数的乘积, 其中一个一定 ?//N能整除i, N不是质数 //N是质数
for ( int i = 3; i*i <= N; i += 2 )
if ( N % i == 0 ) return 0;
return 1;
int NextPrime ( int N ) {
//求下一个>N的质数，设N >= 5 //偶数不是质数 //寻找质数
if ( N % 2 == 0 ) N++; return N; }
for ( ; !IsPrime (N); N += 2 );
N
10-16 编写一个算法，以字典顺序输出散列表中的所有标识符。设散列函数为hash(x) = x中的第一个字符，采用线性探查法来解决冲突。试估计该算法所需的时间。 【解答】
用线性探查法处理溢出时散列表的类的声明。
#define DefaultSize 1000 #include
public:
enum KindOfEntry { Active, Empty, Deleted }; ~HashTable ( ) { delete [ ] ht; } int Find-Ins ( const char * id ); void HashSort ( ); private:
struct HashEntry { Type Element;
219
//表项定义
//表项的数据, 即表项的关键码
//表项分类 (活动 / 空 / 删) //析构函数
//在散列表中搜索标识符id
HashTable ( ) : TableSize ( DefaultSize ) { ht = new HashEntry[TableSize]; } //构造函数
//散列表类定义
KindOfEntry info; };
HashEntry *ht; int TableSize; }
//三种状态: Active, Empty, Deleted //表项构造函数, 置空 //散列表存储数组 //最大桶数 //散列函数
HashEntry ( ) : info (Empty ) { }
int FindPos ( string s ) const { return atoi (*s) - 32; }
int HashTable :: Find-Ins ( const char * id ) {
//i是计算出来的散列地址
//冲突
//当做循环表处理, 找下一个空桶 //转一圈回到开始点, 表已满, 失败 //插入
while ( ht[j].info != Empty && strcmp ( ht[j].Element, id ) != 0 ) { }
if ( ht[j].info != Active ) {
if ( j > i ) {
while ( int k = j; k > i; k-- )
ht[i].Element = id; ht[i].info = Active; HashEntry temp;
temp.Element = ht[TableSize-1].Element; temp.info = ht[TableSize-1].info; while ( int k = TableSize-1; k > i; k-- )
{ ht[k].Element = ht[k-1].Element; ht[k].info = ht[k-1].info; }
ht[i].Element = id; ht[i].info = Active; while ( int k = j; k > 0; k-- )
{ ht[k].Element = ht[k-1].Element; ht[k].info = ht[k-1].info; }
void HashTable :: HashSort ( ) { int n, i; char * str; cin >> n >> str; for ( i = 0; i < n; i++ ) {
}
for ( i = 0; i < TableSize; i++ ) }
if ( ht[i].info == Active ) cout << ht[i].Element << endl;
if ( Find-Ins ( str ) == - Tablesize ) { cout << \表已满\endl; break; } cin >> str; }
ht[0].Element = temp.Element; ht[0].info = temp.info; return j; }
//插入
//插入
j = ( j + 1 ) % TableSize;
if ( j == i ) return -TableSize;
int i = FindPos ( id ), j = i;
{ ht[k].Element = ht[k-1].Element; ht[k].info = ht[k-1].info; }
} else {
10-17 设有1000个值在1到10000的整数，试设计一个利用散列方法的算法，以最少的数据比较次数和移动次数对它们进行排序。 【解答1】
220