数据结构-顺序表及其应用

第1关：顺序表的实现之查找功能

任务描述

���关任务：实现顺序表中数据的查找功能。

相关知识

为了完成本关任务，你需要掌握：1. 线性表，2. 顺序表。

线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中，数据元素之间通过一对一首尾相接的方式连接起来。具体实现时，线性表可以采用不同的存储策略。下面给出了一种基于顺序存储的线性表（即：顺序表）实现方案：

该方案将线性表存储在一片连续空间里，并通过elem和length两个属性元素，组织成为一个结构体：

• elem: 给出线性表存储空间的起始地址
• length: 当前线性表里的数据元素个数

  为了讨论简化，我们假设每个数据元素是一个整数:

  1. typedef int ElemType; // 数据元素的类型

  顺序表

  顺序表的类型定义如下：

  1. #define MAXSIZE 100 //最大长度
  2. typedef struct {
  3. ElemType *elem; //指向数据元素的起始地址
  4. int length; //线性表的当前长度
  5. }SqList;

  若定义：SqList L，则通过L就可对顺序表进行操作。

  对数据元素进行操作处理是一个数据结构的重要组成部分。顺序表涉及的主要操作如下：

  • 顺序表的初始化：构造一个最多可存储MAXSIZE个数据元素的顺序表，并将其初始状态设置为length=0，即为空表。该操作函数具体定义如下：

    1. void SL_Initiate(SqList &L)

  • 释放顺序表：释放L.elem所指向的用于存储数据元素的存储空间。该操作函数具体定义如下：

    1. void SL_Free(SqList &L)

  • 判断顺序表是否为空：若为空表，则返回true,否则返回false。该操作函数具体定义如下：

    1. bool SL_IsEmpty(SqList L)

  • 判断顺序表是否已满：若顺序表达到最大长度，则返回 true,否则返回false。该操作函数具体定义如下：

    1. bool SL_IsFull(SqList L)

  • 创建顺序表：输入n个数据元素，创建一个顺序表。该操作函数具体定义如下：

    1. void SL_Create(SqList &L,int n)

  • 输出顺序表： 输出整个顺序表。该操作函数具体定义如下：

    1. void SL_Print(SqList L)

  • 获取顺序表的第i个数据元素：获取顺序表的第i个数据元素L.elem[i-1]赋给e，i的有效范围[1,L.length]。该操作函数具体定义如下：

    1. void SL_GetAt(SqList L, int i, ElemType &e)

  • 查找顺序表中第一个值为x的数据元素的位置： 在顺序表中查找第一个值为x的元素，找到则返回该元素在表中的位置，否则返回0。该操作函数具体定义如下：

    1. int SL_FindValue(SqList L, ElemType x)

    编程要求

    在右侧编辑器中补充代码，完成SL_GetAt和SL_FindValue两个操作函数，以实现顺序表中数据的查找功能。具体要求如下：

    1. SL_GetAt: 获取顺序表的第i个数据元素L.elem[i-1]，i的有效范围[1,L.length]
    2. SL_FindValue: 在顺序表中查找第一个值为x的元素，找到则返回该元素在表中的位置，否则返回0。

    注意：在实现两个操作函数的函数体内可调用其他操作。

    测试说明

    可在右侧文件夹中查看step1/Main.cpp文件，以便与你的操作。

    平台会对你编写的代码进行测试：

    测试输入： 5 //输入数据元素的个数 8 9 12 33 45 //输入5个数据元素，创建顺序表 2 //获取第2个数据元素 33 //查找值为33的数据元素 预期输出： 9 //输出第2个数据元素的值 4 //输出值为33的数据元素在表中的位置

    开始你的任务吧，祝你成功！

    /*************************************************************    顺序表的实现之查找功能  实现文件**************************************************************/#include #include #include "Seqlist.h"void SL_Initiate(SqList &L)// 顺序表的初始化，即构造一个空的顺序表{L.elem = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);L.length=0;}void SL_Free(SqList &L)// 释放顺序表{free(L.elem);}bool SL_IsEmpty(SqList L)// 判断顺序表是否空{return L.length==0;}bool SL_IsFull(SqList L)// 判断顺序表是否满{return L.length==MAXSIZE;}void SL_Create(SqList &L,int n)// 输入n个数据元素，创建一个顺序表L{int i;L.length=n;for(i=0; i