数据结构--查找的设计实现

查找实验日志指导教师刘锐实验时间：2010年12月06日学院数理专业数学与应用数学班级学号姓名实验室S331-A实验题目：查找实验目的：掌握顺序查找、折半查找及二叉排序树上查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。实验要求：1、分析、理解程序2、设计一组有序数据和一组随机数据输入，分别对线性表进行折半查找和顺序查找，比较它们的查找速度。3、将（45，24，55，12，37，53，60，28，40，70）中关键字依次插入初态为空的二叉排序树中，给出树的先序序列。实验主要步骤：一理解各种查找的基本思想1、顺序查找的基本思想：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。2、折半查找（二分查找）的基本思想：在有序的线性表中，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前查找区间就缩小一半。重复这一过程直到找到关键字为K的结点，或者直至当前查找区间为空（即查找失败）时为止。3、二叉排序树上的查找（BinSearch.c）二叉排序树的定义：或者是一棵空树；或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；（3）它的左、右子树也分别为二叉排序树。基本思想：当二叉排序树不空时，首先将给定值K和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。二在VC6.0的打开窗口中输入各种查找的程序代码，调试，编译，连接，运行。1，顺序查找时输入一组随机的7个数字8，10，5，14，25，16，34，需要查找的数字为25，执行结果为下图（1）。2，折半查找时输入一组有序数的7个数字1，3，5，7，9，11，13，需要查找的数为11，执行结果为下图（2）3，二叉排序树上查找时，将（45，24，55，12，37，53，60，28，40，70）中关键字依次插入初态为空的二叉排序树中，需要查找的数为55，执行结果为下图（3）所得到的二叉排序树为：该二叉排序树的先序序列为45，24，12，37，28，40，55，53，60，70实验结果：图（1）图（2）图（3）心得体会：通过这次实验，我基本理解了顺序查找、折半查找及二叉排序树上查找的基本思想和算法实现。我认为在某种时间性能上折半查找的查找速度要快于顺序查找。但折半查找只针对有序序列。二叉排序树上的查找也是一种比较好的查找方法。总之，不同的序列，应该选用最合适的查找方法，这样可以使平均查找的长度更短。从而节省查找的时间。附加：各种查找的程序代码顺序查找和折半查找#includestdio.h#includestdlib.h#defineMax100//假设文件长度typedefintKeyType;//自定义数据类型typedefstruct{//定义记录类型KeyTypekey;//关键字项}RecType;typedefRecTypeSeqList[Max+1];//SeqList为顺序表，表中第0个元素作为哨兵intn;//实际顺序表的长度intSeqSearch(SeqListR,KeyTypeK){inti;R[0].key=K;//设置哨兵for(i=n;R[i].key!=K;i--);//从表后往前找returni;//若i为0，表示查找失败；否则R[i]是要找的结点}intBinSearch(SeqListR,KeyTypeK){intlow=1,high=n,mid;//置当前查找区间上、下界的初值while(low=high){//当前查找区间R[low..high]不空mid=(low+high)/2;if(R[mid].key==K)returnmid;//查找成功返回if(R[mid].keyK)high=mid-1;//继续在R[low..mid-1]中查找elselow=mid+1;//继续在R[mid+1..high]中查找}return0;//当lowhigh时表示查找区间为空。查找失败}//==========输入顺序表========voidinput_int(SeqListR){inti;printf(Pleaseinputnum(int):);scanf(%d,&n);//读入顺序表的长度printf(Plaseinput%dinteger:,n);for(i=1;i=n;i++)scanf(%d,&R[i].key);}//==========输出顺序表========voidoutput_int(SeqListR){inti;for(i=1;i=n;i++)printf(%4d,R[i].key);}//==========主函数=======voidmain(){SeqListR;intK,i,j=0;input_int(R);//输入顺序表printf(PleaseInputSerachnumber:);scanf(%d,&K);//输入查找关键字printf(========Input1toSeqSearch;2toBinSearch:====);scanf(%d,&i);//输入1采用顺序查找；输入2采用折半查找if(i==1)j=SeqSearch(R,K);if(i==2)j=BinSearch(R,K);output_int(R);//输出顺序表printf(\nSearch%dis%dseat\n,K,j);//输出查找到的结点位置}二叉排序树上的查找#includestdio.h#includestring.htypedefstructnode{//结点类型intkey;//关键字项structnode*lchild,*rchild;//左右孩子指针}BSTNode;typedefBSTNode*BSTree;//BSTree是二叉排序树的类型//=========将K插入二叉排序树（BST）中======voidInsertBST(BSTree*Tptr,intk){BSTNode*f,*p=*Tptr;//p的初值指向根结点while(p){//查找插入位置if(p-key==k)return;//树中已有k，无须插入f=p;//f保存当前查找的结点p=(kp-key)?p-lchild:p-rchild;//若k小于p-key，则在左子树中查找，否则在右子树中查找。}p=(BSTNode*)malloc(sizeof(BSTNode));p-key=k;p-lchild=p-rchild=NULL;//生成新结点if(*Tptr==NULL)//原树为空*Tptr=p;//新插入的结点为新的根else//原树不空时if(kf-key)//将新结点*p作为*f的左孩子插入f-lchild=p;else//否则，新结点*p作为*f的右孩子插入f-rchild=p;}//==========利用插入算法生成二叉排序树=============BSTreeCreatBST(void)//输入一个结点序列，建立一棵二叉排序树，将根结点指针返回。{BSTreeT=NULL;//初始时T为空intk;scanf(%d,&k);//读入一个关键字while(k){//假设K=0是输入结束标志InsertBST(&T,k);//将k插入二叉排序树Tscanf(%d,&k);//读入下一个关键字}returnT;//返回建立的二叉排序树的根指针}//=========二叉排序树上的查找，成功时返回该结点的位置，否则返回NULL=========BSTNode*SearchBST(BSTreeT,intk){if(T==NULL||k==T-key)//递归终结条件returnT;//若T为空，查找失败；否则成功，返回找到的结点位置if(kT-key)//若k小于T-key在左子树上找；否则在右子树上找。returnSearchBST(T-lchild,k);elsereturnSearchBST(T-rchild,k);}//========先序遍历二叉树=============voidPreorder(BSTreeT){if(T){printf(%4d,T-key);//访问结点Preorder(T-lchild);Preorder(T-rchild);}}//==========主函数============voidmain(){BSTreeroot,P;//root为根结点指针intkey;printf(===InputInsertNode,'0'toend===\n);//输入要插入的结点，0结束插入root=CreatBST();//创建二叉排序树printf(====OutputPreorder:====\n);Preorder(root);//先序遍历输出二叉树的结点printf(\n===InputSearchkey:====);scanf(%d,&key);//输入要查找的关键字P=SearchBST(root,key);//查找返回结点的位置或NULLif(P)//P值不为NULL，查找成功；否则失败。printf(SearchFinish!!\n);elseprintf(NOFinish!!\n);}