第10章索引与散列 temp. Element ht[ TableSize-l]Element; temp. info ht[ TableSize-l] info while( int k= TableSize-l; k>i;k--) f ht[]. Element ht[k-1].Element; ht( k]. info= ht[k-1]. info: 3 插入 while( int k=j;k>0; k--) f ht[k].Element = ht[k-1].Element; ht[k]. info= htk-1]info; 1 return j: void Hash Table: Hashsort(i int n, i; char *str; for(i=0;1<n;计++){ if(Fnd-ns(s)=- Tablesize){cout<<"表已满"<<endl; break;} cin > str: for (i=0; i< TableSize; i++) if(ht(i).info=Active)cout<< ht(). Element <<endl; 10-17设有1000个值在1到10000的整数,试设计一个利用散列方法的算法,以最少的数 据比较次数和移动次数对它们进行排序 【解答1】 建立 Tablesize=10000的散列表,散列函数定义为 int Hash Table FindPos( constant x)( return x-1; 相应排序算法基于散列表类 #define DefaultS ize 10000 class HashTable i 散列表类的定义 enum KindofEntry i Active, Empty, Deleted 3: ∥表项分类(活动/空/删) HashTable(): Tables ize( Defaults ize){ht= new HashEntry [TableSize;}∥构造函数 HashTable (i delete [ht; j 析构函数 oid HashSort( int A[, int n ) ∥散列法排序 struct HashEntry /散列表的表项定义 ∥表项的数据,整数 KindofEntry info; ∥三种状态: Active, Empty, Deleted HashEntry ( info(Empty )3 ∥表项构造函数 }; /散列表存储数组 数组长度 indOs( int x ) /散列函数 void Hash Table<Type>: HashSort( int A[ int n)i /散列法排序第 10 章 索引与散列 11 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; } ht[0].Element = temp.Element; ht[0].info = temp.info; } return j; } void HashTable :: HashSort ( ) { int n, i; char * str; cin >> n >> str; for ( i = 0; i < n; i++ ) { if ( Find-Ins ( str ) == - Tablesize ) { cout << "表已满" << endl; break; } cin >> str; } for ( i = 0; i < TableSize; i++ ) if ( ht[i].info == Active ) cout << ht[i].Element << endl; } 10-17 设有 1000 个值在 1 到 10000 的整数，试设计一个利用散列方法的算法，以最少的数 据比较次数和移动次数对它们进行排序。 【解答 1】 建立 TableSize = 10000 的散列表，散列函数定义为 int HashTable :: FindPos ( const int x ) { return x-1; } 相应排序算法基于散列表类 #define DefaultSize 10000 #define n 1000 class HashTable { //散列表类的定义 public: enum KindOfEntry { Active, Empty, Deleted }; //表项分类 (活动 / 空 / 删) HashTable ( ) : TableSize ( DefaultSize ) { ht = new HashEntry[TableSize ]; } //构造函数 ~HashTable ( ) { delete [ ] ht; } //析构函数 void HashSort ( int A[ ], int n ); //散列法排序 private: struct HashEntry { //散列表的表项定义 int Element; //表项的数据, 整数 KindOfEntry info; //三种状态: Active, Empty, Deleted HashEntry ( ) : info (Empty ) { } //表项构造函数 }; HashEntry *ht; //散列表存储数组 int TableSize; //数组长度 int FindPos ( int x ); //散列函数 }; void HashTable<Type> :: HashSort ( int A[ ], int n ) { //散列法排序