算法与数据结构讲解.ppt

大连海事大学,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、连续存储和链式存储比较,大连海事大学,顺序存储的缺点： (1) 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低 (2) 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出温馨提示： 链表的优缺点恰好与顺序表相反大连海事大学,3、在选取存储结构时权衡因素有：,１）基于存储的考虑 顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。

可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，,大连海事大学,２）基于运算的考虑 在顺序表中按序号访问ai的时间性能时O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表； ３）基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，操作简单大连海事大学,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之外的数据进行统计大连海事大学,算法如下：,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共八档次进行。

算法设计：,输入的身高可能在50——250之间，若用输入的身高数据直接作为数组下标进行统计，即使是用PASCAL语言可设置上、下标的下界，也要开辟200多个空间，而统计是分八个档次进行的，这样是完全没有必要的 由于多数统计区间的大小是都固定为5，这样用“身高/5-29”做下标，则只需开辟8个元素的数组，对应八个统计档次，即可完成统计工作大连海事大学,算法如下：,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】一次考试共考了语文、代数和外语三科某小组共有九人，考后各科及格名单如下表，请编写算法找出三科全及格的学生的名单（学号）。

大连海事大学,方法一：,从语文及格名单中逐一抽出各及格学生学号，先在代数及格名单核对，若有该学号（说明代数也及格了），再在外语及格名单中继续查找，看该学号是否也在外语及格名单中若仍在，说明该号属全及格学生的学号，否则就是至少有一科不及格的若语文及格名单中就没有某生的号，显然该生根本不在比较之列，自然不属全及格学生 该方法采用了枚举尝试的方法 A，B，C三组分别存放语文、代数、外语及格名单，尝试范围为三重循环： I循环， 初值0， 终值6， 步长1 J循环， 初值0， 终值5， 步长1 K循环， 初值0， 终值7， 步长1 定解条件： A[I]=B[J]=C[K] 共尝试7*6*8=336次大连海事大学,方法一算法如下：,main( ) {int a[7], b[6], c[8],i,j,k,v,flag; for( i =0;i=6;i=i+1) input(a[i]); for( i =0;i=5;i=i+1) input(b[i]); for( i =0;i=7;i=i+1) input(c[i]); for( i =0;i=6;i=i+1) {v=a[i]; for( j =0;j=5;j=j+1) if ( b[j]=v ) for(k =0;k=7;k=k+1) if(c[k]=v) {print(v); break;} } },大连海事大学,方法二 ：,用数组A的九个下标分量作为各号考生及格科目的计数器。

将三科及格名单共存一个数组，当扫描完毕总及格名单后，凡下标计数器的值为3的就是全及格的，其余则至少有一科不及格的 该方法同样也采用了枚举尝试的方法算法步骤为： 1）用下标计数器累加各学号学生及格科数， 2）尝试、输出部分 累加部分为一重循环，初值1 ，终值为三科及格的总人数，包括重复部分计7+6+8=21，步长1 尝试部分的尝试范围为一重循环，初值1 ，终值9，步长1 定解条件：A（i）=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】统计找数字对的出现频率,算法说明： 输入N（2≤N≤100）个数字（在0与9之间），然后统计出这组数中相邻两数字组成的链环数字对出现的次数例如： 输入：N=20 {表示要输入数的数目} 0 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9 输出：（7，8）=2 （8，7）=3 {指（7，8）、（8，7）数字对出现次数分别为2次、3次 （7，2）=1 （2，7）=1 （2，2）=2 （2，3）=1 （3，2）=1,大连海事大学,算法设计： 其实并不是只有一维数组这样的数据结构可以在算法设计中有多采的应用，根据数据信息的特点，二维数组的使用同样可以使算法易于实现，此题就正是如此。

用10*10的二维数组（行、列下标均为0-9），存储统计结果，i行j列存储数字对（i，j）出现的次数，无需存储原始数据，用其做下标，在数据输入的同时就能统计出问题的结果，,大连海事大学,算法如下：,main( ) {int a[10][10],m,i,j,k1,k0; print(“How many is numbers?”); input(n); print(“Please input these numbers:”); input(k0); for (i=2;i0 and a[j][i]0); print(“(”,i,j,”)=“,a[i][j],”,(”,j,i,”)=”,a[j][i]) },大连海事大学,3．2．2数组使信息有序化,当题目中的数据缺乏规律时，很难把重复的工作抽象成循环不变式来完成，但先用数组结构存储这些地信息后，问题就迎刃而解了，,【例1】编程将编号“翻译”成英文例35706“翻译”成three-five-seven-zero-six算法设计1：,算法设计1： 1） 编号一般位数较多，可按长整型输入和存储 2） 将英文的“zero——nine”存储在数组中，对应下标为0——9。

这样无数值规律可循的单词，通过下标就可以方便存取、访问了 3） 通过求余、取整运算，可以取到编号的各个位数字用这个数字作下标，正好能找到对应的英文数字 4）考虑输出翻译结果是从高位到低位进行的，而取各位数字，比较简单的方法是从低位开始通过求余和整除运算逐步完成的所以还要开辟一个数组来存储从低位到高位翻译好的结果，并记录编号的位数，最后倒着从高位到低位输出结果算法如下：,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元的钱交给售货员。

售货员希望用张数最少的钱币找给顾客问题分析：无论买商品的价值x是多大，找给他的钱最多需要以下六种币值：50，20，10，5，2，1算法设计： 1）为了能达到找给顾客钱的张数最少，先尽量多地取大面额的币种，由大面额到小面额币种逐渐进行 2）六种面额不是等差数列，为了能构造出循环不变式，将六种币值存储在数组B这样，六种币值就可表示为B[i]，i=1，2，3，4，5，6为了能达到先尽量多地找大面额的币种，六种币值应该由大到小存储 3）另外还要为统计六种面额的数量，同样为了能构造出循环不变式，设置一个有六个元素的累加器数组S，这样操作就可以通过循环顺利完成了算法如下：,main( ) {int i,j,x,y,z,a,b[7]={0,50,20,10,5,2,1},s[7]; input(x,y); z=y-x; for(i=1;i0) print(b[i]。