[工学]JAVA语言 -串.ppt

内容提要 串是数据元素为字符的线性表，串的定义及操作 串的基本操作，用串的基本操作来编写算法求串的其他操作 串的存储结构。静态存储和动态存储（块链结构、堆结构）存储的优缺点。 模式匹配算法 串的初步认识 串（字符串）被定义为由零个或多个字符组成的有限序列。记为： s = “a1 a2 … an” (n =0) 其中，s是串的名，也称为串变量。引号内的字符序列为串值；ai (1≤i≤n)称为串元素，可以是字母、数字或其它字符。 例如： s1= “Data” s2 = “Structure” s3= “DataStructure” s4= “Data Structure” 基本术语 长度 串中所包含的字符个数n 空串 长度为0的串 子串 串中任意个连续的字符组成的子序列 主串 包含子串的串称为该子串的主串 位置 字符在序列中的序号 子串的位置 子串的第一个字符在主串中的位置 s1=“Data” s2=“Structure” s3=“DataStructure” s4=“Data Structure” 长度分别为4、9、13和14；并且s1和s2都是s3和s4 的子串，s1在s3和s4中的位置都是0，而s2在s3中 的位置是4，在s4中的位置则是5。 主要的基本操作 求子串 substring(s,start,len) 返回值为串s中第start个字符起，长度为len的字符序列 插入 insert(s,pos,t) 在串s的第pos个字符之后插入串t 删除 delete(s,pos,len) 从串s中删去第pos个字符起长度为len的子串 定位 position(s,t) 若t在s中存在，则返回t在主串s中的位置，否则函数值为0 替换 replace(s,t,v) 操作结果是以串v替换所有在串s中出现的和非空串t相等的子串 判相等???equal(s,t) 若s和t相等，则返回true否则返回false。 求长度 length(s) 返回s中字符的个数 基本操作的例 s1=“Data” s2=“Structure” s3=“DataStructure” s4=“Data Structure” ? length(s3) 返回值为13 length(s4) 返回值为14 position(s4,s2) 返回值为5 substring(s3,4,3) 返回一个字符串“Str” delete(s4,5,3) 执行后串s4的值为“Data ucture” replace(s4,s1,s2) 执行后串s4的值为“Structure Structure” 字符串S=“data structures” 非紧缩存储方式以字为单位顺序存储字符串的每个字符，即一个存储单元只存储一个字符 紧缩存储方式以字节为单位顺序存储字符串的每个字符，根据机器字的长度，紧缩存储方法尽可能将多个字任存放在一个字中 顺序串的类型定义 #define STRMAX 64 //字符串的最大长度 struct node { char data[STRMAX]; //字符数组 int slen ;//整数slen用来指示字符串的实际长度 } 串的链接存储结构 采用链接存储结构的串称为链串 将链表中每个结点数据域存储的字符个数称 为结点的大小。 对于结点大小为1的链串定义如下 struct strnode { char data; strnode *next; } 对于结点大小为4的链串定义如下 #define NODESIZE 4 struct strnode { char data[NODESIZE]; strnode *next; } 系统定义的字符串处理函数 Strcat(连接), strcpy(复制), strcmp(比较), strlen(求长度), strlwr(转换为小写), Strupr(转换为大写) 注意：使用之前，先将头文件string.h包含 到源程序中 作业 用语言编写一个程序，，测试一个顺序存储 的字符串s的串值是否为回文，即从左面读 与从右面读内容一样，例： “上海自来水来自海上” 串的抽象数据类型 class Str {public: virtual int leng()=0; //求长度 virtual int pos(char* t,int k=0)=0; //定位 virtual char* subs(int pos,int len)=0;//求子串 virtual St