算法设计与分析 第三章2 算法与数据结构.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）中选一名厂长。请编程完成统计选票的工作。算法设计： 1）虽然选票发放的数量一般是已知的，但收回的数量通常是无法预知的，所以算法采用随机循环，设计停止标志为“-1”。 2）统计过程的一般方法为：先为五个候选人各自设置五个“计数器”S1，S2，S3，S4，S5，然后根据录入数据通过多分支语句或嵌套条件语句决定为某个“计数器”累加1, 这样做效率太低。 现在把五个“计数器”用数组代替，选票中候选人的编号xp正好做下标，执行A(xp)=A(xp)+1就可方便地将选票内容累加到相应的“计数器”中。也就是说数组结构是存储统计结果的，而其下标正是原始信息。 3）考虑到算法的健壮性，要排除对1——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： 算法如下： main( ) {int i,a[10], ind; long num1,num2; char eng[10][6]={“zero”,”one”,”two”,”three ”,” four”, ” five”,”six”,”seven”,“eight”,”nine”}; print(“Input a num”); input(num1); num2=num1; ind =0; while (num20) {a[ind]=num2 mod 10; ind= ind +1; num2=num2/10; } print(num1, “English_exp:”, eng[a[ind-1]]); for( i=ind-2;i=0;i=i-1) print(“-”，eng[a[i]]); } 【例2】一个顾客买了价值x元的商品，并将y元的钱交给售货员。售货员希望用张数最少的钱币找给顾客。 算法设计： 算法如下： 3.2.3 数组记录状态信息 问题提出： 有的问题会限定在现有数据中，每个数据只能被使用一次，怎么样表示一个数据“使用过”还是没有“使用过”？ 一个朴素的想法是：用数组存储已使用过的数据，然后每处理一个新数据就与前面的数据逐一比较看是否重复。这样做，当数据量大时，判断工作的效率就会越来越低。 例1 【例2】游戏问题： 算法设计： 算法如下： 算法说明： 3.2.4 大整数的存储及运算 算法设计： 算法如下：