您现在的位置:首页 >> 课程案例 >> 内容

数组的综合应用例子

时间:2009-6-19 8:54:45 点击:5679

数组的综合应用
   为了加深对数组的理解,下面结合一些常用算法的编程来更加深入地学习和使用数组。由于一维数组和二维数组是程序设计中最常用的数组形式,因此这里的举例均为一维和二维数组。
1.数组元素的输入和输出
[例5-12] 由用户输入5个数组元素的值并把它们输出在窗体上。
Option Explicit
Private Sub Command1_Click()
    Dim a(1 To 5) As Integer, i As Integer
    For i=1 To 5
        a(i)=InputBox("请输入第" & Str(i) & "个元素")
    Next
    For i=1 To 5
        Print "a (";i; ")="; a(i)
    Next
End Sub
程序运行后,单击命令按钮,执行事件过程Command1_Click。若输入5个值10,20,30,40,50,则窗体上显示的输出结果是:
a(1)=10
a(2)=20
a(3)=30
a(4)=40
a(5)=50
程序中声明了一个具有5个元素的一维整型数组,分别用循环语句输入、输出数组元素的值。在循环体内,数组元素用循环控制变量i作下标,i值的不同就表示数组元素的不同。
在程序中引用数组元素时,其下标可以使用表达式。只要表达式的结果不超出数组定义的上界和下界范围,下标表达式就是合法的。例如本例中,若i=2,则:
a(i+1)的值为30;
a(a(i+3)\10)的值为50。
下标表达式的值还可以是实数,此时VB将自动对其进行四舍五入取整。例如:
a(1+0.4)的值是10;
a(2+0.5)的值30。
2.数组元素插入删除
算法说明:数组中元素的插入和删除一般是在已固定序列的数组中插入或删除一个元素,使得插入或删除操作后的数组还是有序的。
基本思路:首先要找到插入位置或要删除的元素,然后以此位置为基准对后续元素进行移位。
[例5-12]数组元素的插入。把14插入到有序数列1,4,7,10,13,16,19,22,25,28中,如图5-10所示。


图5-10 数组元素的插入
代码如下:
Private Sub Command1_Click()
    Dim a(10) As Integer
    Dim i As Integer, k As Integer
    For i = 0 To 9          '生成数组
        a(i) = i * 3 + 1
       Print a(i);
    Next i
    Print
    Print "插入14"
    For k = 0 To 9          '查找插入14在数组中的位置
        If 14 < a(k) Then Exit For
    Next k
    For i = 9 To k Step -1 '从最后元素开始逐个后移,腾出位置
        a(i + 1) = a(i)
    Next i
    a(k) = 14               '插入数14
    For i = 0 To 10
        Print a(i);
    Next i
    Print
End Sub
[例5-13]数组元素的删除。把有序数列1,4,7,10,13,16,19,22,25,28中元素13删除,如图5-11所示。


图5-11 数组元素的删除
代码如下:
Dim a() as integer
For i = 1 To 10         '生成数组
ReDim a(1 to i)
a(i) = (i-1) * 3 + 1
Print a(i);
Next i
Print
Print "删除13"
For k = 1 To 10         '查找13在数组中的位置
If a(k) = 13 Then Exit For
Next k
For i = k + 1 To 10 '从13所在位置的下一个元素开始逐个前移
a(i - 1) = a(i)
Next i
Redim preserve a(1 to 9)
For i = 1 To 9
Print a(i);
Next i
Print
3.求素数
素数是除了1和它本身之外再不能被其他数整除的自然数。由于找不到一个通项公式来表示所有的素数,所以对于数学家来说,素数一直是一个未解之谜,几百年来不知吸引了世界上多少优秀的数学家。尽管他们苦心钻研,呕心沥血,但至今仍然未见分晓。
自从有了计算机之后,人们借助于计算机的威力,已经找到了

