《算法与数据结构》PPT课件

《《算法与数据结构》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3．2算法与数据结构3．2．1原始信息与处理结果的对应存储3．2．2数组使信息有序化3．2．3数组记录状态信息3．2．4大整数存储及运算3．2．5构造趣味矩阵数据的逻辑结构常分为四大类：（1）集合结构（2）线性结构（3）树形结构（4）图结构（网结构）存储结构可以分为：连续存储和链式存储。连续存储又可以分为：静态存储和动态存储1、常用的几种数据结构顺序存储的优点：(1)方法简单，各种高级语言中都提供数组结构，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。2、连续存储和链式存储比较顺序存储

2、的缺点：(1)在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。(2)需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。温馨提示：链表的优缺点恰好与顺序表相反。3、在选取存储结构时权衡因素有：１）基于存储的考虑顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，２）基于运算

3、的考虑在顺序表中按序号访问ai的时间性能时O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；３）基于环境的考虑顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，操作简单。3．2．1原始信息与处理结果对应存储每一个问题中的信息往往是多方面的，在算法中一般有输入信息、输出信息和信息加工处理过程中的中间信息。那么哪些信息需要用数组进行存储，数组元素下标与信息怎么样对应等问题的确定，在很大程度上影响着算法的编写效率和运行效率。下面的例子恰当地选择了用数组存储的信息，并把题目中的有

4、关信息作为下标使用，使算法的实现过程大大简化。【例1】统计选票【例2】统计身高【例3】统计及格学生的名单【例4】统计找数字对的出现频率【例1】某次选举，要从五个候选人（编号分别为1、2、3、4、5）中选一名厂长。请编程完成统计选票的工作。算法设计：1）虽然选票发放的数量一般是已知的，但收回的数量通常是无法预知的，所以算法采用随机循环，设计停止标志为“-1”。2）统计过程的一般方法为：先为五个候选人各自设置五个“计数器”S1，S2，S3，S4，S5，然后根据录入数据通过多分支语句或嵌套条件语句决定为某个“计数器”累加1,这样做效率太低。现在把五个“计

5、数器”用数组代替，选票中候选人的编号xp正好做下标，执行A(xp)=A(xp)+1就可方便地将选票内容累加到相应的“计数器”中。也就是说数组结构是存储统计结果的，而其下标正是原始信息。3）考虑到算法的健壮性，要排除对1——5之外的数据进行统计。返回3.2.1例1·例2·例3·例4算法如下：vote(){inti,xp,a[6];print(“inputdatauntilinput-1”);input(xp);while(xp!=-1){if(xp>=1andxp<=5)a[xp]=a[xp]+1;elseprint(xp,"inputerror!"

6、);input(xp);}for(i=1;i<=5;i++)print(i,"numberget",a[i],"votes");}返回3.2.1例1·例2·例3·例4【例2】编程统计身高（单位为厘米）。统计分150——154；155——159；160——164；165——169；170——174；175——179及低于是150、高于是179共八档次进行。算法设计：输入的身高可能在50——250之间，若用输入的身高数据直接作为数组下标进行统计，即使是用PASCAL语言可设置上、下标的下界，也要开辟200多个空间，而统计是分八个档次进行的，这样是完全没

7、有必要的。由于多数统计区间的大小是都固定为5，这样用“身高/5-29”做下标，则只需开辟8个元素的数组，对应八个统计档次，即可完成统计工作。返回3.2.1例1·例2·例3·例4算法如下：main(){inti,xp,a[8];print(“inputheightdatauntilinput-1”);input(sg);while（sg<>-1）{if(sg>179)a[7]=a[7]+1；elseif(sg<150)a[0]=a[0]+1；elsea[sg/5-29]=a[sg/5-29]+1；input(sg);}for(i=0;i<=7;i=i

8、+1)print(i+1，“fieldthenumberofpeople：”，a[i]);}返回3.2.1例1·例2·例3