文档介绍：1数据结构4串2开始学****本章前要知道:?从数据结构角度看,串也属于线性结构,具有线性结构的共同特征;?学****本章时,要注意到串所具有的线性结构的共性,更要掌握其个性;?串的特殊性主要是:串的元素是字符。3主要内容?串的基本概念?串的基本操作?串的存储结构–定长顺序存储–块链存储?串的模式匹配–简单算法–KMP算法4串的基本概念?串的定义–串:n个字符的有限序列,n>=0?一般记为:S = ‘a1 a2... an’?其中,S是串名,‘a1 a2... an’是串S的值,串值必须由一对单引号括起来?串的长度:串中字符的个数例如S1=‘abc’S2=‘FORTRAN_77’S3=‘’=Φ(空串)长度为05串的基本概念?:串中若干个连续的字符组成的子序列。例如:S = ‘Beiji ng&Shanghai’ T = ‘ji ng’:包含子串的串。特别规定,空串是任意串的子串,任意串是其自身的子串。6串的基本概念例如:S = ‘Beijing&Nanjing&Shanghai’ T = ‘jing’:(1)单个字符在主串中的位置被定义为该字符在串中的序号。(2)子串在主串中的位置被定义为主串中首次出现的该子串的第一个字符在主串中的位置。,并且对应位置上的字符相等。例如:‘abcd’≠‘bacd’‘abcd’= ‘abcd’(S1,S2)(S1,S2)(S1,S2)(S)(S,i,k)(S1,S2)(S,S1,S2)(S1,S2)(S1,i,S2)(S,i,k)strcpy(S1,S2)strcmp(S1,S2)strcat(S1,S2)strlen(S)strstr(S1,S2)C函数模式匹配9串的存储结构:定长顺序表示?顺序表示–是用一个字符数组来表示?串长度的表示–C:以’\ 0’结尾,隐含串长度#define maxsize 256 / /假设串可能的最大长度是256 char s[maxsize];但最多只能存放255个字符,因为必须留一字节来存放串终结符’\ 0’。10串的存储结构:定长顺序表示若不设置终结符,可用一个整数l ength来表示串的长度,此时顺序串的类型定义完全和顺序表类似:012345……maxsize- struct { char ch[maxsi ze] ; / /串的存储空间i nt curl en ; / /当前串的长度} SeqStri ng ;