查找算法 练习-2021届高三信息技术复习(无答案)

| 7页
| 302人阅读
| 3人下载

查找算法及程序实现

一、顺序查找

  1. 基本思想

在一组数据中按照顺序查找某一个关键字。

  1. 核心代码1(For语句)

   key = Val(Text1.Text)

   For i = 1 To n

     c = c + 1   '查找次数加1

     If a(i) = key Then

        Text2.Text = "在数组的" + Str(i) + "位置中"

        Exit For     '退出For语句

     End If

   Next i

   If i = n+1 Then     '写成If i >n Then也可以

     Text2.Text = "在数组中没有找到" + Str(key)

   End If

   Text3.Text = "共查找了" + Str(c) + "次"

  1. 核心代码2(Do语句)

   key = Val(Text1.Text)

   i = 1:c=0:flag = falsepage number 0


   Do While i <= n and flag = false

     c = c + 1   '查找次数加1

     If a(i) = key Then

        Text2.Text = "在数组的" + Str(i) + "位置中"

        flag = true            '标记找到目标

     End If

     i = i + 1

   Loop

   If  flag = false  Then      '写成If i >n and flag = false Then也可以

     Text2.Text = "在数组中没有找到" + Str(key)

   End If

   Text3.Text = "共查找了" + Str(c) + "次"

二、对分查找

  1. 基本思想

对分查找算法先把待查找的数据进行排序,然后按照折半思想进行查找。假设待查找数据按升序排列,将数组中间位置元素与查找关键字key比较,如果相等,则查找成功;否则利用中间位置将数组分成前、后两个子数组,如果查找关键字key大于中间位置元素,则进一步查找后一半子数组,否则进一步查找前一半子数组。重复以上过程,直到找到key,或直到子数组不存在为止,此时查找不成功。

  1. 核心代码(数组已升序排列)

    key=val(Text1.text)

    i = 1: j = n:c=0        'i表示起始边界,j表示终止边界page number 1


    Do While i <= j       '查找区间至少包含一个元素

       m = (i + j) \ 2     '取中间位置,有多种写法,如:m=fix((i+j)/2)或m=int((i+j)/2)

       c=c+1

       If a(m) = key Then

          Text2.Text = Str(m)

          Exit do     '退出Do语句

       End If

       If key < a(m) Then             '或

          j = m – 1    '前半段找

       Else

          i  = m + 1    '后半段找

       End If

    Loop

If i>j then Text2.Text ="找不到"         '查找的区间为空

Text3.Text = "共查找了" + Str(c) + "次"

  1. 对分查找算法变式(顺序查找类似)

    key=val(Text1.text)

    i = 1: j = n:c=0:found=False       'found=False表示还未找到

    Do While i <= j and found=False         'found=False也可以写成not found

       m = (i + j) \ 2            '取中间位置

       c=c+1page number 2


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。