实验五--查找算法实现

实验类型：验证性 实验要求：必修 实验学时： 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<<\"溢出！\"<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}

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:\"<cout<<\"请输入要查找的数:\"<>t; cout<cout<<\"你要查找的数在数组中的位置为:\"<cout<<\"请插入一个元素:\"<>q; cout<s.insert_sL_List(k+1,q);

cout<<\"插入后有序表变为:\"<实验结果如下：

心得体会：

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

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

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