清华大学:《数据结构》课程电子教案(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
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter6 Graph Algorithms.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter5 trees.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter4 Stacks Queues.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter3 Lists.ppt
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 2 ALGORITHM ANALYSIS.ppt
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 8 THE DISJOINT SET ADT.ppt
- 华中师范大学计算机科学系:《数据结构》第6章 二叉树和树.ppt
- 华中师范大学计算机科学系:《数据结构》第2章 线性表.ppt
- 华中师范大学计算机科学系:《数据结构》第8章 查找表.ppt
- 华中师范大学计算机科学系:《数据结构》第7章 图和广义表.ppt
- 华中师范大学计算机科学系:《数据结构》第5章 串和数组.ppt
- 华中师范大学计算机科学系:《数据结构》第4章 栈与队列.ppt
- 华中师范大学计算机科学系:《数据结构》第3章 排序.ppt
- 华中师范大学计算机科学系:《数据结构》第1章 绪论(王敬华).ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)实验一.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第四章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第六章 树和二叉树.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第二章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第三章 栈和队列.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter8 Sorting.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter9 String.ppt
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验二.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)二叉树试验三.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验一.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验四.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验模板.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验五.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)复习2007级.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)2004级计算机B卷.doc
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第一章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第九章 排序.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第1章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第2章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第3章 栈和队列.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第4章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组和广义表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第6章 树和二叉树.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第七章 图.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)动态查找结构.ppt