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

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

2、 sum + loop;0506sum = 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)0203int loop1, loop2, temp;04for(loop1=1;loop1=loop1+1;loop2-) /内层循环，控制比较位置0708if(rl

5、oop2 rloop2-1) /判别能否符合交换规那么0910temp=rloop2;11rloop2=rloop2-1;12rloop2-1=temp;13141516 18.2.1 起泡排序 n范例18.1 BubbleSortContryTimes.c 设计一段起泡排序算法的排序程序，将下面几个国家到2019年为止打入世界杯决赛圈的次数，按从大到小陈列，一样次数的随机陈列。国家及进入世界杯决赛圈次数：法国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。选择排序的普通表达代码为

7、：01void SelectionSort(DataList array,long len)0203int loop1=0,loop2=0,temp=0;04for(loop1=0;loop1=len-1;loop1+)/外层循环，控制每一趟起始位置0506for(loop2=loop1+1;loop2arrayloop2) /判别能否符合交换规那么0910temp=arrayloop1;11arrayloop1=arrayloop2;12arrayloop2=arrayloop1;1314151617 18.2.2 选择排序 n范例18.2 SelectionSortAirScheduled

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

9、组ArrayMerge；然后，取较小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，反复上述比较过程，直到某个数组被先排完；最后，将另一个数组中剩余元素拷贝到数组ArrayMerge。 18.2.3 合并排序 n2合并排序算法合并排序算法 n合并排序算法最常用的是合并排序算法最常用的是2-路合并排序。运用路合并排序。运用2-路合并排序算法，可以将无序序列陈列成有序序列，路合并排序算法，可以将无序序列陈列成有序序列，n递归方式的递归方式的2-路合并排序方法根本思想：将含路合并排序方法根本思想：将含有有n个元素的待排序序列分为个元素的待排序序列分为n个子序列，然后，两两进展个子序列

10、，然后，两两进展合并，得到合并，得到n/2或或n/2+1个含有个含有2个元素的子序列，将这个元素的子序列，将这些子序列再两两合并，直到生成一个长度为些子序列再两两合并，直到生成一个长度为n的有序序列为的有序序列为止。止。n例如，有序列例如，有序列85，279，948，521，616，888，0，将上述序列按从小到大陈列，运用合并排序算，将上述序列按从小到大陈列，运用合并排序算法的表示图如下图。法的表示图如下图。 18.2.3 合并排序 运用递归方式的合并排序算法普通实现函数如下：01MergeSort(int array, int firstIndex, int lastIndex)0203i

11、nt 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 快速排序 快速排序的根本思想是：经过一趟数据比较和交换，将要排序的数据分成前后两部分，其中一部分的数据都比另外一部分的数

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

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

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

15、，并前往其数组下标位置。那么可以定义遍历变量i，然后依次遍历数组元素，直到找到该元素值为止。查找循环代码如下：01for(i=0; i10; i+) /遍历待查找数组0203if(arrayi= =key)/关键参数比较与判别0405break;060708if(10 = =i)/判别能否查找胜利，假设部胜利，打印信息0910printf(“查找失败，未找到对应元素n);1112else/查找胜利分支1314printf(“找到对应元素，下标为：%dn, i);15 18.3.1 顺序查找算法 n范例18.4 SequencSearch.c 数组MobileCustom712中保管着一周内某地

16、域从早6点到晚6点之间挪动话务接入量，每1小时统计一次，运用顺序查找算法，找出话务量为2019次的日期及时段信息。 18.3.2 折半查找算法 折半查找的根本思想为：首先，将待查找的有序序列中间位置元素与要查找的关键元素比较，假设两者相等，那么查找胜利，否那么，利用中间位置的记录将序列分成前、后两个子序列，假设中间位置元素大于要查找的关键元素，那么进一步查找前一子序列，否那么进一步查找后一子序列。 例如，有如下有序序列array10=-985，-114，0，110，521，991，993，1024，2019，2048，要查找关键元素2019，那么首先需求定位序列的中间位置，然后进一步判别能否需

17、求进展下一步查找，如下图为折半查找过程。 18.3.2 折半查找算法 折半查找的普通表达函数如下：01 int BinarySearch(int InputTableN, int KeyParameter)02 03int low=0, high=N-1,mid=0;04while(lowKeyParameter) /判别当前位置大于或小于要查找元素1213high = mid-1;/挪动高位下标1415else1617low = mid+1;/挪动低位下标181920printf(“未查找到要查找的元素，查找失败n);21 18.4 二叉树 二叉树是数据构造的典型代表之一，它是一类非常重要的

18、非线性数据构造。二叉树在数据库系统和计算机语法构造设计中运用广泛，此外，数据序列的排序和查找也广泛运用二叉树构造设计。由于二叉树常被用于数据查找，因此，二叉树又被称为二叉查找树和二叉堆。 18.4.1 二叉树的构造 n1树的定义树的定义n树形构造是计算机程序设计中一种的数据构造，它是树形构造是计算机程序设计中一种的数据构造，它是由一个或多个结点组成的有限集合。每个结点表示实践运由一个或多个结点组成的有限集合。每个结点表示实践运用中的一个数据元素。对于任何一个包含用中的一个数据元素。对于任何一个包含n个结点的非空树，个结点的非空树，都有如下特点：都有如下特点：n1有且仅有一个称为根的结点有且仅有

