ASCAL数据结构之串.ppt

《ASCAL数据结构之串.ppt》由会员分享，可在线阅读，更多相关《ASCAL数据结构之串.ppt（62页珍藏版）》请在三一办公上搜索。

1、串,濮阳市第一高级中学 王晓斌,字符变量定义Var x:char；字符类型是一个有序类型，字符的大小顺序按ASCII码的大小决定。相关的函数有succ、pred、ord、chr,字符,Ord(x)对于字符来说是求字符对应的序号就是ascii码Chr(x)求ascii码对应字符,ASCII 编码是由美国国家标准委员会制定的一种包括数字、字母、通用符号和控制符号在内的字符编码集，全称叫美国国家信息交换标准代码,回顾知识点,字符类型的概念回顾 字符是一个有序类型,字符的大小顺序按其ASC代码的大小而定。函数succ、pred、ord适用于字符类型。例如：后继函数：succ(a)=b前继函数：pred

2、（B）=A序号函数：ord（A）=65 字符函数：chr(65)=A 注意：AZ的ASCII码是连续的；az的ASCII码是连续的；,字符型数据可以是字母、符号、数字(0-9)等ASCII码的所有字符。Pascal支持扩展ASCII码，共包括256个字符。但非印刷字符是不能在标准显示上显示或打印输出。在计算机内部，字符集的元素是以该元素在字符集内的顺序位置来标记的，位置取值范围为0255，我们称这些整数为字符在字符集内的序数值或序号。每个字符型数据在内存中占一个字节。将字符用单引号括起来，即成字符常数，如，X，7，?。字符常数可按字符的序数值确定大小关系，也就是说它们的大小由它们所对应的ASC

