07计科9-10章作业.doc

P 388 Exercise 9.3 E4 E4. Consider a table of the triangular shape shown in Figure 9.7, where the columns are indexed from ?n to n and the rows from 0 to n. (a) Devise an index function that maps a table of this shape into a sequential array. Answer Entry(i, j) is stored in position i(i+1)+j of a sequential array that is indexed from 0 to n*(n+2). (b) Write a function that will generate an access array for ?nding the ?rst entry of each row of a table of this shape within the contiguous array. Answer The following function maps the position of the ?rst entry in each row, not the position of the entry in column 0, to the access array. void make_access_table(int access_table[], int number_of_rows) { for (int i = 0; i number_of_rows; i++) access_table[i] = i * i; } (c) Write a function that will re?ect the table from left to right. The entries in column 0 (the central column) remain unchanged, those in columns ?1 and 1 are swapped, and so on. Answer void re?ect(int triangle[], int number_of_rows) { for (int i = 0; i number_of_rows; i++) { int mid_col = i * (i+1); //mid_col记录第i行0列(中间位置)的那个元素在一维数组triangle中的存储序号 for (int j = 0; j i; j++) swap(triangle[mid_col ? j], triangle[mid_col+j]); } } E3. Write a C++ function to retrieve an entry froma hash table with open addressing using (a) linear probing; Answer Error_code Hash_table :: retrieve(const Key target, Record found) const { int probe_count, // counter to be sure that table is not full probe; // position currently probed in the hash table Key null; // null key for comparison purposes null.make_blank( ); probe = hash(target); probe_count = 0; while (table[probe]!= null // Is the location empty? table[probe]!= target // Search Successful? probe_count hash_size) { // Full table? probe_count??; probe = (probe+1)%hash_size; } if (table[probe] == target) { found = table[probe]; return success; } else return not_present; } E7. Another method for resolving collisions with open addressing is