第三章2 算法与数据结构1.ppt

3．2 算法与数据结构 3．2．1 原始信息与处理结果的对应存储 3．2．2 数组使信息有序化 3．2．3 数组记录状态信息 3．2．4 大整数存储及运算 3．2．5 构造趣味矩阵 2、连续存储和链式存储比较 3、在选取存储结构时权衡因素有： １）基于存储的考虑 顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低， 3．2．1 原始信息与处理结果对应存储 每一个问题中的信息往往是多方面的，在算法中一般有输入信息、输出信息和信息加工处理过程中的中间信息。那么哪些信息需要用数组进行存储，数组元素下标与信息怎么样对应等问题的确定，在很大程度上影响着算法的编写效率和运行效率。 下面的例子恰当地选择了用数组存储的信息，并把题目中的有关信息作为下标使用，使算法的实现过程大大简化。 【例1】统计选票 【例2】统计身高 【例3】统计及格学生的名单 【例4】统计找数字对的出现频率 【例1】某次选举，要从五个候选人（编号分别为1、2、3、4、5）中选一名厂长。请编程完成统计选票的工作。算法设计： 算法如下： 【例2】编程统计身高（单位为厘米）。统计分150——154；155——159；160——164；165——169；170——174；175——179及低于是150、高于是179共八档次进行。算法设计： 算法如下： 【例3】一次考试共考了语文、代数和外语三科。某小组共有九人，考后各科及格名单如下表，请编写算法找出三科全及格的学生的名单（学号）。 方法一： 方法一算法如下： 方法二 ： 方法二算法如下： 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); } 【例4】统计找数字对的出现频率 算法如下： 3．2．2数组使信息有序化 当题目中的数据缺乏规律时，很难把重复的工作抽象成循环不变式来完成，但先用数组结构存储这些地信息后，问题就迎刃而解了， 算法设计1： 算法如下： 【例2】一个顾客买了价值x元的商品，并将y元的钱交给售货员。售货员希望用张数最少的钱币找给顾客。 算法如下： 3．2．3 数组记录状态信息 问题提出： 有的问题会限定在现有数据中，每个数据只能被使用一次，怎么样表示一个数据“使用过”还是没有“使用过”？ 一个朴素的想法是：用数组存储已使用过的数据，然后每处理一个新数据就与前面的数据逐一比较看是否重复。这样做，当数据量大时，判断工作的效率就会越来越低。 例1 【例2】游戏问题： 算法设计： 算法如下： 算法说明： 3．2．4 大整数的存储及运算 算法设计： 算法如下： 算法说明： 1）算法中“m=log(n)*n/6+2;”是对N！位数的粗略估计。 2）输出时，首先计算结果的准确位数r，然后输出最高位数据，在输出其它存储单元的数据时要特别注意，如若计算结果是123000001，ab[2]中存储的是123，而ab[1]中存储的不是000001，而是1。所以在输出时，通过多个条件语句保证输出的正确性。 3．2．5 构造趣味矩阵 2 【例1】编程打印形如下规律的n*n方阵。 【例2】螺旋阵：任意给定n值，按如下螺旋的方式输出方阵： 算法设计： 2. 算法说明： 【例3】设计算法生成魔方阵 main( ) {int a[100],i,k,p,m; print(“input numbers of game:”); input(n); print(“input serial number of game start:”); input(k); print(“input number of out_ring:”); input(m); for( i=1;i=n;i++) a[i]=1; p=0; while (pn-1) {x=0； while xm {k=k+1; if(kn) k=1; x=x+a[k];} print(k); a[k]=0; p=p+1; } for( i