搜索算法设计
- 格式：doc
- 大小：123.00 KB
- 文档页数：6
实验四 搜索算法设计
一、 实验目的
1 熟练掌握顺序搜索、折半搜索和索引搜索等基本搜索算法，熟悉这些算法适合在何种
存储结构下实现；
2 熟练掌握二叉排序树的特性、建立方法以及动态搜索算法；
3 熟练掌握散列表的特点及构造方法。
二、 实验内容与算法
基本题
1、实现基于有序顺序表的折半搜索。
int binsearch(seqlist r,int n,keytype k)
{
int low=0,high=n-1,mid,count=0;
while(low<=high)
{
mid=(low+high)/2;
cout<<"第"<<++count<<" 次查找:"<<"在【"<
return mid;
if(r[mid].key>k)
high=mid-1;
else
low=mid+1;
}
return -1;
}
2、设单链表的结点是按关键字的值从小到大排列的，试写出对此表的搜索程序并调试。
int find(lnode *head,datatype x)
{
lnode *p=head->next; int i=0;
while(p!=NULL)
{
++i;
if(p->data==x) return i;
p=p->next;
}
return -1;
}
加强题
3 若输入 12000个不同的整数，其值介于0和19999之间，用散列法将这些数进行存
储，散列函数为H(n)=n/2，请设计实现程序并调试。
提高题
4 建立二叉搜索树、实现其删除算法。
要求：实现后分析其时间复杂度
typedef int keytype;
typedef char infortype;
typedef struct node{
keytype key;
infortype data;
struct node *lchild,*rchild;
}bstnode;
int path[max];
void dispbst(bstnode *bt)
{
if(bt!=NULL)
{
printf("%d",bt->key);
if(bt->lchild!=NULL||bt->rchild!=NULL)
{
printf("(");
dispbst(bt->lchild);
if(bt->rchild!=NULL)
printf(",");
dispbst(bt->rchild);
printf(")");
}
}
}
int insert(bstnode *&p,keytype k)
{
if(p==NULL)
{
p=(bstnode*)malloc(sizeof(bstnode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if(k==p->key)
return 0;
else if(k
return insert(p->lchild,k);
else
return insert(p->rchild,k);
}
bstnode* create(keytype a[],int n)//构建
{
bstnode *bt=NULL;
int i=0;
while(i
{
printf(" 第%d步，插入%d：",i+1,a[i]);
dispbst(bt);printf("\n");
i++;
}
return bt;
}
void Delete(bstnode *&p)
{
bstnode *q,*s;
if(p->rchild==NULL)
{
q=p;
p=p->lchild;
free(q);
}
else if(p->lchild==NULL)
{
q=p;
p=p->rchild;
free(q);
}
else
{
q=p;s=p->lchild;
while(s->rchild!=NULL)
{
q=s;s=s->rchild;
}
p->key=s->key;
q->rchild=s->lchild;
free(s);
}
}
int delbst(bstnode *&bt,keytype k)//删除
{
if(bt==NULL)
return 0;
else {
if(k
return delbst(bt->lchild,k);
else if(k>bt->key)
return delbst(bt->rchild,k);
else
{
Delete(bt);
return 1;
}
}
}
三、算法实现
1、实现基于有序顺序表的折半搜索。
2、设单链表的结点是按关键字的值从小到大排列的，试写出对此表的搜索程序并调试。
3 若输入 12000个不同的整数，其值介于0和19999之间，用散列法将这些数进行存储，
散列函数为H(n)=n/2，请设计实现程序并调试。
运行结果：
功能表：
1、创建散列表....
2、向主文件插入元素....
3、向主文件删除元素....
4、向主文件超找元素....
5、输出主文件....
6、结束....
请选择（1-5）：
1
创建散列表.......
功能表：
1、创建散列表....
2、向主文件插入元素....
3、向主文件删除元素....
4、向主文件超找元素....
5、输出主文件....
6、结束....
请选择（1-5）：
2
插入元素...输入插入值
6
功能表：
1、创建散列表....
2、向主文件插入元素....
3、向主文件删除元素....
4、向主文件超找元素....
5、输出主文件....
6、结束....
请选择（1-5）：
3
删除....输入删除值b
12
删除成功！
功能表：
1、创建散列表....
2、向主文件插入元素....
3、向主文件删除元素....
4、向主文件超找元素....
5、输出主文件....
6、结束....
请选择（1-5）：
5
输出.......
0: 48 32
1:
2: 34 18
3:
4: 68
5:
6: 6 54 6
7: 23
8:
9: 9 25 57
10:
11: 59
12:
13:
14: 14 46
15: 15
功能表：
1、创建散列表....
2、向主文件插入元素....
3、向主文件删除元素....
4、向主文件超找元素....
5、输出主文件....
6、结束....
请选择（1-5）：
6
Press any key to continue
4 建立二叉搜索树、实现其删除算法。
四、实验感想
通过本次试验我熟练掌握了顺序搜索、折半搜索和索引搜索等基本搜索算法，并熟悉了
这些算法适合在何种存储结构下实现；同时熟练掌握了二叉排序树的特性、建立方法以及动
态搜索算法；也熟练掌握了散列表的特点及构造方法。
