实现重复操作的算法机制.PPT

算法与数据结构 2、连续存储和链式存储比较 3、在选取存储结构时权衡因素有： １）基于存储的考虑 ２）基于运算的考虑 ３）基于环境的考虑 原始信息与处理结果对应存储 每一个问题中的信息往往是多方面的，在算法中一般有输入信息、输出信息和信息加工处理过程中的中间信息。那么哪些信息需要用数组进行存储，数组元素下标与信息怎么样对应等问题的确定，在很大程度上影响着算法的编写效率和运行效率。 【例1】某次选举，要从五个候选人（编号分别为1、2、3、4、5）中选一名厂长。请编程完成统计选票的工作。 算法如下： 【例】一次考试共考了语文、代数和外语三科。某小组共有九人，考后各科及格名单如下表，请编写算法找出三科全及格的学生的名单（学号）。 方法一算法如下： 方法二算法如下： main( ) {int a[10],i,xh; for(i =1;i=21;i=i+1) {input(xh); a[xh]=a[xh]+1;} for(xh =1;xh=9;xh=xh+1) if(a[xh] =3 ) print(xh); } 数组使信息有序化 当题目中的数据缺乏规律时，很难把重复的工作抽象成循环不变式来完成，但先用数组结构存储这些信息后，问题就迎刃而解了， 算法如下： 数组记录状态信息 问题提出： 有的问题会限定在现有数据中，每个数据只能被使用一次，怎么样表示一个数据“使用过”还是没有“使用过”？ 一个朴素的想法是：用数组存储已使用过的数据，然后每处理一个新数据就与前面的数据逐一比较看是否重复。这样做，当数据量大时，判断工作的效率就会越来越低。 例1 构造趣味矩阵 2 【例1】编程打印形如下规律的n*n方阵。 * 数据的逻辑结构常分为四大类： （1）集合结构 （2）线性结构 （3）树形结构 （4）图结构（网结构） 存储结构可以分为：连续存储和链式存储。连续存储又可以分为：静态存储和动态存储 1、常用的几种数据结构 顺序存储的优点： (1) 方法简单，各种高级语言中都提供数组结构，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。 顺序存储的缺点： (1)?? 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。 (2)?? 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。 温馨提示： 链表的优缺点恰好与顺序表相反。 vote( ) { int i,xp,a[6]; print(“input data until input -1”); input(xp ); while(xp!=-1) {if (xp=1 and xp=5 ) a[xp]=a[xp]+1; else print(xp, input error!); input(xp ); } for (i=1;i=5;i++) print(i,number get, a[i], votes); } 返回3.2.1 例1· 例2· 例3· 例4 科目 及格学生学号 语文 1，9，6，8，4，3，7 代数 5，2，9，1，3，7 外语 8，1，6，7，3，5，4，9 ? main( ) {int a[7], b[6], c[8],i,j,k,v,flag; for( i =0;i=6;i=i+1) input(a[i]); for( i =0;i=5;i=i+1) input(b[i]); for( i =0;i=7;i=i+1) input(c[i]); for( i =0;i=6;i=i+1) {v=a[i]; for( j =0;j=5;j=j+1) if ( b[j]=v ) for(k =0;k=7;k=k+1) if(c[k]=v) {print(v); break;} } } 返回3.2.1 例1· 例2· 例3· 例4 【例1】编程将编号“翻译”成英文。例