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

《c语言程序设计与项目实践第18章.ppt》由会员分享，可在线阅读，更多相关《c语言程序设计与项目实践第18章.ppt（36页珍藏版）》请在三一办公上搜索。

1、第18章 C语言常用算法,本章的学习重点了解起泡排序、选择排序及合并排序算法掌握快速排序算法掌握折半查找算法了解二叉树的概念及其简单操作,18.1 什么是算法,算法的程序公式：程序=数据结构+算法1计算机算法计算机算法主要有两类：数值运算算法和非数值运算算法。2算法的程序实现使用程序实现算法，应做到程序简洁明了，易读性强，执行效率高。例如，要实现下面的公式的加和运算：1+3+5+7+99+100对于这样的累加计算，可以使用下面的C语言程序实现：01int loop=0,sum=0;02for(loop=1;loop100;loop=loop+2)0304sum=sum+loop;0506sum

2、=sum+100;,18.1 什么是算法,如果利用数学算法，可以使程序效率提高近10倍。数学运算中，可以使用和差算法计算这样的加和运算，公式为：sum=n*(a1+an)/2使用C语言实现的程序为：01int sum=0;02sum=49*(99+1)/2.0;03sum=sum+100;3非数值算法C语言中最常用的非数值算法主要包括排序算法和查找算法。在这些算法的理论设计中，有时需要用到某些数学模型，通常称为数据结构。典型的数据结构类型主要有链表、二叉树、图等。,18.2 排序算法,排序，是指将一系列数据按照某种规则按照一定的顺序进行排列，以符合实际处理需求的操作过程。例如，对于一组数据，可

3、以按照由大到小的顺序排序，也可以按照由小到大的顺序排序。对于人员姓名，可以按照首字母前后顺序排序，也可以按照姓名长度排序等等。一个合理的排序算法可以使程序执行效率提高，程序健壮性增强。,18.2.1 起泡排序,起泡排序也叫冒泡排序，它的一般实现规则为：首先制定排序规则，然后，依次两两比较待排序的数据，若不符合排序规则，则进行交换，然后依次比较下去，直到全部元素排列有序为止。例如，有如下一组数据85，279，948，521，616，888，按照从大到小的顺序排列，使用起泡法排序，首先执行第一趟交换，过程如图所示。,18.2.1 起泡排序,在第一趟数据比较的基础上，继续进行第二趟数据比较。第二趟数

4、据比较共执行4次比较与交换，执行完毕后数据顺序为948，521，616，888，279，85，次小值279将被放到倒数第二的位置，如图所示。,18.2.1 起泡排序,经过五趟数据比较与交换后，数据顺序变为由大到小的有序序列。从而实现了使用起泡法排序的目的。其一般表达函数为：01void BubbleSort(dataList r,int n)0203int loop1,loop2,temp;04for(loop1=1;loop1=loop1+1;loop2-)/内层循环，控制比较位置0708if(rloop2 rloop2-1)/判断是否符合交换规则0910temp=rloop2;11rloo

5、p2=rloop2-1;12rloop2-1=temp;13141516,18.2.1 起泡排序,范例18.1 BubbleSortContryTimes.c 设计一段起泡排序算法的排序程序，将下面几个国家到2010年为止打入世界杯决赛圈的次数，按从大到小排列，相同次数的随机排列。国家及进入世界杯决赛圈次数：法国（13），西班牙（13），荷兰（9），美国（9），德国（13），巴西（19），英格兰（13），阿根廷（15），中国（1），澳大利亚（3），希腊（2），意大利（17），喀麦隆（6）。,18.2.2 选择排序,选择排序的基本思想是：首先制定排序规则（例如按照从小到大排序原则），排序过程中首

6、先在未排序序列中找到最小值，放在排序序列的起始位置，随后，逐趟从余下未排序的数值中逐次寻找最小值，直到整个序列有序为止。例如，有如下随机序列6,18,45,3,77,-88，将该序列从小到大排序，使用选择排序算法过程如下：首先，进行第一趟排序，找出其中最小的数，如图所示。,18.2.2 选择排序,经过第四趟排序之后，数值18被交换到第四的位置，此时数据序列顺序为-88,30,6,18,77,45。然后，排序遍历起始位置移到第5个参数，进行第五趟排序，第五趟排序之后，将得到从小到大的有序数列-88,30,6,18,45,77。选择排序的一般表达代码为：01void SelectionSort(D

7、ataList array,long len)0203int loop1=0,loop2=0,temp=0;04for(loop1=0;loop1arrayloop2)/判断是否符合交换规则0910temp=arrayloop1;11arrayloop1=arrayloop2;12arrayloop2=arrayloop1;1314151617,18.2.2 选择排序,范例18.2 SelectionSortAirScheduled.c 设计一段选择排序算法的排序程序，将周四由上海飞往各地的内地航班按目的地首字母先后顺序排序，并输出航班号、航班所属公司以及起飞时间。,18.2.3 合并排序,合

