Pascal字符串的过程.ppt
2023/11/8,信息学竞赛培训 提高班,1,第三-四讲 字符串处理,PASCAL基本教程,2023/11/8,信息学竞赛培训 提高班,2,回顾知识点,字符类型的概念回顾 字符是一个有序类型,字符的大小顺序按其ASC代码的大小而定。函数succ、pred、ord适用于字符类型。例如：后继函数：succ(a)=b前继函数：pred（B）=A序号函数：ord（A）=65 字符函数：chr(65)=A注意：AZ的ASCII码是连续的；az的ASCII码是连续的；,2023/11/8,信息学竞赛培训 提高班,3,例1 按字母表顺序和逆序每隔一个字母打印。即打印出：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 letter:char;beginfor letter:=a to z doif(ord(letter)-ord(a)mod 2=0 then write(letter:3);writeln;for letter:=z downto a doif(ord(letter)-ord(z)mod 2=0 then write(letter:3);writeln;end.分析：程序中，我们利用了字符类型是顺序类型这一特性，直接将字符类型变量作为循环变量，使程序处理起来比较直观。,2023/11/8,信息学竞赛培训 提高班,4,数组类型运用回顾 输入十个正整数,把这十个数按由小到大的顺序排列。（冒泡法排序）下面对5个进行排序，这个五个数分别为829105。按选择排序方法，过程如下：初始数据：829105第一次排序：829105928105102895102895第二次排序：108295109285109285第三次排序：109825109825第四次排序：109852对于十个数，则排序要进行9次，一共要比较N2。,2023/11/8,信息学竞赛培训 提高班,5,源程序如下：program ex5_2;var a:array1.10of integer;i,j,t:integer;beginwriteln(Input 10 integers:);for i:=1 to 10 do read(ai);读入10个初始数据readln;for i:=1 to 9 do进行9次排序beginfor j:=i+1 to 10 do将第i个数与其后所有数比较if aiaj then 若有比ai大,则与之交换begint:=ai;ai:=aj;aj:=t;end;write(ai:5);end;end.,2023/11/8,信息学竞赛培训 提高班,6,一：字符串的定义,字符串是由字符组成的有穷序列。一个字符串中的字符可以通过其对应的下标灵活使用。字符串类型定义：type=stringn;var字符串变量:字符串类型标识符;其中:n是定义的字符串长度,必须是0255之间的自然整数,第0号单元中存放串的实际长度,程序运行时由系统自动提供,第1n号单元中存放串的字符。若将stringn写成string，则默认n值为255。例如：typeman=string8；varname：man；字符串的输入和输出：read(name),write(name);,字符串可以直接输入、输出,2023/11/8,信息学竞赛培训 提高班,7,求输入英文句子单词的平均长度.程序如下:program ex8_2;varch:string;字符串类型 s,count,j:integer;beginwrite(The sentence is:);readln(ch);读入字符串 s:=0;count:=0;j:=0;repeatinc(j);if not(chj in:,;,!,?,.,)then inc(s);if chj in,.,!,?then inc(count);until(j=ord（ch0)or(chj in.,!,?);if chj.then writeln(It is not a sentence.)else writeln(Average length is,s/count:10:4);end.分析:程序中，变量s用于存句子中英文字母的总数，变量count用于存放句子中单词的个数，chj表示ch串中的第j个位置上的字符，ord（ch0）为ch串的串长度。程序充分利用Turbo Pascal允许直接通过字符串下标得到串中的字符这一特点，使程序比较简捷。,CHJ是单词的间隔符,2023/11/8,信息学竞赛培训 提高班,8,二、字符串的操作,（一）字符串的运算和比较 由字符串的常量、变量和运算符组成的表达式称为字符串表达式。字符串运算符包括：1+：连接运算符例如：Turbo+PASCAL的结果是Turbo PASCAL。若连接的结果字符串长度超过255，则被截成255个字符。若连接后的字符串存放在定义的字符串变量中，当其长度超过定义的字符串长度时，超过部份字符串被截断。例如：varstr1，str2，str3：string8；beginstr1：=Turbo；str2：=PASCAL；str3：=str1+str2；end则str3的值为：Turbo PA。,2023/11/8,信息学竞赛培训 提高班,9,2=、=、=：关系运算符两个字符串的比较规则为，从左到右按照ASC码值逐个比较，遇到ASC码不等时,规定ASC码值大的字符所在的字符串为大。例如：ABAC 结果为真；122 结果为真；PASCAL=PASCAL 结果为假；,2023/11/8,信息学竞赛培训 提高班,10,程序欣赏,对给定的10个国家名，按其字母的顺序输出。程序如下：program ex8_3;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:=t;end;for i:=1 to 10 do writeln(cnamei);end.分析：程序中，当执行到if cnamekcnamej时，自动将cnamek串与cnamej串中的每一个字符逐个比较，直至遇到不等而决定其大小。这种比较方式是计算机中字符串比较的一般方式。,2023/11/8,信息学竞赛培训 提高班,11,三、字符串的函数和过程,Turbo Pascal提供了八个标准函数和标准过程，见下表，利用这些标准函数与标准过程，一些涉及到字符串的问题可以灵活解决。,2023/11/8,信息学竞赛培训 提高班,12,经典运用之“最长公共子字符串”,题目：我们把一个字符串中在两个字符串中找到最长公共子串；题目分析：若存在公共子串，则子串肯定存在在两个字符串st1,st2中,所以1.两个字符串的公共自字符串的长度肯定l=min(length(st1),length(st2);2.因为我们要求最长公共子串，所以我们可以先设子串=st1(较短)，然后利用pos函数在st2中查找子串pos(st,st2),如果我们找到了则既为所求。否则我们将尝试长度为l:=l-1的st1的子字符串（利用函数str:=copy(st1,1,l),copy(st1,2,l)直到找到为止。,2023/11/8,信息学竞赛培训 提高班,13,program search(input,output);var str1,str2,str:string;l1,l2,l,a,:integer;flag:boolean;布鲁形变量它的值只有TRUE，FALSEbegin flag:=false;标识有没有找到最大公共子字符串 writeln(please input string1);readln(str1);writeln(please input string2);readln(str2);输入两个字符串 l1:=length(str1);l2:=length(str2);用length函数求两个字符串的长度 if l1l2 then begin str:=str2;str2:=str1;str1:=str end;l:=length(str1);将较短的字符串-str1,较长的字符串-str2,l:=min(l1,l2);for a:=L downto 1 do公共子字符串的长度依次减少 for b:=1 to L do 起始位置1-L begin str:=copy(str1,b,a);取长度为a,第b个位置开始的字符串为假定的公共子字符串 if pos(str,str2)0 then用POS函数来找str2中有没有此字符串 begin write(str1);flag:=true;exit;end如果有既为所求，输出，退出循环 end;if flag=false then writeln(no match);如果始终没有找到，则输出没有 end.,2023/11/8,信息学竞赛培训 提高班,14,看程序写答案,program program2;var i,j:integer;str1,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.,2023/11/8,信息学竞赛培训 提高班,15,思考题,Context 1:统计字符数字【题目】读入一字符串，请输出大写英文字母数、小写英文字母数，和数字字母的数量和其他字符数。例：输入字符串abc$deAD38H 输出：3 5 2 2 context 2:统计单词数【题目】读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。(句子末尾不一定用.结束)【算法分析】要注意连续两个空格或逗号与空格连在一起时的误判断。例如输入以下字符串:“abc_abc_abc,_abc_,_abc_,_.”(_ 代表空格),2023/11/8,信息学竞赛培训 提高班,16,提高思考题,CONTEXT：在键盘中输入两个位数不超过200位的正整数A和B，求A-B的差和和A+B；求N个字符串的最长公共子串，n20,字符串的长度不超过255；例如N=3,由键盘依次输入三个字符串为：What is local bus?Name some local bus?Local bus is high speed I/0 bus close to the processor.则最大公共子字符串是：“local bus”;,2023/11/8,信息学竞赛培训 提高班,17,测试题一,一、拆分整数输入一个正整数N（不超过一百位），如果N是偶数，则拆分N的各个数字相加求和；如果N是奇数，则拆分N的各个数字相乘求积。输入输出样例：输入：输出：H输入：输出：J数据范围：30%的数据在二十位以内；100%的数据在一百位以内,2023/11/8,信息学竞赛培训 提高班,18,测试题二,二、排最大数输入N个正整数，请你将它们连接在一起，排成一个最大的数。例如：N时，如果四个正整数是、，则连接成的最大数为。输入：N（N）输出：连接成的最大数N个正整数（以空格相隔）输入输出样例：输入：输出：数据范围：30%的正整数都在十位以内100%的正整数都在一百位以内,
