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

会计学1c语言程序设计与项目实践18.1什么是算法

如果利用数学算法，可以使程序效率提高近10倍。数学运算中，可以使用和差算法计算这样的加和运算，公式为：

sum=n*(a1+an)/2

使用C语言实现的程序为：

01 intsum=0; 02 sum=49*(99+1)/2.0; 03 sum=sum+100;

3．非数值算法

C语言中最常用的非数值算法主要包括排序算法和查找算法。在这些算法的理论设计中，有时需要用到某些数学模型，通常称为数据结构。典型的数据结构类型主要有链表、二叉树、图等。

第1页/共35页18.2排序算法

排序，是指将一系列数据按照某种规则按照一定的顺序进行排列，以符合实际处理需求的操作过程。 例如，对于一组数据，可以按照由大到小的顺序排序，也可以按照由小到大的顺序排序。对于人员姓名，可以按照首字母前后顺序排序，也可以按照姓名长度排序等等。一个合理的排序算法可以使程序执行效率提高，程序健壮性增强。第2页/共35页18.2.1起泡排序

起泡排序也叫冒泡排序，它的一般实现规则为：首先制定排序规则，然后，依次两两比较待排序的数据，若不符合排序规则，则进行交换，然后依次比较下去，直到全部元素排列有序为止。 例如，有如下一组数据{85，279，948，521，616，888}，按照从大到小的顺序排列，使用起泡法排序，首先执行第一趟交换，过程如图所示。第3页/共35页18.2.1起泡排序

在第一趟数据比较的基础上，继续进行第二趟数据比较。第二趟数据比较共执行4次比较与交换，执行完毕后数据顺序为{948，521，616，888，279，85}，次小值279将被放到倒数第二的位置，如图所示。第4页/共35页18.2.1起泡排序

经过五趟数据比较与交换后，数据顺序变为由大到小的有序序列。从而实现了使用起泡法排序的目的。其一般表达函数为：

01 voidBubbleSort(dataListr[],intn) 02 { 03 intloop1,loop2,temp; 04 for(loop1=1;loop1<=n-1;loop1++)//外层循环，控制循环比较趟数

05 { 06 for(loop2=n;loop2>=loop1+1;loop2--)//内层循环，控制比较位置

07 { 08 if(r[loop2]<r[loop2-1])//判断是否符合交换规则

09 { 10 temp=r[loop2]; 11 r[loop2]=r[loop2-1]; 12 r[loop2-1]=temp; 13 } 14 } 15 } 16 }第5页/共35页18.2.1起泡排序范例18.1BubbleSortContryTimes.c设计一段起泡排序算法的排序程序，将下面几个国家到2010年为止打入世界杯决赛圈的次数，按从大到小排列，相同次数的随机排列。国家及进入世界杯决赛圈次数：法国（13），西班牙（13），荷兰（9），美国（9），德国（13），巴西（19），英格兰（13），阿根廷（15），中国（1），澳大利亚（3），希腊（2），意大利（17），喀麦隆（6）。

第6页/共35页18.2.2选择排序

选择排序的基本思想是：首先制定排序规则（例如按照从小到大排序原则），排序过程中首先在未排序序列中找到最小值，放在排序序列的起始位置，随后，逐趟从余下未排序的数值中逐次寻找最小值，直到整个序列有序为止。 例如，有如下随机序列{6,18,45,3,77,-88}，将该序列从小到大排序，使用选择排序算法过程如下： 首先，进行第一趟排序，找出其中最小的数，如图所示。

第7页/共35页18.2.2选择排序

经过第四趟排序之后，数值18被交换到第四的位置，此时数据序列顺序为{-88,30,6,18,77,45}。然后，排序遍历起始位置移到第5个参数，进行第五趟排序，第五趟排序之后，将得到从小到大的有序数列{-88,30,6,18,45,77}。 选择排序的一般表达代码为：

01 voidSelectionSort(DataListarray[],longlen) 02 { 03 intloop1=0,loop2=0,temp=0; 04 for(loop1=0;loop1<=len-1;loop1++) //外层循环，控制每一趟起始位置

05 { 06 for(loop2=loop1+1;loop2<len;loop2++) //内层循环，控制每趟循环比较次数

07 { 08 if(array[loop1]>array[loop2])//判断是否符合交换规则

09 { 10 temp=array[loop1]; 11 array[loop1]=array[loop2]; 12 array[loop2]=array[loop1]; 13 } 14 } 15 } 16 } 17 }

