数据结构第四章串A教学

《数据结构第四章串A教学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构李鑫辽宁工程技术大学电信学院内容安排章内容学时章内容学时1绪论27图62线性表88动态存储管理略3栈和队列49查找44串310内部排序85数组和广义表311外部排序26树和二叉树1012文件略8/7/20212数据结构第4章串（String）4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法8/7/20213数据结构记为：s=‘a1a2……..an’(n≥0)串名串值（用‘’括起来）串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。4.1串类型的定义隐含结束符‘’，即ASCII码NULL为何要单独讨论“串”

2、类型？1）字符串操作比其他数据类型更复杂（如拷贝、连接操作）2）程序设计中，处理对象很多都是串类型。8/7/20214数据结构若干术语：串长：串中字符的个数（n≥0）.n=0时称为空串。空白串：由一个或多个空格符组成的串。问：空串和空白串有无区别？答：有区别。空串(NullString)是指长度为零的串；而空白串(BlankString),是指包含一个或多个空白字符‘’(空格键)的字符串.8/7/20215数据结构子串：子串位置：字符位置：串相等：例1：现有以下4个字符串：a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEIJING’问：①他们

3、各自的长度？a是c和d的子串，在c和d中的位置都是1串S中任意个连续的字符序列叫S的子串;S叫主串。子串的第一个字符在主串中的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。②a是哪个串的子串？在主串中的位置是多少？a=3，b=4，c=7，d=8“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。”——《数据结构与算法》中山大学出版社③空串是哪个串的子串？a是不是自己的子串？8/7/20216数据结构C语言中已有类似串运算函数！ADTString{Objects:D={ai

4、ai∈CharacterSet,i=1

5、,2,…，n,n≥0}Relations:R1={

6、ai-1,ai∈D,i=2,…，n}functions://至少有13种基本操作StrAssign(&T,chars)//串赋值，生成值为chars的串TStrCompare(S,T)//串比较，若S>T，返回值大于0…StrLength(S)//求串长，即返回串S中的元素个数Concat(&T,S1,S2)//串连接，用T返回S1＋S2的新串SubString(&Sub,S,pos,len)//求S中pos起长度为len的子串StrCopy（&T,S）//由串S复制得到T……Index(

7、S,T,pos)//子串定位函数（模式匹配），返回位置Replace(&S,T,V)//用子串V替换子串T}ADTString串的抽象数据类型定义（参见教材P71）最小操作子集8/7/20217数据结构StrCopy(&T,S)初始条件：串S已经存在操作结果：由串S复制得到串TConcat（&T，S1，S2）初始条件：串S1和S2存在操作结果：用T返回有S1和S2连接而成地新串。StrLength(S)初始条件：串S已经存在操作结果：返回S的元素个数，即串的长度StrCompare（S，T）初始条件：串S和串T存在操作结果：若S>T,返回值>0若S=T,返回

8、值=0若S

9、结果：用V替换主串S中出现的所有与T相等的不重叠的子串。这些操作不可能利用其它串操作来实现，即最小操作子集8/7/20219数据结构注：Concat操作＝concatenation，把多个短字符串合并为长字符串复习：C语言中常用的串运算C串比较：intstrcmp(char*s1,char*s2);求串长：intstrlen(char*s);串连接：charstrcat(char*to,char*from)子串T定位：charstrchr(char*s,char*c);……参考C语言书P135-138注：用C处理字符串时，要调用标准库函数#include

10、tring.h>类CStrCompare(S,T)S