实验: 简单查找算法
一． 需求和规格说明：
查找算法这里主要使用了顺序查找，折半查找，二叉排序树查找和哈希表查找四种方法。
设计思想：
开始的时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树，以使得更直观。哈希表则是利用给定的函数式建立索引，方便查找。
二． 设计表示：
三． 实现注释：
其实查找排序这部分和前面的一些知识联系的比较紧密，例如顺序表的建立和实现，顺序表节点的排序，二叉树的生成和遍历，这里主要是中序遍历。应该说有些知识点较为熟悉，但在实现的时候并不是那么顺利。在查找到数据的时候要想办法输出查找过程的相关信息，并统计。这里顺序查找和折半查找均使用了数组存储的顺序表，而二叉树则是采用了链表存储的树形结构。为了直观起见，在用户输入了数据后，分别输出已经生成的数组和树。折半查找由于只能查找有序表，因此在查找前先调用函数对数据进行了排序。
在查找后对查找数据进行了统计。二叉排序树应该说由于有了之前二叉树的基础，并没有费太大力气，主要是在构造二叉树的时候，要对新加入的节点数据和跟数据进行比较，如果比根节点数据大则放在右子树里，如果比根节点数据小则放入左子树。建立了二叉树后，遍历和查找就很简单了。具体代码见源代码部分。
5.详细设计表示：
6.用户手册：
程序运行后，用户首先要输入数据的个数。接下来输入一组数据并根据提示进行顺序查找，二分查找，二叉排序树查找和哈希表查找等操作，由于操作直接简单这里不再详述。
8.源代码清单和结果：
#include <stdio.h>
#define LENGTH 100
#include <stdlib.h>
#include <time.h>
#define INFMT "%d"
#define OUTFMT "%d "
/* #define NULL 0L */
#define BOOL int
#define TRUE 1
#define FALSE 0
#define LEN 10000
typedef int ElemType;
typedef struct BSTNode
{
ElemType data;
struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;
typedef BSTree BiTree;
/* 插入新节点 */
void Insert(BSTree *tree, ElemType item)
{
BSTree node = (BSTree)malloc(sizeof(BSTNode));
node->data = item;
node->lchild = node->rchild = NULL;
if (!*tree)
*tree = node;
else
{
BSTree cursor = *tree;
while (1)
{
if (item < cursor->data)
{
if (NULL == cursor->lchild)
{
cursor->lchild = node;
break;
}
cursor = cursor->lchild;
}
else
{
if (NULL == cursor->rchild)
{
cursor->rchild = node;
break;
}
cursor = cursor->rchild;
}
}
}
return;
}
void showbitree(BiTree T)
// 递归显示二叉树的广义表形式
{
if(!T){printf("空");return;}
printf("%d",T->data);// 打印根节点
if(T->lchild ||T->rchild)
{
putchar('(');
showbitree(T->lchild);// 递归显示左子树
putchar(',');
showbitree(T->rchild);// 递归显示右子树
putchar(')');
}
}
/* 查找指定值 */
BSTree Search(BSTree tree, ElemType item)
{
BSTree cursor = tree;
while (cursor)
{
if (item == cursor->data)
return cursor;
else if ( item < cursor->data)
cursor = cursor->lchild;
else
cursor = cursor->rchild;
}
return NULL;
}
/* 中缀遍历 */
void Inorder(BSTree tree)
{
BSTree cursor = tree;
if (cursor)
{
Inorder(cursor->lchild);
printf(OUTFMT, cursor->data);
Inorder(cursor->rchild);
}
}
/* 回收资源 */
void Cleanup(BSTree tree)
{
BSTree cursor = tree, temp = NULL;
if (cursor)
{
Cleanup(cursor->lchild);
Cleanup(cursor->rchild);
free(cursor);
}
}
void searchtree(BSTree root)
{
char choice;
printf("中序遍历的结果为:\n");
Inorder(root);
printf("\n\n");
ElemType item;
BSTree ret;
/* 二叉排序树的查找测试 */
do
{
printf("\n请输入查找数据：");
scanf("%d", &item);
getchar();
printf("Searching...\n");
ret = Search(root, item);
if (NULL == ret)
printf("查找失败！");
else
printf("查找成功！");