19、一个称为根的结点rootn2假设假设n1，那么剩余结点被可以被分成，那么剩余结点被可以被分成m个个互不相交的集合互不相交的集合Tree1、Tree2、Tree2、Treem，这些集合被称为子树这些集合被称为子树SubTree。如下图为一个典型的。如下图为一个典型的树形构造。树形构造。 18.4.1 二叉树的构造 n2二叉树的定义二叉树的定义n二叉树是一种特殊的树形构造，其特点是每个二叉树是一种特殊的树形构造，其特点是每个结点至多有两个子树，即每个结点中最多有两个孩子结点，结点至多有两个子树，即每个结点中最多有两个孩子结点，并且二叉树的结点有左右之分，也就是说，二叉树是有序并且二叉树的结点有左右

20、之分，也就是说，二叉树是有序的。如下图为几种不同的二叉树构造。的。如下图为几种不同的二叉树构造。 18.4.2 C言语实现简单的二叉树 n1二叉树结点的存储构造二叉树结点的存储构造n二叉树结点至少需求三个向其他结点的索引才二叉树结点至少需求三个向其他结点的索引才干满足整个二叉树的构造。如下图为一个即有双亲结点又干满足整个二叉树的构造。如下图为一个即有双亲结点又有孩子结点的二叉树结点数据构造索引表示图。有孩子结点的二叉树结点数据构造索引表示图。这种结点构造可以由三个指针域和一个数据域构成，如下图。 可以运用构造体定义上述二叉树结点，定义格式如下：01 struct TreeNode02 03st

21、ruct TreeNode *parent;/指向双亲结点04int data;/数据域05struct TreeNode *leftchild;/指向左孩子结点06struct TreeNode *rightchild;/指向右孩子结点07 BinaryTreeNode; 18.4.2 C言语实现简单的二叉树 n2C言语分配二叉树内存言语分配二叉树内存n二叉树的一切结点在内存中都延续存放，因此，二叉树的一切结点在内存中都延续存放，因此，可以动态分配一定的延续内存空间用以建立二叉树，也可可以动态分配一定的延续内存空间用以建立二叉树，也可以定义构造体数组用于构建二叉树。但对于某些新建结点，以定义

22、构造体数组用于构建二叉树。但对于某些新建结点，也可以在物理内存上不延续。也可以在物理内存上不延续。n例如，可以定义下面的数组用于存储二叉树：例如，可以定义下面的数组用于存储二叉树：nstruct TreeNode BinTree100;n上述代码定义了一个上述代码定义了一个TreeNode类型的构造体类型的构造体数组数组BinTree，用于构建含有，用于构建含有100个结点的二叉树。另外，个结点的二叉树。另外，也可以动态分配一定的内存空间，用于构建二叉树，可以也可以动态分配一定的内存空间，用于构建二叉树，可以运用下面的代码：运用下面的代码：nstruct TreeNode *pBinTree=

