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

第4章 串 在计算机的应用中，非数值处理问题越来越多。 在汇编程序和编译程序中，源程序和目标程序都是作为字符串数据处理的。 在事务处理系统中，用户的姓名、地址、货物的名称、规格等也是字符串数据。 字符串是特殊的线性表：数据元素是字符型的。 在一般线性表的操作中，大多以“单个元素”作为操作对象。 在串中，则以“串的整体或一部分”作为操作对象。因此，一般线性表和串的操作有很大的不同。 本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。 第四章 串 4.1 串及基本运算 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例 要 求 掌握串的逻辑结构 掌握串的存储结构（难点） 熟练掌握串的基本运算 能设计串的简单算法 了解串的匹配运算算法的基本思想（难点） 补充说明 1.在C语言中，用单引号引起来的单个字符与单个字符的串是不同的， 如s1= ’a’表示字符，而s2= ”a ”表示字符串。 2.在C++语言中，字符串由双引号括起来： 先包括头文件： #include string using namespace std; //注意这里不是string.h，string.h是C字符串头文件 然后：string str1; 4.1.2 主串和子串 子串：一个串的任意个连续字符组成的子序列。 主串：包含该子串的串。 位置：一个字符在串中的序号。 例：s=“ababcabcac” , t=“abc” 子串t 在主串s中的位置为3 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 串操作应用举例 定长顺序存储表示