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

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)

2、03 04sum = sum + loop; 05 06sum = 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，按照从大到小的顺序排列，使用起泡法排序，首先执

4、行第一趟交换，过程如图所示,18.2.1 起泡排序,在第一趟数据比较的基础上，继续进行第二趟数据比较。第二趟数据比较共执行4次比较与交换，执行完毕后数据顺序为948，521，616，888，279，85，次小值279将被放到倒数第二的位置，如图所示,18.2.1 起泡排序,经过五趟数据比较与交换后，数据顺序变为由大到小的有序序列。从而实现了使用起泡法排序的目的。其一般表达函数为： 01void BubbleSort(dataList r, int n) 02 03int loop1, loop2, temp; 04for(loop1=1;loop1=loop1+1;loop2-) /内层循环，

5、控制比较位置 07 08if(rloop2 rloop2-1) /判断是否符合交换规则 09 10temp=rloop2; 11rloop2=rloop2-1; 12rloop2-1=temp; 13 14 15 16,18.2.1 起泡排序,范例18.1 BubbleSortContryTimes.c 设计一段起泡排序算法的排序程序，将下面几个国家到2010年为止打入世界杯决赛圈的次数，按从大到小排列，相同次数的随机排列。国家及进入世界杯决赛圈次数：法国（13），西班牙（13），荷兰（9），美国（9），德国（13），巴西（19），英格兰（13），阿根廷（15），中国（1），澳大利亚（3），希

6、腊（2），意大利（17），喀麦隆（6,18.2.2 选择排序,选择排序的基本思想是：首先制定排序规则（例如按照从小到大排序原则），排序过程中首先在未排序序列中找到最小值，放在排序序列的起始位置，随后，逐趟从余下未排序的数值中逐次寻找最小值，直到整个序列有序为止。 例如，有如下随机序列6,18,45,3,77,-88，将该序列从小到大排序，使用选择排序算法过程如下： 首先，进行第一趟排序，找出其中最小的数，如图所示,18.2.2 选择排序,经过第四趟排序之后，数值18被交换到第四的位置，此时数据序列顺序为-88,30,6,18,77,45。然后，排序遍历起始位置移到第5个参数，进行第五趟排序，第

7、五趟排序之后，将得到从小到大的有序数列-88,30,6,18,45,77。 选择排序的一般表达代码为： 01void SelectionSort(DataList array,long len) 02 03int loop1=0,loop2=0,temp=0; 04for(loop1=0;loop1arrayloop2) /判断是否符合交换规则 09 10temp=arrayloop1; 11arrayloop1=arrayloop2; 12arrayloop2=arrayloop1; 13 14 15 16 17,18.2.2 选择排序,范例18.2 SelectionSortAirSche

8、duled.c 设计一段选择排序算法的排序程序，将周四由上海飞往各地的内地航班按目的地首字母先后顺序排序，并输出航班号、航班所属公司以及起飞时间,18.2.3 合并排序,合并排序又叫归并排序，合并排序的主要目的是将两个或多个有序的数组或链表等有序表合并成一个新的有序表。最简单的合并是将两个有序数组合并成一个有序数组。典型的合并排序算法是2-路合并排序，即按照排序规则将两个位置相邻的有序表合并为一个有序表。 1两个数组合并排序 将两个有序数组Array1和Array2进行排序并放到另一个数组ArrayMerge的基本思想为： 首先，在Array1和Array2数组中各取第一个元素进行比较，将小的

9、元素放入数组ArrayMerge； 然后，取较小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组被先排完； 最后，将另一个数组中剩余元素拷贝到数组ArrayMerge,18.2.3 合并排序,2合并排序算法 合并排序算法最常用的是2-路合并排序。使用2-路合并排序算法，可以将无序序列排列成有序序列， 递归形式的2-路合并排序方法基本思想：将含有n个元素的待排序序列分为n个子序列，然后，两两进行合并，得到n/2或n/2+1个含有2个元素的子序列，将这些子序列再两两合并，直到生成一个长度为n的有序序列为止。 例如，有序列85，279，948，521，6

10、16，888，0，将上述序列按从小到大排列，使用合并排序算法的示意图如图所示,18.2.3 合并排序,使用递归方式的合并排序算法一般实现函数如下： 01MergeSort(int array, int firstIndex, int lastIndex) 02 03int midIndex = 0; 04if (firstIndex lastIndex) 05 06midIndex = (firstIndex + lastIndex) / 2; 07MergeSort(array, firstIndex, midIndex); 08MergeSort(array, midIndex + 1,

11、lastIndex); 09arrayMergeFun(array, firstIndex, midIndex, lastIndex); 10 11,18.2.4 快速排序,快速排序的基本思想是：通过一趟数据比较和交换，将要排序的数据分成前后两部分，其中一部分的数据都比另外一部分的数据都要小，然后，再按这种方法对分开的两部分数据分别进行一次快速排序，依次执行下去，直到整个序列有序为止。 例如，有无序序列a1，a2，a3，a4，an，使用快速排序的过程为： 首先，任选一个数据（通常选第一个元素数据a1）作为关键数据。然后，将所有比它小的元素都交换到它前面，所有比它大的元素都交换到它后面，执行这样