8、并排序又叫归并排序，合并排序的主要目的是将两个或多个有序的数组或链表等有序表合并成一个新的有序表。最简单的合并是将两个有序数组合并成一个有序数组。典型的合并排序算法是2-路合并排序，即按照排序规则将两个位置相邻的有序表合并为一个有序表。1两个数组合并排序将两个有序数组Array1和Array2进行排序并放到另一个数组ArrayMerge的基本思想为：首先，在Array1和Array2数组中各取第一个元素进行比较，将小的元素放入数组ArrayMerge；然后，取较小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组被先排完；最后，将另一个数组中剩余元素

9、拷贝到数组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(int ar

10、ray,int firstIndex,int lastIndex)0203int midIndex=0;04if(firstIndex lastIndex)0506midIndex=(firstIndex+lastIndex)/2;07MergeSort(array,firstIndex,midIndex);08MergeSort(array,midIndex+1,lastIndex);09arrayMergeFun(array,firstIndex,midIndex,lastIndex);1011,18.2.4 快速排序,快速排序的基本思想是：通过一趟数据比较和交换，将要排序的数据分成前后两

11、部分，其中一部分的数据都比另外一部分的数据都要小，然后，再按这种方法对分开的两部分数据分别进行一次快速排序，依次执行下去，直到整个序列有序为止。例如，有无序序列a1，a2，a3，a4，an，使用快速排序的过程为：首先，任选一个数据（通常选第一个元素数据a1）作为关键数据。然后，将所有比它小的元素都交换到它前面，所有比它大的元素都交换到它后面，执行这样一次比较和交换过程称为一趟快速排序。一趟快速排序的算法描述如下：1）设置两个变量i和j，排序初始时设置初始值为：i=1，j=n-1；2）取第一个元素a1作为关键数据，赋值给临时变量KeyTemp，令KeyTemp=a1；3）从j开始逐渐向序列前面搜

12、索，即执行j-操作，依次与KeyTemp比较，直到找到第一个小于KeyTemp的元素为止，然后将找到的元素与KeyTemp交换；4）从i开始向序列后面搜索，即执行i+操作，依次与KeyTemp比较，直到找到第一个大于KeyTemp的元素，然后将找到的元素与KeyTemp交换；5）重复上述第3、4步，直到i=j；,18.2.4 快速排序,范例18.3 QuickSort.c 某公司执行年度考评，考评结果放在一个二维数组PerformanceScore中，第一维记录员工工号，第二维记录员工年终考评成绩，使用快速排序算法，将员工考评成绩编号。,18.3 查找算法,查找算法是程序设计中最常用的算法之一

13、。所谓查找，就是要在一组数据中找出某个特定的元素，若找到，则执行某种预定的动作，若未找到，则输出提示信息，并执行相应的操作。查找的算法很多，常用的查找算法是顺序查找算法和折半查找算法。,18.3.1 顺序查找算法,顺序查找的基本思想是：从元素序列开始位置，逐个比较序列中的元素与被查找关键元素，若序列中某元素与关键元素相等，则查找成功，否则，继续查找直到找到对应元素。若直到最后一个序列元素仍未找到，则该序列中没有与关键元素相匹配的数据，查找失败。例如，有数组array10=101,-80,96,11458,-3.14,495,6174,705,56,93.45，要在该数组中查找关键元素key=5

14、6，并返回其数组下标位置。则可以定义遍历变量i，然后顺次遍历数组元素，直到找到该元素值为止。查找循环代码如下：01for(i=0;i10;i+)/遍历待查找数组0203if(arrayi=key)/关键参数比较与判断0405break;060708if(10=i)/判断是否查找成功，若部成功，打印信息0910printf(“查找失败，未找到对应元素n”);1112else/查找成功分支1314printf(“找到对应元素，下标为：%dn”,i);15,18.3.1 顺序查找算法,范例18.4 SequencSearch.c 数组MobileCustom712中保存着一周内某地区从早6点到晚6点

15、之间移动话务接入量，每1小时统计一次，使用顺序查找算法，找出话务量为2010次的日期及时段信息。,18.3.2 折半查找算法,折半查找的基本思想为：首先，将待查找的有序序列中间位置元素与要查找的关键元素比较，如果两者相等，则查找成功，否则，利用中间位置的记录将序列分成前、后两个子序列，若中间位置元素大于要查找的关键元素，则进一步查找前一子序列，否则进一步查找后一子序列。,例如，有如下有序序列array10=-985，-114，0，110，521，991，993，1024，2010，2048，要查找关键元素2010，则首先需要定位序列的中间位置，然后进一步判断是否需要进行下一步查找，如图所示为折