以内的所有素数。
求素数的方法有很多种,最简单的方法是根据素数的定义来求。对于一个自然数N,用大于1小于N的各个自然数都去除一下N,如果都除不尽,则N为素数,否则N为合数。但是,如果用素数定义的方法来编制计算机程序,它的效率一定是非常低的,其中有许多地方都值得改进。
1)对于一个自然数N,只要能被一个非1非自身的数整除,它就肯定不是素数,所以不必再用其他的数去除。
2)对于N来说,只需用小于N的素数去除就可以了。例如,如果N能被15整除,实际上就能被3和5整除,如果N不能被3和5整除,那么N也决不会被15整除。
3)对于N来说,不必用从2到N-1的所有素数去除,只需用小于等于

的所有素数去除就可以了。这一点可以用反证法来证明:
如果N是合数,则一定存在大于1小于N的整数d1和d2,使得N=d1×d2。
如果d1和d2均大于

,则有:N=d1×d2>

×

=N。而这是不可能的,所以,d1和d2中必有一个小于或等于


第二种求素数的方法是用筛法求素数。此法称厄拉多塞筛法。厄拉多塞是一位古希腊数学家,他在寻找素数时,采用了一种与众不同的方法:
先将2~N的各数写在纸上,并在在2的上面画一个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再划去3的其他倍数;现在既未画圈又没有被划去的第一个数 是5,将它画圈,并划去5的其他倍数……,依次类推,直到所有小于或等于N的各数都画了圈或划去为止。这时,表中画了圈的以及未划去的那些数正好就是小于 N的素数。
这种方法很像一面筛子,把满足条件的数留下来,把不满足条件的数筛掉。在计算机中,筛法可以用给数组单元置零的方法来实现。具体来说就是:
首先声明一个数组a(i),i=1,2,3,…,同时,令所有的数组元素都等于下标值,即a(i)=i,以生成1~N的自然数。并根据以上做法,令i不是素数的元素a(i)=0(即划去该数)。输出结果时,只要判断a(i)是否等于零即可。
筛法是计算机程序设计中常用的算法之一。
第三种方法是用6N±1法求素数。任何一个自然数,总可以表示成为如下的形式之一:
6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)
显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,除了2和3之外,所有的素数都可以表示成6N±1的形式(N为自然数)。
根据上述分析,我们可以构造另一面筛子,只对形如6 N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。在程序上,我们可以用一个二重循环实现这一点,外循环i按3的倍数递增,内循环j为0~1的循环,则2(i+j)-1恰好就是形如6N±1的自然数。
[例5-14]用素数定义求N以内的素数。
在窗体上放置txtN和txtP两个文本框、一个标签、两个选项按钮、一个名为cmdStart的命令按钮,txtN用于N,txtP用于输出结果。txtP的MultiLine属性设为True,Scrollbar设为Horizontal。按钮的Click事件代码如下:
Option Explicit

Private Sub cmdStart_Click()
    Dim i As Long, j As Long, k As Long
    Dim NonP As Boolean
    Dim PrimeNumber() As Long  '存放素数
   
    k = 0
    ReDim PrimeNumber(0)
    PrimeNumber(0) = 2         '2是最小素数
    For i = 3 To txtN
        NonP = False
        For j = 2 To Sqr(i)
            If i Mod j = 0 Then    '判断i是否可被j整除
                NonP = True
                Exit For
            End If
        Next j
        If Not NonP Then
            k = k + 1
            ReDim Preserve PrimeNumber(k)
            PrimeNumber(k) = i
        End If
    Next i
   
    txtP = ""                      '清空显示结果文本框
    For i = 0 To UBound(PrimeNumber)  '显示结果,每行3个
        If (i + 1) Mod 3 = 0 Then
            txtP = txtP & PrimeNumber(i) & vbCrLf
        Else
            txtP = txtP & PrimeNumber(i) & vbTab
        End If
    Next i
End Sub
程序中vbCrLf和 vbTab是VB内置常量,分别代表回车换行和Tab。图5-12是求10000以内素数的运行结果。


