问答题


阅读下列函数说明和C代码,回答下面问题。
[说明]
冒泡排序算法的基本思想是:对于无序序列(假设扫描方向为从前向后,进行升序排列),两两比较相邻数据,若反序则交换,直到没有反序为止。一般情况下,整个冒泡排序需要进行众(1≤k≤n)趟冒泡操作,冒泡排序的结束条件是在某一趟排序过程中没有进行数据交换。若数据初态为正序时,只需1趟扫描,而数据初态为反序时,需进行n-1趟扫描。在冒泡排序中,一趟扫描有可能无数据交换,也有可能有一次或多次数据交换,在传统的冒泡排序算法及近年的一些改进的算法中[2,3],只记录一趟扫描有无数据交换的信息,对数据交换发生的位置信息则不予处理。为了充分利用这一信息,可以在一趟全局扫描中,对每一反序数据对进行局部冒泡排序处理,称之为局部冒泡排序。
局部冒泡排序的基本思想是:对于N个待排序数据组成的序列,在一趟从前向后扫描待排数据序列时,两两比较相邻数据,若反序则对后一个数据作一趟前向的局部冒泡排序,即用冒泡的排序方法把反序对的后一个数据向前排到适合的位置。扫描第—对数据对,若反序,对第2个数据向前冒泡,使前两个数据成为,有序序列;扫描第二对数据对,若反序,对第3个数据向前冒泡,使得前3个数据变成有序序列;……;扫描第i对数据对时,其前i个数据已成有序序列,若第i对数据对反序,则对第i+1个数据向前冒泡,使前i+1个数据成有序序列;……;依次类推,直至处理完第n-1对数据对。当扫描完第n-1对数据对后,N个待排序数据已成了有序序列,此时排序算法结束。该算法只对待排序列作局部的冒泡处理,局部冒泡算法的
名称由此得来。
以下为C语言设计的实现局部冒泡排序策略的算法,根据说明及算法代码回答问题1和问题2。
[变量说明]
#define N=100 //排序的数据量
typedef struct{ //排序结点
int key;
info datatype;
......
}node;
node SortData[N]; //待排序的数据组
node类型为待排序的记录(或称结点)。数组SortData[]为待排序记录的全体称为一个文件。key是作为排序依据的字段,称为排序码。datatype是与具体问题有关的数据类型。下面是用C语言实现的排序函数,参数R[]为待排序数组,n是待排序数组的维数,Finish为完成标志。
[算法代码]
void Part-BubbleSort (node R[], int n)
{
int=0 ; //定义向前局部冒泡排序的循环变量
//暂时结点,存放交换数据
node tempnode;
for (int i=0;i<n-1;i++) ;
if (R[i].key>R[i+1].key)
{
(1)
while ( (2) )
{
tempnode=R[j] ;
(3)
R[j-1]=tempnode ;
Finish=false ;
(4)
} // end while
} // end if
} // end for
} // end function
问题1
阅读下列函数说明和C代码,将应填入 (n) 处的字句写在的对应栏内。

【参考答案】

(1)j=i+1; (2)j>0& &R[j].key<R[j-1].key (3)R[j]=R[j-1]; //反序,......

(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)
热门 试题

问答题
[说明]分糖果问题是一个经典问题。问题描述如下:幼儿国有n(<20)个孩子围成一圈分糖果,老师先随机地发给每个孩子若干颗糖果,然后按以下规则调整:每个孩子同时将自己手中的糖果分一半给坐在他右边的小朋友;如共有8个孩子,则第1个将原来的一半分给第2个,第2个将原有的一半分给第3个……第8个将原来的一半分给第1个,这样的平分动作同时进行;若平分前,某个孩子手中的糖果是奇数颗,则必须从老师那里要一颗,使他的糖果变成偶数。小孩人数和每个小孩的初始数由键盘输入。经过多少次调整,使每个孩子手中的糖果一样多,调整结束时每个孩子有糖果多少颗,在调整过程中老师又新增发了多少颗糖果。[C程序]#include <stdlib.h>#include <stdio.h>bool allequall (int child[], int n ) 判断各小孩子手中的糖果是否相等{for ( int i=0; i<n-1; i++)if (child[i]!=child[i+1] )return false; 不相等返回假return true; 相等返回真}const int MaxNum=20; 定义最大人数 主函数void main ( ){int Num=0;int *child;int *child1; 构造两个相应大小的数组child代表小朋友现有的粮果数child1代表小朋友原来有的糖果数int Tnum=0;int i=0;do{ printf ( Pelase input the number of the children: ).,scanf ( %d ,&Num );if ( Num>MaxNum )printf ( Error Number!! );} while ( Num>MaxNum );child=new int [Nmn];child1=new int [Num];for ( i=0; i<Num; i++ ) 将数组赋值{printf ( Input NO. %d child’s candy numbers: ,i+1);scanf ( %d , &child[i] );}while ( (1) ){for (i=0; i<Num; i++ ){if( (2) ){(3) Tnum++;}}for ( i=0; i<Num; i++ )child1[i]=child[i]; 将child1赋值用来记忆原来小朋友的粮果数for ( i=0; i<Nam; i++ )(4) for (i=0; i<Num-1; i++) 用循环实现前一个小朋友粮果数加后一个小朋友粮果数的一半{child[i] =2;child[i]+=child 1 [i+1];}child[Num-1] =2;(5) }printf ( 每个同学最后分到糖果数目是%d n , child[1]);printf ( 老师分发出的糖果是%d n , Tnum );}图12-7是一种解决问题的流程图,请根据该流程图将对应C代码 (n) 处补充完整。