实验报告
计算机科学与技术学院
实验教学中心
2014 年 12 月 10日
实验项目名称:查找( 2 学时)
一、实验目的
1. 掌握顺序表的查找算法在顺序存储结构上的实现。
2. 掌握建立二叉排序树和在二叉排序树上查找指定结点的算法在链式存储结构上的实现。
3. 掌握散列表的建立和查找算法在顺序存储结构上的实现。
4. 掌握散列表的建立和查找算法在链式存储结构上的实现。
二、实验内容
1 顺序表查找在顺序存储结构上的实现。其中函数sqsearch的功能是实现在顺序线性表中顺序查找关键字,函数bisearch的功能是实现在顺序线性表中折半查找关键字。
2. 建立二叉排序树和在二叉排序树上查找指定结点的算法在链式存储结构上的实现。其中函数bstsearch的功能是实现利用递归方法在二叉排序树上查找指定结点,函数bstsearch1的功能是实现利用非递归方法在二叉排序树上查找指定结点,函数bstinsert的功能是实现在二叉排序树上插入结点,函数createbsttree的功能是实现建立一棵二叉排序树,函数inorder的功能是实现中序遍历二叉树。
3. 建立散列表和在散列表中查找指定结点的算法在顺序存储结构的实现。其中函数createsqhash的功能是实现建立顺序存储结构的散列表,函数hashsqsearch的功能是实现在顺序存储结构上实现散列表查找。
4.建立散列表和在散列表中查找指定结点的算法在链式存储结构的实现。其中函数createlkhash的功能是实现建立链式存储结构的散列表,函数hashlksearch的功能是实现在链式存储结构上实现散列表查找。
三、实验步骤
实验一:
1、建立顺序储存结构。
2、建立sqsearch函数和bisearch函数。
3、在主函数中调用。
实验二:
1、在链式储存结构上建立二叉树;
2、建立线索二叉树;
3、对线索二叉树进行索引;
4、在主函数上运行;
实验三:
1、建立顺序储存结构;
2、创建createsqhash函数;
3、在主函数中运行调用;
实验四:
1、用链式储存结构建立散列表;
2、创建createlkhash函数;
3、在主函数中调用;
四、实验结果
实验一:
实验二:
实验三:
实验四:
五、程序代码
实验一:
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
#define n 10
struct record {int key;datatype others;};
int sqsearch(struct record r[], int k)
{
int i;
for(i=0; i<=n-1; i++) if (r[i].key==k) return(i+1);
return(0);
}
int bisearch(struct record r[ ], int k)
{
int low=0,mid,high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(r[mid].key==k) return(mid+1);
else if(r[mid].key>k) high=mid-1; else low=mid+1;
}
return(0);
}
int main()
{
int i; struct record r[n];
for (i=0;i<n;i++){r[i].key=rand() * 100/ RAND_MAX; printf("%d\t",r[i].key);}
if (sqsearch(r,44)>0) printf("44 found\n"); else printf("44 not found\n");
if(bisearch(r,44)>0) printf("44 found\n"); else printf("44 not found\n");
}
实验二:
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
#define n 10
typedef struct node{int key; struct node *lchild,*rchild;}bitree;
void inorder(bitree *bt)
{
if (bt!=0) {inorder(bt->lchild); printf("%d\t",bt->key); inorder(bt->rchild);}
}
bitree *bstsearch(bitree *t, int key)
{
if (t==0 || t->key==key) return(t);
else if (t->key<key) return(bstsearch(t->rchild,key)); else return(bstsearch(t->rchild,key));
}
bitree *bstsearch1(bitree *t, int key)
{
bitree *p=t;
while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild;
return(0);
}
void bstinsert(bitree *bt,int key)
{
if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;}
else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key);
}
void createbsttree(bitree *bt)
{
int i;
for(i=1;i<=n;i++) bstinsert(bt,rand() * 100/ RAND_MAX);
}
main( )
{
bitree *bt=0;
createbsttree(bt);
inorder(bt); printf("\n");
if(bstsearch(bt,44)!=0) printf("found\n"); else printf("not found\n");
}
实验三:
#include <stdio.h>
#define m 8
#define n 7
#define p 7
struct record {int key; int flag;};
int a[n]={7,9,16,23,30,32,34};
void createsqhash(struct record hashtable[])
{
int i,j,k;
for(k=0;k<m;k++)hashtable[k].flag=0;
for(k=0;k<n;k++)
{
j=i=a[k] % p;
while(1)
if(hashtable[j].flag==0){hashtable[j].key=a[k];hashtable[j].flag=1;break;}
else {j=(j+1)%m; if(j==i){printf("overflow\n");break;}}
}
}
int hashsqsearch(struct record hashtable[ ],int k)
{
int i,j; j=i=k % p;
while (hashtable[j].key!=k && hashtable[j].flag!=0 ) {j=(j+1)%m; if (i==j) return(-1);}
if (hashtable[j].key==k) return(j); else return(-1);
}
main( )
{
struct record hashtable[m]; int i;
createsqhash(hashtable);
for(i=0;i<m;i++) if (hashtable[i].flag==0) printf("%c\t",'$'); else printf("%d\t",hashtable[i].key);
if (hashsqsearch(hashtable,16)!=-1) printf("found\n"); else printf("not fouund\n");
}
实验四:
#include <stdio.h>
#include <stdlib.h>
#define m 8
#define n 7
#define p 7
typedef struct node {int key; struct node *next;} lklist;
int a[n]={7,9,16,23,30,32,34};
void createlkhash(lklist *hashtable[ ])
{
int i,k; lklist *s;
for(i=0;i<m;i++)hashtable[i]=0;
for(i=0;i<n;i++){s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];k=a[i] % p; s->next=hashtable[k]; hashtable[k]=s;}
}
lklist *hashlksearch(lklist *hashtable[ ],int k)
{
int i=k % p; lklist *s;
for(s=hashtable[i]->next; s!=0; s=s->next) if (s->key==k) return(s);
return(0);
}
main( )
{
lklist *hashtable[m],*s; int i;
createlkhash(hashtable);
for(i=0;i<m;i++){for(s=hashtable[i]; s!=0;s=s->next) printf("%d\t",s->key); printf("\n");}
if (hashlksearch(hashtable,16)!=0) printf("found\n"); else printf("not fouund\n");
}
福州大学数计学院
《数据结构》上机实验报告
专业:应用数学
实验题91设计一个程序exp91cpp输出在顺序表36210185749中采用顺序方法找关键字5的过程程序如下文件名exp91cp…
昆明理工大学信息工程与自动化学院学生实验报告201201学年第一学期课程名称数据结构开课实验室年月日一实验内容查找算法其中线性表的…
实验报告课程名称实验项目数据结构查找姓名xx专业班级学号网络工程网络132130402xxxx计算机科学与技术学院实验教学中心20…
100410528孙晨添数据结构实验报告实验第四章实验简单查找算法一需求和规格说明查找算法这里主要使用了顺序查找折半查找二叉排序树…
实验四查找一实验目的1掌握顺序表的查找方法尤其是折半查找方法2掌握二叉排序树的查找算法二实验内容1234建立一个顺序表用顺序查找的…
数据结构实验实验一静态查找表中的查找一、实验目的:1、理解静态查找表的概念2、掌握顺序查找和折半查找算法及其实现方法3、理解顺序查…
实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删…
81实现顺序查找的算法一实验目的1熟悉掌握各种查找方法深刻理解各种查找算法及其执行的过程2学会分析各种查找算法的性能二实验内容81…
一实验目的和要求1掌握图的相关概念包括图有向图无向图完全图子图连通图度入度出度简单回路和环等定义2重点掌握图的各种存储结构包括邻接…
河南省高等教育自学考试实验报告册计算机及应用专业本科段数据结构姓名李威威准考证号所属地市焦作市实验地点焦作大学实验实训中心实验日期…
信息检索课程结业报告姓学信息检索与web搜索应用背景及概念信息检索InformationRetrieval是指信息按一定的方式组织…