图5-12 定义法求素数
[例5-15]用筛法求N以内的素数。
窗体设计同[例5-14],程序清单如下:
Option Explicit

Private Sub cmdStart_Click()
    Dim i As Long, j As Long, k As Long
    Dim PrimeNumber() As Long
   
ReDim PrimeNumber(1 To txtN)
For i = 1 To txtN           '生成1~N的自然数
PrimeNumber(i) = i
Next i
       
PrimeNumber(1) = 0          '1不是素数
For i = 2 To Sqr(txtN)
If PrimeNumber(i) <> 0 Then
For j = i + 1 To txtN
If PrimeNumber(j) <> 0 And j Mod i = 0 Then
   PrimeNumber(j) = 0   '划去素数的倍数
End If
Next j
End If
Next i
       
txtP = ""
k = 0
   For i = 1 To UBound(PrimeNumber)
       If PrimeNumber(i) <> 0 Then     '非0的是素数
          k = k + 1
          If k Mod 3 = 0 Then
              txtP = txtP & PrimeNumber(i) & vbCrLf
          Else
              txtP = txtP & PrimeNumber(i) & vbTab
          End If
       End If
   Next i
End Sub
求10000以内素数的运行结果如图5-13所示。对比图5-12,可以发现两种方法所求结果相同。读者可以用两种方法求10000000以内的素数,根据它们所耗时间来判断两种算法的优劣。


图5-13 筛法求素数
4.有序数组的合并
将两个有序数组A、B合并成另一个有序的数组C,最容易想到的算法是采用合并后重新排序的方式,但此法显然效率不高。为讨论方便,我们假设A、B、C均为升序数组,则另一种常用的合并算法的基本思想是:
(1)先在A、B数组中各取第一个元素进行比较,将小的元素放入C数组;
(2)取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较,重复上述比较过程,直到某个数组被先排完;
(3)将另一个数组剩余元素抄入C数组,合并排序完成。
[例5-16]已知升序数组A和B,请将A、B合并新的升序数组C。不能采用合并后重新排序的方式合并。
程序清单如下:
Private Sub Form_Click()
    Dim ia As Integer, ib As Integer, ic As Integer
    Dim A(), B(), C()
   
    A = Array(3, 5, 7)                '初始化A和B
    B = Array(1, 2, 4, 6, 8, 9)
    ReDim C(UBound(A) + UBound(B) + 1)    '重定义C的大小为A、B之和
   
    Print "数组A:";                  '输出A、B
    For ia = 0 To UBound(A)
        Print A(ia);
    Next ia
    Print
    Print "数组B:";
    For ib = 0 To UBound(B)
        Print B(ib);
    Next ib
    Print
   
    ia = 0: ib = 0: ic = 0
    Do While ia <= UBound(A) And ib <= UBound(B) '当A和B数组均未比较完
       If A(ia) < B(ib) Then                     'A、B较小者放入C
          C(ic) = A(ia): ia = ia + 1
       Else
           C(ic) = B(ib): ib = ib + 1
       End If
    ic = ic + 1
    Loop
    Do While ia <= UBound(A)    'B组先排完,A数组中的剩余元素抄入C数组
        C(ic) = A(ia)
        ia = ia + 1: ic = ic + 1
    Loop
    Do While ib <= UBound(B)    'A组先排完,B数组中的剩余元素抄入C数组
        C(ic) = B(ib)
        ib = ib + 1: ic = ic + 1
    Loop
   
    Print "数组C:";           '输出C
    For ic = 0 To UBound(C)
        Print C(ic);
    Next ic
End Sub
程序运行结果如图5-14所示。


图5-14 有序数组的合并
讨论:为什么重定义C的大小用“ReDim C(UBound(A) + UBound(B) + 1)”,而不用“ReDim C(UBound(A) + UBound(B))”或“ ReDim C(UBound(A) + UBound(B) + 2)”?
5.矩阵运算
矩阵可用二维数组表示,建立和输出二维数组要用嵌套的循环语句。此部分用两个典型的矩阵运算举例来说明二维数组及控件的应用。
[例5-17]求矩阵相乘C=A×B。设A、B、C分别为m×p,p×n和m×n的矩阵,按矩阵乘法的定义有:


若有一个4×3的数组A乘以一个3×2的数组B,将得到一个4×2的数组C。
程序用Load方法生成若干个文本框用于输入矩阵A、B及输出C。程序界面设计如图5-15所示,三个文本框作仅为Load方法的模板,不用于数据的输入与输出,它们分别命名为txtA、txtB、txtC,Index属性为0,Visible属性为False;命令按钮名为cmdStart。


图5-15 矩阵乘法界面设计
程序为:
Option Explicit
Option Base 1    '设置数组的默认下标下界为1
Const M = 4, P = 3, N = 2

Private Sub Form_Load()
    Dim i%, j%, k%, iOrd(2) As Integer
   
    k = 1
    iOrd(1) = txtA(0).Left: iOrd(2) = txtA(0).Top
    For i = 1 To M
        For j = 1 To P
            Load txtA(k)
            txtA(k).Left = iOrd(1) + txtA(0).Width * j + 5
            txtA(k).Top = iOrd(2)
            txtA(k).Visible = True
            k = k + 1
        Next j
        iOrd(2) = iOrd(2) + txtA(0).Height + 5
        iOrd(1) = txtA(0).Left
    Next i
   
    k = 1
    iOrd(1) = txtB(0).Left: iOrd(2) = txtB(0).Top
    For i = 1 To P
        For j = 1 To N
            Load txtB(k)
            txtB(k).Left = iOrd(1) + txtB(0).Width * j + 5
            txtB(k).Top = iOrd(2)
            txtB(k).Visible = True
            k = k + 1
        Next j
        iOrd(2) = iOrd(2) + txtB(0).Height + 5
        iOrd(1) = txtB(0).Left
    Next i
   
    k = 1
    iOrd(1) = txtC(0).Left: iOrd(2) = txtC(0).Top
    For i = 1 To M
        For j = 1 To N
            Load txtC(k)
            txtC(k).Left = iOrd(1) + txtC(0).Width * j + 5
            txtC(k).Top = iOrd(2)
            txtC(k).Visible = True
            k = k + 1
        Next j
        iOrd(2) = iOrd(2) + txtC(0).Height + 5
        iOrd(1) = txtC(0).Left
    Next i
End Sub
Private Sub cmdStart_Click()
    Dim A(M, P) As Integer
    Dim B(P, N) As Integer
    Dim C(M, N) As Integer
    Dim i%, j%, k%, l%, sum%
 
    l = 1
    For i = 1 To M
        For k = 1 To P  '输入矩阵A元素
            A(i, k) = Val(txtA(l))
            l = l + 1
    Next k, i
   
    l = 1
    For k = 1 To P      '输入矩阵A元素
        For j = 1 To N
            B(k, j) = Val(txtB(l))
            l = l + 1
    Next j, k

    For i = 1 To M      '矩阵相乘
        For j = 1 To N
            sum = 0
            For k = 1 To P
                sum = sum + A(i, k) * B(k, j)
            Next k
            C(i, j) = sum
    Next j, i
   
    l = 1
    For i = 1 To M      '输出矩阵C
        For j = 1 To N
            txtC(l) = C(i, j)
            l = l + 1
    Next j, i
End Sub
程序中数组iOrd用于保存模板文本框的x和y坐标;形如“Next j,i”之类的语句是嵌套For循环的简洁写法。若

  

,则程序运行后,

,结果如图5-16所示。


图5-16 矩阵乘法运行结果
如果更改常量M、P、N的值,程序可实现更多类型矩阵的乘法。
[例5-18]矩阵的转置是指把矩阵元素aij与aji交换,即把矩阵顺时针旋转90°。试编程实现n阶方阵转置。
程序清单如下:
Option Explicit