第8页/共35页18.2.2选择排序范例18.2SelectionSortAirScheduled.c设计一段选择排序算法的排序程序，将周四由上海飞往各地的内地航班按目的地首字母先后顺序排序，并输出航班号、航班所属公司以及起飞时间。

第9页/共35页18.2.3合并排序

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

合并排序算法最常用的是2-路合并排序。使用2-路合并排序算法，可以将无序序列排列成有序序列， 递归形式的2-路合并排序方法基本思想：将含有n个元素的待排序序列分为n个子序列，然后，两两进行合并，得到n/2或n/2+1个含有2个元素的子序列，将这些子序列再两两合并，直到生成一个长度为n的有序序列为止。 例如，有序列{85，279，948，521，616，888，0}，将上述序列按从小到大排列，使用合并排序算法的示意图如图所示。第11页/共35页18.2.3合并排序

使用递归方式的合并排序算法一般实现函数如下：

01 MergeSort(intarray[],intfirstIndex,intlastIndex) 02 { 03 intmidIndex=0; 04 if(firstIndex<lastIndex) 05 { 06 midIndex=(firstIndex+lastIndex)/2; 07 MergeSort(array,firstIndex,midIndex); 08 MergeSort(array,midIndex+1,lastIndex); 09 arrayMergeFun(array,firstIndex,midIndex,lastIndex); 10 } 11 }第12页/共35页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；

第13页/共35页18.2.4快速排序范例18.3QuickSort.c某公司执行年度考评，考评结果放在一个二维数组PerformanceScore中，第一维记录员工工号，第二维记录员工年终考评成绩，使用快速排序算法，将员工考评成绩编号。

第14页/共35页18.3查找算法

查找算法是程序设计中最常用的算法之一。所谓查找，就是要在一组数据中找出某个特定的元素，若找到，则执行某种预定的动作，若未找到，则输出提示信息，并执行相应的操作。查找的算法很多，常用的查找算法是顺序查找算法和折半查找算法。

第15页/共35页18.3.1顺序查找算法

顺序查找的基本思想是：从元素序列开始位置，逐个比较序列中的元素与被查找关键元素，若序列中某元素与关键元素相等，则查找成功，否则，继续查找直到找到对应元素。若直到最后一个序列元素仍未找到，则该序列中没有与关键元素相匹配的数据，查找失败。 例如，有数组array[10]={101,-80,96,11458,-3.14,495,6174,705,56,93.45}，要在该数组中查找关键元素key=56，并返回其数组下标位置。则可以定义遍历变量i，然后顺次遍历数组元素，直到找到该元素值为止。查找循环代码如下：

01 for(i=0;i<10;i++) //遍历待查找数组

02 { 03 if(array[i]==key) //关键参数比较与判断

04 { 05 break; 06 } 07 } 08 if(10==i) //判断是否查找成功，若部成功，打印信息

09 { 10 printf(“查找失败，未找到对应元素\n”); 11 } 12 else //查找成功分支

13 { 14 printf(“找到对应元素，下标为：%d\n”,i); 15 }第16页/共35页18.3.1顺序查找算法范例18.4SequencSearch.c数组MobileCustom[7][12]中保存着一周内某地区从早6点到晚6点之间移动话务接入量，每1小时统计一次，使用顺序查找算法，找出话务量为2010次的日期及时段信息。第17页/共35页18.3.2折半查找算法

折半查找的基本思想为：首先，将待查找的有序序列中间位置元素与要查找的关键元素比较，如果两者相等，则查找成功，否则，利用中间位置的记录将序列分成前、后两个子序列，若中间位置元素大于要查找的关键元素，则进一步查找前一子序列，否则进一步查找后一子序列。

例如，有如下有序序列array[10]={-985，-114，0，110，521，991，993，1024，2010，2048}，要查找关键元素2010，则首先需要定位序列的中间位置，然后进一步判断是否需要进行下一步查找，如图所示为折半查找过程。

第18页/共35页18.3.2折半查找算法

