1、补充： C语言中常用的串运算串比较， int strcmp(chars1,char s2); / StrCompare(S,T) 求串长， int strlen(char s); / StrLength(S)串连接， char strcat(char to,char from) / Concat( / Index(S, T, pos)Concat concatenation，在字符串处理中 ,把多个短字符串合成为长字符串的操作。注：用 C处理字符串时，要调用标准库函数 #include数据结构课程的内容* 3在计算机的应用中，非数值处理问题的应用越来越多。如在汇编程序和编译程序中，源程序和目标
2、程序都是作为一种字符串数据进行处理的。在事务处理系统中，用户的姓名和地址及货物的名称、规格等也是字符串数据。字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。在线性表的基本操作中，大多以 “单个元素 ”作为操作对象，而在串中，则是以 “串的整体 ”或一部分作为操作对象。因此，线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。本章学习导读本章学习导读第 4章 串（ String）4.2 串的表示和实现4.3 串的模式匹配算法1. 定义2. 逻辑结构3. 存储结构4. 运算规则5. 实现方
3、式4.1 串类型的定义记为： s = a1 , a2 , . , a n (n0 )串名 串值（用 括起来）串中字符个数（ n0 ） . n=0 时称为空串 。由一个或多个空格符组成的串。串 s中任意个连续的字符序列叫 s的子串 ; S叫 主串。子串的第一个字符的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。 串 即字符串，是由 零个或多个 字符组成的有限序列，是数据元素为单个字符的 特殊线性表 。4.1 串类型的定义若干术语：串长：空白串：子串：子串位置：字符位置：串相等：隐含结束符 0 ，即 ASCII码 NULL练 1： 串是由 字符组成的序列，一般记为 。练 2： 现有以下
4、 4个字符串：a =BEI b =JING c = BEIJING d = BEI JING问： 他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？a =3， b =4， c = 7， d=8a是 c和 d的子串，在 c和 d中的位置都是 1练 3： 空串和空白串有无区别？答： 有区别。空串 (Null String)是指长度为零的串；而空白串 (Blank String),是指包含一个或多个空白字符 (空格键 )的字符串 .0个或多个S=a1a2a nADT StingObjects: D=ai | ai CharacterSet, i=1, 2, ， n, n0Relations:
5、 R1= | ai-1,ai D, i=2, ， nfunctions: / 有 13种之多StrAssign(&T, chars) / 串赋值，生成值为 chars的串 TStrCompare(S,T) / 串比较，若 ST，返回值大于 0StrLength(S) / 求串长，即返回 S的元素个数Concat(&T, S1, S2) / 串连接，用 T返回 S1 S2的新串SubString(&Sub, S, pos, len) / 求 S中 pos起长度为 len的子串Index(S, T, pos) / 返回子串 T在 pos之后的位置Replace(&S, T,V) / 用子串 V替换
6、子串 TADT Sting串的抽象数据类型定义（ 参见教材 P71）最小操作子集设 s =I AM A STUDENT, t =GOOD, q=WORKER 。求：练习：StrLength(s) StrLength(t) SubString(s, 8, 7)=SubString(t, 2, 1)=Index(s, A,0)=Index(s, t,0)=Replace(s, STUDENT,q)=144STUDENTO30 （ s中没有 t！）I AM A WORKER再问： Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ？A GOOD S
7、TUDENT* 94.2 串的存储结构串是一种特殊的线性表， 其存储结构与线性表的存储结构类似 ， 只不过组成串的结点是单个字符。 串的存储结构表示有两种方法：静态存储和动态存储静态存储采用 顺序 存储结构，动态存储采用的是 链式 存储和 堆存储 结构。4.2.1 串的顺序存储结构及其基本运算的实现1顺序存储结构 （静态 ）串的顺序存储结构是采用与其逻辑结构相对应的存储结构，将串中的各个字符按顺序依次存放在一组地址连续的存储单元里，逻辑上相邻的字符在内存中也相邻。 * 10类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。这是一种静态存储结构，串值的存储分配是在编译时完成的。因此，需要预先定义串的存储空间大小。如果定义的空间过大，则会造成空间浪费；如果定义的空间过小，则会限制串的某些运算，如联接、置换运算等。