23、NULL;npBinTree = (struct TreeNode *)malloc(100*sizeof(struct TreeNode); 18.4.2 C言语实现简单的二叉树 n3建立二叉树建立二叉树n在为二叉树分配了一定的内存空间后，可以根在为二叉树分配了一定的内存空间后，可以根据二叉树的构造建立二叉树。构造体数组据二叉树的构造建立二叉树。构造体数组InBinTree各元各元素与二叉树结点的对应关系如下图。素与二叉树结点的对应关系如下图。n 18.4.2 C言语实现简单的二叉树 n4验证二叉树能否为空验证二叉树能否为空n二叉树运用前应先判别能否为空，假设为空，二叉树运用前应先判别能否为

24、空，假设为空，那么不能继续对二叉树进展任何操作。二叉树为空的判别那么不能继续对二叉树进展任何操作。二叉树为空的判别程序为：程序为：n01int emptyBinTree(struct TreeNode *BinTree)n02n03if(NULL = = BinTree)n04n05printf(“二叉树为空二叉树为空n);n06return 0;n07n08elsen09n10printf(“二叉树不为空二叉树不为空n);n11return 1;n12n13 n 18.4.3 二叉树的简单操作 二叉树的遍历分为先序遍历、中序遍历和后序遍历三种。1先序遍历二叉树先序遍历二叉树又叫先根序遍历二叉

25、树，即先遍历二叉树及其子树的根结点，然后再遍历其他结点，其根本规那么为：先访问根结点，然后先序遍历左子树，先序遍历右子树。采用先序遍历算法，各结点的先后遍历顺序为：A-B-D-E-C-F-G。先序遍历的根本代码如下：01void preOrderTreversingTree(struct TreeNode *InBinTree) 02 03if(NULL= =InBinTree)0405printf(“输入参数错误，前往n);06return;0708else0910printf( %d, InBinTree-data); /访问根结点11preOrderTreversingTree(InBi

26、nTree-leftchild);/先序遍历左子树12preOrderTreversingTree(InBinTree-rightchild);/先序遍历右子树1314return;15 18.4.3 二叉树的简单操作 n2中序遍历二叉树中序遍历二叉树n中序遍历二叉树又叫中根序遍历二叉树，即先中序遍历二叉树又叫中根序遍历二叉树，即先遍历左子树，再遍历根结点，然后遍历右子树。其根本规遍历左子树，再遍历根结点，然后遍历右子树。其根本规那么为：中序遍历左子树，遍历根结点，中序遍历右子树。那么为：中序遍历左子树，遍历根结点，中序遍历右子树。中序遍历的根本代码如下：中序遍历的根本代码如下：n01void

27、 MidOrderTreversingTree(struct TreeNode *InBinTree) n02 n03 if(NULL= =InBinTree)n04 n05printf(“输入参数错误，前往输入参数错误，前往n);n06return;n07 n08 elsen09 n10MidOrderTreversingTree(InBinTree-leftchild);/中序遍历左子树中序遍历左子树n11printf( %d, InBinTree-data);/访问根结点访问根结点n12MidOrderTreversingTree(InBinTree-rightchild); /中序遍历

28、右子树中序遍历右子树n13 n14 return;n15 18.4.3 二叉树的简单操作 n3后序遍历二叉树后序遍历二叉树n后序遍历二叉树又叫后根序遍历二叉树，即先后序遍历二叉树又叫后根序遍历二叉树，即先遍历左子树，再遍历右子树，然后遍历根结点。其根本规遍历左子树，再遍历右子树，然后遍历根结点。其根本规那么为：后序遍历左子树，后序遍历右子树，遍历根结点。那么为：后序遍历左子树，后序遍历右子树，遍历根结点。后序遍历的根本代码如下：后序遍历的根本代码如下：n01void LastOrderTreversingTree(struct TreeNode *InBinTree) n02 n03 if(N

29、ULL= =InBinTree)n04 n05printf(“输入参数错误，前往输入参数错误，前往n);n06return;n07 n08 elsen09 n10LastOrderTreversingTree (InBinTree-leftchild); /后序遍历左子树后序遍历左子树n11LastOrderTreversingTree (InBinTree-rightchild);/后序遍历右子树后序遍历右子树n12printf( %d, InBinTree-data);/访问根结点访问根结点n13 n14 return;n15 18.4.3 二叉树的简单操作 n4二叉树中查找某个结点二叉树

30、中查找某个结点n对于任何一个非空二叉树，都可以经过遍历来对于任何一个非空二叉树，都可以经过遍历来查找值为查找值为val的某个结点，假设找到，那么前往该结点位置，的某个结点，假设找到，那么前往该结点位置，否那么，输出提示信息。运用递归算法，代码如下：否那么，输出提示信息。运用递归算法，代码如下：n01struct TreeNode *SearchBinTree(struct TreeNode *InBinTree, int Indata) n02 n03struct TreeNode *pTree=NULL;n04printf(开场处置函数开场处置函数SearchBinTree()n);n05i

31、f(NULL=InBinTree)n06n07printf(输入参数错误，退出输入参数错误，退出n);n08return NULL;n09n10elsen11n12if(InBinTree-data = Indata)n13n14return InBinTree;n15n16elsen17/* 分别向左右子树递归查找分别向左右子树递归查找 */ n18if(pTree = SearchBinTree(InBinTree-leftchild, Indata) /遍遍历左子树历左子树n19 n20return pTree;/前往查找到的结点前往查找到的结点n21n22if(pTree = Sear

32、chBinTree(InBinTree-rightchild, Indata)/遍历右子树遍历右子树n23n24return pTree;/前往查找到的结点前往查找到的结点n25n26printf(没有匹配的结点没有匹配的结点n);n27return NULL; n28 n29 n30 18.4.3 二叉树的简单操作 n5二叉树中插入一个结点二叉树中插入一个结点n向二叉树中插入结点时应思索二叉树的有序性，向二叉树中插入结点时应思索二叉树的有序性，即在不破坏二叉树的有序性的前提下插入一个新的结点，即在不破坏二叉树的有序性的前提下插入一个新的结点，假设二叉树为空，那么新建一个结点，构成一个仅有一个

33、假设二叉树为空，那么新建一个结点，构成一个仅有一个结点的二叉树。二叉树插入结点的根本代码如下：结点的二叉树。二叉树插入结点的根本代码如下：n01void InsertBinTree(struct TreeNode *InBinTree, int NewData) n02 n03if(NULL= =InBinTree)/树为空，新建一个根结点树为空，新建一个根结点n04n05struct TreeNode *pNode=(struct TreeNode *)malloc(sizeof(struct TreeNode);n06pNode-data=NewData;n07pNode-leftchild=NULL;n08pNode-rightchild=NULL;n09InBinTree=pNode;n10return;n11n12el