数据结构查找实验报告

计算机科学与技术学院

实验教学中心

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");

}

                                                          

 

第二篇:数据结构查找实验报告电子版

福州大学数计学院

《数据结构》上机实验报告

专业:应用数学

相关推荐