《王建德3线性结构》由会员分享，可在线阅读，更多相关《王建德3线性结构（98页珍藏版）》请在金锄头文库上搜索。
1、线性表线性表是是由有限个数据元素组成的有序集合，每个数据元素 有一个数据项或者含多个数据项。例如26个英文字母表(A，B， ，Z)是一个线性表，表中每一个数据元素由单个字母组成 数据项。又如下图也是一个线性表，表中含8个数据元素，每一 个数据元素由n个选手在该项目的竞赛成绩组成。 线性表的结构特征均匀性：即同一线性表的各数据元素的数 据类型一致且数据项数相同；有序性：表中数据元素之间的相对位置是 线性的，即存在唯一的“第一个”和“最后 一个”数据元素。除第一个和最后一个外， 其它元素前面均只有一个数据元素（直接前 趋）和后面均只有一个数据元素（直接后继 ）。线性表的分类1、元素的存储方式分类顺
2、序存储结构：用一组地址连续的存贮单元 依次存储线性表的元素（数组）链式存储结构：逻辑上相邻的两元素，其物 理位置不要求相邻。实现方式即可采用数组，亦可采 用指针。 2、根据存取方式限制和表元素类型限制的分类： 栈 队列（宽度优先搜索讲） 串 （一般采用顺序存储结构）数组数组有限个同类型数据元素的序列，元素在序列 的位置由下标指明。可用作存储一维序列、 矩阵数组、队列、堆栈、链表等。数组存储 于静态数据区，其空间大小取决于数组容量 。津津的储蓄计划【问题描述】津津的零花钱一直都是自己管理。每个月的 月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能 做到实际花销和预算的相同。为了让津津学
3、习如何储蓄，妈妈提出，津津可以随时 把整百的钱存在她那里，到了年末她会加上20%还给津津。因此 津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零 花钱后，如果她预计到这个月的月末手中还会有多于100元或恰 好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己 手中。例如11月初津津手中还有83元，妈妈给了津津300元。 津津预计11月的花销是180元，那么她就会在妈妈那里存200元 ，自己留下183元。到了11月月末，津津手中会剩下3元钱。津津发现这个储蓄计划的主要风险是，存在妈妈那里的 钱在年末之前不能取出。有可能在某个月的月初，津津手中的 钱加上这个月妈妈给的钱，不够这个月的原
4、定预算。如果出现 这种情况，津津将不得不在这个月省吃俭用，压缩预算。现在请你根据2004年1月到12月每个月津津的预算，判 断会不会出现这种情况。如果不会，计算到2004年年末，妈妈 将津津平常存的钱加上20%还给津津之后，津津手中会有多少 钱。 【输入文件】输入文件save.in包括12行数据，每行包含一 个小于350的非负整数，分别表示1月到12月津津的预算。 【输出文件】输出文件save.out包括一行，这一行只包含 一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情 况，输出-X，X表示出现这种情况的第一个月；否则输出到 2004年年末津津手中会有多少钱。算法分析这道题属于一道基础
5、题，出题的目的，主要是为了考 核同学能不能应用程序设计语言的基本知识（一维数组，复合 、循环、选择三种控制结构）和数学推理的一般方法，编程解 决简单问题。设 vari,total,p:integer; /*total为当前剩余的钱；p为百 元为单位的储蓄数；a:array112 of integer; /*每个月的预算，其中ai 为第i个月的预算*/由于每个月的月初妈妈给津津300元钱，因此津津第i个月 剩余的钱total=total+（300-ai）。若total100 /*若剩余的钱够储蓄，则以百元 为单位累计储蓄数，并计算剩余的钱*/ then inc(p,total div 100);
6、totaltotal mod 100 ; /*then*/;/*for*/writeln(p*120+total);/*输出年末手中的钱*/TV-station在一维空间轴上，存在N个整点X1XN，每个点上有 一定数量的居民。要求在该轴上建立一个TV-station ，使得所有人到达TV-station的距离和尽可能小。数 据量：0 =temp /*若为中位数，则输出坐标*/then writeln(i,.00000);halt ;/*for*/校门外的树【问题描述】某校大门外长度为L的马路上有一排树，每两 棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴 ，马路的一端在数轴0的位置，
7、另一端在L的位置；数轴上的每 个整数点，即0，1，2，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们 在数轴上的起始点和终止点表示。已知任一区域的起始点和终 止点的坐标都是整数，区域之间可能有重合的部分。现在要把 这些区域中的树（包括区域端点处的两棵树）移走。你的任务 是计算将这些树都移走后，马路上还有多少棵树。 【输入文件】输入文件tree.in的第一行有两个整数L（ 1L 10000）和 M（1M100），L代表马路的长度，M代表 区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含 两个不同的整数，用一个空格隔开，表示一个区域的起始点和 终止点的坐标。 【输出文
8、件】输出文件tree.out包括一行，这一行只包含 一个整数，表示马路上剩余的树的数目。第1种方法：模拟统计在一个布尔类型数组的支持下直接模拟，数组的下标表示坐标，坐标从0开始。值为 true表示该位置有树，false表示该位置没树。每次读入一段区间，就将这个区间内所有 下标的布尔值设为false。显然，最后布尔数组中值为true的下标个数即为马路上剩余树 木的总数。 program ex; var a:array010000 of boolean;l,m,x,y,i,j,ans:longint; assign(input,tree.in);assign(output,tree.out); r
9、eset(input);rewrite(output);readln(l,m); /*读马路的长度和区域数*/ fillchar(a,sizeof(a),true);for i1 to m do readln(x,y); /*读第i个区域的起始点和终止点的坐标*/for jx to y do ajfalse /*该区域的树被移走*/;/*for*/ans0; /*计算马路上剩余的树数*/for i0 to l do if ai then inc(ans);writeln(ans); /*输出结果*/close(input);close(output) /*关闭输入文件和输出文件*/ . 上述算
10、法的时间复杂度为O(L*M)。 第2种方法：线段分割区间表存储互不重合的线段。每读入一个地铁区域， 则与区间表中的每一条线段比较，去掉线段中被重合的部分， 因为该区间内的树将被移走。例如，a,b为区间表中的一条线 段，c,d为地铁区域，阴影部分为a,b调整后的线段。最后，统计区间表中所有线段所含的坐标数total（total 即为被移走的树的总数）， const maxn=2000; type linetype=record /*线段的类型*/a,b:longint /*起始点和终止点的坐标*/end; var line:array1maxnof linetype; /*线段序列*/a,b,i
11、,tot,total,n,j,l:longint; func cross(a,b,c,d:longint):boolean; /*若线段（a,b）与线段（c,d）相交，则 返回true；否则返回false*/ if (ad)or(cb)then crossfalseelse crosstrue ;/* cross*/ proc add(a,b:longint); /*将线段（a,b）加入线段序列line */ tottot+1; linetot.aa;linetot.bb;/* add */ Proc dlt(num:integer); /*去除线段序列line中的第num条线段*/ line
12、numlinetot;tottot-1;/* dlt */ Proce cut(num:integer;cc,dd:longint); /*若线段序列line中的第num条线段覆盖 线段（cc,dd），则线段序列不变；否则线段序列line中的第num条线段被分割后的子线 段取代*/ if linenum.add /* 线段（dd+1,linenum.b）进入线段序列line */then add(dd+1,linenum.b); dlt(num) /*删除线段序列line中的第num条线段*/ ;/* cut */ assign(input,tree.in);/*输入文件读准备，输出文件写准备
13、*/reset(input);assign(output,tree.out);rewrite(output);readln(l,n); /*读马路的长度和区域数*/readln(a,b); /*读第1个区域的起始点和终止点的坐 标*/line1.aa; line1.bb; /*该线段进入线段序列 line*/tot1; /*线段数为1*/for i2 to n do readln(a,b);add(a,b); /*第i条线段(a,b) 进入线段序列 line*/for jtot-1 downto 1 do /*枚举线段序列line中的每条线 段。若（a,b）与之相交，则分割*/if cross
14、(a,b,linej.a,linej.b) then cut(j,a,b) ;/* for */total0; /*累计线段序列line的点数和，即被移走的树 数*/for i1 to tot do totaltotal+linei.b-linei.a+1;writeln(l+1-total); /*输出马路上剩余的树数 */close(input);close(output) /*关闭输入文件和输出文 件*/ . 显然，上述算法的时间复杂度为O(M2)。 第3种方法：快速排序首先，将所有的地铁区域按起始点坐标递增的顺序 排列，建立数组a，其中ai,1,ai,2为序列中第i 个地铁区域。设一个尾指针en，初始时，en为地铁区域 1的终止点坐标a1,2。然后依次处理每一个地铁区域 ，累计被移走的树木数total： 每处理一个地铁区域i后，en调整为ai,2。依次类 推，直至处理完地铁区域m后，便计算出被移走的树 木总数total。显然，L+1-total即为问题的解。时 间复杂度为O(Mlo
