首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


(1) 方法:首先将要查找的给定值 k 与中间位置的记录关键字进行比较,这个中间记录将查找表分成两 个区间,如果比较结果相等则查找成功;若不相等,再根据 k 与中间记录关键字的比较结果确定下一步在 哪个区间查找,这样逐步缩小区间,直到查找成功或该表中没有这样的元素为止。 (2) 性能分析:对含有 n 个记录的有序顺序表,记录的查找在等概率的前提下,查找成功的平均查找长 度 ASL 成功= = ;查找不成功的比较次数最多为 。 3. 索引顺序表查找(又称分块查找) 若以索引顺序表表示静态查找表,则可采用分块查找的方法进行查找。要求必须先将数据元素组成按关键 字有序的索引表,而顺序表(表本身)则分块有序。 (1) 方法:首先确定待查关键字所在的块(子表) ,此时可采用顺序查找/折半查找方法,然后再在已确 定的块内进行顺序查找。 (2) 性能分析:假设长度为 n 的表均匀地分为 b 块,每块中的记录个数有 s 个,则: ①用顺序查找法确定所在的块 ASL 成功= + = ; 当 时,ASL 取最小值 。 ②用折半查找确定所在的块:ASL 成功 。 三、 动态查找表 1.二叉排序树 (1) 定义:二叉排序树或者为一棵空树,或者是具有如下性质的二叉树: ① 若它的左子树非空,则左子树上所有结点的值均小于它的根结点的值; ② 若它的右子树非空,则右子树上所有结点的值均大于它的根结点的值; ③ 它的左右子树也分别为二叉排序树。 (2) 特点:对二叉排序树进行中序遍历必定得到所有元素值的一个有序序列,二叉排序树的构造过程即 是对无序序列进行排序的过程。 (3) 构造过程:二叉排序树的构造过程是在二叉排序树中逐次插入新结点的过程,每次插入的新结点都 是二叉排序树上新的叶子结点。 (4) 查找性能分析:假设二叉排序树共有 n 个结点,在等概率情况下,查找成功的平均查找长度 ASL 与 二叉排序树的形态有关。 ①最坏情况(二叉排序树成为一棵单枝树,即每个结点至多一个分支) ASL 成功= = ②最好情况(二叉排序树与 n 个的结点的折半查找树形态相同)

ASL 成功= ③随机情况: ASL 成功= 2. 平衡二叉树(AVL) (1) 定义:平衡二叉树或者为一棵空树,或者是具有如下性质的二叉树: 、 ① 它的左子树和右子树深度之差的绝对值不超过 1; ② 它的左右子树分别为平衡二叉树。 、 (2) 结点的平衡因子:结点的左子树的深度减去结点右子树的深度。 (3) 平衡二叉树的构造过程是一个逐步插入,逐步平衡的过程,每次插入的结点如果发生了不平衡,可 以按照一定的规律旋转子树,从而达到平衡。 四、 哈希表查找 1.研究哈希表查找技术的两个重要问题是:构造哈希函数和处理冲突。 (1)构造哈希函数的方法有:直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。 其中除留余数法最为常用。 (2)处理冲突的方法有:开放定址法、再哈希法、链地址法、公共溢出区。 2.哈希表查找过程 设哈希函数为 H(key) ,哈希表为 A[0..m-1], 则对给定的值 key,哈希查找过程见图 8-1。 </P><P></P><P></P><P></P><P></P><P> 图 8-1 哈希表查找过程

第二节 静态查找表
【问题描述】 静态查找表可以有不同的表示方法,在不同的表示方法中,实现查找操作的方法也不同。对静态查找表可 以用顺序表或线性链表进行表示,也可组织成有序的顺序表,或者是索引顺序表,相应的查找方法可采用 顺序查找方法、折半查找方法和索引顺序查找的方法。设计一个有关静态查找表的建立、查找等基本操作 的演示程序,并计算和分析查找成功时的平均查找长度。 【数据描述】 静态查找表的抽象数据类型定义: ADT StaticSearchTable{ 数据对象 D: D 是由具有相同特性的数据元素的集合。 数据关系 R:数据元素同属一个集合。 基本操作 P: Create(&ST,n) 构造一个含有 n 个元素的静态查找表 ST。

Destroy(&ST)

将一个已经存在的静态查找表 ST 销毁;

Search(ST,key) 在表 ST 中查找是否存在其关键字和给定的 key 相等的数据元素 Traverse(ST,visit()) 按某种次序对 ST 的每个元素进行访问 }ADT StaticSearchTable; 在本章以后各节的讨论中,涉及的关键字类型和数据元素类型统一约定如下; typedef int KeyType; typedef struct{ KeyType key; …… } ElemType; 【算法描述】 //静态查找表的顺序存储结构 typedef struct{ ElemType *elem; int length; }SSTable; Status Create(SSTable &ST){ //建立一个含有 n 个元素的顺序表,表的长度 n 由键盘输入 Scanf(n); if (!(ST.elem=(ElemType*) malloc( (n+1)*sizeof(ElemType))) return OVERFLOW; For (i=1;i<=n;i++) scanf(ST.elem[i].key);//输入数据元素的关键字和其他数据项 ST.length=n; Return OK; }//Create int Search(Sstable ST,KeyType key){ //在顺序表中查找其关键字等于 key 的数据元素,若查找成功,返回该元素在表中的//位置,否则返回 0; ST.elem[0].key=key;//设置监视哨 For (i=ST.length;!EQ(ST.elem[i].key,key);i--); Return i; } //定义关键字类型

// 定义元素类型

【C 源程序】 #include <stdlib.h> #include <stdio.h> typedef int KeyType; typedef struct { KeyType key; }ElemType; typedef struct{ ElemType *elem; int length; }SSTable; int create(SSTable * ST){ int i,n; printf("nPlease input the length of table:"); scanf("%d",&n); ST->elem=(ElemType*)malloc((n+1)*sizeof(ElemType)); if (!ST->elem) return 0; printf("nPlease input %d data:",n); for (i=1;i<=n;i++) scanf("%d",&(ST->elem[i].key)); ST->length=n; return 1; } int search(SSTable ST,KeyType key,int *time){ /*在顺序表中查找其关键字等于 key 的数据元素,若找到,则函数值为该元素在表中的位置,否则为 0 , 指针变量 time 记录所需和关键字进行比较的次数。 */ int i; ST.elem[0].key=key; *time=1; for (i=ST.length;ST.elem[i].key!=key;i--,++*time); return i;

} main(){ SSTable ST; KeyType key; int i,time; char ch; if (create(&ST)){ /*创建成功*/ printf("nCreate is complete"); /*可重复查询, */ do { printf("nInput the key you want to search:"); scanf("%d",&key); i=search(ST,key,&time); if (i!=0) /*查找成功,输出所在位置及 key 与元素关键字的比较次数*/ {printf("nSuccess,the position is %d ",i); printf("nThe time of compare is %d",time); } else /*查找失败,输出 key 与元素关键字的比较次数*/

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