Private Sub Form_Click()
    Const N = 4
    Dim a(1 To N, 1 To N) As Integer
    Dim i As Integer, j As Integer, Temp As Integer
   
    For i = 1 To N             '输入矩阵
        For j = 1 To N
            a(i, j) = InputBox("输入A(" & Str(i) & "," & Str(j) & ")")
    Next j, i
   
    Print "输入的矩阵为:"
    For i = 1 To N
        For j = 1 To N
            Print a(i, j);
        Next j
        Print
    Next i
   
    For i = 1 To N             '求转置矩阵
        For j = i + 1 To N
            Temp = a(i, j)
            a(i, j) = a(j, i)
            a(j, i) = Temp
    Next j, i
   
    Print
    Print "转置后矩阵为:"
    For i = 1 To N             '输入矩阵
        For j = 1 To N
            Print a(i, j);
        Next j
        Print
    Next i
End Sub
由于转置矩阵行列交换对角线元素不变,为了防止已交换过的两个元素被再次交换,在实施交换的嵌套For循环语句中,内循环的控制变量从i+1增加到n。
程序运行结果如图5-17所示。


图5-17 转置矩阵
6.数组排序
数组排序通常是对一维数组操作,其排序方法多种多样,其中常用主要有选择法排序和冒泡法排序。为便于讨论,我们以升序为例。
(1)选择法排序基本思想是:
1)对有n个数的序列(存放在数组a(n)中),从中选出最小的数,与第1个数交换位置;
2)除第1 个数外,其余n-1个数中选最小的数,与第2个数交换位置;
3)依次类推,选择了n-1次后,这个数列已按升序排列。
算法可以描述为:
For i=1 To n-1
     从a(i)到a(n)找最小元素a(t)
     把a(t)与a(i)交换
Next i
细化寻找最小元素算法。在每一趟寻找中,可以设一个变量t,记录当前最小元素的下标:
For j=i+1 To n
    If a(j)<a(t) Then t=j
Next j
对数组一趟搜索完成后,找到当前最小值a(t),然后执行a(i)与a(t)交换。
(2)冒泡法排序(比较相邻两个数,小的调前)基本思想:
1)有n个数(存放在数组a(n)中),第一趟将每相邻数比较,小的调至前面,经n-1次两两相邻比较后,最大的数已“沉底”,放在最后一个位置,小数上升“浮起”;
2)第二趟对余下的n-1个数(最大的数已“沉底”)按上法比较,经n-2次两两相邻比较后得次大的数;
3)依次类推,n个数共进行n-1趟比较,在第j趟中要进行n-j次两两比较。
图5-18展示了一个冒泡排序实例。
 SHAPE  \* MERGEFORMAT


图5-18 冒泡法排序思想
从以上分析可知,冒泡排序的比较方式与选择排序不同,但它们的排序效率一样。冒泡排序算法可以改进,以减少不必要的排序趟次。容易看出,如果在某一趟排序中,数组元素没有进行过交换,说明序列已经是正序,不需要继续执行排序了。由此可以设一个辅助变量,监视交换操作,若没有交换过,则退出循环,结束排序。
[例5-19]用随机函数初始化数组,并用选择法对其排序。
程序清单如下:
Option Explicit

Private Sub Form_Click()
    Const N = 10
    Dim a(1 To N) As Integer
    Dim i As Integer, j As Integer, t As Integer, Min As Integer

    Randomize
    For i = 1 To N               '用随机数初始化数组
        a(i) = Int(90 * Rnd) + 10
    Next i

    Print "原 始  序 列:";
    For i = 1 To N               '输出原始序列
        Print a(i);
    Next i
    Print

    For i = 1 To N - 1           '对数组排序
        t = i
        For j = i + 1 To N       '寻找最小元素
            If a(j) < a(t) Then t = j
        Next j
        If t <> i Then           '交换数组元素
            Min = a(i)
            a(i) = a(t)
            a(t) = Min
        End If
    Next i

    Print "选择法排序后:";
    For i = 1 To N               '输出排序后序列
        Print a(i);
    Next i