12、一次比较和交换过程称为一趟快速排序。一趟快速排序的算法描述如下： 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 快速

13、排序,范例18.3 QuickSort.c 某公司执行年度考评，考评结果放在一个二维数组PerformanceScore中，第一维记录员工工号，第二维记录员工年终考评成绩，使用快速排序算法，将员工考评成绩编号,18.3 查找算法,查找算法是程序设计中最常用的算法之一。所谓查找，就是要在一组数据中找出某个特定的元素，若找到，则执行某种预定的动作，若未找到，则输出提示信息，并执行相应的操作。查找的算法很多，常用的查找算法是顺序查找算法和折半查找算法,18.3.1 顺序查找算法,顺序查找的基本思想是：从元素序列开始位置，逐个比较序列中的元素与被查找关键元素，若序列中某元素与关键元素相等，则查找成功，

14、否则，继续查找直到找到对应元素。若直到最后一个序列元素仍未找到，则该序列中没有与关键元素相匹配的数据，查找失败。 例如，有数组array10=101, -80, 96, 11458, -3.14, 495, 6174, 705, 56, 93.45，要在该数组中查找关键元素key=56，并返回其数组下标位置。则可以定义遍历变量i，然后顺次遍历数组元素，直到找到该元素值为止。查找循环代码如下： 01for(i=0; i10; i+)/遍历待查找数组 02 03if(arrayi= =key)/关键参数比较与判断 04 05break; 06 07 08if(10 = =i)/判断是否查找成功，若

15、部成功，打印信息 09 10printf(“查找失败，未找到对应元素n”); 11 12else/查找成功分支 13 14printf(“找到对应元素，下标为：%dn”, i); 15,18.3.1 顺序查找算法,范例18.4 SequencSearch.c 数组MobileCustom712中保存着一周内某地区从早6点到晚6点之间移动话务接入量，每1小时统计一次，使用顺序查找算法，找出话务量为2010次的日期及时段信息,18.3.2 折半查找算法,折半查找的基本思想为：首先，将待查找的有序序列中间位置元素与要查找的关键元素比较，如果两者相等，则查找成功，否则，利用中间位置的记录将序列分成前、

16、后两个子序列，若中间位置元素大于要查找的关键元素，则进一步查找前一子序列，否则进一步查找后一子序列,例如，有如下有序序列array10=-985，-114，0，110，521，991，993，1024，2010，2048，要查找关键元素2010，则首先需要定位序列的中间位置，然后进一步判断是否需要进行下一步查找，如图所示为折半查找过程,18.3.2 折半查找算法,折半查找的一般表达函数如下： 01int BinarySearch(int InputTableN, int KeyParameter) 02 03int low=0, high=N-1,mid=0; 04while(lowKeyPa

17、rameter) /判断当前位置大于或小于要查找元素 12 13high = mid-1;/移动高位下标 14 15else 16 17low = mid+1;/移动低位下标 18 19 20printf(“未查找到要查找的元素，查找失败n”); 21,18.4 二叉树,二叉树是数据结构的典型代表之一，它是一类非常重要的非线性数据结构。二叉树在数据库系统和计算机语法结构设计中应用广泛，此外，数据序列的排序和查找也广泛应用二叉树结构设计。由于二叉树常被用于数据查找，因此，二叉树又被称为二叉查找树和二叉堆,18.4.1 二叉树的结构,1树的定义 树形结构是计算机程序设计中一种的数据结构，它是由一个

18、或多个结点组成的有限集合。每个结点表示实际应用中的一个数据元素。对于任何一个包含n个结点的非空树，都有如下特点： 1）有且仅有一个称为根的结点（root） 2）若n1，则剩余结点被可以被分成m个互不相交的集合Tree1、Tree2、Tree2、Treem，这些集合被称为子树（SubTree）。如图所示为一个典型的树形结构,18.4.1 二叉树的结构,2二叉树的定义 二叉树是一种特殊的树形结构，其特点是每个结点至多有两个子树，即每个结点中最多有两个孩子结点，并且二叉树的结点有左右之分，也就是说，二叉树是有序的。如图所示为几种不同的二叉树结构,18.4.2 C语言实现简单的二叉树,1二叉树结点的存

