实验五--查找算法实现

实验类型：验证性 

实验要求：必修

实验学时： 2学时

一、实验目的：

参照各种查找算法程序样例，验证给出的查找常见算法。 

二、实验要求：

1、掌握各种查找算法的特点，测试并验证查找的常见算法。

2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。

三、实验内容：

1. 建立有序表，采用折半查找实现某一已知的关键字的查找。

2．利用折半查找算法在一个有序表中插入一个元素，并保持表的有序性。

源程序如下：

#include

using namespace std;

template

class sL_List

{

    private:

        int mm;

        int nn;

        T *v;

    public:

        sL_List(){mm=0;nn=0;return;}

        sL_List(int);

        int search_sL_List(T);

        int insert_sL_List(int,T);

        void prt_sL_List();

};

template

sL_List::sL_List(int m)

{

    mm=m;

    v=new T[mm];

    nn=0;

    return;

}

template

int sL_List::search_sL_List(T x)

{

    int i,j,k;

    i=1;j=nn;

while(i<=j)

    {

        k=(i+j)/2;

        if(v[k-1]==x)

            return(k-1);

     if(v[k-1]>x)

            j=k-1;

        else i=k+1;

    }

    return(-1);

}

template

int sL_List::insert_sL_List(int p,T x)

{

    if(nn==mm)

    {

     cout<<"溢出！"<        return(-1);

    }

    p=nn-1;

while(v[p]>x)

    {

        v[p+1]=v[p];

        p=p-1;

    }

    v[p+1]=x;

    nn=nn+1;

    return(1);

}

template

void sL_List::prt_sL_List()

{

    int i;

for(i=0;i     cout<    return;

}

int main()

{

    int k,t,q,result;

    int a[20]={10,20,30,40,50,60,70,80};

sL_Lists(20);

for(k=0;k<8;k++)

        s.insert_sL_List(k+1,a[k]);

cout<<"输出有序对象s:"<    s.prt_sL_List();

cout<<"请输入要查找的数:"< cin>>t;

cout< cout<<"你要查找的数在数组中的位置为:"<    result=s.search_sL_List(t);

cout< cout<<"请插入一个元素:"< cin>>q;

cout<    s.insert_sL_List(k+1,q);

cout<<"插入后有序表变为:"<    s.prt_sL_List();

    return 0;

}

实验结果如下：

心得体会：

1.通过这次试验，我知道了一些查找的基本方法，并且了解了折半查找的典型方法及技巧。

2.并且我掌握了利用折半法插入一个元素的方法。

3.常见问题在于在插入位置时，易混淆位置与数值的关系，以及c++中的一些基本定义方法易忘记。