VB程序设计的常用算法

六、查找问题

1．①顺序查找法（在一列数中查找某数x）

基本思想：一列数放在数组a(1)---a(n)中，待查找的数放在x 中，把x与a数组中的元素从头到尾一一进行比较查找。用变量p表示a数组元素下标，p初值为1，使x与a(p)比较，如果x不等于a(p)，则使p=p+1，不断重复这个过程；一旦x等于a(p)则退出循环；另外，如果p大于数组长度，循环也应该停止。（这个过程可由下语句实现）

p = 1

Do While x <> a(p) And p < =n

p = p + 1

Loop

下面写一查找函数Find，若找到则返回下标值，找不到返回0

Option Base 1

Private Function Find( a( ) As Single,x As Single) As Integer

Dim n%,p%

n=Ubound( a )

p = 1

Do While x <> a(p) And p < =n

p = p + 1

Loop

If p>n then p=0

Find=p

End Function

②基本思想：一列数放在数组a(1)---a(n)中，待查找的关键值为key，把key与a数组中的元素从头到尾一一进行比较查找，若相同，查找成功，若找不到，则查找失败。(查找子过程如下。index：存放找到元素的下标。)

Public Sub Search(a() As Variant, key As Variant, index%)

Dim i%

For i = LBound(a) To UBound(a)

If key = a(i) Then

index = i

Exit Sub

End If

Next i

index = -1

End Sub

2．折半查找法（只能对有序数列进行查找）

基本思想：设n个有序数（从小到大）存放在数组a(1)----a(n)中，要查找的数为x。用变量bot、top、mid 分别表示查找数据范围的底部（数组下界）、顶部（数组的上界）和中间，mid=(top+bot)/2，折半查找的算法如下：

（1）x=a(mid)，则已找到退出循环，否则进行下面的判断；

（2）x<a(mid)，x必定落在bot和mid-1的范围之内，即top=mid-1；

（3）x>a(mid)，x必定落在mid+1和top的范围之内，即bot=mid+1；

（4）在确定了新的查找范围后，重复进行以上比较，直到找到或者bot<=top。

将上面的算法写成如下函数，若找到则返回该数所在的下标值，没找到则返回-1。

Function search(a() As Integer, x As Integer) As Integer

Dim bot%, top%, mid%

Dim find As Boolean '代表是否找到

bot = LBound(a)

top = UBound(a)

find = False '判断是否找到的逻辑变量，初值为False

Do While bot <= top And Not find

mid = (top + bot) \ 2

If x = a(mid) Then

find = True

Exit Do

ElseIf x < a(mid) Then

top = mid - 1

Else

bot = mid + 1

End If

Loop

If find Then

search = mid

Else

search = -1

End If

End Function

七、插入法

把一个数插到有序数列中，插入后数列仍然有序

基本思想：n个有序数（从小到大）存放在数组a(1)—a(n)中，要插入的数x。首先确定x插在数组中的位置P；（可由以下语句实现）

p=1

do while x>a(p) and p<=n

p=p+1

loop

a(p)—a(n)元素向后顺移一个位置以空出a(p)元素放入x，可由以下语句实现：

for i=n to p step-1

a(i+1)=a(i)

next i

a(p)=x

将其写成一插入函数

Private Sub Instert(a() As Single, x As Single)

Dim p%, n%, i%

n = UBound(a)

ReDim Preserve a(n + 1)

p = 0

Do While x > a(p) And p < =n ' 确定x应插入的位置

p = p + 1

Loop

For i = n To p Step -1

a(i + 1) = a(i)

Next i

a(p) = x

End Sub