19、储结构 二叉树结点至少需要三个向其他结点的索引才能满足整个二叉树的结构。如图所示为一个即有双亲结点又有孩子结点的二叉树结点数据结构索引示意图,这种结点结构可以由三个指针域和一个数据域构成，如图所示,可以使用结构体定义上述二叉树结点，定义格式如下： 01struct TreeNode 02 03struct TreeNode *parent;/指向双亲结点 04int data;/数据域 05struct TreeNode *leftchild;/指向左孩子结点 06struct TreeNode *rightchild;/指向右孩子结点 07BinaryTreeNode,18.4.2 C语言实

20、现简单的二叉树,2C语言分配二叉树内存 二叉树的所有结点在内存中都连续存放，因此，可以动态分配一定的连续内存空间用以建立二叉树，也可以定义结构体数组用于构建二叉树。但对于某些新建结点，也可以在物理内存上不连续。 例如，可以定义下面的数组用于存储二叉树： struct TreeNode BinTree100; 上述代码定义了一个TreeNode类型的结构体数组BinTree，用于构建含有100个结点的二叉树。另外，也可以动态分配一定的内存空间，用于构建二叉树，可以使用下面的代码： struct TreeNode *pBinTree=NULL; pBinTree = (struct TreeNod

21、e *)malloc(100*sizeof(struct TreeNode,18.4.2 C语言实现简单的二叉树,3建立二叉树 在为二叉树分配了一定的内存空间后，可以根据二叉树的结构建立二叉树。结构体数组InBinTree各元素与二叉树结点的对应关系如图所示,18.4.2 C语言实现简单的二叉树,4验证二叉树是否为空 二叉树使用前应先判断是否为空，若为空，则不能继续对二叉树进行任何操作。二叉树为空的判断程序为： 01int emptyBinTree(struct TreeNode *BinTree) 02 03if(NULL = = BinTree) 04 05printf(“二叉树为空n”)

22、; 06return 0; 07 08else 09 10printf(“二叉树不为空n”); 11return 1; 12 13,18.4.3 二叉树的简单操作,二叉树的遍历分为先序遍历、中序遍历和后序遍历三种。 1先序遍历二叉树 先序遍历二叉树又叫先根序遍历二叉树，即先遍历二叉树及其子树的根结点，然后再遍历其他结点，其基本规则为：先访问根结点，然后先序遍历左子树，先序遍历右子树。采用先序遍历算法，各结点的先后遍历顺序为：A-B-D-E-C-F-G。先序遍历的基本代码如下： 01void preOrderTreversingTree(struct TreeNode *InBinTree) 0

23、2 03if(NULL= =InBinTree) 04 05printf(“输入参数错误，返回n”); 06return; 07 08else 09 10printf( %d, InBinTree-data);/访问根结点 11preOrderTreversingTree(InBinTree-leftchild);/先序遍历左子树 12preOrderTreversingTree(InBinTree-rightchild);/先序遍历右子树 13 14return; 15,18.4.3 二叉树的简单操作,2中序遍历二叉树 中序遍历二叉树又叫中根序遍历二叉树，即先遍历左子树，再遍历根结点，然后遍

24、历右子树。其基本规则为：中序遍历左子树，遍历根结点，中序遍历右子树。中序遍历的基本代码如下： 01void MidOrderTreversingTree(struct TreeNode *InBinTree) 02 03 if(NULL= =InBinTree) 04 05printf(“输入参数错误，返回n”); 06return; 07 08 else 09 10MidOrderTreversingTree(InBinTree-leftchild);/中序遍历左子树 11printf( %d, InBinTree-data);/访问根结点 12MidOrderTreversingTree(

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

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

27、 TreeNode *InBinTree, int Indata) 02 03struct TreeNode *pTree=NULL; 04printf(开始处理函数SearchBinTree()n); 05if(NULL=InBinTree) 06 07printf(输入参数错误，退出n); 08return NULL; 09 10else 11 12if(InBinTree-data = Indata) 13 14return InBinTree; 15 16else 17/* 分别向左右子树递归查找 */ 18if(pTree = SearchBinTree(InBinTree-left

28、child, Indata) /遍历左子树 19 20return pTree;/返回查找到的结点 21 22if(pTree = SearchBinTree(InBinTree-rightchild, Indata)/遍历右子树 23 24return pTree;/返回查找到的结点 25 26printf(没有匹配的结点n); 27return NULL; 28 29 30,18.4.3 二叉树的简单操作,5二叉树中插入一个结点 向二叉树中插入结点时应考虑二叉树的有序性，即在不破坏二叉树的有序性的前提下插入一个新的结点，若二叉树为空，则新建一个结点，构成一个仅有一个结点的二叉树。二叉树插入结点的基本代码如下： 01void InsertBinTree(struct TreeNode *InBinTree, int NewData) 02 03if(NULL= =InBinTree)/树为空，新建一个根结点 04 05struct TreeNode *pNode=(struct TreeNode *)malloc(sizeof(struct TreeNode); 06pNode-data=NewData; 07pNode-le