int Is Prime( intN)i 测试N是否质数 for(inti=3;i<=N;i+=2)若N能分解为两个整数的乘积,其中一个一定≤√N (n %i=0)return 0; N能整除iN不是质数 /N是质数 10-16编写一个算法,以字典顺序输出散列表中的所有标识符。设散列函数为hash(x)=x 中的第一个字符,采用线性探查法来解决冲突。试估计该算法所需的时间。 【解答】 用线性探查法处理溢出时散列表的类的声明 #include <string. h> #include <stdlib. h class Hash Table i 散列表类定义 enum KindofEntry{ Active, Empty, Deleted};∥表项分类(活动/空/删) HashTable): Tables ize( DefaultS ize){ht= new Hash Entry[TableSize;}∥构造函数 HashTable (i delete [ht:) ∥析构函数 int Find-Ins( constchar *id); ∥在散列表中搜索标识符id void HashSort ( struct HashEntry t ∥表项定义 Type Element; ∥表项的数据,即表项的关键码 KindofEntry info; ∥三种状态: active, Empty, Deleted HashEntry ( info(Empty ∥表项构造函数,置空 }; /散列表存储数组 int Tables ∥最大桶数 int FindPos( string s)const{ return atol(·s)-32;}/散列函数 int Hash Table Find-Ins( const char*id)i int i=FindPos(id),j=i; 是计算出来的散列地址 whil( hto. info=Empy&& strcmp(h] ement,id)l=0){∥冲突 j=(j+ 1)% Tablesize ∥当做循环表处理,找下一个空桶 if(j==i)return-Tablesize ∥转一圈回到开始点,表已满,失败 if( htj info I= Active )i 质插入 if(>l while( ink=j;k>1: k--) t ht[k]. Element=ht(k-1].Element; ht[k]. info= htk-1]. info; 3 hto Element =id; htO info= Active 插入第 10 章 索引与散列 10 return N; } int IsPrime ( int N ) { //测试 N 是否质数 for ( int i = 3; i*i <= N; i += 2 ) //若 N 能分解为两个整数的乘积, 其中一个一定  N if ( N % i == 0 ) return 0; //N 能整除 i, N 不是质数 return 1; //N 是质数 } 10-16 编写一个算法，以字典顺序输出散列表中的所有标识符。设散列函数为 hash(x) = x 中的第一个字符，采用线性探查法来解决冲突。试估计该算法所需的时间。 【解答】 用线性探查法处理溢出时散列表的类的声明。 #define DefaultSize 1000 #include <iostream.h> #include <string.h> #include <stdlib.h> class HashTable { //散列表类定义 public: enum KindOfEntry { Active, Empty, Deleted }; //表项分类 (活动 / 空 / 删) HashTable ( ) : TableSize ( DefaultSize ) { ht = new HashEntry[TableSize]; } //构造函数 ~HashTable ( ) { delete [ ] ht; } //析构函数 int Find-Ins ( const char * id ); //在散列表中搜索标识符 id void HashSort ( ); private: struct HashEntry { //表项定义 Type Element; //表项的数据, 即表项的关键码 KindOfEntry info; //三种状态: Active, Empty, Deleted HashEntry ( ) : info (Empty ) { } //表项构造函数, 置空 }; HashEntry *ht; //散列表存储数组 int TableSize; //最大桶数 int FindPos ( string s) const { return atoi (*s) - 32; } //散列函数 } int HashTable :: Find-Ins ( const char * id ) { int i = FindPos ( id ), j = i; //i 是计算出来的散列地址 while ( ht[j].info != Empty && strcmp ( ht[j].Element, id ) != 0 ) { //冲突 j = ( j + 1 ) % TableSize; //当做循环表处理, 找下一个空桶 if ( j == i ) return -TableSize; //转一圈回到开始点, 表已满, 失败 } if ( ht[j].info != Active ) { //插入 if ( j > i ) { while ( int k = j; 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; //插入 } else { HashEntry temp;