PASCAL数据结构之串.ppt
《PASCAL数据结构之串.ppt》由会员分享,可在线阅读,更多相关《PASCAL数据结构之串.ppt(62页珍藏版)》请在三一文库上搜索。
1、串,濮阳市第一高级中学 王晓斌 2011.10.05,字符变量定义 Var x:char; 字符类型是一个有序类型,字符的大小顺序按ASCII码的大小决定。相关的函数有succ、pred、ord、chr,字符,Ord(x) 对于字符来说是求字符对应的序号就是ascii码 Chr(x)求ascii码对应字符,ASCII 编码是由美国国家标准委员会制定的一种包括数字、字母、通用符号和控制符号在内的字符编码集,全称叫美国国家信息交换标准代码,回顾知识点,字符类型的概念回顾 字符是一个有序类型, 字符的大小顺序按其ASC代码的大小而定。函数succ、pred、ord适用于字符类型。 例如:后继函数:s
2、ucc(a)=b 前继函数:pred(B)=A 序号函数:ord(A)=65 字符函数:chr(65)=A 注意:AZ的ASCII码是连续的; az的ASCII码是连续的;,字符型数据可以是字母、符号、数字(0-9)等ASCII码的所有字符。 Pascal支持扩展ASCII码,共包括256个字符。但非印刷字符是不能在标准显示上显示或打印输出。 在计算机内部,字符集的元素是以该元素在字符集内的顺序位置来标记的,位置取值范围为0255,我们称这些整数为字符在字符集内的序数值或序号。每个字符型数据在内存中占一个字节。 将字符用单引号括起来,即成字符常数,如,X,7,?。字符常数可按字符的序数值确定大
3、小关系,也就是说它们的大小由它们所对应的ASCII码值决定,如:Aa。 由于采用ASCII码,字符依ASCII码序号排列。这样,字符与ASCII码序号有一一对应的映射关系。,ord(1=1)=1 true ord(1=5)=0 false,Ord(X)函数返回顺序(离散)类型的序号 整型、字符型、布尔型、子界型、枚举型 整型返回本身 字符型返回对应的ASCII (美国国家标准交换码) 序数值 布尔型假为0、真为1 最后两种返回自变量在集中的序号,0-48 A-65 a-97,将数字8转换为一个字符“8”的表达式为( ) A. chr(8) B. ord(8)-ord(0) C. chr(8+o
4、rd(0) D.chr(ord(8),chr 自变量对应的字符 字符型 ord 自变量对应的序号 longint 例:chr(66)=B ord(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,因此,我们
5、只要将大写字母的ASCII值加上小写与大写字母之差,即可得到该字母的小写字母的ASCII值:chr(ord(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 y z x r v t p n l j h f d b,程序如下: program ex8_1; var ch:char; begin for ch:=a to z do if (ord(ch)-ord(a)mod
6、2=0 then write(ch:3); writeln; for ch:=z downto a do if (ord(ch)-ord(z)mod 2 =0 then write(ch:3); writeln; end. 分析:程序中,我们利用了字符类型是顺序类型这一特性,直接将字符类型变量作为循环变量,使程序处理起来比较直观。,题三:输入一串字符,字符个数不超过100,且以“.”结束。 判断它们是否构成回文。 分析:回文指从左到右和从右到左读一串字符的值是一样的, 如12321,ABCBA,AA等。先读入要判断的一串字符,放入数组中, 并记住这串字符的长度,然后首尾字符比较,并不断向中间靠
7、拢,就可判断出是否为回文。 var letter:array1100of char; i,j:0100; ch:char; begin read(ch); i:=0; while ch. do 读入一个字符串以.号结束 begin i:=i+1; letteri:=ch; read(ch) end; j:=1; while (j=i then writeln(Yes.) else writeln(No.); end.,abcdfdcba,abcddcba,j,i,j,i,字符串处理,串(即字符串)是一种特殊的线性表,它的数据元素由字符组成,计算机非数值处理的对象经常是字符串数据.串是由零个或多
8、个字符组成的有穷序列.,字符串的定义,字符串是由字符组成的有穷序列。一个字符串中的字符可以通过其对应的下标灵活使用。 字符串类型定义: type =stringn; var 字符串变量: 字符串类型标识符; 其中:n是定义的字符串长度,必须是0255之间的自然整数,第0号单元中存放串的实际长度,程序运行时由系统自动提供,第1n号单元中存放串的字符。若将stringn写成string,则默认n值为255。 如:type man=string8; var name:man; 字符串的输入和输出:read(name),write(name);,一般我们可直接定义为 Var Name:string;,
9、字符串的操作,(一)字符串的运算和比较 由字符串的常量、变量和运算符组成的表达式称为字符串表达式。 字符串运算符包括: 1+:连接运算符 例如:Free +PASCAL的结果是Free PASCAL。 若连接的结果字符串长度超过255,则被截成255个字符。若连接后的字符串存放在定义的字符串变量中,当其长度超过定义的字符串长度时,超过部份字符串被截断。 例如:var str1,str2,str3:string8; begin str1:=Free ; str2:=PASCAL; str3:=str1+str2; end 则str3的值为:Free PAS。,2、关系运算符,=、=、=:关系运算
10、符 两个字符串的比较规则为,从左到右按照ASC码值逐个比较,遇到ASC码不等时,规定ASC码值大的字符所在的字符串为大。 例如:ABAC 结果为真; 122 结果为真; PASCAL =PASCAL 结果为假;,串的存储,串的存储方法与线性表的一般存储方法类似。不同点在于:因为串的每个结点只含一个字符,若要提高存储密度(即存储结点中数据域占用的存储量与整个存储结点用的存储量之比),则需作出特殊的考虑。串的常见存储结构在顺序存储、链接存储和索引存储。,串的顺序存储 串的顺序存储结构有时称为顺序串。在顺序串中,串中的字符被依次存放在一组连续的存储单元里。一般的来说,一个字节(8位二进制)可以表示一
11、个字符(即该字符的ASCII码)。因此,一个内存单元可以存储多个字符。例如,一个32位的内存单元可以存储4个字符(即4个字符的ASCII码)。因此,串的顺序存储有两种方法:一种是每个单元只存一个字符,这称为非紧缩格式。另一种是每个单元存放多个字符,这称为紧缩格式。,在字节编址和非紧缩格式的字编址下,顺序串的类型定义与顺序表类似,可用含字符数组的记录描述: const maxlen=串的最大长度; type string=record ch: array1maxlen of char; curlen: 0maxlen end;,在紧缩格式的字编址方式的类型定义可借助于紧缩数组,即只需将上述定义的
12、ch域改为:ch: packed array 1maxlen of char;,容易看出,紧缩格式的存储密度高,节省存贮空间,但对串的单个字符操作不够方便。而非紧缩格式存储密度低,但操作比较方便。,串的链接存储 串的链式储结构有时称为链串。链串的组织式与一般的链表类似。主要的区别在于,链串中的一个存储点可以存储多个字符。通常将链串中每个存储结点所存储的字符个数称为结点大小。 当结点大小大于1(例如4)时,链串的最后一个结点的各个数据域不一定总能全被字符占满。此时,应在这些未占用的数据域里补上不属于字符集的特殊符号(例如#),以示区别。 链串的类型定义为: const nodesize=用户定义
13、的结点大小; type pointer= node; node=record ch:arry1nodesize of char; next:pointer end; strlist=pointer; 当结点大小为1时,可将ch域简单地定义为:ch:char; 链串结点大小的选择与顺序串的格式选择类似。结点大小为1时存储密度低但操作方便而结点大小大于1时存储密度高但操作不方便。,串的存储结构 1.静态存储结构 数组 s: array 1maxsize of char; 紧缩数组: s:packed array 1maxlen of char; 2.动态存储结构 const chunksize=c
14、hunk; chunk=record ch:array qchunksize of char; next : pointer; end; 3.堆结构 每次从自由空间中动态分配一块内存给串,并建立空间的起始地址,阅读理解:看程序写答案,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);
15、 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 := 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; wr
16、iteln(str) end. 输出:_,字符串的函数和过程,Pascal提供了八个标准函数和标准过程,见下表,利用这些标准函数与标准过程,一些涉及到字符串的问题可以灵活解决。,例1:找出所有的四位回文数: (回文数就是一个数从左往右读与从右往左读都是同一个数),或者用如下程序: var n:integer; s,t:string; Begin for n:=10 to 99 do begin str(n,s); t:=s+s2+s1;write(s:6); end; end.,var s:string4; n:integer; Begin for n:=1000 to 9999 do Beg
17、in 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 else begin writeln(str2); writeln(str1); end; end .,例3、 对输入的一句子实现查找且置换的功能。 分析:程序中,输入要查找的字符串及
18、要置换的字符串,充分用上了字符串处理的标准过程delete、insert及标准函数pos。,程序如下: program ex3; var s1,s,o:string; i:integer; begin write(The text:);readln(s1); write(Find:);readln(s); write(Replace:);readln(o); i:=pos(s,s1); while i0 do begin delete(s1,i,length(s); insert(o,s1,i); i:=pos(s,s1); end; writeln(s1); readln; end.,例4、
19、对给定的10个国家名,按其字母的顺序输出。,program ex4; var i,j,k:integer; t:string20; cname:array110 of string20; begin for i:=1 to 10 do readln(cnamei); for i:=1 to 9 do begin k:=i; for j:=i+1 to 10 do if cnamekcnamej then k:=j; t:=cnamei;cnamei:=cnamek;cnamek:=t; end; for i:=1 to 10 do writeln(cnamei); end.,分析:这是一个选择
20、法排序的应用,程序中,当执行到if cnamekcnamej时,自动将cnamek串与cnamej串中的每一个字符逐个比较,直至遇到不等而决定其大小。这种比较方式是计算机中字符串比较的一般方式。,一轮下来找到最小的字符串的下标,然后再交换而不是找到一个就交换,这样少了很多次的交接过程,让程序执行效率大大提高。,Japan Poland Spain Australia China Chile Denmark Greece India Iran,Cname1,2,3,4,5,6,7,8,9,10,K象一个哨兵一样标识在查找范围内的最小值,例5:有一个四位数它是一个完全平方数千位数和百位数相等,十位
21、数和个位数相等。求这个四位数。,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 bus? Name some local buses. local bus is a h
22、igh 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:=copy(st1,1,l), copy(st1,2,l)直到找到为止。,
23、program search(input,output); var str1,str2,str:string; l1,l2,q,a,:integer; flag:boolean;布尔形变量它的值只有true,false begin flag:=false;标识有没有找到最大公共子字符串 readln(str1); readln(str2);输入两个字符串 l1:=length(str1); l2:=length(str2);用length函数求两个字符串的长度 if l1l2 then begin str:=str2;str2:=str1;str1:=str end; ); 将较短的字符串-s
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- PASCAL 数据结构
链接地址:https://www.31doc.com/p-2202424.html