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)0304sum=sum+loop;0506sum=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，按照从大到小的顺序排列，使用起泡法排序，首先执行第一趟交换，过程如图所示。,18.2.1起泡排序,在第一趟数据比较的基础上，继续进行第二趟数据比较。第二趟数据比较共执行4次比较与交换，执行完毕后数据顺序为948，521，616，888，279，85，次小值279将被放到倒数第二的位置，如图所示。,18.2.1起泡排序,经过五趟数据比较与交换后，数据顺序变为由大到小的有序序列。从而实现了使用起泡法排序的目的。其一般表达函数为：01voidBubbleSort(dataListr,intn)0203intloop1,loop2,temp;04for(loop1=1;loop1=loop1+1;loop2-)/内层循环，控制比较位置0708if(rloop2rloop2-1)/判断是否符合交换规则0910temp=rloop2;11rloop2=rloop2-1;12rloop2-1=temp;13141516,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，将该序列从小到大排序，使用选择排序算法过程如下：首先，进行第一趟排序，找出其中最小的数，如图所示。,18.2.2选择排序,经过第四趟排序之后，数值18被交换到第四的位置，此时数据序列顺序为-88,30,6,18,77,45。然后，排序遍历起始位置移到第5个参数，进行第五趟排序，第五趟排序之后，将得到从小到大的有序数列-88,30,6,18,45,77。选择排序的一般表达代码为：01voidSelectionSort(DataListarray,longlen)0203intloop1=0,loop2=0,temp=0;04for(loop1=0;loop1arrayloop2)/判断是否符合交换规则0910temp=arrayloop1;11arrayloop1=arrayloop2;12arrayloop2=arrayloop1;1314151617,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，将上述序列按从小到大排列，使用合并排序算法的示意图如图所示。,18.2.3合并排序,使用递归方式的合并排序算法一般实现函数如下：01MergeSort(intarray,intfirstIndex,intlastIndex)0203intmidIndex=0;04if(firstIndexB-D-E-C-F-G。先序遍历的基本代码如下：01voidpreOrderTreversingTree(structTreeNode*InBinTree)0203if(NULL=InBinTree)0405printf(“输入参数错误，返回n”);06return;0708else0910printf(%d,InBinTree-data);/访问根结点11preOrderTreversingTree(InBinTree-leftchild);/先序遍历左子树12preOrderTreversingTree(InBinTree-rightchild);/先序遍历右子树1314return;15,18.4.3二叉树的简单操作,2中序遍历二叉树中序遍历二叉树又叫中根序遍历二叉树，即先遍历左子树，再遍历根结点，然后遍历右子树。其基本规则为：中序遍历左子树，遍历根结点，中序遍历右子树。中序遍历的基本代码如下：01voidMidOrderTreversingTree(structTreeNode*InBinTree)0203if(NULL=InBinTree)0405printf(“输入参数错误，返回n”);06return;0708else0910MidOrderTreversingTree(InBinTree-leftchild);/中序遍历左子树11printf(%d,InBinTree-data);/访问根结点12MidOrderTreversingTree(InBinTree-rightchild);/中序遍历右子树1314return;15,18.4.3二叉树的简单操作,3后序遍历二叉树后序遍历二叉树又叫后根序遍历二叉树，即先遍历左子树，再遍历右子树，然后遍历根结点。其基本规则为：后序遍历左子树，后序遍历右子树，遍历根结点。后序遍历的基本代码如下：01voidLastOrderTreversingTree(structTreeNode*InBinTree)0203if(NULL=InBinTree)0405printf(“输入参数错误，返回n”);06return;0708else0910LastOrderTreversingTree(InBinTree-leftchild);/后序遍历左子树11LastOrderTreversingTree(InBinTree-rightchild);/后序遍历右子树12printf(%d,InBinTree-data);/访问根结点1314return;15,18.4.3二叉树的简单操作,4二叉树中查找某个结点对于任何一个非空二叉树，都可以通过遍历来查找值为val的某个结点，若找到，则返回该结点位置，否则，输出提示信息。使用递归算法，代码如下：01structTreeNode*SearchBinTree(structTreeNode*InBinTree,intIndata)0203structTreeNode*pTree=NULL;04printf(开始处理函数SearchBinTree()n);05if(NULL=InBinTree)0607printf(输入参数错误，退出n);08returnNULL;0910else1112if(InBinTree-data=Indata)1314returnInBinTree;1516else17/*分别向左右子树递归查找*/18if(pTree=SearchBinTree(InBinTree-leftchild,Indata)/遍历左子树1920returnpTree;/返回查找到的结点2122if(pTree=SearchBinTree(InBinTree-rightchild,Indata)/遍历右子树2324returnpTree;/返回查找到的结点2526printf(没有匹配的结点n);27returnNULL;282930,18.4.3二叉树的简单操作,5二叉树中插入一个结点向二叉树中插入结点时应考虑二叉树的有序性，即在不破坏二叉树的有序性的前提下插入一个新的结点，若二叉树为空，则新建一个结点，构成一个仅有一个结点的二叉树。二叉树插入结点的基本代码如下：01voidInsertBinTree(structTreeNode*InBinTree,intNewData)0203if(NULL=InBinTree)/树为空，新建一个根结点0405structTreeNode*pNode=(structTreeNode*)malloc(sizeof(structTreeNode);06pNode-data=NewData;07pNode-leftchild=NULL;08pNode-rightchild=NULL;09InBinTree=pNode;10return;1112elseif(NewDatadata)/判断插入结点的位置1314InsertBinTree(InBinTree-leftchild,NewData);/向左子树中插入该结点1516else1718InsertBinTree(InBinTree-rightchild,NewData);/向右子树中插入该结点1920,18.4.3二叉树的简单操作,6二叉树中删除一个结点删除结点时需要考虑二叉树的各种可能结构。当二叉树为空树时，无法执行删除操作，输出提示信息并返回。当二叉树根结点为要删除的结点且左子树为空时，直接删除根结点，将右子树作为保留二叉树。当二叉树根结点为要删除的结点且右子树为空时，直接删除根结点，将左子树作为保留二叉树。当二叉树仅有一个结点且为要删除的结点时，删除该结点，并结束。其他情况，将使用中序遍历算法进行递归查找并删除找到的结点。,实训18.1合并两个有序数组,已知两个有序数组array1=3810，array2-3928101。将这两个数组合并成一个有序数组，并将其放在arrayMerge里。1需求分析：需求1：分配数组arrayMerge的大小应不小于两个数组array1和array2长度之和。需求2：对两个数组中元素进行比较，依次按大小顺序插入数组arrayMerge中。2技术应用将两个有序数组进行合并，按照有序数组合并的基本思想，第一