顺序表查找

在这里我们采用最简单的查找算法，就是顺序查找。

主要工作：

1、新建一个数据结构SeqList代表顺序表。

2、确定线性表长度，元素内容，和查找元素，返回元素的位置。

1、当我们新建一个C++控制台应用程序之后，默认的给出的初始代码如下：

#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}

那么这个#include "stdafx.h" 与#include "stdio.h" 是什么关系呢，我们看一下stdfx.h的定义内容：

#pragma once
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>

这样就明白了，stdfx.h里面包含了stdio.h，这个问题就不用纠结了。

2、明确一下，我们顺序表中的元素数据类型都是int类型，所以要提前定义一下：

#define ElemType int

为了演示方便我们限定一下列表的最大长度为100，同样需要提前声明一下：

#define    MAXSIZE  100

3、顺序表的数据结构

typedef  struct
{
    ElemType  elem[MAXSIZE];  /*线性表占用的数组空间*/
    int       last;    /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），从0开始，空表置为-1*/
}SeqList;

4、查找函数

 

int  Locate(SeqList L, ElemType e)
{    
    int i=0;        /*i为扫描计数器，初值为0，即从第一个元素开始比较*/
    while ((i<=L.last)&&(L.elem[i]!=e))        /*顺序扫描表，直到找到值为key的元素, 或扫描到表尾而没找到*/
        i++; 
    if  (i<=L.last)
        return(i+1);  /*若找到值为e的元素，则返回其序号*/
    else
        return(-1);  /*若没找到，则返回空序号*/
}

需要注意的是在这里我们如果查找到相关元素，返回的是它的位置，不是索引，所以是从1开始。

5、完整代码

 

// SqlList.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#define ElemType int
#define    MAXSIZE  100  

typedef  struct
{ 
    ElemType  elem[MAXSIZE]; 
    int       last;  
}SeqList;

int  Locate(SeqList L, ElemType e)
{    
    int i=0;        /*i为扫描计数器，初值为0，即从第一个元素开始比较*/
    while ((i<=L.last)&&(L.elem[i]!=e))        /*顺序扫描表，直到找到值为key的元素, 或扫描到表尾而没找到*/
        i++; 
    if  (i<=L.last)
        return(i+1);  /*若找到值为e的元素，则返回其序号*/
    else
        return(-1);  /*若没找到，则返回空序号*/
}

int _tmain(int argc, _TCHAR* argv[])
{
    SeqList l;
    int p,q,r;
    int i;
    printf("请输入线性表的长度:");
    scanf("%d",&r);
    l.last = r-1;
    printf("请输入线性表的各元素值:\n");
    for(i=0; i<=l.last; i++)
    {
        scanf("%d",&l.elem[i]);
    }
    printf("请输入要查找的元素值:\n");
    scanf("%d",&q);
    p=Locate(l,q);
    if(p == -1)
        printf("在此线性表中没有该元素!\n");
    else
        printf("该元素在线性表中的位置为:%d\n",p);
    return 0;
}