清华大学：《数据结构》课程电子教案（PPT课件讲稿）Chapter7 Search

CHAPTER 6 Search ☆ Definition of search ☆ Static search table ☆ Dynamic search table Hash table 米 米

❖Definition of search ❖Static search table ❖Dynamic search table ❖Hash table CHAPTER 6 Search

s 1 Definition of search Search table is collection constituted By the same types of data elements (or record), because the elements in the collection has loose relationship to each other, so search table is a facilitating application data structure. Basic operation of search table Search a specific data element in the search table Search the properties of a specific data element 米 Insert a data element into the search table Delete a data element in the search table

Search table is collection constituted By the same types of data elements (or record), because the elements in the collection has loose relationship to each other , so search table is a facilitating application data structure. Basic operation of search table: ▪Search a specific data element in the search table ； ▪Search the properties of a specific data element； ▪Insert a data element into the search table； ▪Delete a data element in the search table §1 Definition of search

The classification of search table Static search table only for querying and searching Dynamic search table In the process of searching in the search table insert the inexistent data elements or remove a pre-existing data elements at the same time. Such table is called dynamic search table

Static search table only for querying and searching。 Dynamic search table In the process of searching in the search table , insert the inexistent data elements or remove a pre-existing data elements at the same time. Such table is called dynamic search table. The classification of search table：

Keyword it is a value of property of a data element (or record) to identify the data element(or record). If keyword can be identified only as a record, said that the " primary keyword. If keyword can identify a number of records, said that the" general keyword

Keyword it is a value of property of a data element (or record) to identify the data element( or record). If keyword can be identified only as a record, said that the “primary keyword." If keyword can identify a number of records, said that the “general keyword

Searching According to a giving value, search the table to return data element whose keyword equal to the value If search table has this data element(or record) then call search successful and return. the entire record or the position of it in the table else call search failed and return. null record or null pointer

According to a giving value, search the table to return a data element whose keyword equal to the value. If search table has this data element(or record) then call ”search successful”, and return：the entire record or the position of it in the table； else call“search failed” ,and return：null record or null pointer. Searching

How to search Searching method depends on the structure of the search table As the data elements in the search table does not exist obvious relation, it is not easy to find In order to improve the efficiency of finding, it is need to attach artificial relationship among records. in other words, to use a different structure to implement search table

How to search？ Searching method depends on the structure of the search table. As the data elements in the search table does not exist obvious relation, it is not easy to find. In order to improve the efficiency of finding , it is need to attach artificial relationship among records. in other words, to use a different structure to implement search table

evaluate searching method Search speed How much storage space occupied Complexity of the algorithm ASL(Average Search Length): To ascertain the position of record in the table, and the expect number of key word comparing with the giving value To the table with n records ASL=>p,c, P, is the probability of the ith record in the table >P,=l C, is the number of keyword comparing

evaluate searching method • Search speed • How much storage space occupied • Complexity of the algorithm • ASL(Average Search Length)： To ascertain the position of record in the table, and the expect number of keyword comparing with the giving value 1 1 1 = =   = = n i i n i i i p To the table with n records ASL p c is the probability of the ith record in the table i is the number of keyword comparing i c p

8 2 static search table adT definition of static search table: ADT StaticSearchTable i Data object D: It is a collection composed by the same characteristics data elements. Each type of data elements contain the same type keyword, marking the only data elements Data relation: data elements belongs to a collection

ADT definition of static search table: ADT StaticSearchTable { It is a collection composed by the same characteristics data elements. Each type of data elements contain the same type keyword, marking the only data elements. Data relation R：data elements belongs to a collection Data object D: §2 static search table

Basic operation P Create&STn;/构造一个含n个数据 元素的静态查找表ST Destroy (&ST); /销毁表ST Search( ST, key;/查找ST中其关键字等 于kva的数据元素。 Traverse( ST, Visit();/按某种次序对 ST的每个元素调用函数 Visit0一次且仅一次, 3 ADT StaticSearch Table

Create(&ST, n); //构造一个含 n 个数据 元素的静态查找表ST。 Destroy(&ST); //销毁表ST。 Search(ST, key); //查找 ST 中其关键字等 于kval 的数据元素。 Traverse(ST, Visit()); //按某种次序对 ST的每个元素调用函数 Visit()一次且仅一次， } ADT StaticSearchTable Basic operation P：

Sequential lists' search Use sequential lists as a static search table, and the function of Search can be implemented by sequential search method As follows is the sequential storage structure typedef struct t E| emType*elem;∥/数据元素存储空间基址,建表时 按实际长度分配,0号单元留空 int length;∥/表的长度 1 SSTable

▪Sequential lists’ search typedef struct { ElemType *elem; // 数据元素存储空间基址，建表时 按实际长度分配，0号单元留空 int length; // 表的长度 } SSTable; Use sequential lists as a static search table, and the function of Search can be implemented by sequential search method . As follows is the sequential storage structure