数据结构(c语言版李春葆)(精品·公开课件).ppt

第七章 如何进行查找? 取决于查找表的结构，即记录在查找表中所处的位置。然而，查找表本身是一种很松散的结构，因此，为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，即用另外一种结构来表示查找表。 一些约定： 典型的关键字类型说明： typedef float KeyType; //实型 typedef int KeyType; //整型 typedef char *KeyType; //字符串型 数据元素类型定义为： typedef struct{ KeyType key; // 关键字域 ... //其它域 }ElemType; 对两个关键字的比较约定为如下的宏定义： 对数值型关键字： #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)(b)) #define LQ(a,b) ((a)=(b)) 对字符串型关键字： #define EQ(a,b) (!strcmp((a),(b))) #define LT(a,b) (strcmp((a),(b))0) #define LQ(a,b) (strcmp((a),(b))=0) 8.1 静 态 查 找 表 抽象数据类型静态查找表的定义为： ADT StaticSearchTable{ 数据对象D：D是具有相同特性的数据元素的集合。 各个数据元素均含有类型相同、可唯一 标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： Create(ST，n)： 操作结果：构造一个含n个数据元素的静态查找表ST。 Destroy(ST)： 初始条件：静态查找表ST存在。 操作结果：销毁表ST。 Search(ST，key)： 初始条件：静态查找表ST存在，key为和关键字 类型相同的给定值。 操作结果：若ST中存在其关键字等于key的数据元素， 则函数值为该元素的值或在表中的位置， 否则为 “空”。 Traverse(ST，visit( ))： 初始条件：静态查找表ST存在， visit是对元素操作的应用函数。 操作结果：按某种次序对ST的每个元素调用 函数visit()一次且仅一次，一旦visit() 失败，则操作失败。 } ADT StaticSearchTable 静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。 8.1.1 顺序表的查找 以顺序表或线性链表表示静态查找表，则Search函数可用顺序查找来实现。本节中只讨论它在顺序存储结构模块中的实现。 //静态查找表的顺序存储结构 typdef struct{ ElemType * elem; //数据元素存储空间基址 //建表时按实际长度分配，0号单元留空 int length; //表长度 }SSTable； 算法描述： int Search_Seq(SSTable ST，KeyType key){ //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。 ST.elem[0].key = key; //0号单元作为监视哨 for ( i=ST.length; ST.elem[i].key!=key; --i ); //从后往前找 return i； //找不到时，i为0 } // Search_Seq