3、II码值决定，如：Aa。由于采用ASCII码，字符依ASCII码序号排列。这样，字符与ASCII码序号有一一对应的映射关系。,ord(1=1)=1 trueord(1=5)=0 false,Ord（X）函数返回顺序（离散）类型的序号整型、字符型、布尔型、子界型、枚举型整型返回本身字符型返回对应的ASCII(美国国家标准交换码)序数值布尔型假为0、真为1最后两种返回自变量在集中的序号,0-48A-65a-97,将数字8转换为一个字符“8”的表达式为()A.chr(8)B.ord(8)-ord(0)C.chr(8+ord(0)D.chr(ord(8),chr自变量对应的字符 字符型 ord 自变量

4、对应的序号longint 例：chr(66)=Bord(A)=65,Ord(8)8，正确的是：Ord(8)=Ord(0)+8=48+8=56若ch是数字字符，则Ord(ch)-Ord(0)是该数字字符的数值。例如：Ord(8)-Ord(0)=8,题一,对于字符，就是对应的字符与序号之间的关系,例题一,将任一大写字母,转换成小写字母。,【问题分析】假设变量是x为一大写字母,我们仔细观察ASCII码表发现小写字母与大写字母之间的差为一定值，因同一个字母的大写和小写ASC码相差32，因此，我们只要将大写字母的ASCII值加上小写与大写字母之差，即可得到该字母的小写字母的ASCII值：chr（ord（

5、x）+32）,Program p6;Var x,y:char;begin readln(x);y:=chr（ord（x）+32）；writeln（y）;end.,题二 按字母表顺序和逆序每隔一个字母打印。即打印出：a c e g I k m o q s u w yz x r v t p n l j h f d b,程序如下：program ex8_1;var ch:char;beginfor ch:=a to z doif(ord(ch)-ord(a)mod 2=0 then write(ch:3);writeln;for ch:=z downto a doif(ord(ch)-ord(z)m

6、od 2=0 then write(ch:3);writeln;end.分析：程序中，我们利用了字符类型是顺序类型这一特性，直接将字符类型变量作为循环变量，使程序处理起来比较直观。,题三：输入一串字符，字符个数不超过100，且以“.”结束。判断它们是否构成回文。分析：回文指从左到右和从右到左读一串字符的值是一样的，如12321,ABCBA,AA等。先读入要判断的一串字符,放入数组中，并记住这串字符的长度，然后首尾字符比较，并不断向中间靠拢，就可判断出是否为回文。var letter:array1.100of char;i,j:0.100;ch:char;begin read(ch);i:=0;

7、while ch.do 读入一个字符串以.号结束 begini:=i+1;letteri:=ch;read(ch)end;j:=1;while(j=ithen writeln(Yes.)else writeln(No.);end.,abcdfdcba,abcddcba,j,i,j,i,字符串处理,串（即字符串）是一种特殊的线性表，它的数据元素由字符组成，计算机非数值处理的对象经常是字符串数据.串是由零个或多个字符组成的有穷序列.,字符串的定义,字符串是由字符组成的有穷序列。一个字符串中的字符可以通过其对应的下标灵活使用。字符串类型定义：type=stringn;var字符串变量:字符串类型标识

8、符;其中:n是定义的字符串长度,必须是0255之间的自然整数,第0号单元中存放串的实际长度,程序运行时由系统自动提供,第1n号单元中存放串的字符。若将stringn写成string，则默认n值为255。如：typeman=string8；var name：man；字符串的输入和输出：read(name),write(name);,一般我们可直接定义为Var Name:string;,字符串的操作,（一）字符串的运算和比较 由字符串的常量、变量和运算符组成的表达式称为字符串表达式。字符串运算符包括：1+：连接运算符例如：Free+PASCAL的结果是Free PASCAL。若连接的结果字符串长度

9、超过255，则被截成255个字符。若连接后的字符串存放在定义的字符串变量中，当其长度超过定义的字符串长度时，超过部份字符串被截断。例如：varstr1，str2，str3：string8；beginstr1：=Free；str2：=PASCAL；str3：=str1+str2；end则str3的值为：Free PAS。,2、关系运算符,=、=、=：关系运算符两个字符串的比较规则为，从左到右按照ASC码值逐个比较，遇到ASC码不等时,规定ASC码值大的字符所在的字符串为大。例如：ABAC 结果为真；122 结果为真；PASCAL=PASCAL 结果为假；,串的存储,串的存储方法与线性表的一般存储

10、方法类似。不同点在于：因为串的每个结点只含一个字符，若要提高存储密度(即存储结点中数据域占用的存储量与整个存储结点用的存储量之比)，则需作出特殊的考虑。串的常见存储结构在顺序存储、链接存储和索引存储。,串的顺序存储串的顺序存储结构有时称为顺序串。在顺序串中，串中的字符被依次存放在一组连续的存储单元里。一般的来说，一个字节(8位二进制)可以表示一个字符(即该字符的ASCII码)。因此，一个内存单元可以存储多个字符。例如，一个32位的内存单元可以存储4个字符(即4个字符的ASCII码)。因此，串的顺序存储有两种方法：一种是每个单元只存一个字符，这称为非紧缩格式。另一种是每个单元存放多个字符，这称为

11、紧缩格式。,在字节编址和非紧缩格式的字编址下，顺序串的类型定义与顺序表类似，可用含字符数组的记录描述：const maxlen=串的最大长度；type string=recordch:array1.maxlen of char;curlen:0.maxlenend;,在紧缩格式的字编址方式的类型定义可借助于紧缩数组，即只需将上述定义的ch域改为：ch:packed array 1.maxlen of char;,容易看出，紧缩格式的存储密度高，节省存贮空间，但对串的单个字符操作不够方便。而非紧缩格式存储密度低，但操作比较方便。,串的链接存储串的链式储结构有时称为链串。链串的组织式与一般的链表类

12、似。主要的区别在于，链串中的一个存储点可以存储多个字符。通常将链串中每个存储结点所存储的字符个数称为结点大小。当结点大小大于1(例如4)时，链串的最后一个结点的各个数据域不一定总能全被字符占满。此时，应在这些未占用的数据域里补上不属于字符集的特殊符号(例如#)，以示区别。链串的类型定义为：const nodesize=用户定义的结点大小；type pointer=node;node=recordch:arry1.nodesize of char;next:pointerend;strlist=pointer;当结点大小为1时，可将ch域简单地定义为：ch:char;链串结点大小的选择与顺序串的

13、格式选择类似。结点大小为1时存储密度低但操作方便而结点大小大于1时存储密度高但操作不方便。,串的存储结构 1.静态存储结构 数组 s:array 1.maxsize of char;紧缩数组:s:packed array 1.maxlen of char;2.动态存储结构 const chunksize=chunk;chunk=record ch:array q.chunksize of char;next:pointer;end;3.堆结构每次从自由空间中动态分配一块内存给串，并建立空间的起始地址,阅读理解：看程序写答案,program program2;var i,j:integer;st

14、r1,str2:string;begin str1:=pig-is-stupid;str2:=clever;str11:=d;str12:=o;i:=8;for j:=1 to 6 do begin str1i:=str2j;inc(i);end;writeln(str1);end.,注意：INC（N）自增，DEC（N）自减,str1,pig-is-stupid,str2,clever,dig-is-stupid,dog-is-clever,dog-is-stupid,阅读理解：看程序写答案,program program2;var str:string;i:integer;begin str

15、:=Today-is-terrible!;for i:=7 to 11 do if stri=-then stri-1:=x;for i:=13 downto 1 do if stri=t then stri+1:=e;writeln(str)end.输出：_,字符串的函数和过程,Pascal提供了八个标准函数和标准过程，见下表，利用这些标准函数与标准过程，一些涉及到字符串的问题可以灵活解决。,例1：找出所有的四位回文数：（回文数就是一个数从左往右读与从右往左读都是同一个数）,或者用如下程序：var n:integer;s,t:string;Begin for n:=10 to 99 do b

16、egin str(n,s);t:=s+s2+s1;write(s:6);end;end.,var s:string4;n:integer;Begin for n:=1000 to 9999 do Begin str(n,s);if(s1=s4)and(s2=s3)then write(n:6);end;end.,字符串的输入与输出,例2 输入两串字母，并按字典顺序将其输出。,var str1,str2:string;begin readln(str1);readln(str2);if str1str2 then begin writeln(str1);writeln(str2);end els

17、e begin writeln(str2);writeln(str1);end;end.,例3、对输入的一句子实现查找且置换的功能。分析:程序中,输入要查找的字符串及要置换的字符串,充分用上了字符串处理的标准过程delete、insert及标准函数pos。,程序如下:program ex3;var s1,s,o:string;i:integer;beginwrite(The text:);readln(s1);write(Find:);readln(s);write(Replace:);readln(o);i:=pos(s,s1);while i0 do begin delete(s1,i,l

18、ength(s);insert(o,s1,i);i:=pos(s,s1);end;writeln(s1);readln;end.,例4、对给定的10个国家名，按其字母的顺序输出。,program ex4;var i,j,k:integer;t:string20;cname:array1.10 of string20;beginfor i:=1 to 10 do readln(cnamei);for i:=1 to 9 dobegink:=i;for j:=i+1 to 10 doif cnamekcnamej then k:=j;t:=cnamei;cnamei:=cnamek;cnamek:

19、=t;end;for i:=1 to 10 do writeln(cnamei);end.,分析：这是一个选择法排序的应用，程序中，当执行到if cnamekcnamej时，自动将cnamek串与cnamej串中的每一个字符逐个比较，直至遇到不等而决定其大小。这种比较方式是计算机中字符串比较的一般方式。,一轮下来找到最小的字符串的下标，然后再交换而不是找到一个就交换，这样少了很多次的交接过程，让程序执行效率大大提高。,Japan Poland Spain Australia China Chile Denmark Greece India Iran,Cname1,2,3,4,5,6,7,8,9

20、,10,K象一个哨兵一样标识在查找范围内的最小值,例5：有一个四位数它是一个完全平方数千位数和百位数相等，十位数和个位数相等。求这个四位数。,var m,n:integer;st:string4;begin for n=32 to 99 do begin m:=n*n;str(m,st);if(copy(st,1,1)=copy(st,2,1)and(copy(st,3,1)=copy(st,4,1)then writeln(m)end end.,经典运用之“最长公共子字符串”,题目：我们把一个字符串中在两个字符串中找到最长公共子串；例如：由键盘依次输入三个字符串为 What is local

21、 bus?Name some local buses.local bus is a high speed I/O bus close to the processer.则最长公共子串为local bus。题目分析：若存在公共子串，则子串肯定存在在两个字符串st1,st2中,所以1.两个字符串的公共自字符串的长度肯定l=min(length(st1),length(st2);2.因为我们要求最长公共子串，所以我们可以先设子串=st1(较短)，然后利用pos函数在st2中查找子串pos(st,st2),如果我们找到了则既为所求。否则我们将尝试长度为l:=l-1的st1的子字符串（利用函数str:=

22、copy(st1,1,l),copy(st1,2,l)直到找到为止。,program search(input,output);var str1,str2,str:string;l1,l2,q,a,:integer;flag:boolean;布尔形变量它的值只有true，falsebegin flag:=false;标识有没有找到最大公共子字符串 readln(str1);readln(str2);输入两个字符串 l1:=length(str1);l2:=length(str2);用length函数求两个字符串的长度 if l1l2 then begin str:=str2;str2:=str

23、1;str1:=str end;);将较短的字符串-str1,较长的字符串-str2 q:=length(str1）；for a:=q downto 1 do公共子字符串的长度依次减少 for b:=1 to q do 起始位置1-q begin str:=copy(str1,b,a);取长度为a,第b个位置开始的字符串为假定的公共子字符串 if pos(str,str2)0 then用pos函数来找str2中有没有此字符串 begin write(str);flag:=true;exit;end如果有既为所求，输出，退出循环 end;if flag=false then writeln(no

24、 match);如果始终没有找到，则输出没有end.,输入两个整数 x、y（0 x,y10100），输出它们的和,var x,y:array0.100 of integer;高精度计算 st1,st2:string;i,j,sw1,sw2:integer;begin write(input x:);readln(st1);x,y作为字符串读入 write(input y:);readln(st2);sw1:=length(st1);sw2:=length(st2);记录数组x,y的位数 fillchar(x,sizeof(x),0);fillchar(y,sizeof(y),0);数组x,y的

25、元素赋0 for i:=sw1 downto 1 do 将st1反向存入数组x中 xsw1-i:=ord(st1i)-ord(0);第一次循环 xsw1-i为x0,存放个位数 for i:=sw2 downto 1 do 将st2反向存入数组y中 ysw2-i:=ord(st2i)-ord(0);if sw1sw2 then sw1:=sw2;置sw1为加法时的最大位 for i:=0 to sw1 do begin xi:=xi+yi;xi+1:=xi+1+xi div 10;进位 xi:=xi mod 10 end;write(st1,+,st2,=);j:=100;while xj=0

26、do j:=j-1;找到第一个有效数位 writelnend.,input x:123456789,练习一：巧破奇案：三位学生走在马路上，发现一辆汽车违反交通规则肇事后逃走了。他们没记下汽车的号码，不过每个人都注意到这是个四位数。甲记得这个号码的前两位数字相同，乙记得这个号码的后两位数字相同，丙记得整个整个四位数恰好是完全平方数。根据这些条件编程确定汽车牌照号码。【问题分析】从32到99这些数的平方数都是四位，我们可以一个数一个数地试，看其平方数的前两位和后两位是否相同。如是，则打印这四位数。在处理平方数时，将数值转换成字符串再进行进一步的处理比较方便，省去了分离数字的步骤。,Program

27、pavar i,n:integer;s:string4;begin for i:=32 to 99 do begin n：=i*i 计算平方数str（n，s）；将数值转换成字符串 if s1=s2 判断前两位数字是否相同 then if s3=s4 then writeln（car number：，s）；end；end.,练习二：电文加密：在密码的发展史上，有过一中“文字替换法密码”。早在古罗马，凯撒大帝就使用过它。凯撒用每个字母换成它后面的第三个字母的办法来编制密码，这样处理后，文章像“天书”一样难以读懂。如chinese加密后变成fklqhvh。为了加强保密性，凡是大写字母都用小写字母表示

28、，且用其后第5个字母表示，小写字母用其后第3个字母表示。【问题分析】要将每个字母用它后面的第3个字母替换，可以利用序号函数将字符换算成ASC码，此码加上3，然后再用字符函数将其转换成字符即可。例如：chr（ord（）+3）=f。根据题目要求，大写字母要转换成小写字母，还要用其后的第5个字母表示。因同一个字母的大写和小写ASC码相差32，所以大写字母的ASC码加上32，再加上5，即加上37求出的字母就符合题意了。当相加出来的ASC码的值超过122时，就会取到26个英文字母以外的字符，出现这种情况时，只要将其计算值减去26即可。,program secrect;var s:string;/定义字符

29、串变量 i,j,k:integer;/定义循环变量begin read(s);/读入字符串 for i:=1 to length(s)do/开始处理每个字符 begin if(si=A)and(siz then/如果修改后的字符超过z si:=chr(ord(si)-26);/将该字符减26 end else/开始处理小写字符 begin si:=chr(ord(si)+3);/计算该小写字符后面的第三个字符 if siz then/如果该字符超过z si:=chr(ord(si)-26);/将该字符减去26 end;end;writeln(s);/输出加密后的字符串end.,练习三：数码排序

30、,设有n个正整数，将他们连接成一排，组成一个最大的多位整数.例如：n=3时，3个整数13，312，343，连成的最大整数为：34331213。又如：n=4时，4个整数7，13，4，246连接成的最大整数为7424613。程序输入：N N个数程序输出：连接成的多位数,分析：组成最大的数，顾名思义就是第一位永远都是最大的，即对真个数进行第一位排序，然后第二位将数字先转换为字符串，比较字符串，然后再按字符串大小数排序，再转换为整数，最后输出,program maxnum;var n:integer;a:array1.100of longint;/存放整数 s:array1.100of string;

31、/将整数转换为字符串 stemp:string;/字符串临时变量 ok:integer;/字符串转换为整数错误标志 i,j,k:integer;/循环变量begin read(n);/读入要组合的整数个数 for i:=1 to n do begin read(ai);/读入整数到数组a中 str(ai,si);/将整数转换为字符串保存在s数组中 end;for i:=1 to n-1 do/字符串排序，冒泡处理 for j:=i+1 to n do if sisj then begin stemp:=si;si:=sj;sj:=stemp;end;for i:=1 to n do val(s

32、i,ai,ok);/将处理后的字符串还原成整数 for i:=1 to n do write(ai);/输出这n个数end.,选做：校对输入日期(以标准英语日期,月/日/年)的正确性，若输入正确则以年月日的方式输出。分析：此题的题意很简单，但在程序处理时还需考虑以下几方面的问题。1判定输入的月和日应是位或位的数字，利用串函数 pos，求得分隔符/所在的位置而判定输入的月和日是否为位或位，利用标准过程val判定输入的月和日是否为数字；2判定月和日是否规定的日期范围及输入的年是否正确；3若输入的月是2月份，则还需考虑闰年的情况。,07/21/1994,program change_year;con

33、st max:array1.12 of byte=(31,29,31,30,31,30,31,31,30,31,30,31);var st:string;p,w,y,m,d:integer;procedure err;begin write(Input Error!);readln;halt;end;procedure init(var x:integer);begin p:=pos(/,st);if(p=0)or(p=1)or(p3)then err;val(copy(st,1,p-1),x,w);if w0 then err;delete(st,1,p);end;begin write(T

34、he Date is:);readln(st);init(m);init(d);val(st,y,w);if not(length(st)4)or(w0)or(m12)or(dmaxm)then err;if(m=2)and(d=29)then if y mod 100=0 then begin if y mod 4000 then err;end else if y mod 40 then err;write(Date:,y,.,m,.,d);readln;end.,模式匹配,串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，在主串s中找到等于子串t的过程称为模式匹配，如果在

35、s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回-1。t也称为模式。为了运算方便，设字符串的长度存放在0号单元，串值从1号单元存放，这样字符序号与存储位置一致。(Pascal语言pos()函数返回的是首位置或0),例如：设主串s=ababcabcacbab，模式t=abcac,此算法太难，下次讲课给大家详细讲解，此部分可以略过不看，直接做后面练习题,模式匹配,基本思想：从主串 s 的第一个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后序字符，否则从主串的第二个字符起再重新和模式的字符比较之。依次类推，直至模式 t 中的每个字符依次

36、和主串s 中的一个连续字符序列相等，则称匹配成功，否则匹配不成功。这种算法也叫BF算法。,BF算法,function bf(p,s:string):integer;求模式串 t 在主串 s 中的位置的定位函数 var i,j:integer begin i:=1;j:=1 指针初始化 WHILE(i length(p)THEN bf:=i length(p)else bf:=0;END;end;,KMP(Knuth-Morris-Pratt)算法,KMP的基本原理,由(1)可知,pj-k+1pj-k+2pj-1=s i-k+1si-k+2si-1-(1)由(2)可知,p1p2pk-1=s i-

37、k+1si-k+2si-1-(2)所以有 p1p2pk-1=pj-k+1pj-k+2pj-1-(3),怎样求K,KMP示例,KMP算法框架,function KMP(p,t:string):integer;var i,j:integer;begin i:=1;j:=1 指针初始化 WHILE(i length(p)THEN kmp:=i length(p);ELSE kmp:=0;END;end;,怎样求nextj?,首先有,next1=0,设nextj=k,表明:p1p2pk-1=pj-k+1pj-k+2pj-1(1)若pk=pj,则在模式串中有,p1p2pk=pj-k+1pj-k+2pj

38、所以,nextj+1=k+1(2)若pk pj,则杂模式串中有 p1p2pk pj-k+1pj-k+2pj 则可将求next函数的问题看成整个模式串既是主串又是模式串的问题,应将模式串滑动到nextk个字符和主串的第j个字符相比较.若nextk=k,且pj=pk,则说明在主串中第j+1个字符之前存在一个长度为k的最长子串,和模式串中从首字符起长度为k的子串相等,即 p1p2pk pj-k+1pj-k+2pj也就是说nextj+1=k+1=nextk+1,求NEXT算法,program get_next(t:string);next为全程变量 var i,j:integer;beginj:=1;

39、k:=0;next1:=0;While jlength(p)do if(k=0)or(pj=pk)then begin j:=j+1;k:=k+1;nextj:=k;end;else k:=nextkEND;,该算法的时间复杂度仅为O(length(p),上面算法的时间复杂度是O(m)，所以KMP算法的时间复杂度是O(n*m)，但在一般情况下，实际的执行时间是O(n+m)。当然KMP算法和简单的模式匹配算法相比，增加了很大难度，我们主要学习该算法的设计技巧，在以后设计有关匹配程序时可用上此技巧。,串应用例子,练习一判断题1线性表的逻辑顺序与存储顺序总是一致的。2顺序存储的线性表可以按序号随机存

40、取。3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。6在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7线性表的链式存储结构优于顺序存储结构。8在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。9线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存

41、取的存储结构。,二 单选题(请从下列A，B，C，D选项中选择一项)1线性表是()。(A)一个有限序列，可以为空；(B)一个有限序列，不能为空；(C)一个无限序列，可以为空；(D)一个无序序列，不能为空。2对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。(A)n/2(B)n+1/2(C)n-1/2(D)n 3线性表采用链式存储时，其地址()。(A)必须是连续的；(B)部分地址必须是连续的；(C)一定是不连续的；(D)连续与否均可以。4用链表表示线性表的优点是（）。(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和

42、删除(D)数据元素的物理顺序与逻辑顺序相同5 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用()存储方式最节省运算时间。(A)单链表(B)双链表(C)单循环链表(D)带头结点的双循环链表6 循环链表的主要优点是()。(A)不在需要头指针了(B)已知某个结点的位置后，能够容易找到他的直接前趋(C)在进行插入、删除运算时，能更好的保证链表不断开(D)从表中的任意结点出发都能扫描到整个链表7 下面关于线性表的叙述错误的是()。(A)线性表采用顺序存储，必须占用一片地址连续的单元；(B)线性表采用顺序存储，便于进行插入和删除操作；(C)线性表采用链式存储，不必占用一片地

43、址连续的单元；(D)线性表采用链式存储，不便于进行插入和删除操作；,8.单链表中，增加一个头结点的目的是为了（）。(A)使单链表至少有一个结点(B)标识表结点中首结点的位置(C)方便运算的实现(D)说明单链表是线性表的链式存储9 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。(A)单链表(B)仅有头指针的单循环链表(C)双链表(D)仅有尾指针的单循环链表10 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间（）。(A)单链表(B)顺序表(C)双链表(D)单循环链表,作业：,作业要求：1

44、.在星期五之前完成2.每道题的源程序保存为如下的名字3.将五道程序压缩后发送到邮箱中,第一题：jsf.pas第二题：fruit.pas第三题：fract.pas第四题：numcon.pas第五题：count.pas,一、约瑟夫的新问题（jsf.pas）问题描述：将1M这M个自然数按由小到大的顺序沿顺时针方向围成一圈，以S为起点，先沿顺时针方向数到第N个数就出圈，然后再沿逆时针方向数到第K个数出圈，再沿顺时针方向数到第N个数就出圈，然后再沿逆时针方向数到第K个数再出圈。这样按顺时针方向和逆时针方向不断出圈，直到全部数都出圈为止。请输出先后出圈的数的序列。输入格式：文件共4行，每行为一个自然数，分

45、别表示M，S，N，K。（M不超过1000）。输出格式：仅一行，先后出圈的数的序列，每个数之间有1个空格。样例输入：(jsf.in)8132样例输出：(jsf.out)3 1 5 2 7 4 6 8（解释：先从1开始没顺时针方向数到3，所以3先出圈；再从2开始没逆时针方向数到1所以1出圈；再从2开始没顺时针方向数到5，所以5出圈，再从4开始沿逆时针方向数到2，所以2出圈，）,二、合并果子(fruit.pas、noip2004tg2)【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消

46、耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

47、【输入文件】输入文件fruit.in包括两行，第一行是一个整数n（1=n=30000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1=ai=20000）是第i种果子的数目。【输出文件】输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。【样例输入】31 2 9【样例输出】15【数据规模】对于30%的数据，保证有n=100；对于50%的数据，保证有n=5000；对于全部的数据，保证有n=30000。【要求与提示】,三、第M个分数（fract.pas）【问题描述】分数是分子除以分母的一种数，一般描述为a/b，其中a

48、、b都是整数且b不等于0，a为分子、b为分母等于0，如果a和b最大公约数为1，则称这个分数为最简分数。考虑0到1之间所有分母不大于N的最简分数，如N=5时有如下的11个：0/1，1/5，1/4，1/3，2/5，1/2，3/5，2/3，3/4，4/5，1/1这几个分数已根据由小到大的顺序排列好了，其中第5个分数为2/5。现要求你根据输入的N（1N10000），将符合条件的最简分数根据由小到大的顺序排列好，输出其中第M个分数。【输入文件】输入文件fract.in包括两行，第一行是一个整数n（1 n 10000）表示分母允许的最大值，第二行是一个整数M（1=M3*107），是要求的第M个。【输出文件

49、】输出文件fract.out包括一行，这一行只包含一个分数。【样例输入】55【样例输出】2/5,四、数字合并（numcon.pas）【问题描述】设有n个正整数(n=200)，将它们联接成一排，组成一个最大的多位整数。【输入文件】输入文件numcon.in，第一行是一个整数n（1 n 201），接下来n行每行是一个整数。【输出文件】输出文件numcon.out包括一行，是联成的最大整数。【样例输入】313131343【样例输出】34313131,五、统计不同单词个数(count.pas)问题描述：输入一行英文句子，句子中只有英文单词和空格。每个单词之间由若干个空格隔开，英文单词由大小写字母组成，

50、统计此句子中的单词个数。假定重复出现的单词只计一次，且认为大小写字母是相同的，如The和the是同一个单词。【输入文件】输入文件count.in由若干个单词和空格组成，每个单词不超过200个，单词个数不超过210个。【输出文件】输出文件count.out是一个整数，是单词的个数【输入样例】If you get a good idea it will not work unless you work at it【输出样例】12算法思路：对于输入的一行英文句子，首先要根据空格进行划分成一个一个的单词，为了方便单词个数的统计，如果是大写字母则统一转成小写字母。统计个数有两种思路，一是直接的思路，即先