第4章 串 数据结构(C语言版)课件.ppt

安徽理工大学 第4章 串 在计算机应用中，非数值处理问题的应用越来越多。如在编译程序中，源程序和目标程序都是作为一种字符数据进行处理的。 字符串一般简称为串，它是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的。在一般线性表的基本操作中，大多以“单个元素”作为操作对象，而在串中，则是以“串的整体”或一部分作为操作对象。本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。 学习要点 4.1 串类型的定义 基本概念 串：是由零个或多个字符组成的有限序列 ，记作 S = ‘a1a2a3…an’ (n≥0)，其中 S是串名字，‘a1a2a3…an’是串值 ai是串中字符，n是串的长度，表示串中字符数目。 空串：零个字符的串称为空串，记作 “?”。 空格串：由一个或多个空格组成的串。 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串。 子串在串中的位置：子串的第一个字符在主串中的位置。 串相等：串长度相等，且对应位置上字符相等。 1. 空串和空格串的不同，例如‘ ’和‘ ’分别表示长度为1的空格串和长度为0的空串。 2. 空串是任意串的子串，任意串是其自身的子串。 3. 串的逻辑结构与线性表相似，区别在于串的数据对象约束为字符集，但基本操作和线性表有很大差别。线性表大多以“单个元素”作为操作对象，而串通常以“串的整体”作为操作对象。 注意 串的基本操作 串赋值 StrAssign (T, chars)：把 chars 赋为 T 的值。 串复制 StrCopy (T, S) ：由串 S 复制得串 T。 串判空 StrEmpty (S)：若 S 为空串，则返回 true，否则 返回false。 串比较 StrCompare (S, T)：若S ? T，则返回值 ? 0；若 S?T，则返回值 ? 0；若S ? T，则返回值 ? 0。 求串长 StrLength(S)：返回 S 的元素个数。 串清除 ClearString (S)：将S清为空串。 串联接 Concat (T, S1, S2)：用 T 返回由 S1 和 S2联 接而成的新串。 串的基本操作 求子串 SubString (Sub, S, pos, len) ：用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。 串定位 Index (S, T, pos)：若主串 S 中存在和串 T 值相同的串，则返回它在主串 S 中第pos个字符之后第一次出现的位置。 串替换 Replace (S, T, V)：用 V 替换主串 S 中出现的所有与(模式串)T相等的不重叠的子串。 串插入 StrInsert (S, pos, T)：在串S的第pos个字符之前插入串T。 串删除 StrDelete (S, pos, len)：从串S中删除第pos个字符起长度为len的子串。 串销毁 DestroyString(S)：串 S 被销毁。 例子 例1：StrCompare(‘data’, ‘state’) 0； StrCompare(‘cat’, ‘case’) 0。 例2：Concat ( T, ‘man’, ‘kind’)； 求得 T = ‘mankind’。 例3：SubString( sub, ‘commander ’, 4, 3)； 求得 sub = ‘man ’ 。 例4：假设 S = ‘abcaabcaaabc ’, T = ‘bca ’； 则 Index(S, T, 1) = 2; Index(S, T, 3) = 6。 例5：假设 S = ‘abcaabcaaabca’, T = ‘bca ’； V = ‘bc ’, 则经Replace (S, T, V)置换后得到S = ‘abcabcaabc’。 例6：S = ‘chater ’，T = ‘rac ’； 则执行 StrInsert(S, 4, T) 之后得到 S = ‘character ’。 基本思想 从主串S中第pos位置开始的字符与子串T的字符依次比较，若不匹配，再从主串的pos+1位置开始继续比较，如此反复，直到匹配成功，返回子串与主串匹配的第一个字符在主串中的位置序号；否则匹配失败，返回函数值为0。 S 串 T 串 T 串 i pos n-m+1 求串的定位I