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