ascal数据结构之串

串,濮阳市第一高级中学 王晓斌 2011.10.05,字符变量定义 Var x:char； 字符类型是一个有序类型，字符的大小顺序按ASCII码的大小决定。相关的函数有succ、pred、ord、chr,字符,Ord(x) 对于字符来说是求字符对应的序号就是ascii码 Chr(x)求ascii码对应字符,ASCII 编码是由美国国家标准委员会制定的一种包括数字、字母、通用符号和控制符号在内的字符编码集，全称叫美国国家信息交换标准代码,回顾知识点,字符类型的概念回顾 字符是一个有序类型, 字符的大小顺序按其ASC代码的大小而定。函数succ、pred、ord适用于字符类型。 例如：后继函数：succ('a')='b' 前继函数：pred（'B'）='A' 序号函数：ord（'A'）=65 字符函数：chr(65)=A 注意：AZ的ASCII码是连续的； az的ASCII码是连续的；,字符型数据可以是字母、符号、数字(0-9)等ASCII码的所有字符。 Pascal支持扩展ASCII码，共包括256个字符。但非印刷字符是不能在标准显示上显示或打印输出。 在计算机内部，字符集的元素是以该元素在字符集内的顺序位置来标记的，位置取值范围为0255，我们称这些整数为字符在字符集内的序数值或序号。每个字符型数据在内存中占一个字节。 将字符用单引号括起来，即成字符常数，如，X，7，?。字符常数可按字符的序数值确定大小关系，也就是说它们的大小由它们所对应的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+ord(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，因此，我们只要将大写字母的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 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等。先读入要判断的一串字符,放入数组中， 并记住这串字符的长度，然后首尾字符比较，并不断向中间靠拢，就可判断出是否为回文。 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,字符串处理,串（即字符串）是一种特殊的线性表，它的数据元素由字符组成，计算机非数值处理的对象经常是字符串数据.串是由零个或多个字符组成的有穷序列.,字符串的定义,字符串是由字符组成的有穷序列。一个字符串中的字符可以通过其对应的下标灵活使用。 字符串类型定义： type =stringn; var 字符串变量: 字符串类型标识符; 其中:n是定义的字符串长度,必须是0255之间的自然整数,第0号单元中存放串的实际长度,程序运行时由系统自动提供,第1n号单元中存放串的字符。若将stringn写成string，则默认n值为255。 如：type man=string8； var name：man； 字符串的输入和输出：read(name),write(name);,一般我们可直接定义为 Var Name:string;,字符串的操作,（一）字符串的运算和比较 由字符串的常量、变量和运算符组成的表达式称为字符串表达式。 字符串运算符包括： 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、关系运算符,=、=、=：关系运算符 两个字符串的比较规则为，从左到右按照ASC码值逐个比较，遇到ASC码不等时,规定ASC码值大的字符所在的字符串为大。 例如：'AB''AC' 结果为真； '12''2' 结果为真； 'PASCAL '='PASCAL' 结果为假；,串的存储,串的存储方法与线性表的一般存储方法类似。不同点在于：因为串的每个结点只含一个字符，若要提高存储密度(即存储结点中数据域占用的存储量与整个存储结点用的存储量之比)，则需作出特殊的考虑。串的常见存储结构在顺序存储、链接存储和索引存储。,串的顺序存储 串的顺序存储结构有时称为顺序串。在顺序串中，串中的字符被依次存放在一组连续的存储单元里。一般的来说，一个字节(8位二进制)可以表示一个字符(即该字符的ASCII码)。因此，一个内存单元可以存储多个字符。例如，一个32位的内存单元可以存储4个字符(即4个字符的ASCII码)。因此，串的顺序存储有两种方法：一种是每个单元只存一个字符，这称为非紧缩格式。另一种是每个单元存放多个字符，这称为紧缩格式。,在字节编址和非紧缩格式的字编址下，顺序串的类型定义与顺序表类似，可用含字符数组的记录描述： const maxlen=串的最大长度； type string=record ch: array1maxlen of char; curlen: 0maxlen end;,在紧缩格式的字编址方式的类型定义可借助于紧缩数组，即只需将上述定义的ch域改为：ch: packed array 1maxlen of char;,容易看出，紧缩格式的存储密度高，节省存贮空间，但对串的单个字符操作不够方便。而非紧缩格式存储密度低，但操作比较方便。,串的链接存储 串的链式储结构有时称为链串。链串的组织式与一般的链表类似。主要的区别在于，链串中的一个存储点可以存储多个字符。通常将链串中每个存储结点所存储的字符个数称为结点大小。 当结点大小大于1(例如4)时，链串的最后一个结点的各个数据域不一定总能全被字符占满。此时，应在这些未占用的数据域里补上不属于字符集的特殊符号(例如#)，以示区别。 链串的类型定义为： const nodesize=用户定义的结点大小； 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=chunk; 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); 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' writeln(str) end. 输出：_,字符串的函数和过程,Pascal提供了八个标准函数和标准过程，见下表，利用这些标准函数与标准过程，一些涉及到字符串的问题可以灵活解决。,例1：找出所有的四位回文数： （回文数就是一个数从左往右读与从右往左读都