c语言程序设计与项目实践第18章

第18章C语言常用算法本章的学习重点◆了解起泡排序、选择排序及合并排序算法◆掌握快速排序算法◆掌握折半查找算法◆了解二叉树的概念及其简单操作18.1什么是算法算法的程序公式：程序=数据结构+算法1．计算机算法计算机算法主要有两类：数值运算算法和非数值运算算法。2．算法的程序实现使用程序实现算法，应做到程序简洁明了，易读性强，执行效率高。例如，要实现下面的公式的加和运算：1+3+5+7+……+99+100对于这样的累加计算，可以使用下面的C语言程序实现：01intloop=0,sum=0;02for(loop=1;loop100;loop=loop+2)03{04sum=sum+loop;05}06sum=sum+100;18.1什么是算法如果利用数学算法，可以使程序效率提高近10倍。数学运算中，可以使用和差算法计算这样的加和运算，公式为：sum=n*(a1+an)/2使用C语言实现的程序为：01intsum=0;02sum=49*(99+1)/2.0;03sum=sum+100;3．非数值算法C语言中最常用的非数值算法主要包括排序算法和查找算法。在这些算法的理论设计中，有时需要用到某些数学模型，通常称为数据结构。典型的数据结构类型主要有链表、二叉树、图等。18.2排序算法排序，是指将一系列数据按照某种规则按照一定的顺序进行排列，以符合实际处理需求的操作过程。例如，对于一组数据，可以按照由大到小的顺序排序，也可以按照由小到大的顺序排序。对于人员姓名，可以按照首字母前后顺序排序，也可以按照姓名长度排序等等。一个合理的排序算法可以使程序执行效率提高，程序健壮性增强。18.2.1起泡排序起泡排序也叫冒泡排序，它的一般实现规则为：首先制定排序规则，然后，依次两两比较待排序的数据，若不符合排序规则，则进行交换，然后依次比较下去，直到全部元素排列有序为止。例如，有如下一组数据{85，279，948，521，616，888}，按照从大到小的顺序排列，使用起泡法排序，首先执行第一趟交换，过程如图所示。279616888948521858561688894852127994861688885521279948616888521852799488588852161627994888885521616279第一次交换第三次交换第一趟交换结果第四次交换第五次交换第六次交换18.2.1起泡排序在第一趟数据比较的基础上，继续进行第二趟数据比较。第二趟数据比较共执行4次比较与交换，执行完毕后数据顺序为{948，521，616，888，279，85}，次小值279将被放到倒数第二的位置，如图所示。94888885521616279第一次交换第二次交换第三次交换第四次交换27988885521616948521888852796169485218888561627994852127985616888948第二趟交换结果18.2.1起泡排序经过五趟数据比较与交换后，数据顺序变为由大到小的有序序列。从而实现了使用起泡法排序的目的。其一般表达函数为：01voidBubbleSort(dataListr[],intn)02{03intloop1,loop2,temp;04for(loop1=1;loop1=n-1;loop1++)//外层循环，控制循环比较趟数05{06for(loop2=n;loop2=loop1+1;loop2--)//内层循环，控制比较位置07{08if(r[loop2]r[loop2-1])//判断是否符合交换规则09{10temp=r[loop2];11r[loop2]=r[loop2-1];12r[loop2-1]=temp;13}14}15}16}18.2.1起泡排序范例18.1BubbleSortContryTimes.c设计一段起泡排序算法的排序程序，将下面几个国家到2010年为止打入世界杯决赛圈的次数，按从大到小排列，相同次数的随机排列。国家及进入世界杯决赛圈次数：法国（13），西班牙（13），荷兰（9），美国（9），德国（13），巴西（19），英格兰（13），阿根廷（15），中国（1），澳大利亚（3），希腊（2），意大利（17），喀麦隆（6）。18.2.2选择排序选择排序的基本思想是：首先制定排序规则（例如按照从小到大排序原则），排序过程中首先在未排序序列中找到最小值，放在排序序列的起始位置，随后，逐趟从余下未排序的数值中逐次寻找最小值，直到整个序列有序为止。例如，有如下随机序列{6,18,45,3,77,-88}，将该序列从小到大排序，使用选择排序算法过程如下：首先，进行第一趟排序，找出其中最小的数，如图所示。1877-8845361877-8845361877-8845361877-8845631877-88456318773456-88第一次比较第二次比较第一趟交换结果第一次交换第四次比较第二次交换18.2.2选择排序经过第四趟排序之后，数值18被交换到第四的位置，此时数据序列顺序为{-88,30,6,18,77,45}。然后，排序遍历起始位置移到第5个参数，进行第五趟排序，第五趟排序之后，将得到从小到大的有序数列{-88,30,6,18,45,77}。选择排序的一般表达代码为：01voidSelectionSort(DataListarray[],longlen)02{03intloop1=0,loop2=0,temp=0;04for(loop1=0;loop1=len-1;loop1++)//外层循环，控制每一趟起始位置05{06for(loop2=loop1+1;loop2len;loop2++)//内层循环，控制每趟循环比较次数07{08if(array[loop1]array[loop2])//判断是否符合交换规则09{10temp=array[loop1];11array[loop1]=array[loop2];12array[loop2]=array[loop1];13}14}15}16}17}18.2.2选择排序范例18.2SelectionSortAirScheduled.c设计一段选择排序算法的排序程序，将周四由上海飞往各地的内地航班按目的地首字母先后顺序排序，并输出航班号、航班所属公司以及起飞时间。18.2.3合并排序合并排序又叫归并排序，合并排序的主要目的是将两个或多个有序的数组或链表等有序表合并成一个新的有序表。最简单的合并是将两个有序数组合并成一个有序数组。典型的合并排序算法是2-路合并排序，即按照排序规则将两个位置相邻的有序表合并为一个有序表。1．两个数组合并排序将两个有序数组Array1和Array2进行排序并放到另一个数组ArrayMerge的基本思想为：首先，在Array1和Array2数组中各取第一个元素进行比较，将小的元素放入数组ArrayMerge；然后，取较小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组被先排完；最后，将另一个数组中剩余元素拷贝到数组ArrayMerge。18.2.3合并排序2．合并排序算法合并排序算法最常用的是2-路合并排序。使用2-路合并排序算法，可以将无序序列排列成有序序列，递归形式的2-路合并排序方法基本思想：将含有n个元素的待排序序列分为n个子序列，然后，两两进行合并，得到n/2或n/2+1个含有2个元素的子序列，将这些子序列再两两合并，直到生成一个长度为n的有序序列为止。例如，有序列{85，279，948，521，616，888，0}，将上述序列按从小到大排列，使用合并排序算法的示意图如图所示。[948][888][85][521][616][279][0][85279][521948][616888][0][85279521948][0616888][085279521616888948]未排序序列第一趟合并排序第二趟合并排序第三趟合并排序18.2.3合并排序使用递归方式的合并排序算法一般实现函数如下：01MergeSort(intarray[],intfirstIndex,intlastIndex)02{03intmidIndex=0;04if(firstIndexlastIndex)05{06midIndex=(firstIndex+lastIndex)/2;07MergeSort(array,firstIndex,midIndex);08MergeSort(array,midIndex+1,lastIndex);09arrayMergeFun(array,firstIndex,midIndex,lastIndex);10}11}18.2.4快速排序快速排序的基本思想是：通过一趟数据比较和交换，将要排序的数据分成前后两部分，其中一部分的数据都比另外一部分的数据都要小，然后，再按这种方法对分开的两部分数据分别进行一次快速排序，依次执行下去，直到整个序列有序为止。例如，有无序序列{a1，a2，a3，a4，……，an}，使用快速排序的过程为：首先，任选一个数据（通常选第一个元素数据a1）作为关键数据。然后，将所有比它小的元素都交换到它前面，所有比它大的元素都交换到它后面，执行这样一次比较和交换过程称为一趟快速排序。一趟快速排序的算法描述如下：1）设置两个变量i和j，排序初始时设置初始值为：i=1，j=n-1；2）取第一个元素a1作为关键数据，赋值给临时变量KeyTemp，令KeyTemp=a1；3）从j开始逐渐向序列前面搜索，即执行j--操作，依次与KeyTemp比较，直到找到第一个小于KeyTemp的元素为止，然后将找到的元素与KeyTemp交换；4）从i开始向序列后面搜索，即执行i++操作，依次与KeyTemp比较，直到找到第一个大于KeyTemp的元素，然后将找到的元素与KeyTemp交换；5）重复上述第3、4步，直到i==j；18.2.4快速排序范例18.3QuickSort.c某公司执行年度考评，考评结果放在一个二维数组PerformanceScore中，第一维记录员工工号，第二维记录员工年终考评成绩，使用快速排序算法，将员工考评成绩编号。18.3查找算法查找算法是程序设计中最常用的算法之一。所谓查找，就是要在一组数据中找出某个特定的元素，若找到，则执行某种预定的动作，若未找到，则输出提示信息，并执行相应的操作。查找的算法很多，常用的查找算法是顺序查找算法和折半查找算法。18.3.1顺序查找算法顺序查找的基本思想是：从元素序列开始位置，逐个比较序列中的元素与被查找关键元素，若序列中某元素与关键元素相等，则查找成功，否则，继续查找直到找到对应元素。若直到最后一个序列元素仍未找到，则该序列中没有与关键元素相匹配的数据，查找失败。例如，有数组array[10]={101,-80,96,11458,-3.14,495,6174,705,56,93.45}，要在该数组中查找关键元素key=56，并返回其数组下标位置。则可以定义遍历变量i，然后顺次遍历数组元素，直到找到该元素值为止。查找循环代码如下：01for(i=0;i10;i++)//遍历待查找数组02{03if(array[i]==key)//关键参数比较与判断04{05break;06}07}08if(10==i)//判断是否查找成功，若部成功，打印信息09{10printf(“查找失败，未找到对应元素\n”);11}12else//查找成功分支13{14printf(“找到对应元素，下标为：%d\n”,i);15}18.3.1顺序查找算法范例18.4SequencSearch.c数组MobileCustom[7][12]中保存着一周内某地区从早6点到晚6点之间移动话务接入量，每1小时统计一次，使用顺序查找算法，找出话务量为2010次的日期及时段信息。18.3.2折半查找算法折半查找的基本思想为：首先，将待查找的有序序列中间位置元素与要查找的关键元素比较，如果两者相等，则查找成功，否则，利用中间