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

3．2 算法与数据结构 3．2．1 原始信息与处理结果的对应存储 3．2．2 数组使信息有序化 3．2．3 数组记录状态信息 3．2．4 大整数存储及运算 3．2．5 构造趣味矩阵 2、连续存储和链式存储比较 3、在选取存储结构时权衡因素有： １）基于存储的考虑 顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，过大造成浪费，过小造成溢出。 对线性表的长度或存储规模难以估计时，不宜采用顺序表； 链表不用事先估计存储规模，但链表的存储密度较低， 3．2．1 原始信息与处理结果对应存储 在算法中一般有输入信息、输出信息和信息加工处理过程中的中间信息。那么哪些信息需要用数组进行存储，数组元素下标与信息怎么样对应等问题的确定，在很大程度上影响着算法的编写效率和运行效率。 【例1】统计选票 【例2】统计身高 【例3】统计及格学生的名单 【例4】统计找数字对的出现频率 【例1】某次选举，要从五个候选人（编号分别为1、2、3、4、5）中选一名厂长。请编程完成统计选票的工作。算法设计： 把五个“计数器”用数组代替，选票中候选人的编号xp正好做下标，执行A(xp)=A(xp)+1就可方便地将选票内容累加到相应的“计数器”中。也就是说数组结构是存储统计结果的，而其下标正是原始信息。 3）考虑到算法的健壮性，要排除对1——5之外的数据进行统计。 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); } 【例2】编程统计身高（单位为厘米）。统计分150——154；155——159；160——164；165——169；170——174；175——179及低于是150、高于是179共八档次进行。 main( ) { int i,xp,a[8]; print(“input height data until input -1”); input(sg ); while （sg-1） {if (sg179) a[7]=a[7]+1； else if (sg150) a[0]=a[0]+1； else a[sg\5-29]=a[sg\5-29]+1； input( sg ); } for (i=0;i=7;i=i+1) print(i+1 ，“field the number of people： ”，a[i]); } 【例3】一次考试共考了语文、代数和外语三科。某小组共有九人，考后各科及格名单如下表，请编写算法找出三科全及格的学生的名单（学号）。 方法一： 方法一算法如下： 方法二 ： 方法二算法如下： 【例4】统计找数字对的出现频率 算法如下： 3．2．2数组使信息有序化 当题目中的数据缺乏规律时，很难把重复的工作抽象成循环不变式来完成，但先用数组结构存储这些地信息后，问题就迎刃而解了， 3．2．3 数组记录状态信息 问题提出： 有的问题会限定在现有数据中每个数据只能被使用一次，怎么样表示一个数据“使用过”还是没有“使用过”？ 一般想法是：用数组存储已使用过的数据，然后每处理一个新数据就与前面的数据逐一比较看是否重复。这样做，当数据量大时，判断工作的效率就会越来越低。 例1 【例2】游戏问题： 3．2．4 大整数的存储及运算 算法设计： 算法如下： 算法说明： 1）算法中“m=log(n)*n/6+2;”是对N！位数的粗略估计。 可换为： m=1; if(d0) { a[j]=d; m=m+1; } 3．2．5 构造趣味矩阵 2 【例1】编程打印形如下规律的n*n方阵。 【例2】螺旋阵：任意给定n值，按如下螺旋的方式输出方阵： 算法设计： 【例3】设计算法生成魔方阵 12个小朋友手拉手站成一个圆圈，从某一个小朋友开始报数，报到7的那个小朋友退到圈外，然后他的下一位重新报“1”。这样继续下去，直到最后只剩下一个小朋友，求解这个小朋