数据结构 查找与排序.docx

《数据结构 查找与排序.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验5查找与排序（一）班级：计科1404学号：4姓名：马莹玉一．实现思路开始的时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。当二叉树建好后，中序遍历序

2、列即为由小到大的有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树，以使得更直观。哈希表则是利用给定的函数式建立索引，方便查找。。二.源代码：#include#defineLENGTH100#include#include#defineINFMT"%d"#defineOUTFMT"%d"/*#defineNULL0L*/#defineBOOLint#defineTRUE1#defineFALSE0#defineLEN10000typedefintElemType;typ

3、edefstructBSTNode{ElemTypedata;structBSTNode*lchild,*rchild;}BSTNode,*BSTree;typedefBSTreeBiTree;/*插入新节点*/voidInsert(BSTree*tree,ElemTypeitem){BSTreenode=(BSTree)malloc(sizeof(BSTNode));node->data=item;node->lchild=node->rchild=NULL;if(!*tree)*tree=node;else{BSTreecursor=*

4、tree;while(1){if(itemdata){if(NULL==cursor->lchild){cursor->lchild=node;break;}cursor=cursor->lchild;}else{if(NULL==cursor->rchild){cursor->rchild=node;break;}cursor=cursor->rchild;}}}return;}voidshowbitree(BiTreeT)//递归显示二叉树的广义表形式{if(!T){printf("空");return;}printf

5、("%d",T->data);//打印根节点if(T->lchild

6、

7、T->rchild){putchar('(');showbitree(T->lchild);//递归显示左子树putchar(',');showbitree(T->rchild);//递归显示右子树putchar(')');}}/*查找指定值*/BSTreeSearch(BSTreetree,ElemTypeitem){BSTreecursor=tree;while(cursor){if(item==cursor->data)returncursor;elseif(it

8、emdata)cursor=cursor->lchild;elsecursor=cursor->rchild;}returnNULL;}/*中缀遍历*/voidInorder(BSTreetree){BSTreecursor=tree;if(cursor){Inorder(cursor->lchild);printf(OUTFMT,cursor->data);Inorder(cursor->rchild);}}/*回收资源*/voidCleanup(BSTreetree){BSTreecursor=tree,temp=NU

9、LL;if(cursor){Cleanup(cursor->lchild);Cleanup(cursor->rchild);free(cursor);}}voidsearchtree(BSTreeroot){charchoice;printf("中序遍历的结果为:");Inorder(root);printf("");ElemTypeitem;BSTreeret;/*二叉排序树的查找测试*/do{printf("请输入查找数据：");scanf("%d",&item);getchar();printf("Searching.

10、..");ret=Search(root,item);if(NULL==ret)printf("查找失败！");elseprintf("查找成功！");printf("继