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


} } main(){ char ch; KeyType key; BiTree bt,s; int i=0; /*建立一棵二叉排序树,元素值从键盘输入,直到输入关键字等于-1 为止*/ printf("nPlease input data(-1:end)n"); scanf("%d",&key); bt=NULL; while (key!=-1){ s=(BiTree)malloc(sizeof(BiTNode)); (s->data).key=key;s->lchild=s->rchild=NULL; insertBST(&bt,s); scanf("%d",&key); } printf("nCreate is completen"); /*中序遍历已建立的二叉排序树*/ inorder(bt); /*二叉排序树的查找,可多次查找,并输出查找的结果*/ do { printf("nInput the key you want to search:"); scanf("%d",&key); s=searchBST(bt,key); if (s!=NULL) printf("nsuccess,the value is %d ",s->data.key); else printf("nunsuccess");

printf("ncontinue(y/n):n"); ch=getch(); }

while (ch=='y' || ch=='Y') ; } 【测试数据】 1.根据运行提示,在建立时输入: Please input data(-1:end) 45 24 53 45 12 24 90 –1 Input the key you want to search: 90 success,the value is 90 continue(y/n):y Input the key you want to search:100 unsuccess continue(y/n):n 2.读者可根据运行提示,自己输入数据建立一棵二叉排序树,然后进行多次查询。注意观察运行结果,读者 可自己先在纸上画出这棵二叉排序树,注意分析和比较运行结果,以加强对二叉树排序的建立和查找过程 的理解。 【说明】 1. 简单的算法分析:设二叉排序树的结点数目为 n,在等概率情况下二叉排序树的查找成功的平均查找长 度与二叉排序树的形状有关,最坏情况(二叉排序树成为一棵单枝树,即每个结点至多一个分支) ,ASL 成功= = ;最好情况(二叉排序树与 n 个的结点的折半查找树形态相同)ASL 成功= ) ; 2. 数据元素类型定义时只写了关键字,若有其他数据项略,读者可根据实际情况加入,并在数据元素的 输入和输出中加入其它数据项即可。 【实验题】 1. 以上程序实现了二叉排序树的建立、查找、中序遍历算法,要求读者完善以上程序,实现以下功能: (1) 遍历二叉排序树(如先序、后序和层次遍历) ; (2) 在二叉排序树中删除一个结点,并释放结点的空间; (3) 完善查找算法,计算和输出每次查找所需和关键字进行比较的次数,以及在等概率情况下查找成功 时的平均查找长度。 2. 试写一个判定给定二叉树是否为二叉排序树的算法。 (设二叉树以二叉链表作存储结构) 。 3. 将两棵二叉排序树合并成一棵二叉排序树。 4. 对于一些实际的问题:如图书管理、学籍管理等能抽象出适当的数学模型,对数据对象和它们的关系进

行分析,以合适的方式加以组织,综合应用动态查找算法完成数据的日常建立、查询、插入、删除等工作。

第四节

哈希表设计

【问题描述】 研究哈希(HAXI)表查找技术的两个重要问题是:构造 HAXI 函数和处理冲突。现在要求针对某个数 据集合中的关键字设计一个哈希表 (选择合适的哈希函数和处理冲突的方法) , 完成 HAXI 表的建立、 查找, 并计算 HAXI 表查找成功的平均查找长度。HAXI 函数的构造方法有多种,其中除留余数法是一种最简单 和最常用的方法。 考虑具体问题的关键字集合,如{19,14,23,1,68,20,84,27,55,11,10,79}这样一组数据和给定 的哈希表长 m 或哈希表的装填因子 a,选用除留余数法和线性探测再散列技术解决冲突所形成的哈希表以 及该哈希表在查找成功时的平均查找长度 ASL。 【数据描述】 HAXI 表是根据设定的 HAXI 函数和处理冲突的方法将一组关键字映射到一个有限的连续的地址区间上, 并以关键字在地址区间的“象”作为记录在表中的存储位置。因此我们可以采用动态分配的顺序存储结构表 示 HAXI 表。 typedef struct { KeyType key ;</P><P>}ElemType; //元素类型的定义

ElemType *HAXI;//动态分配的哈希表的首地址 【算法描述】 step1:选择合适的哈希函数 H( key)=key % p(P 为小于或等于 HAXI 表长的最大质数) ; step2:计算各个关键字的直接哈希函数值; step3:根据处理冲突的方法建立哈希表,并输出; step4:在哈希表中进行查找,输出查找的结果,以及所需和记录关键字比较的次数,并计算和输出在等概 率情况下查找成功的平均查找长度。 【C 源程序】 #include <stdlib.h> #include <stdio.h> #define NULL 0 typedef int KeyType; typedef struct { KeyType key ;</P><P>}ElemType;

int haxi(KeyType key,int m){ /*根据哈希表长 m, 构造除留余数法的哈希函数 haxi*/ int i,p,flag; for (p=m ; p>=2 ; p--) /*p 为不超过 m 的最大素数*/

{ for (i=2,flag=1;i<=p/2 &&flag;i++) if (p %i==0) flag=0; if (flag==1) break; } return key%p; } void inputdata(ElemType **ST,int n ){ /*从键盘输入 n 个数据,存入数据表 ST(采用动态分配的数组空间)*/ KeyType key; int i; (*ST)=(ElemType*)malloc(n*sizeof(ElemType)); printf("nPlease input %d data:",n); for (i=0;i<n;i++) scanf("%d",&((*ST)[i].key)); } void createhaxi(ElemType **HAXI,ElemType *ST,int n,int m){ /*根据数据表 ST,构造哈希表 HAXI*,n,m 分别为数据集合 ST 和哈希表的长度*/ int i,j; (*HAXI)=(ElemType*)malloc(m*sizeof(ElemType)); for (i=0;i<m;i++) (*HAXI)[i].key=NULL; /*初始化哈希为空表(以 0 表示空)*/ for (i=0;i<n;i++){ j=haxi(ST[i].key,m); /*获得直接哈希地址*/ /*哈希函数*/

while ((*HAXI)[j].key!=NULL) j=(j+1)%m;/*用线性探测再散列技术确定存放位置*/ (*HAXI)[j].key=ST[i].key; } } /*将元素存入哈希表的相应位置*/

int search(ElemType *HAXI,KeyType key,int m,int *time){ /*在表长为 m 的哈希表中查找关键字等于 key 的元素,并用 time 记录比较次数, 若查找成功,函数返回值为其在哈希表中的位置,否则返回-1*/ int i; *time=1; i=haxi(key,m); while (HAXI[i].key!=0 && HAXI[i].key!=key) {i++; ++*time;} if (HAXI[i].key==0) return -1; else return i; } main(){ ElemType *ST,*HAXI; KeyType key; int i,n,m,stime,time; char ch; printf("nPlease input n && m(n<=m)"); /*输入关键字集合元素个数和 HAXI 表长*/ scanf("%d%d",&n,&m); inputdata(&ST,n); createhaxi(&HAXI,ST,n,m); /*输出已建立的哈希表*/ printf("nThe haxi Table isn"); for (i=0;i<m;i++) printf("%5d",i); printf("n"); for (i=0;i<m;i++) printf("%5d",HAXI[i].key); /*哈希表的查找,可进行多次查找*/ do { printf("nInput the key you want to search:"); scanf("%d",&key); i=search(HAXI,key,m,&time); if (i!=-1) {printf("nSuccess,the position is %d ",i);/*查找成功*/ /*调用函数,输入 n 个数据*/ /*建立哈希表*/

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