在顺序表中实现按值查找

课程名称：数据结构  班级： 2007信息   实验日期： 2009年3 月20日 

学    号：    070703010051           姓名：石炳利  指导教师： 王端理    

                                               实验成绩：             

一、实验名称

    在顺序表中实现按值查找

2、实验目的及要求

     1.学会写算法2.学会对数据进行分析3.掌握线性表

三、实验环境

硬件：IBM-PC及兼容机

软件：windowsXP操作系统

Microsoft Visual C++ 6.0

4、实验内容

     在顺序表中实现按值查找

5、算法描述及实验步骤

     定义元素类型：ElemType int

     用building_sqlist(sqlist &)函数开辟一片连续空间

     用input(sqlist &)函数实现空间的数据输入

    用search(sqlist&)函数进行按值查找

Typedef class {

public:

    friend void building_sqlist(sqlist &);//创建顺序表

    friend void input(sqlist &);//为顺序表赋值

    friend void search(sqlist&，int);//按值找查值

    private:

     TypeElem *elem;  //顺序表基址

      int length;//顺序表长度

      int listsize;//顺序表大小    };

void building_sqlist(sqlist &L) {       

     L.elem=(TypeElem *)malloc(Sq_size*sizeof(TypeElem)); //开辟空间

        if(!L.elem)      exit ERROR   //开辟失败则返回

     L.length=Sq_size;  //开辟成功则空间的大小

     L.listsize=Sq_size;

     return Open success; //开辟成功 }

void search(sqlist&L,int e)

{        for(i=1;i<=L.length;i++){

            if(e==L.elem[i])        {w=i;break;}}

        if(w!=-1)

       输出元素所在位置；

            else        输出失败；

}

六 源代码：

 #include

#include

using namespace std;

#define Sq_size 5

class sqlist

    {

public:

    friend void building_sqlist(sqlist &);

    //创建顺序表

    friend void input(sqlist &);

    //为顺序表赋值

    friend void search(sqlist&,int);

    //按值找查值

private:

     int *elem;  //顺序表基址

      int length;//顺序表长度

      int listsize;//顺序表大小

    };

void main()

{    

    sqlist L;

     building_sqlist(L);

     input(L);

     int e;

     void findnumber(int&);

     findnumber(e);

     search(L,e);

}

void building_sqlist(sqlist &L)

   {      

     L.elem=(int *)malloc(Sq_size*sizeof(int));

     //开辟空间

    if(!L.elem) {cout<<"ERROR"<     exit(1);}//开辟失败则返回

     L.length=Sq_size;//开辟成功则空间的大小

     L.listsize=Sq_size;

cout<<"开辟空间成功"<    

}

inline void input(sqlist &L)

{    

    int i;

cout<<"输入顺序表的"<     for( i=1;i<=L.length;i++)

{cin>>L.elem[i];}    

      for(i=1;i<=L.length;i++)

{cout<}

void findnumber(int &e)

{

cout<<"输入要查找的数";

cin>>e;

}

void search(sqlist&L,int e)

{

      int w=-1,i;

    for(i=1;i<=L.length;i++)

    {

        if(e==L.elem[i])

        {w=i;break;}

    }

    if(w!=-1)

     cout<    else

     cout<<"找不到"<   

}

7、调试过程及实验结果

八 算法分析：在算法中按值查找是从头到尾的查找所以共循环了Sq_size次

如果Sq_size大小不定为n则该算法时间复杂度为O(n);