西安建筑科技大学：《数据结构与算法》课程教学资源（PPT电子教案）第四部分 查找、排列_检索 Chapter 9 Tables And Information Retrieval（英文）

Chapter 9 Tables And Information Retrieval 1 Introduction: Breaking the lgn Barrier 2. Rectangular arrays 3. Tables of Various Shapes 4.Tables: A New abstract Data Type 5. Application: Radix Sort

Chapter 9 Tables And Information Retrieval 1. Introduction: Breaking the lgn Barrier 2. Rectangular Arrays 3. Tables of Various Shapes 4. Tables: A New Abstract Data Type 5. Application: Radix Sort

Chapter 9 Tables And Information Retrieval 6. Hashing 7. Analysis of Hashing I8. Conclusions: Comparison of Methods 9. Application: The Life game revisited 10. Pointers and Pitfalls

Chapter 9 Tables And Information Retrieval 6. Hashing 7. Analysis of Hashing 8. Conclusions: Comparison of Methods 9. Application: The Life Game Revisited 10. Pointers and Pitfalls

9.1 Introduction: Breaking the Ign Barrier By use of key comparisons alone it is impossible to complete a search of n items in fewer than ig n comparisons, on average (lower bound search thm) Ordinary table lookup or array access requires only constant time o(1. C Both table lookup and searching share the same essential purpose, that of information retrieval. The key used for searching and the index used for table lookup have the same essential purpose: one piece of information that is used to locate further information

9.1 Introduction: Breaking the lgn Barrier ◆By use of key comparisons alone, it is impossible to complete a search of n items in fewer than lg n comparisons, on average(lower bound_search_thm). ◆Ordinary table lookup or array access requires only constant time O(1). ◆Both table lookup and searching share the same essential purpose, that of information retrieval. The key used for searching and the index used for table lookup have the same essential purpose: one piece of information that is used to locate further information

Both table lookup and searching algorithms provide functions from a set of keys or indices to locations in a list or array. L In this chapter we study ways to implement and access various kinds of tables in contiguous storage. Several steps may be needed to retrieve an entry from some kinds of tables but the time required remains o(1 It is bounded by a constant that does not depend on the size of the table. Thus table lookup can be more efficient than any searching method

◆Both table lookup and searching algorithms provide functions from a set of keys or indices to locations in a list or array. ◆In this chapter we study ways to implement and access various kinds of tables in contiguous storage. ◆Several steps may be needed to retrieve an entry from some kinds of tables, but the time required remains O(1).It is bounded by a constant that does not depend on the size of the table. Thus table lookup can be more efficient than any searching method

We shall implement abstractly defined tables with arrays. In order to distinguish between the abstract concept and its implementation, we introduce Convention The index defining an entry of an abstractly defined table is enclosed in parentheses whereas the index of an entry of an array is enclosed in square brackets

◆We shall implement abstractly defined tables with arrays. In order to distinguish between the abstract concept and its implementation, we introduce: Convention The index defining an entry of an abstractly defined table is enclosed in parentheses, whereas the index of an entry of an array is enclosed in square brackets

9.2 Rectangular Arrays 通常行主序 存储方式较普遍 1 Row-major and column-major Orderi COS Rectangular are table Row-major ordering Column-major ordering C a sea a e Fig 9.1 pg 381

9.2 Rectangular Arrays 1 Row-major and Column-major Ordering: Fig 9.1 pg.381 通常行主序 存储方式较普遍

存储位置 2 indexing Rectangular table Pg 382 (地址) Suppose position of Entry(0,0)is Loc/,0), every entry store c cell, then Entry(i,j) position voc(i,j) 序号 index Loc(j)=Loc(0,0)+(*3+j)*c Row-major order Loc(i,j)=Loc(0,0)+(i+2*j)*c( Column-major ord\ ing In row-major ordering, entry ei j] goes to position nit+

2 indexing Rectangular table Pg.382 Suppose position of Entry(0,0) is Loc(0,0), every entry store c cell，then Entry(i,j) position Loc(i,j) Loc(i,j)=Loc(0,0)+(i*3+j)*c （Row-major ordering） Loc(i,j)=Loc(0,0)+(i+2*j)*c （Column-major ordering ） In row-major ordering, entry [i, j ] goes to position ni+j . 存储位置 (地址) 序号 index

3 Variation: A Access Arrays Pg382 In row-major ordering, entry [i, jI goes to position ni+j CoS is represented in row-major order as costrel e a Access array Fig 9.2 pg 383

3 Variation: A Access Arrays Pg.382 Fig 9.2 pg.383

9.3 Tables of Various Shapes XXX XX X XX XXX XX XX XX X XX XXX Tri-diagonal matrix Block diagonal matrix XX 0 ower triangular matrix Strictly upper triangular matrix Fig 9. 3 pg 384

9.3 Tables of Various Shapes Fig 9.3 pg.384

1 triangular table oweI triangular table 的的 Contiguous implementation Access table Fig 9. 4 pg 384

1 triangular table Fig 9.4 pg.384