数据结构第四章

一、1、串的基本概念

? 串---由零个或多个字符组成的有限序列，一般记为：s='a1a2...an' (n≥0)

? 串中字符的个数n称为串的长度；零个字符，即长度为零的串称为空串，用?或''表示。 空串不等于空格串，空格串：由一个或多个空格组成的串 子串：串中任意个连续的字符组成的子序列 主串：包含子串的串相应地称为主串

相等：两个串的长度相等，并且对应位置的字符都相同。 2、串结构与线性表结构的比较：

逻辑结构：极为相似，区别仅在于串的数据对象约束为字符集。

基本操作：有很大差别1、线性表大多以“单个元素”作为操作对象2、串通常以“串的整体”作为操作对象 3、串类型定义 4、 串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString

等六种操作构成串类型的最小操作子集。

1、 StrAssign (&T, chars) 初始条件：chars 是字符串常量。操作结果：把 chars 赋为 T 的值。等价于

C语言中的strset函数 2、 StrCopy (&T, S) 初始条件：串 S 存在。操作结果：由串 S 复制得串 T。等价于C语言中的strcpy

函数 3、 StrCompare (S, T) 初始条件：串 S 和 T 存在。操作结果：若S＞T，则返回值＞0； 若S＝T，则返回值＝0； 若S＜T，则返回值＜0。等价于C语言中的strcmp函数(按ASCII码值进行大小比较) 4、 StrLength (S) 初始条件：串 S 存在。操作结果：返回 S 的元素个数，称为串的长度。等价于C语言中的strlen函数

5、 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。操作结果：用T返回由S1和S2联接而成的新串。

例如： Concate( T, ?man?, ?kind?) 求得 T = ?mankind? 等价于C语言中的strcat函数

6、 SubString (&Sub, S, pos, len) 初始条件：串S存在，1≤pos≤StrLength(S) 且 0≤len≤

StrLength(S)-pos+1。 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。子串为“串”

中的一个字符子序列。例如：SubString( sub, 'commander', 4, 3)，求得sub = 'man'；

SubString( sub, 'commander', 1, 9)，求得sub = 'commander'； SubString( sub, 'commander', 9, 1)，求得sub = 'r'；

起始位置pos和子串长度len之间存在约束关系，pos+len<=StrLength(S)+1

SubString('student', 5, 0) = ? ——长度为0的子串为“合法”串

5、Index (S, T, pos) 初始条件：串S和T存在，T是非空串， 1≤pos≤StrLength(S)。操作结果：若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置;否则函数值为0。 “子串在主串中的位置”指子串中的第一个字符在主串中的位序。

假设 S = ?abcaabcaaabc?, T = ?bca? Index(S, T, 1) =2 Index(S, T, 3) = 6 Index(S, T, 8) = 0 6、Replace (&S, T, V) 初始条件：串S, T和V均已存在，且T是非空串。

操作结果：用 V 替换主串 S 中出现的所有与（模式串）T 相等的不重叠的子串。

例如：假设 S = ?abcaabcaaabca?，T = ?bca?若 V = ?x?， 则经置换后得到 S = ?abcaabcaaabca?

7、StrInsert (&S, pos, T) 初始条件：串S和T存在， 1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T

例如：S = 'chater'，T = 'rac'，则执行 StrInsert(S, 4, T)之后得到S = 'cha racter'? 二、串的表示和实现

1、定长顺序存储表示：用一组地址连续的存储单元存储串值的字符序列，称为顺序串。可用一个数组来表示。 特点：①串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断” 。②按这种串的表示方法实现的串运算时，其基本操作为 “字符序列的复制”

顺序存储结构中，串操作的基本操作为“字符序列的复制”，其时间复杂度基于复制的字符序列的长度。 2、堆分配存储表示：特点：仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执

行过程中动态分配而得的。 串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。 3、串的模式匹配算法

课堂练习

已知：a=?THIS?, f=?A SAMPLE?, c=?GOOD?, d=?NE?, b=? ?,

1、s=Concat(a, Concat(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2)))), 2、t=Replace(f, SubString(f, 3, 6), c),

3、u=Concat(SubString(c, 3, 1), d), g=?IS?, 4、v=Concat(s, Concat(b, Concat(t, Concat(b, u)))),

试问：s, t, v, StrLength(s), Index(v, g), Index(u, g)各是什么？

1、?THIS SAMPLE IS? 2、?A GOOD? 3、?ONE? 4、v=?THIS SAMPLE IS A GOOD ONE? 课后作业

P28：4.5(要求：写出每一个函数执行后的结果)

1. 已知：s=?(XYZ)+*?，t=?(X+Z)*Y?。试利用联接、求子串和置换等基本操作，将s转化为t。 SubString(&s1, s, 3, 1); 'Y' SubString(&s2, s, 6, 1); '+' SubString(&s3, s, 7, 1);'*' Replace(&s, s1, s2); '(X+Z)+*' Concat(&s4, s3, s1);

'*Y'

Concat(&t, SubString(&s5, s, 1, 5), s4);

'(X+Z)*Y'

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构第四章在线全文阅读。