算法与数据结构85.pptVIP

3．2 算法与数据结构;数据的逻辑结构常分为四大类： （1）集合结构 （2）线性结构 （3）树形结构 （4）图结构（网结构） ;顺序存储的优点： (1) 方法简单，各种高级语言中都提供数组结构，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。;顺序存储的缺点： (1)?? 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。 (2)?? 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。;3、在选取存储结构时权衡因素有：;２）基于运算的考虑 在顺序表中按序号访问ai的时间性能时O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表； ３）基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，操作简单。 ;3．2．1 原始信息与处理结果对应存储; 【例1】某次选举，要从五个候选人（编号分别为1、2、3、4、5）中选一名厂长。请编程完成统计选票的工作。算法设计：;算法如下： ; 【例2】编程统计身高（单位为厘米）。统计分150——154；155——159；160——164；165——169；170——174；175——179及低于是150、高于是179共八档次进行。算法设计： ;算法如下： ;科目 ;方法一：;方法一算法如下：;方法二 ：;方法二算法如下：;【例4】统计找数字对的出现频率 ;算法设计： 其实并不是只有一维数组这样的数据结构可以在算法设计中有多采的应用，根据数据信息的特点，二维数组的使用同样可以使算法易于实现，此题就正是如此。 用10*10的二维数组（行、列下标均为0-9），存储统计结果，i行j列存储数字对（i，j）出现的次数，无需存储原始数据，用其做下标，在数据输入的同时就能统计出问题的结果， ;算法如下： ;3．2．2数组使信息有序化;算法设计1： ;算法如下： ;【例2】一个顾客买了价值x元的商品，并将y元的钱交给售货员。售货员希望用张数最少的钱币找给顾客。 ;算法如下： ;算法说???： 1）每求出一种面额所需的张数后，一定要把这部分金额减去： “y=y-A*B[j];”，否则将会重复计算。 2）算法无论要找的钱z是多大，我们都从50元开始统计，所以在输出时要注意合理性，不要输出无用的张数为0 的信息。;3．2．3 数组记录状态信息;例1;算法设计： 1）? 用一个10 个元素的状态数组p，记录数字0——9在X2中出现的情况。数组元素都赋初值为1，表示数字0——9没有被使用过。 2）? 对尝试的每一个数x，求x*x,并取其各个位数字，数字作为数组的下标，若对应元素为1，则该数字第一次出现，将对应的元素赋为0，表示该数字已出现一次。否则，若对应元素为0，则说明有重复数字，结束这次尝试。 3） 容易理解当状态数组p中有9个元素为0时，就找到了问题的解。但这样判定有解，需要扫描一遍数组p。为避免这个步骤，设置一个计数器k，在取x*x各个位数字的过程中记录不同的数字的个数，当k=9时就找到了问题的解。 ;main( ) {long x, y1, y2; int p[10], 2, i, t, k, num=0; for (x=10000;x32000; x=x+1) { for(i=0; i=9; i=i+1) p[i]=1; y1=x*x ; y2=y1; k=0; for(i=1; i=9. i=i+1) {t=y2 mod 10; y2=y2/10; if(p[t]=1) {k=k+1; p[t]=0;} else break; } if(k=9) {num=num+1; print (“No.”,num , “：n=”, x, “n2=”, y1);} } };12个小朋友手拉手站成一个圆圈，从某一个小朋友开始报数，报到7的那个小朋友退到圈外，然后他的下一位重新报“1”。这样继续下去，直到最后只剩下一个小朋友，求解这个小朋友原来站在什么位置上呢？ ;算法设计：;算法如下：;算法说明：;3．2．4 大整数的存储及运算; 虽然现在工作站或小型机等机型上都有更高精度的数值类型，但这些机型价格昂贵，只有大型科研机构