折半查找的一般表达函数如下：01 intBinarySearch(intInputTable[N],intKeyParameter)02 {03 intlow=0,high=N-1,mid=0;04 while(low<high) //判断是否查找结束05 {06 mid=(low+high)/2; //选择中间位置07 if(KeyParameter==InputTable[mid])//判断是否查找到所需元素08 {09 returnmid; //返回查找到的位置10 }11 elseif(InputTable[mid]>KeyParameter)//判断当前位置大于或小于要查找元素12 {13 high=mid-1; //移动高位下标14 }15 else16 {17 low=mid+1; //移动低位下标18 }19 }20 printf(“未查找到要查找的元素，查找失败\n”);21 }

第19页/共35页18.4二叉树

二叉树是数据结构的典型代表之一，它是一类非常重要的非线性数据结构。二叉树在数据库系统和计算机语法结构设计中应用广泛，此外，数据序列的排序和查找也广泛应用二叉树结构设计。由于二叉树常被用于数据查找，因此，二叉树又被称为二叉查找树和二叉堆。

第20页/共35页18.4.1二叉树的结构1．树的定义 树形结构是计算机程序设计中一种的数据结构，它是由一个或多个结点组成的有限集合。每个结点表示实际应用中的一个数据元素。对于任何一个包含n个结点的非空树，都有如下特点：

1）有且仅有一个称为根的结点（root）

2）若n>1，则剩余结点被可以被分成m个互不相交的集合Tree1、Tree2、Tree2、……Treem，这些集合被称为子树（SubTree）。如图所示为一个典型的树形结构。

第21页/共35页18.4.1二叉树的结构2．二叉树的定义 二叉树是一种特殊的树形结构，其特点是每个结点至多有两个子树，即每个结点中最多有两个孩子结点，并且二叉树的结点有左右之分，也就是说，二叉树是有序的。如图所示为几种不同的二叉树结构。第22页/共35页18.4.2C语言实现简单的二叉树1．二叉树结点的存储结构 二叉树结点至少需要三个向其他结点的索引才能满足整个二叉树的结构。如图所示为一个即有双亲结点又有孩子结点的二叉树结点数据结构索引示意图。

这种结点结构可以由三个指针域和一个数据域构成，如图所示。

可以使用结构体定义上述二叉树结点，定义格式如下：01 structTreeNode02 {03 structTreeNode*parent; //指向双亲结点04 intdata; //数据域05 structTreeNode*leftchild; //指向左孩子结点06 structTreeNode*rightchild; //指向右孩子结点07 }BinaryTreeNode;

第23页/共35页18.4.2C语言实现简单的二叉树2．C语言分配二叉树内存 二叉树的所有结点在内存中都连续存放，因此，可以动态分配一定的连续内存空间用以建立二叉树，也可以定义结构体数组用于构建二叉树。但对于某些新建结点，也可以在物理内存上不连续。 例如，可以定义下面的数组用于存储二叉树：

structTreeNodeBinTree[100];

上述代码定义了一个TreeNode类型的结构体数组BinTree，用于构建含有100个结点的二叉树。另外，也可以动态分配一定的内存空间，用于构建二叉树，可以使用下面的代码：

structTreeNode*pBinTree=NULL; pBinTree=(structTreeNode*)malloc(100*sizeof(structTreeNode));

第24页/共35页18.4.2C语言实现简单的二叉树3．建立二叉树 在为二叉树分配了一定的内存空间后，可以根据二叉树的结构建立二叉树。结构体数组InBinTree各元素与二叉树结点的对应关系如图所示。

第25页/共35页18.4.2C语言实现简单的二叉树4．验证二叉树是否为空 二叉树使用前应先判断是否为空，若为空，则不能继续对二叉树进行任何操作。二叉树为空的判断程序为：

01 intemptyBinTree(structTreeNode*BinTree) 02 { 03 if(NULL==BinTree) 04 { 05 printf(“二叉树为空\n”); 06 return0; 07 } 08 else 09 { 10 printf(“二叉树不为空\n”); 11 return1; 12 } 13 }

第26页/共35页18.4.3二叉树的简单操作

二叉树的遍历分为先序遍历、中序遍历和后序遍历三种。1．先序遍历二叉树

先序遍历二叉树又叫先根序遍历二叉树，即先遍历二叉树及其子树的根结点，然后再遍历其他结点，其基本规则为：先访问根结点，然后先序遍历左子树，先序遍历右子树。采用先序遍历算法，各结点的先后遍历顺序为：A->B->D->E->C->F->G。先序遍历的基本代码如下：

01 voidpreOrderTreversingTree(structTreeNode*InBinTree) 02 { 03 if(NULL==InBinTree) 04 { 05 printf(“输入参数错误，返回\n”); 06 return; 07 } 08 else 09 { 10 printf("%d",InBinTree->data); //访问根结点

11 preOrderTreversingTree(InBinTree->leftchild);//先序遍历左子树

12 preOrderTreversingTree(InBinTree->rightchild);//先序遍历右子树

13 } 14 return; 15 }第27页/共35页18.4.3二叉树的简单操作2．中序遍历二叉树 中序遍历二叉树又叫中根序遍历二叉树，即先遍历左子树，再遍历根结点，然后遍历右子树。其基本规则为：中序遍历左子树，遍历根结点，中序遍历右子树。中序遍历的基本代码如下：

01 voidMidOrderTreversingTree(structTreeNode*InBinTree) 02 { 03 if(NULL==InBinTree) 04 { 05 printf(“输入参数错误，返回\n”); 06 return; 07 } 08 else 09 { 10 MidOrderTreversingTree(InBinTree->leftchild);//中序遍历左子树

11 printf("%d",InBinTree->data); //访问根结点

12 MidOrderTreversingTree(InBinTree->rightchild);//中序遍历右子树

13 } 14 return; 15 }第28页/共35页18.4.3二叉树的简单操作3．后序遍历二叉树

后序遍历二叉树又叫后根序遍历二叉树，即先遍历左子树，再遍历右子树，然后遍历根结点。其基本规则为：后序遍历左子树，后序遍历右子树，遍历根结点。后序遍历的基本代码如下：

01 voidLastOrderTreversingTree(structTreeNode*InBinTree) 02 { 03 if(NULL==InBinTree) 04 { 05 printf(“输入参数错误，返回\n”); 06 return; 07 } 08 else 09 { 10 LastOrderTreversingTree(InBinTree->leftchild);//后序遍历左子树

11 LastOrderTreversingTree(InBinTree->rightchild);//后序遍历右子树

12 printf("%d",InBinTree->data);//访问根结点

13 } 14 return; 15 }第29页/共35页18.4.3二叉树的简单操作4．二叉树中查找某个结点 对于任何一个非空二叉树，都可以通过遍历来查找值为val的某个结点，若找到，则返回该结点位置，否则，输出提示信息。使用递归算法，代码如下：

01 structTreeNode*SearchBinTree(structTreeNode*InBinTree,intIndata) 02 { 03 structTreeNode*pTree=NULL; 04 printf("开始处理函数SearchBinTree()\n"); 05 if(NULL==InBinTree) 06 { 07 printf("输入参数错误，退出\n"); 08 returnNULL; 09 } 10 else 11 { 12 if(InBinTree->data==Indata) 13 { 14 returnInBinTree; 15 } 16 else 17 {/*分别向左右子树递归查找*/ 18 if(pTree=SearchBinTree(InBinTree->leftchild,Indata))//遍历左子树

19 { 20 returnpTree; //返回查找到的结点

21 } 22 if(pTree=SearchBinTree(InBinTree->rightchild,Indata)) //遍历右子树

23 { 24 returnpTree; //返回查找到的结点

25 } 26 printf("没有匹配的结点\n"); 27 returnNULL; 28 } 29 } 30 }

第30页/共35页18.4.3二叉树的简单操作5．二叉树中插入一个结点 向二叉树中插入结点时应考虑二叉树的有序性，即在不破坏二叉树的有序性的前提下插入一个新的结点，若二叉树为空，则新建一个结点，构成一个仅有一个结点的二叉树。二叉树插入结点的基本代码如下：

01 voidInsertBinTree(structTreeNode*InBinTree,intNewData) 02 { 03 if(NULL==InBinTree) //树为空，新建一个根结点

04 { 05 structTreeNode*pNode=(structTreeNode*)malloc(sizeof(structTreeNode)); 06 pNode->data=NewData; 07 pN