资源简介

(共40张PPT)
专题28 数据的分段、分组与并归
1.数据的分段往往是连续的几个数据放在一起，形成一个数据段，这种数据结构往往用矩阵来描述。类似所有的数据存储在一个连续的数组中，一段往往用矩阵的______来表示。
2.若一段的数据个数为n个，第i段的数据的左右边界依次为(i－1)*n＋1和______。若变量i表示n个数组元素中第i个位置，那么他所在段的结束位置是______________。
一行
i*n
((i－1)\n)*n
3.数据的分组往往指数据距离n个步长依次存储在一起，如奇偶位数位置依次排序，把数据分成两列，第1列为奇数列，第2列为偶数列。因此数据的分组往往指数据存储在每行有n个元素的矩阵中，每一____数据就是一组数据。一组数据中，前后两个数据的下标差距为____。
4.在一个m行n列的矩阵中，可以把数据分成n组，第i组数据的开始位置是第一行的第i个位置，第i组数据的结束位置是_____________，由于每组的最后一个数据的位置比___________大，小于等于m*n，因此可以用循环结构For j ＝____ To ________Step ____来表示第i组中每一个数据的位置。
列
n
(m－1)*n＋i
(m－1)*n
i
m*n
n
5.对于一个m*n的矩阵数据结构，共有n组数据，每组数据中有____个数据，每组中相邻的两个数据的下标差值为____。若要遍历每组数据，外循环i表示组的编号，内循环j表示每组数据中位置或者在组中序号，实现的代码如下：
For i＝1 To n For j＝i To ________Step n ′a(j)是每组数据中下标位置 Next j Next i For i＝1 To n
For j ＝1 To ____
′a(i*j)是每组数据中下标位置
Next j
Next i
m
n
m*n
m
6.若有n个数据存储在数组a中，在数组中的步长为m个元素为一组，则可以分成______组。若要遍历每组数据，外循环i表示组的编号，内循环j表示每组数据中位置或者在组中序号，实现的代码如下：
For i＝1 To ______ For j＝i To n Step ____ ′a(j)是每组数据中下标位置 Next j Next i For i＝1 To n\m
For j ＝1 To ____
′a((i－1)*m＋j)是每组数据中下标位置
Next j
Next i
n\m
n\m
m
m
7.数据的并归指将2个或2个以上相同类型的数组合并为一个数组。往往从每个数组的开始位置开始遍历数组元素，用多个指针指向遍历的位置。如将数组a、b的值按条件P并归到数组c中，用i和j分别来表示a、b数组的遍历位置，La和Lb分别表示两个数组的长度，可以用如下循环结构来进行并归。
t＝0
Do While ____________________
t＝t＋1
If j>Lb Or 条件P Then
c(t)＝a(i): i＝i＋1
Else
c(t)＝a(j): j＝j＋1
End If
Loop
i<＝La Or j <＝ Lb
考点一　数据的分段
处理大量数据时，往往采用分而治之的方法，先对数据按某个类别进行分段，在每段中，再对数据进行排序。在2020年1月浙江省选考卷第16题中，先按城市进行分组，同一城市的志愿者按参加志愿服务的次数从多到少排列。该章节部分内容在专题28矩阵中已经有介绍，城市志愿者例题在专题24桶排序、计数排序和索引排序中已经进行讲解。
【例1】 小王基于选择排序算法编写了一个VB程序，功能如下：读取若干数据依次存储在数组a中，并将数据分段排序，每段数据的元素个数及排序的次序要求依次存储在数组b中。如图，在文本框Text1中显示数组a的原始数据，在文本框Text2中显示每段数据的元素个数及排序次序要求(0表示升序、1表示降序)；单击“排序”按钮Command1，根据要求输出对每段数据进行排序的结果。实现上述功能的VB程序如下：
· · · ·
Dim n As Integer
Dim a(1 To 100) As Integer　 ′排序的数据依次存储到数组a中，
Dim b(1 To 100) As Integer　 ′排序数据段的个数及排序次序依次存储到数组b中：
′b(1)、b(2)分别存储第1段数据的元素个数、排序的次序，’代码略。
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer, t As Integer
Dim pb As Integer, endpos As Integer
pb＝1: endpos＝b(1)
For i＝1 To n－1
If i＝endpos Then
pb＝pb＋2
i ＝____①____
　　____②____
End If
k＝i
For j＝i＋1 To endpos
Next j
If k <>i Then
　t＝a(k): a(k)＝a(i): a(i)＝t
End If
Next i
Text3.Text＝””　　　　　　′(4)
For i＝1 To n
Text3.Text＝Text3.Text＋Str(a(i))
Next i
End Sub
(1)观察代码，排序后的数据输出在________对象中(填对象名)。
(2)程序中加框处代码有错，请改正。
(3)为了实现上述功能，请在划线处填写合适的代码。
(4)若程序运行时，读取了100个整数存储到数组a中，数组b各元素的值依次为“30，1，20，0，40，0，10，1”，则程序运行到(4)处代码时，endpos的值为__________。
答案　(1)Text3　(2)b(pb＋1)＝0 And a(j)a(k)　
(3)①endpos＋1 或i＋1　②endpos＝endpos＋b(pb)　(4)100
解析　从语句endpos＝b(1)和条件i＝endpos来看，存储每段结束的位置，pb是每段个数的下标，因此可以决定endpos的增加值。当i指向该段的结束时，该段的排序已完成，i指向下段的开始，比较的条件是根据b数组偶数位上的值是0还是1来决定。程序运行到(4)处代码时，endpos已经指向最后一段的结束位置。
考点二　数据的分组
把全部元素分组排序，将所有距离为步长m的元素放在同一个组中，通过“跳跃式移动”的方法，能让元素每次移动一大步，即步长m>1，大大提高了移动的效率。一趟排序下来，虽然同组的元素没有挨在一起，各组元素相互隔开，每一组都已经各自排好序了。
【例2】 分组排序。将n个数组元素分成若干组(在数组中的步长为m个元素为一组，即步长为m)，各自按升序排序。例如，对于数组a＝(9，7，12，4，17，10，4，16)。当m＝2时，分组排序的结果为a＝(4，4，9，7，12，10，17，16)；当m＝3时，分组排序的结果为a＝(4，7，10，4，16，12，9，17)。用合适的数据结构画出相应的数据。
分别采用选择排序、冒泡排序和插入排序，按题目要求进行排序。
请补充划线处语句。
(1)选择排序算法实现
Private Sub Command1_Click()
Dim i As Integer, t As Integer, imin As Integer
Dim m As Integer
m＝Val(Text2.Text) ′同组元素跳跃的步长
For i＝1 To____①____
imin＝i
For j ＝____②____To n Step m ′跳跃式扫描，跳跃步长为m
If a(j)Next j
If i <>imin Then ′将最小值与a(i)交换
t＝a(imin): a(imin)＝a(i): a(i)＝t
End If
Next i
End Sub
答案　①n-m　 ②m＋i
解析　一共有m组数据，每组中共有n\m个数据，需要循环m次分组排序，而每组排序需进行n\m－1趟排序，因此需进行总的排序趟数为(n\m－1)*m，即n－m。变量i表示第i组数据，从1循环到m，每组数组的第1个元素的位置是i，第2个元素的位置是m＋i，最后1个元素的位置是(n\m－1)*n＋m，也可以用最后一个位置n来代替，但步长为m。
(2)冒泡排序算法实现
m＝Val(Text2.Text) ′同组元素跳跃的步长
For i＝1 To n－m　
For j ＝n－(m－((i－1) Mod m＋1)) To ____①____Step －m ′从右向左逐个扫描，一次性将各组最小元素都推出来
p ＝____②____
If a(j)　　　　t＝a(j): a(j)＝a(p): a(p)＝t
End If
Next j
Next i
答案　①i＋m　②j－m
解析　该算法实现从后往向对每组数据分别进行排序，每组元素的最后1个位置是(n\m－1)*m＋i，第1个位置是i，他和他前面相邻的数据是j－m进行比较。
(3)插入排序算法实现
m＝Val(Text3.Text) ′同组元素跳跃的步长
For i ＝____①____ To n
t＝a(i)
For j ＝____②____ To 1 Step －m ′跳跃式扫描，跳跃步长为m
If a(j)>t Then
　　　　a(j＋m)＝a(j)
Else
　　　　Exit For
End If
Next j
　a(j＋m)＝t
Next i
答案　①m＋1　②i－m
解析　从每组的第2个元素开始，找到并插入合适的位置，因此①的初值为m＋1。t与他前面间隔m位置的数据进行比较，并找到合适的位置，t是i的位置，因此他前面的第1个位置是i－m。
【例3】 有一个包含10个正整数的数组，要求对其按升序排序。该排序算法是对直接插入排序进行优化，具体的算法思想是：第一步，选择一个元素选择步长将数组划分为若干小组，对各个小组分别进行排序；第二步，不断将步长缩小，不断分组和排序，直到后的步长为1，对所有的元素进行排序，此时，经过前期的排序工作，能够减少全体元素插入排序的对比次数。如数据{7，6，3，2，9，1，8，1，5，0}。第一轮分组排序：步长gap＝5，所以将数组分为5组：{7，1}，{6，8}，{3，1}，{2，5}，{9，0}分别进行直接插入排序，得到{1，7}，{6，8}，{1，3}，{2，5}，{0，9}。数组整体变为{1，6，1，2，0，7，8，3，5，9}
第二轮分组排序：步长 gap ＝2，所以将数组分为 2 组：{1，1，0，8，5}, {6，2，7，3，9}；经过分别的插入排序得到：{0，1，1，5，8}，{2，3，6，7，9}。数组整体变成{0，2，1，3，1，6，5，7，8，9}
第三轮分组排序：步长 gap ＝1, 所以就是对整个数组进行直接插入排序了。{0，1，1，2，3，5，6，7，8，9}
实现上述功能的 VB 代码如下，但加框出有错误，请改正。
Const n＝10
Dim a(n) As Integer
Private Sub Form_Load()
′随机产生n个数，代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, gap As Integer
Dim k As Integer, x As Integer, n As Integer
gap＝Int(n/2)
For i＝gap＋1 To n
j＝i－gap
Do While j>0
　　　　If a(j)>a(j＋gap) Then
　　　　　　x＝a(j): a(j)＝a(j＋gap): a(j＋gap)＝x
　　　　Else
　　　　　　j＝0
　　　　End If
Loop
Next i
gap＝Int(gap/2)
Loop
′输出排序后的结果
End Sub
答案　①gap>0或gap>＝1或其它等价答案　②j＝j－gap
解析　根据算法，最后的步长必须是1，因此gap>＝1。在第1组数中，即数组元素a(1)至a(gap)作为每组的第1元素，是每组中均有序的，插入排序应从每组的第2个元素即gap＋1开始，找到并插入到每组相应的位置，并使得每组中元素有序。在每趟插入排序中，j的初值为i－gap，他与j＋gap比较，下次比较的是j后面gap，因此第2处应填入j＝j－gap。
考点三　数组的并归
将2个数组中元素按某种规则合并到一个数组中，往往需要用到2个指针分别来控制读取的数组元素的位置，当其中一个指针到达数组最后位置时，表示合并已经结束，需要将另外一个没有达到结尾的数组元素全部添加到合并后的数组中。
【例4】 数组a存储降序排列的m个数据，数组b中存储的是升序排列的n个数据，且两个数组中存储的数据为区间[1，20]范围内的不重复的随机整数。现将两个数组的数据合并到c数组中，使c数组的数据为左右交替上升，如下表所示：
下标 1 2 3 4 5 6 7 8 9 10 11
a数组 19 17 6 4 3
b数组 5 7 8 13 15 20
c数组 3 5 7 13 17 20 19 15 8 6 4
当窗体Form1加载时，自动产生a、b数组的数据，并分别显示在列表框List1与List2中，单击合并按钮Command1后，在c数组中保存按规则合并后的a、b数组的数据，并显示在列表框List3中。程序截图如图所示。
实现该功能的VB程序如下：
Const m＝5
Const n＝6
Dim a(1 To m) As Integer：
Dim b(1 To n) As Integer
Dime(1 To m＋m) As Intger
′窗体加载时，生成数组a , b中的数据.并按要求排序后显示在列表柜中， 代码略
Private Sub Command1_Cick()
Dim pa　As Integer, pb As Integer, pe As Integer, s As Integer, flag As Boolean
pa＝m: pb＝1: pc＝1
flag＝True
Do While____①____
If a(pa)s＝a(pa)
pa＝pa－1
Else
s＝b(pb)
pb＝pb＋1
End If
c(pc)＝s
If flag Then
pc＝m＋n－pc＋1
Else
End If
　　____②____
Loop
′处理a , b数组中剩余数据， 并在列表框List3中输出数组c, 代码略
End Sub
(1)窗体加载的事件处理过程名为_______。( 填字母；A.Form1_Click/
B.Form.Click/C.Form1_Load/D.Form_load)
(2)加框处代码有错。请改正。
(3)在划线处填入合适的代码。
答案　(1)D　(2)m＋n－pc＋2或其他等同答案　(3)①pa>＝1 And pb <＝n　
②flag＝Not flag
解析　(1)Form指当前窗体
(2)c数组的数据为左右交替上升，所以pc的取值为1，m＋n，2，m＋n－1，……，flag值为True时，为数组c右侧元素赋值，否则为左侧赋值，确定答案为m＋n－ pc＋2；
(3)①结合注释语句“处理a、b数组中剩余数据”，说明循环仅处理数组a和b等长部分数据，即pa>＝1且pb<＝n时的部分数据，确定循环条件为pa>＝1 And pb<＝n；
②flag是在True 和False间交替变化，确定答案为flag＝ Not flag。
1.有如下VB程序段：
n＝10
For k＝1 To n\3
p＝3*k－2
x＝p
For t＝p＋1 To 3*k
If a(t)Next t
If p<>x Then
y＝a(p)：a(p)＝a(x)：a(x)＝y
End If
Next k
a(1)到a(10)中的元素依次为8，3，5，9，7，5，7，6，5，4，程序运行结束后，数组元素a(5)的值是________。
答案　7
解析　把数据分成3段，在每段中查找最值，并实现升序排列。内层循环功能：在p开始的3个数中，找到最小数的位置存入x，将最小数与p位置的数交换。程序执行结束后，数组a的值依次是：3，8，5，5，7，9，5，6，7，4。
2.编号分别为1～n (n为偶数)的学生分成两组进行投篮比赛，奇数编号的为第一组，偶数编号的为第二组。对每个分组的成绩按从高到低排序，先比较处于分组第1位的两个队员成绩，成绩高的得1分，低的扣1分，相等均不得分，再依次比较处于分组相同位置的队员成绩，最后得到每组得分。如10名运动员1号到10号的成绩分别是“13，6，9，8，10，11，10，14，16，13”，从高到低排序后，第一组的成绩依次是“16，13，10，10，9”，第二组的成绩依次是“14，13，11，8，6”。第1位的成绩分别是16和14，则第一组获胜得1分，第二组扣1分，再比较两个分组第2位的成绩13和13，则两组均不得分。依次处理，比较完剩余队员的成绩，可得第一组得分为2，第二组得分为－2。编写一个VB程序，实现如下功能：在文本框Text1中依次输入成绩(偶数个整数，用逗号分隔并以逗号结尾)，单击“确定”按钮Command1后，在列表框List1 中显示对阵编号、对阵成绩及两个分组的最后得分。程序运行界面如图所示。
(1)下列对象不具有Caption属性的是__________。(单选，填字母： A.Command1 /B.Form1 C.Text1 /D.Label1)
(2)实现上述功能的VB程序如下，请在划线处填入合适代码。
(3)程序代码中的加框处代码有误，请改正。
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer
Dim s As String, ch As String，sum1 As Integer, sum2 As Integer
Dim bh(1 To 50) As Integer, cj(1 To 50) As Integer
s＝Text1.Text
j＝1: k＝0
For i＝1 To____①____
ch＝Mid(s, i, 1)
If Not (ch>＝ ”0” And ch <＝ ”9”) Then
k＝k＋1
bh(k)＝k
cj(k)＝Val(Mid(s, j, i－j))
　　____②____
End If
Next i
For i＝1 To k－2 Step 2
For j＝k To____③____ Step －1
If cj(j)>cj(j－2) Then
t＝cj(j): cj(j)＝cj(j－2): cj(j－2)＝t
t＝bh(j): bh(j)＝bh(j－2): bh(j－2)＝t
End If
Next j
Next i
sum1＝0: sum2＝0#
List1.AddItem ”对阵编号对阵成绩”
For i＝1 To k－1 Step 2
If cj(i)>cj(i＋1) Then
sum1＝sum1＋1: sum2＝sum2－1
sum1 ＝sum1－1: sum2＝sum2＋1
End If
List1.AddItem adj(bh())＋”<－－>”＋adj(bh(i＋1))＋adj(cj(j))＋”<－－>”＋adj(cj(i＋1))
Next i
List1.AddItem ”第一组得分： ”＋adj(sum1)
List1.AddItem ”第二组得分： ”＋adj(sum2)
End Sub
Function adj(x As Integer) As String
′函数功能：将数值x转换成字符串，并在字符串的左侧添加若干空格。代码略
End Function
答案　(1)C　(2)①Len(s)或 Len(Text1.Text)　②j＝i＋1　③i＋2　(3)ElseIf cj(i)解析　对字符串从头开始遍历到字符串的最后。从表达式Val(Mid(s, j, i－j))来看，j表示数字串的开始，当i的位置不是数字时，下一个数字串的开始位置是j＋1。在排序时，用第一趟的开始和结束位置分别去代入，找到规律，当i＝1时，最后一次交换是第3个和第1个，因此是i＋2。
3.小王基于选择排序算法编写了一个VB程序，功能如下：数组a有n*n个元素，按n行n列进行排列，按列进行排序。例如6*6的数组，第一列将a(1)，a(7)，a(13)，a(19)，a(25)，a(31)进行排序。运行程序，在列表框List1中显示n*n个数列单击“排序”按钮Command1，在列表框List2中显示排序后的结果，程序运行界面如图所示。
Const n＝6
Dim a(1 To n*n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer, w As Integer, s As String
′以下产生n*n个数组元素，每行n个数值显示在list1中
For i＝1 To n*n　　
a(i)＝Int(Rnd*90)＋10：s＝s＋Str(a(i))
If i Mod n＝0 Then
List1.AddItem s
　　____①____
End if
Next i
′以下为对n*n个数组元素进行按列排序
　For i＝1 To n*n
k＝i
For j＝k＋n To____②____
If a(k)>a(j) Then k＝j
Next j
If____③____ Then t＝a(k): a(k)＝a(i): a(i)＝t
　Next i
　′将排序后数组a的元素，每行按n个数显示在list2中
End Sub
(1)观察运行结果，图中①处“47”在数组a中下标是________(填数字)。
(2)为了实现上述功能，请在划线处填写合适的代码。
答案　(1)12　(2)①s＝”” 或其他等价表达式　②n*n Step n 或其他等价语句　③k<>i
解析　本题考查选择排序。
(1)a数组的下标为[1，n*n]，第一行的下标为[1，n]，第二行的下标为[n＋1，2n]，n＝6，47处于第12个位置。
(2)i＝1时，被比较的范围是n＋1、2n＋1…(n－1)*n＋1，i＝2时，被比较的范围是n＋2、2n＋2…(n－1)*n＋2，……，i＝n时，被比较的范围是n＋n、2n＋n…(n－1)*n＋n，每次比较的位置步长为n，故有step n，被比较范围的终值为n*n，例如n＝6，当i＝1时，j＝7 to 36 step 6，即j＝7、13、19、25、31，i＝2时，j＝8 to 36 step 6，即j＝8、14、20、26、32。

展开更多......

收起↑