16、半查找过程。,18.3.2 折半查找算法,折半查找的一般表达函数如下：01int BinarySearch(int InputTableN,int KeyParameter)0203int low=0,high=N-1,mid=0;04while(lowKeyParameter)/判断当前位置大于或小于要查找元素1213high=mid-1;/移动高位下标1415else1617low=mid+1;/移动低位下标181920printf(“未查找到要查找的元素，查找失败n”);21,18.4 二叉树,二叉树是数据结构的典型代表之一，它是一类非常重要的非线性数据结构。二叉树在数据库系统和计算机语

17、法结构设计中应用广泛，此外，数据序列的排序和查找也广泛应用二叉树结构设计。由于二叉树常被用于数据查找，因此，二叉树又被称为二叉查找树和二叉堆。,18.4.1 二叉树的结构,1树的定义树形结构是计算机程序设计中一种的数据结构，它是由一个或多个结点组成的有限集合。每个结点表示实际应用中的一个数据元素。对于任何一个包含n个结点的非空树，都有如下特点：1）有且仅有一个称为根的结点（root）2）若n1，则剩余结点被可以被分成m个互不相交的集合Tree1、Tree2、Tree2、Treem，这些集合被称为子树（SubTree）。如图所示为一个典型的树形结构。,18.4.1 二叉树的结构,2二叉树的定义二

18、叉树是一种特殊的树形结构，其特点是每个结点至多有两个子树，即每个结点中最多有两个孩子结点，并且二叉树的结点有左右之分，也就是说，二叉树是有序的。如图所示为几种不同的二叉树结构。,18.4.2 C语言实现简单的二叉树,1二叉树结点的存储结构二叉树结点至少需要三个向其他结点的索引才能满足整个二叉树的结构。如图所示为一个即有双亲结点又有孩子结点的二叉树结点数据结构索引示意图。,这种结点结构可以由三个指针域和一个数据域构成，如图所示。,可以使用结构体定义上述二叉树结点，定义格式如下：01struct TreeNode0203struct TreeNode*parent;/指向双亲结点04int dat

19、a;/数据域05struct TreeNode*leftchild;/指向左孩子结点06struct TreeNode*rightchild;/指向右孩子结点07BinaryTreeNode;,18.4.2 C语言实现简单的二叉树,2C语言分配二叉树内存二叉树的所有结点在内存中都连续存放，因此，可以动态分配一定的连续内存空间用以建立二叉树，也可以定义结构体数组用于构建二叉树。但对于某些新建结点，也可以在物理内存上不连续。例如，可以定义下面的数组用于存储二叉树：struct TreeNode BinTree100;上述代码定义了一个TreeNode类型的结构体数组BinTree，用于构建含有10

