网站模板设计工具,免费全自动推广平台,建网站能多少带宽,物业管理系统排行目录#x1f60b;
任务描述
相关知识
一、根据输入数据建立顺序表
二、顺序表的输出
三、顺序查找算法
测试说明
通关代码
测试结果 任务描述 本关任务#xff1a;实现顺序查找的算法 相关知识 为了完成本关任务#xff0c;你需要掌握#xff1a; 根据输入数据建立…目录
任务描述
相关知识
一、根据输入数据建立顺序表
二、顺序表的输出
三、顺序查找算法
测试说明
通关代码
测试结果 任务描述 本关任务实现顺序查找的算法 相关知识 为了完成本关任务你需要掌握 根据输入数据建立顺序表顺序表的输出顺序查找算法 一、根据输入数据建立顺序表 顺序表的基本概念 顺序表是线性表的一种存储结构它将线性表中的元素依次存放在一组连续的存储单元中。可以把它想象成一个排成一列的盒子每个盒子用来存放一个元素。实现步骤以简单的 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(SeqListT 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 SeqListT 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 SeqListT 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, 若查找的关键字k5则SeqSearch函数输出是3,6,2,10,1,8,5并返回值7。 若查找的关键字为k15则函数输出是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(vectorRecType R, const vectorint keys) {for (size_t i 0; i keys.size(); i) {RecType temp;temp.key keys[i];R.push_back(temp);}
}// 输出顺序表的函数遍历顺序表并输出每个元素的关键字
void DispList(const vectorRecType R) {for (size_t i 0; i R.size(); i) {cout R[i].key ;}cout endl;
}// 顺序查找算法按照要求输出比较的关键字并返回查找结果
int SeqSearch(const vectorRecType 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() {vectorRecType R;vectorint 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;
}测试结果
