最新数据结构总结.教学讲义ppt.ppt

《最新数据结构总结.教学讲义ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构总结.◆高精度运算◆排序的应用◆栈的应用◆队列的应用◆图的应用一、高精度运算主要解决的问题：1、高精度数的输入和保存。2、运算时的进位与借位。3、运算结果的保存。4、运算结果的输出。正整数大小的比较：◆实数数据大小的比较：S1;s2(s1<>s2)la:=length(s1);lb:=length(s2);if(las2实数大小的比较：a=‘1234.343’b=‘4.5545545’补齐：容易比较大小a=‘1234.3

2、430000’b=‘0004.5545545’记录小数点的位置p．去掉小数点．a=‘12343430000’b=‘00045545545’根据整数大小的比较。运算按照整数减法。◆结果的输出小数点的处理3435435.345453454000003444.4355454000000000.0004354554500000345534540000.000000输出合法要求：不能有多余的0k1:最后一位小数位置；p：小数点位置。k2:整数最高位。k1:=1;while(a[k1]=0)and(k1<=p)doinc

3、(k1);k2:=len;while(a[k2]=0)and(k2>p+1)dodec(k2);fori:=k2downtop+1dowrite(a[i]);ifk1<=pthenbeginwrite('.');fori:=p-1downtok1dowrite(a[i]);end;……342444.84584938……..k2k1p1、选择排序2、冒泡排序3、插入排序4、快速排序5、堆排序二、排序的应用时间：O(n2)N<1000时间：O(n*log(n))N<100001、区间合并【问题描述：】从键盘上任意

4、输入n个区间，然后按从小到大的顺序依次输出n个区间的并集。【输入：】第一行，区间个数n（<=1000）以下n行，每行两个整数a、b（-1000000000

5、一个区间　abFori:=1tonForj:=atobdof[j]=1◆最后输出f[j]=1的区间。时间复杂度：1012，只能过部分数据。算法二：直接合并1、按每个区间的左端的的值升序排列。由于N<=1000,任意排序算法。注意数据结构的设置:◆记录类型◆二维数组：a:array[1..1000,1..2]oflongint;a:array[1..1000]ofarray[1..2]oflongint2、合并过程◆输出第一个区间　的左端点坐标（最小的）◆依次处理后面的n-1的区间。Ifa[I,2]<=tail

6、Tail不变If(a[I,1]<=tail)and(tail<=a[I,2])Tail=a[I,2]Iftail

7、');tail:=a[i,2];end;end;writeln(tail);2、潜水比赛在马其顿王国举行了一次潜水比赛。其中一个项目是从高山上跳下水，再潜水达到终点。这是一个团体项目，一支队伍由n人组成。在潜水时必须使用氧气瓶，但是每只队伍只有一个氧气瓶。最多两人同时使用一个氧气瓶，但此时两人必须同步游泳，因此两人达到终点的时间等于较慢的一个人单独游到终点所需要的时间。好在大家都很友好，因此任何两个人后都愿意一起游水。安排一种潜水的策略，使得最后一名选手尽量的达到终点。输入：第一行：队伍的人数n（<=1000

8、）。第二行：n个数，分别是n个人潜水所用的时间ti(<=1000)。样例：输入：3134输出：8分析:先从简单入手:1)n=2,时间t:110所需的时间为:102)n=3,时间t:134所需的时间为:3+1+4=83)n=4,时间t:1101112所需的时间为:10+1+11+1+12=35贪心策略方法一:N个人:每个人所需的时间:t1，t2，……tn。假设t1最小。每次由t1接送人和氧气瓶，则总时