End Sub
程序运行结果如图5-19。


图5-19 选择法排序
[例5-20]用随机函数初始化数组,并用冒泡法对其排序。
程序清单如下:
Option Explicit

Private Sub Form_Click()
    Const N = 10
    Dim a(1 To N) As Integer, bWork As Boolean
    Dim i As Integer, j As Integer, x As Integer

    Randomize
    For i = 1 To N
        a(i) = Int(90 * Rnd) + 10
    Next i

    Print "原 始  序 列:";
    For i = 1 To N
        Print a(i);
    Next i
    Print

    Print "冒泡法排序后:";
    For i = N To 2 Step -1
        bWork = True
        For j = 1 To i - 1
            If a(j) > a(j + 1) Then
                x = a(j)
                a(j) = a(j + 1)
                a(j + 1) = x
                bWork = False
            End If
        Next j
        If bWork Then Exit For
    Next i

    For i = 1 To N
        Print a(i);
    Next i
End Sub
程序中bWork是布尔变量,进入每一趟排序的内循环之前赋给True,若在内层循环执行了赋False语句,表示进行过交换。如果执行完内循环之后,bWork的值依然为True,说明不需要继续排序,用Exit For语句结束外循环。最后输出有序数组元素。
7.数组元素的查找
从一个数组(通常是一维线性数组)中查找指定元素的方法一般有两种:一是顺序查找;二是折半查找。顺序查找法的效率不高,但可查找无序数组;折半查找法效率高,但只能查找有序数组。[例5-12]和[例5-13]都采用顺序查找法。当被查找的数组较大时,折半查找法有明显的优势。
(1)顺序查找法基本思想:一列数放在数组元素a(1)~a(n)中,待查找的数放在x 中,把x与数组a中的元素从头到尾一一进行比较。若用变量p表示a数组元素下标,先令p初值为1,使x与a(p)比较,如果x不等于a(p),则使p=p+1,不断重复这个过程;一旦x等于a(p)则退出循环;另外,如果p大于数组长度,循环也应该停止。
(2)折半查找法基本思想:设n个有序数(从小到大)存放在数组a(1)~a(n)中,要查找的数为x。用变量iBot、iTop、iMid 分别表示查找数据范围的底部(数组下界)、顶部(数组的上界)和中间,iMid=(iTop+iBot)\2,折半查找的算法如下:
1)x=a(iMid),则已找到退出循环,否则进行下面的判断;
2)x<a(iMid),x必定落在iBot和iMid -1的范围之内,即iTop = iMid -1;
3)x>a(iMid),x必定落在iMid +1和iTop的范围之内,即iBot= iMid +1;
4)在确定了新的查找范围后,重复进行以上比较,直到找到或者iBot<= iTop。
[例5-21]编写函数过程实现折半查找,若找到则返回该数所在的下标值,没找到则返回-1。
函数过程清单如下:
Function Search(a() As Integer, x As Integer) As Integer
    Dim iBot%, iTop%, iMid%
    Dim bFind As Boolean   '代表是否找到
    iBot = LBound(a)
    iTop = UBound(a)
    bFind = False          '判断是否找到的逻辑变量,初值为False
    Do While iBot <= iTop And Not bFind
         iMid = (iTop + iBot) \ 2
        If x = a(iMid) Then
            bFind = True
            Exit Do
          ElseIf x < a(iMid) Then
              iTop = iMid - 1
            Else
              iBot = iMid + 1
            End If
        Loop
    If bFind Then
       Search = iMid
     Else
       Search = -1
    End If
End Function
过程参数a()是待查数组,x是被查找数。

作者:Admin  
  • VB程序设计学习网站(赣南师范学院) © 2008 版权所有 All Rights Reserved.
  • 地址:江西省赣州市经济技术开发区 赣南师范学院数学与计算机科学学院 邮政编码:341000
    Email:ZQ188@163.com 技术支持QQ:87319633 移ICP备10086号
  • GnsySjxy! V2.4