电子教案C 语言案例教程第五章1

1、第五章常用算法学习任务利用前面学到的流程控制语句和构造数据的方法，归纳总结常用的编程方法学习目标掌握后面八种程序设计的常用方法学习要点理解和掌握常用算法的一般步骤小猪小猴，请抢答：1+2+100=？1+2+3+100=?？能力要点能熟练选择恰当的算法，编写常见的程序算法 算法：程序员所说的“算法”，正是解决某一个特定问题的方案的准确而完整的描述。 用什么描述算法呢？ 流程图、自然语言、伪码（PDL）均是描述算法的工具 。评价算法优劣的标准：l 计算量的大小；占用存储空间的大小；逻辑结构是否简单。 算法具有有穷性、确定性、能行性、有输入输出等特征。 第一节排序本节任务 学会冒泡排序（见第四章）、

2、定位交换排序、直接插入排序 学习要点 掌握定位交换排序、直接插入排序的一般步骤排序排序是将任意排列的数据元素重新排列成有序序列的过程。 排序分为两种：内排序、外排序。 排序的方式有升序、降序两种。 排序过程的主要操作是什么？显然不外乎是比较、交换和移动。 1.1 定位交换排序 定义定位交换排序算法思想是： 将原始数据放入数组xN中； 让每个xi（0iN-2）与xj 逐次比较（i+1jN-1），只要是xixj（或xixj )则立即交换xi与xj，由此得到原始数据升序（或降序）的排序结果。交换排序的主要工作是比较与交换。定位交换排序流程图见图5-1 ；定位交换排序的变量表见表5-1；定位交换排序过

3、程见表5-2；#includeconio.h#define N 10main() int xN,i; void sort(); clrscr(); for(i=0;iN;i+) scanf(%d,&xi); /* 输入N位战士的原始身高 */ sort(x); for(i=0;iN;i+) printf(%dt,xi); /* 输出N位战士的排序结果 */void sort(int x) int i,j,t; for(i=0;iN-1;i+) for(j=i+1;jN;j+) if (xixj) t=xi; xi=xj; xj=t; 小结 （降序排序时） 定位交换排序法实现的步骤： 第一轮，将

4、第一个数与后面的每个数依次相比，如第一个小，就把大的放到第一个的位置，原来第一个换到与它相比的那个的位置（交换）；继续将新的第一个与后面的继续比，凡小于后面某个，就交换排完第一轮，最前面的那个已经是最大的。第二轮，将第二个数与后面的各数依次相比，小于后面的就交换排完第二轮，第二个比它后面的数已经又是最大的；排完n-1轮，数组里的数已经按大到小排好了。1.2 直接插入排序定义将一个新元素插入到已排好序的有序序列中，从而得到一个新的、元素个数增加了1个的有序序列，这就是插入排序。插入排序的主要工作是比较与移动。直接插入排序流程图见图5-2 ；直接插入排序的变量表见表5-1；直接插入排序过程 见表5

5、-3 ；#includeconio.h#define N 10main() int xN,i; void sort(); clrscr(); for(i=0;iN;i+) scanf(%d,&xi); sort(x); for(i=0;iN;i+) printf(%dt,xi);void sort(int x) int i,j,t; for(i=1;i=0;j-) if(txj) break; /* 找到了新元素该去的位置 */ else xj+1=xj; /* 原有序序列xj后移一个位置 */ xj+1=t; /* 新元素到位 */ 小结 （升序排序时） 直接插入排序法实现的步骤 第一轮，拿

6、最前面两个数比，后一个设为t；如果t小于第一个，第一个挪后一位，内循环结束，t插入第一个的位置；这时候，前两个数已经按升序排好； 第二轮，拿前三个数比，设第三个数为t；t与第二个比，t小，第二个挪后一位，否则（即t大）停止比较，t放回第三个位置；当t小，挪位后，再与第一个比，类似的，t小，第一个挪后一位，内循环结束，t插入第一个的位置；否则（即t大）停止比较，t放到第二个的位置；这时候，前三个数已经按升序排好； 第k轮，拿第k+1个数设为t，与其前面的数比，凡是t小，所比的那个数向后挪位直到第一个比完t都小，内循环结束，t插入第一个的位置；否则，只要遇到某次t大，内循环停止，t插入到比它小的数的后面位置； 排完n-2轮，数组里的数已经按小到大排好了。作业与练习 以下各题，均要求列变量表，画大致流程图，关键语句注释。4为了给进货提供依据，商场进行商品管理时往往从键盘输入各商品的的品名、销售数量，请按销售数量降序排。设输入商品品名为空时表示结束。5奥运会