数据结构查找实验报告

实验题9.1 设计一个程序exp9-1.cpp,输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序方法找关键字5的过程。

程序如下:

//文件名:exp9-1.cpp

#include <stdio.h>

#define MAXL 100                             //定义表中最多记录个数

typedef int KeyType;

typedef char InfoType[10];

typedef struct

{    

       KeyType key;                         //KeyType为关键字的数据类型

    InfoType data;                         //其他数据

} NodeType;

typedef NodeType SeqList[MAXL];                   //顺序表类型

int SeqSearch(SeqList R,int n,KeyType k) //顺序查找算法

{

    int i=0;

    while (i<n && R[i].key!=k)

       {

              printf("%d ",R[i].key);

              i++;                             //从表头往后找

       }

    if (i>=n)

              return -1;

    else

       {

              printf("%d",R[i].key);

              return i;

       }

}

void main()

{

       SeqList R;

       int n=10,i;

       KeyType k=5;

       int a[]={3,6,2,10,1,8,5,7,4,9};

       for (i=0;i<n;i++)                         //建立顺序表

              R[i].key=a[i];

       printf("关键字序列:");

       for (i=0;i<n;i++)

              printf("%d ",R[i].key);

       printf("\n");

       printf("查找%d所比较的关键字:\n\t",k);

       if ((i=SeqSearch(R,n,k))!=-1)

              printf("\n元素%d的位置是%d\n",k,i);

       else

              printf("\n元素%d不在表中\n",k);

       printf("\n");

}

   截图如下:

实验题9.2 设计一个程序exp9-2.cpp,输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找法查找关键字9的过程。

  程序如下:

//文件名:exp9-2.cpp

#include <stdio.h>

#define MAXL 100                             //定义表中最多记录个数

typedef int KeyType;

typedef char InfoType[10];

typedef struct

{    

       KeyType key;                  //KeyType为关键字的数据类型

    InfoType data;                  //其他数据

} NodeType;

typedef NodeType SeqList[MAXL];                          //顺序表类型

int BinSearch(SeqList R,int n,KeyType k)    //二分查找算法

{

       int low=0,high=n-1,mid,count=0;

       while (low<=high)

       {    

              mid=(low+high)/2;

              printf("  第%d次比较:在[%d,%d]中比较元素R[%d]:%d\n",++count,low,high,mid,R[mid].key);

                     if (R[mid].key==k)     //查找成功返回

                     return mid;

              if (R[mid].key>k)     //继续在R[low..mid-1]中查找

                     high=mid-1;

              else

                     low=mid+1;            //继续在R[mid+1..high]中查找

       }

       return -1;

}

void main()

{

       SeqList R;

       KeyType k=9;

       int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;

       for (i=0;i<n;i++)                         //建立顺序表

              R[i].key=a[i];

       printf("关键字序列:");

       for (i=0;i<n;i++)

              printf("%d ",R[i].key);

       printf("\n");

       printf("查找%d的比较过程如下:\n",k);

       if ((i=BinSearch(R,n,k))!=-1)

              printf("元素%d的位置是%d\n",k,i);

       else

              printf("元素%d不在表中\n",k);

}

   截图如下:

实验题9.3 设计一个程序exp9-3.cpp,输出在顺序表{8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分块查找法查找(每块的块长为5,共5块)关键字46的过程。

  程序如下:

//文件名:exp9-3.cpp

#include <stdio.h>

#define MAXL 100                             //定义表中最多记录个数

#define MAXI 20                                      //定义索引表的最大长度

typedef int KeyType;

typedef char InfoType[10];

typedef struct

{    

       KeyType key;                  //KeyType为关键字的数据类型

    InfoType data;                  //其他数据

} NodeType;

typedef NodeType SeqList[MAXL];            //顺序表类型

typedef struct

{    

       KeyType key;                              //KeyType为关键字的类型

       int link;                                      //指向分块的起始下标

} IdxType;

typedef IdxType IDX[MAXI];                    //索引表类型

int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)       //分块查找算法

{

       int low=0,high=m-1,mid,i,count1=0,count2=0;

       int b=n/m;                  //b为每块的记录个数

       printf("二分查找\n");

       while (low<=high)    //在索引表中进行二分查找,找到的位置存放在low中

       {    

              mid=(low+high)/2;

              printf("  第%d次比较:在[%d,%d]中比较元素R[%d]:%d\n",count1+1,low,high,mid,R[mid].key);

           if (I[mid].key>=k)

                     high=mid-1;

           else

                     low=mid+1;

              count1++;                     //累计在索引表中的比较次数

       }

       if (low<m)                 //在索引表中查找成功后,再在线性表中进行顺序查找

       {    

              printf("比较%d次,在第%d块中查找元素%d\n",count1,low,k);

              i=I[low].link;

              printf("顺序查找:\n    ");

              while (i<=I[low].link+b-1 && R[i].key!=k)

              {

                     i++;count2++;

                     printf("%d ",R[i].key);

              }                   //count2累计在顺序表对应块中的比较次数

           printf("\n");

              printf("比较%d次,在顺序表中查找元素%d\n",count2,k);

              if (i<=I[low].link+b-1)

                     return i;

           else

                     return -1;

       }

       return -1;

}

void main()

{

       SeqList R;

       KeyType k=46;

       IDX I;

       int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;

       for (i=0;i<25;i++)                       //建立顺序表

              R[i].key=a[i];

       I[0].key=14;I[0].link=0;

       I[1].key=34;I[1].link=4;

       I[2].key=66;I[2].link=10;

       I[3].key=85;I[3].link=15;

       I[4].key=100;I[4].link=20;

       if ((i=IdxSearch(I,5,R,25,k))!=-1)

              printf("元素%d的位置是%d\n",k,i);

       else

              printf("元素%d不在表中\n",k);

       printf("\n");

}

  截图如下:

 

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

福州大学数计学院

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

专业:应用数学

相关推荐