20、0个结点的二叉树。另外，也可以动态分配一定的内存空间，用于构建二叉树，可以使用下面的代码：struct TreeNode*pBinTree=NULL;pBinTree=(struct TreeNode*)malloc(100*sizeof(struct TreeNode);,18.4.2 C语言实现简单的二叉树,3建立二叉树在为二叉树分配了一定的内存空间后，可以根据二叉树的结构建立二叉树。结构体数组InBinTree各元素与二叉树结点的对应关系如图所示。,18.4.2 C语言实现简单的二叉树,4验证二叉树是否为空二叉树使用前应先判断是否为空，若为空，则不能继续对二叉树进行任何操作。二叉树为空的

21、判断程序为：01int emptyBinTree(struct TreeNode*BinTree)0203if(NULL=BinTree)0405printf(“二叉树为空n”);06return 0;0708else0910printf(“二叉树不为空n”);11return 1;1213,18.4.3 二叉树的简单操作,二叉树的遍历分为先序遍历、中序遍历和后序遍历三种。1先序遍历二叉树先序遍历二叉树又叫先根序遍历二叉树，即先遍历二叉树及其子树的根结点，然后再遍历其他结点，其基本规则为：先访问根结点，然后先序遍历左子树，先序遍历右子树。采用先序遍历算法，各结点的先后遍历顺序为：A-B-D-E

22、-C-F-G。先序遍历的基本代码如下：01void preOrderTreversingTree(struct TreeNode*InBinTree)02 03if(NULL=InBinTree)0405printf(“输入参数错误，返回n”);06return;0708else0910printf(%d,InBinTree-data);/访问根结点11preOrderTreversingTree(InBinTree-leftchild);/先序遍历左子树12preOrderTreversingTree(InBinTree-rightchild);/先序遍历右子树1314return;15,1

23、8.4.3 二叉树的简单操作,2中序遍历二叉树中序遍历二叉树又叫中根序遍历二叉树，即先遍历左子树，再遍历根结点，然后遍历右子树。其基本规则为：中序遍历左子树，遍历根结点，中序遍历右子树。中序遍历的基本代码如下：01void MidOrderTreversingTree(struct TreeNode*InBinTree)02 03 if(NULL=InBinTree)04 05printf(“输入参数错误，返回n”);06return;07 08 else09 10MidOrderTreversingTree(InBinTree-leftchild);/中序遍历左子树11printf(%d,I

24、nBinTree-data);/访问根结点12MidOrderTreversingTree(InBinTree-rightchild);/中序遍历右子树13 14 return;15,18.4.3 二叉树的简单操作,3后序遍历二叉树后序遍历二叉树又叫后根序遍历二叉树，即先遍历左子树，再遍历右子树，然后遍历根结点。其基本规则为：后序遍历左子树，后序遍历右子树，遍历根结点。后序遍历的基本代码如下：01void LastOrderTreversingTree(struct TreeNode*InBinTree)02 03 if(NULL=InBinTree)04 05printf(“输入参数错误，返

25、回n”);06return;07 08 else09 10LastOrderTreversingTree(InBinTree-leftchild);/后序遍历左子树11LastOrderTreversingTree(InBinTree-rightchild);/后序遍历右子树12printf(%d,InBinTree-data);/访问根结点13 14 return;15,18.4.3 二叉树的简单操作,4二叉树中查找某个结点对于任何一个非空二叉树，都可以通过遍历来查找值为val的某个结点，若找到，则返回该结点位置，否则，输出提示信息。使用递归算法，代码如下：01struct TreeNode

26、*SearchBinTree(struct TreeNode*InBinTree,int Indata)02 03struct TreeNode*pTree=NULL;04printf(开始处理函数SearchBinTree()n);05if(NULL=InBinTree)0607printf(输入参数错误，退出n);08return NULL;0910else1112if(InBinTree-data=Indata)1314return InBinTree;1516else17/*分别向左右子树递归查找*/18if(pTree=SearchBinTree(InBinTree-leftchil

27、d,Indata)/遍历左子树19 20return pTree;/返回查找到的结点2122if(pTree=SearchBinTree(InBinTree-rightchild,Indata)/遍历右子树2324return pTree;/返回查找到的结点2526printf(没有匹配的结点n);27return NULL;28 29 30,18.4.3 二叉树的简单操作,5二叉树中插入一个结点向二叉树中插入结点时应考虑二叉树的有序性，即在不破坏二叉树的有序性的前提下插入一个新的结点，若二叉树为空，则新建一个结点，构成一个仅有一个结点的二叉树。二叉树插入结点的基本代码如下：01void In

28、sertBinTree(struct TreeNode*InBinTree,int NewData)02 03if(NULL=InBinTree)/树为空，新建一个根结点0405struct TreeNode*pNode=(struct TreeNode*)malloc(sizeof(struct TreeNode);06pNode-data=NewData;07pNode-leftchild=NULL;08pNode-rightchild=NULL;09InBinTree=pNode;10return;1112else if(NewDatadata)/判断插入结点的位置1314InsertB

29、inTree(InBinTree-leftchild,NewData);/向左子树中插入该结点1516else1718InsertBinTree(InBinTree-rightchild,NewData);/向右子树中插入该结点1920,18.4.3 二叉树的简单操作,6二叉树中删除一个结点删除结点时需要考虑二叉树的各种可能结构。当二叉树为空树时，无法执行删除操作，输出提示信息并返回。当二叉树根结点为要删除的结点且左子树为空时，直接删除根结点，将右子树作为保留二叉树。当二叉树根结点为要删除的结点且右子树为空时，直接删除根结点，将左子树作为保留二叉树。当二叉树仅有一个结点且为要删除的结点时，删除

30、该结点，并结束。其他情况，将使用中序遍历算法进行递归查找并删除找到的结点。,实训18.1合并两个有序数组,已知两个有序数组array1=3 8 10，array2-3 9 28101。将这两个数组合并成一个有序数组，并将其放在arrayMerge里。1需求分析：需求1：分配数组arrayMerge的大小应不小于两个数组array1和array2长度之和。需求2：对两个数组中元素进行比较，依次按大小顺序插入数组arrayMerge中。2技术应用将两个有序数组进行合并，按照有序数组合并的基本思想，第一次比较结果如图所示，图中i为数组array1的元素指示下标，j为数组array2的元素指示下标，k为数组arrayMerge的元素指示下标。,实训18.1合并两个有序数组,进行第一次比较之后，将array2中的值-3插入数组arrayMerge中，下标j和k分别将指向下一个元素，然后重新进行比较，如图所示。进行第二次比较之后，将array1中的值3插入数组arrayMerge中，下标i和k分别将指向下一个元素。重复上述比较方法，依次比较下去，直到数组array1遍历完毕为止，然后将数组array2的剩余元素依次插入数组arrayMerge中，如图所示。,