网站符号河南怎样做网站推广
目录😋
任务描述
相关知识
一、根据输入数据建立顺序表
二、顺序表的输出
三、顺序查找算法
测试说明
通关代码
测试结果
任务描述
本关任务：实现顺序查找的算法
相关知识
为了完成本关任务，你需要掌握：
- 根据输入数据建立顺序表
- 顺序表的输出
- 顺序查找算法
一、根据输入数据建立顺序表
- 顺序表的基本概念
顺序表是线性表的一种存储结构，它将线性表中的元素依次存放在一组连续的存储单元中。可以把它想象成一个排成一列的盒子，每个盒子用来存放一个元素。- 实现步骤（以简单的 C++ 代码为例）
- 定义顺序表结构：
首先要定义一个结构体来表示顺序表。这个结构体通常包含一个数组来存放元素，以及一个变量来记录当前顺序表中元素的个数。例如：#define MAX_SIZE 100 // 假设顺序表最大容量为 100 template <typename T> struct SeqList {T data[MAX_SIZE]; // 存储元素的数组int length; // 顺序表中元素的个数SeqList() : length(0) {} // 构造函数，初始化元素个数为 0 };- 输入数据并构建顺序表：
通过循环从用户输入中获取数据，并将其存入顺序表的数组中，同时更新元素个数（length）。示例代码如下：template <typename T> void createSeqList(SeqList<T>& list) {T element;int i = 0;std::cout << "请输入元素（输入非数字字符结束）：";while (std::cin >> element) {if (i < MAX_SIZE) {list.data[i++] = element;} else {std::cout << "顺序表已满。" << std::endl;break;}}list.length = i; }二、顺序表的输出
- 基本思路
顺序表的输出就是遍历顺序表中的元素并将它们打印出来。从顺序表的第一个元素开始，按照元素的存储顺序，逐个访问并输出元素。- 代码实现（以 C++ 为例）
以下是一个简单的输出顺序表的函数：template <typename T> void printSeqList(const SeqList<T>& list) {std::cout << "顺序表中的元素为：";for (int i = 0; i < list.length; i++) {std::cout << list.data[i] << " ";}std::cout << std::endl; }三、顺序查找算法
- 算法原理
- 顺序查找是一种最简单的查找算法。它从顺序表的第一个元素开始，逐个将元素与要查找的目标元素进行比较，直到找到目标元素或者遍历完整个顺序表。
- 就像在一排盒子里找东西，从第一个盒子开始，一个一个地看，直到找到想要的东西或者看完所有盒子。
- 代码实现（以 C++ 为例）
以下是顺序查找算法的函数实现：template <typename T> int sequentialSearch(const SeqList<T>& list, T target) {for (int i = 0; i < list.length; i++) {if (list.data[i] == target) {return i; // 返回目标元素在顺序表中的位置（下标）}}return -1; // 如果未找到，返回 -1 }- 性能分析
- 时间复杂度：在最坏情况下，需要遍历整个顺序表才能确定目标元素是否存在。如果顺序表中有个元素，那么时间复杂度为。在最好情况下，目标元素是顺序表中的第一个元素，时间复杂度为。平均时间复杂度也是。
- 空间复杂度：顺序查找算法只需要几个额外的变量来进行循环和比较，不依赖于顺序表的大小，所以空间复杂度为。
测试说明
平台会对你编写的代码进行测试：
测试输入：(第一行是输入的一组原始关键字数据，第二行是要查找的关键字）
3 6 2 10 1 8 5 7 4 9 5
预期输出：
请输入一组数据 : 关键字序列:3 6 2 10 1 8 5 7 4 9 请输入要查找的关键字 :5 查找5所比较的关键字: 3 6 2 10 1 8 5 元素5的位置是7
测试输入：
3 6 2 10 1 8 5 7 4 9 15
预期输出：
请输入一组数据 : 关键字序列:3 6 2 10 1 8 5 7 4 9 请输入要查找的关键字 :15 查找15所比较的关键字:3 6 2 10 1 8 5 7 4 9 元素15不在表中
提示：顺序查找算法中要依次输出与k所比较的关键字，用空格分隔开。
假设顺序表中R的关键字依次是3,6,2,10,1,8,5,7,4,9,
若查找的关键字k=5，则SeqSearch函数输出是3,6,2,10,1,8,5，并返回值7。
若查找的关键字为k=15，则函数输出是3,6,2,10,1,8,5,7,4,9，并返回值0。
开始你的任务吧，祝你成功！
通关代码
#include <iostream>
#include <vector>
using namespace std;
// 定义查找元素的结构体类型，包含关键字和其他数据（这里暂未详细使用其他数据部分）
struct RecType {int key;// 可以按需添加其他数据成员及对应操作，此处简化只关注关键字key
};// 创建顺序表，将输入的关键字数据存入顺序表中
void CreateList(vector<RecType> &R, const vector<int> &keys) {for (size_t i = 0; i < keys.size(); ++i) {RecType temp;temp.key = keys[i];R.push_back(temp);}
}// 输出顺序表的函数，遍历顺序表并输出每个元素的关键字
void DispList(const vector<RecType> &R) {for (size_t i = 0; i < R.size(); ++i) {cout << R[i].key << " ";}cout << endl;
}// 顺序查找算法，按照要求输出比较的关键字，并返回查找结果
int SeqSearch(const vector<RecType> &R, int k) {for (size_t i = 0; i < R.size(); ++i) {cout << R[i].key << " ";if (R[i].key == k) {return i + 1; // 返回位置，这里的位置是从1开始计数，所以下标加1}}return 0; // 如果没找到，返回0表示元素不在表中
}int main() {vector<RecType> R;vector<int> keys;cout << "请输入一组数据 :" << endl;int num;while (cin >> num) {keys.push_back(num);if (cin.get() == '\n') {break;}}CreateList(R, keys);cout << "关键字序列:";DispList(R);int k;cin >> k;cout << "请输入要查找的关键字 :" << k << endl;cout << "查找" << k << "所比较的关键字: ";int result = SeqSearch(R, k);if (result != 0) {cout << endl << "元素" << k << "的位置是" << result << endl;} else {cout << endl << "元素" << k << "不在表中" << endl;}return 0;
}
测试结果
