计算机上的非数值处理的对象基本上都是字符串数据

《计算机上的非数值处理的对象基本上都是字符串数据》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章串7/22/2021计算机上的非数值处理的对象基本上都是字符串数据。例：学生管理系统中，学生学号、姓名、性别、院系等；图书管理系统中，图书编号、书名、作者、简介等；7/22/2021字符串常量字符串变量+一系列字符串操作=一种新的数据类型—串类型由于硬件结构的特点，决定了处理字符串数据时要比数值数据复杂的多。(1)字符串是由一个个字符组成的，需要对每个字符分别处理(2)字符串需要先转化为数值后再进行处理ASC(‘A’)ASC(‘a’)=65=977/22/20214.1串类型的定义1.基本概念串:由零个或多个

2、字符组成的有限序列。s=‘a1a2an’(n≥0)…s—串名a1a2an—串值…

3、s

4、—串的长度，即串中字符的数目。零个字符的串称为空串，计作φ=‘’。

5、φ

6、=0ai为字符7/22/2021串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。例，串‘eij’是串‘beijing’的子串，‘beijing’称为主串。字符在序列中的序号称为该字符在串中的位置。子串在主串中的位置定义为子串的第一个字符在主串中的位置。例，字符‘n’在串‘beijing’中的位置为6。例，子串‘eij’在串‘beij

7、ing’中的位置为。27/22/2021两个串相等，当且仅当这两个串的值相等。例，串‘beijing’与串‘beijing’不相等。串值必须用一对单引号括起来，但单引号本身不属于串，只起界定作用。由一个或多个空格组成的串称为空格串。‘’‘’φ≠7/22/2021串的基本操作和线性表区别很大。线性表:大多以“单个元素”为操作对象串:通常以“串的整体”为操作对象例:查找某个元素；插入某个元素；删除某个元素例:查找某个子串；截取某个子串；在某个位置插入、删除某个子串串的逻辑结构和线性表相似，故看作一种线性表。s=‘a1a

8、2an’(n≥0)…7/22/20212.串的抽象数据类型的定义ClearString(&S)结果:将S清为空串。条件:串S已存在。数据对象:D={ai

9、ai∈CharacterSet，i=1,2,…,n}数据关系:R1={}基本操作:ADTString{DestroyString(&S)结果:销毁串S。条件:串S已存在。StrAssign(&T，chars)结果:生成一个其值等于chars的串T。条件:chars是字符串常量。7/22/2021StrEmpty(S)StrCopy(&T，S)St

10、rCompare(S，T)StrLength(S)Concat(&T，S1，S2)SubString(&Sub，S，pos，len)Index(S，T)Replace(&S，T，V)StrInsert(&S，pos，T)StrDelete(&S，pos，len)‘xyz’,‘xyzz’‘xyz’,‘xyzf’‘Abc’,‘abc’}ADTString7/22/2021StrAssign，StrCompare，StrLength，Concat，SubString五种操作构成串类型的最小操作子集。例，利用判等、求串长和

11、求子串实现子串定位Index。Index(StringS，StringT)//S为原串，T为目标串思想:nmmmm123456nn-m+1m7/22/2021n=StrLength(S)；m=StrLength(T)；i=pos；SubString(sub，S，i，m)；//截取子串if(StrCompare(sub，T)!=0)++i；//比较elsereturni；while(i<=n–m+1){}if(pos>0){}return0；intIndex(StringS，StringT，intpos){}7/22

12、/20214.2串的表示和实现定长顺序存储表示——顺序存储堆分配存储表示——顺序存储块链存储表示——链式存储7/22/20214.2.1定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列；按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。012255串的实际长度可在此预定义长度内随意，但超过预定义长度的串值则被舍去，称之为“截断”。7/22/2021串有两种表示方法:下标0的分量存放串的长度，其它存放串字符。在串值后面加一个不计入串长的结束标记字符。C语言中以“”表示串值的终结#define

13、MAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1]0122557/22/2021算法4.2串联接Concat(&T，S1，S2)要求:顺序联接串S1和串S2得到新串T。思想:基于串S1和S2长度的不同情况，串T可能出现3种情况:若S1[0]+S2[0]≤MAXSTRLEN，若S1[0]+S2[0]＞MAXS