大学计算机基础 课件 10.4.1顺序查找

大学计算机基础——基于计算思维（Windows10+Office2016）第10章算法思维与运用10.4.1顺序查找10.4查找算法查找算法在手机中查找联系人查找是从较大的数据集中找出或定位某个给定值（键值）的过程在图书馆中查找图书问题4顺序查找数据文件“data1.txt”中，有若干英语单词（每行一个），现从键盘输入一个单词，请在文件中查找该词，若找到则给出其位置（第几行），若没找到，提示“nofound”。1．问题分析由于数据集是存储在文本文件中的，所以首先要按顺序读出这些数据存放到某数组中，然后在数组中查找。但这些数据是无序的，所以只能从数组第1个元素（或最后1个元素）开始，按正序（或逆序）逐个扫描每个元素是否和键值相等，若相等则数组下标即为其位置，若扫描结束都不相等，则表明没有所查的数据（称为查找失败），所以称这种查找算法为顺序查找（sequentialsearch）。123456键值正序逆序顺序查找问题4顺序查找2．算法实现（1）设计main子图粗框图在main中应完成的功能是：①调用input子程序读文件到数组a中。②输入键值存入key中。③调用search子程序在数组a中查找key。④调用output子程序输出查找结果。①②③④问题4顺序查找2．算法实现（2）设计读文件子程序input该子程序的目的就是将文本文件中的数据读出到数组a中，所以a应作为其输出参数。a数组的大小n也应作为输出参数返回，以便控制查找范围，本题中n是动态的，由文件长度决定。顺序查找读文件子程序input问题4顺序查找2．算法实现（3）设计顺序查找子程序searchsearch的功能是从a数组的第1个元素开始到最后第n个元素，逐个扫描并和键值key比较，并返回一个值表示找到还是未找到，找到了还要返回所在位置。1234...nkeysearch返回一个值找到未找到所在位置问题4顺序查找2．算法实现（3）设计顺序查找子程序search注意在search中不做最后的输出处理，而是在output子程序中输出结果，所以输入参数有a、n、key，再增加2个输出参数，一个输出参数flag，目的是用来区分不同种状态。例如flag=0表示没找到，flag=1表示找到，通常称flag为状态变量，另一个输出参数为找到时的位置wz。问题4顺序查找2．算法实现（3）设计顺序查找子程序search在search中，查找前可以分别赋给状态变量和找到的位置一个初值（flag=0，wz=0），然后构造一个循环结构（设循环变量为i，初始值i=1，循环结束条件是i>n），在循环体内判断a[i]=key是否成立，若成立则状态变量发生改变（flag=1），同时保存当前位置wz=i，但循环不会中途结束，还会继续，所以可以在循环结束条件中再增加一个条件，或者找到了（即flag=1），也结束循环；而若a[i]=key不成立，则继续循环判断，此时状态变量一直不变化（flag=0）。所以循环结束后，通过flag返回的值就可判断找到还是没找到。顺序查找子程序search问题4顺序查找2．算法实现（4）设计输出子程序output根据search子程序查找的结果分别输出：若找到了（flag=1），则输出其位置wz，若没找到（flag=0），则显示输出“nofound”，所以其只要2个输入参数flag和wz。顺序查找输出子程序output问题4顺序查找2．算法实现（5）完善main子图当所有子程序设计好后，