数据结构－第04章－串.pptVIP

第4章 串 第四章 串 4.1 串及基本运算 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例 要 求 掌握串的逻辑结构 掌握串的存储结构（难点） 熟练掌握串的基本运算 能设计串的简单算法 了解串的匹配运算算法的基本思想（难点） 零个字符的串称为空串（Null String） ，长度为0；以两个相邻的单引号来表示： s= ’’； 由若干个空格字符组成的串称为空格串，如：s= ’ ’；空格应计入串的长度中，如：s= ’It’s cool!’的长度为10。 补充说明 1.在C语言中，用单引号引起来的单个字符与单个字符的串是不同的， 如s1= ’a’表示字符，而s2= ”a ”表示字符串。 2.在C++语言中，字符串由双引号括起来： 先包括头文件： #include string using namespace std; //注意这里不是string.h，string.h是C字符串头文件 然后：string str1; 4.1.3 串类型的定义 ADT String｛ 数据对象：D={ai| ai ∈CharacterSet，i=1，2，…，n，n≥０} 数据关系：R1={ ai-1, ai | ai-1, ai ∈D，i=2,…,n} 基本操作： StrAssign (T,chars) 　　初始条件：chars是字符串常量 操作结果：生成一个起始值chars的串 StrCopy(T,S) 初始条件：串S 已存在 操作结果：由串S复制得串T StrEmpty(S) 初始条件：串S已存在 操作结果：若S为空串，则返回TRUE,否则返回FALSE ClearString(S) 初始条件：串S 已存在 操作结果：将S 清为空串 4.1.3 串类型的定义 ADT String｛ ……. StrLength(S) 初始条件：串S已存在 操作结果：返回S中的数据元素个数，即串的长度 Concat(T，S1，S2) 初始条件：串S1、S2已存在 操作结果：用T 返回由S1和S2联接成的新串 StrCompare(S,T) 初始条件：串S和T已存在 操作结果：若ST则返回值0, S=T则返回值=0， ST则返回值0 SubString(Sub,S,pos,len) ……. ADT String｛ Index(S，T，pos) ……. Replace(S，T，V) ……. StrInsert(S，pos，T) ……. StrDelete(S，pos，len) ……. DestroyString(S) ……. 串赋值 StrAssign 串比较 StrCompare 求串长 StrLength 串联接 Concat 求子串 SubString 算法4.1 int Index(String s, String T, int Pos){ if(pos0){ n=StrLength(s); m=StrLength(T); i=pos; while (i=n-m+1) { SubString(sub,s,I,m); If ( StrCompare(sub,T) != 0 ) ++ i; else return i; //返回子串在主串中的位置 }//while }//if return 0; } //Index 串操作应用举例 1. 文字处理中常用的:串的查找(比较,定位)与替换 在VC集成环境中可用Ctrl＋F快速查找 在Word中可用有哪些信誉好的足球投注网站与替换批量改变文本 2. 串的截断与连接 可用求子串及串连接的方法进行文字处理 第四章 串 4.1 串及基本运算 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例 定长顺序存储表示法 类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列. #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN+1] //0号单元存放串长 注：串的实际长度可在这预定义长度的范围内随意,超过预定义长度的串值则被舍去 ——“截断” 串长可用下标为0的数组元素存储,也可在串值后设特殊标记 1串联接的实现Concat(T,S1,S2) 假设S1,S2和T都