《数据结构(c语言)第四章字符串》由会员分享，可在线阅读，更多相关《数据结构(c语言)第四章字符串（29页珍藏版）》请在金锄头文库上搜索。
1、字符串 (String) 字符串:是 n ( 0 ) 个字符的有限序列， 记作 S : “c1c2c3cn” 其中，S 是串名字 “c1c2c3cn”是串值 ci 是串中字符 n 是串的长度。 例如, S = “Tsinghua University” 空串空串：零个字符的串称为空串：零个字符的串称为空串 记作记作 “ “” ” 子串子串：串中任意个连续的字符组成的子序：串中任意个连续的字符组成的子序 列列 主串主串：包含子串的串：包含子串的串 字符在串中的位置字符在串中的位置：字符在序列中的序号：字符在序列中的序号 子串在串中的位置子串在串中的位置：子串的第一个字符在：子串的第一个字符在 主
2、串中的位置主串中的位置 串的基本运算 串插入 串赋值 求串长 串比较 串联接 求子串 串定位 串删除 置换 StrAssign (T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 StrCmp (S, T) 初始条件：串 S 和 T 存在。 操作结果：若S T，则返回值 0； 若S T，则返回值 0； 若S T，则返回值 0。 例如：StrCmp(“data”, “state”) 0 StrLen (S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个 数，称为串的长度。 Strcat ( S1, S2) 初始条件：串 S1 和 S2
3、 存在。 操作结果：返回由 S1 和 S2 联接而成的新串。 例如： Strcat( man, kind) 求得 S1 = mankind SubStr( S, i, j) 初始条件： 操作结果： 返回串 S 的第 i个字符起 长度为 j的子串。 串 S 存在，1iStrLen(S) 且 0jStrLen(S) - i+1。 例如： SubStr( commander , 4, 3) 子串为“串”中的一个字符子序列 求得 sub = man ; SubStr(commander , 1, 9) SubStr( commander , 9, 1) 求得 sub = r 求得 sub = comm
4、ander SubStr(“commander”, 4, 7) sub = ? SubStr(“beijing”, 7, 2) = ? sub = ? SubStr(student, 5, 0) = 起始位置和子串长度之间存在约束关系 长度为 0 的子串为“合法”串 Index (S, T) 初始条件：串S和T存在，T是非空串 操作结果： 若主串 S 中存在和串 T 值 相同的子串, 则返回它在主串 S 中第一 次出现的位置，否则函数值为0。 假设 S = abcaabcaaabc , T = bca Index(S, T) = 2; “子串在主串中的位置”意指子串 中的第一个字符在主串中的位
5、序。 Replace (S, T, V) 初始条件：串S, T和 V 均已存在， 且 T 是非空串。 操作结果：用 V 替换主串 S 中出现 的所有与（模式串）T 相等的子串。 例如： 假设 S = abcaabcaaabca, T = bca 若 V = x , 则经置换后得到 S = axaxaax 若 V = bc , 则经置换后得到 S = abcabcaabc Insert (S, i, T) 初始条件：串S和T存在， 1iStrLength(S) 操作结果：在串S的第i个字符之后 插入串T。 例如：S = chater ，T = rac ， 则执行 Insert(S, 4, T)
6、之后得到 S = chatracer Delete (S, i, j) 初始条件：串S存在 1iStrLen(S) - j+1。 操作结果：从串S中删除第i个字符 起长度为j的子串。 对于串的基本操作集可以有不同的定义 方法，在使用高级程序设计语言中的串类型 时，应以该语言的参考手册为准。 gets(str) 输入一个串； puts(str) 输出一个串； strcat(str1, str2) 串联接函数； strcpy(str1, str2, k) 串复制函数； strcmp(str1, str2) 串比较函数； strlen(str) 求串长函数； 例如：C语言函数库中提供下列串处理函数：
7、 在程序设计语言中，串只是 作为输入或输出的常量出现，则只 需存储此串的串值，即字符序列即 可。但在多数非数值处理的程序中， 串也以变量的形式出现。 4.2 串的存储结构 一、串的定长顺序存储表示 二、串的堆分配存储表示 三、串的块链存储表示 #define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char String MAXSTRLEN + 1; / 0号单元存放串的长度 一、串的定长顺序存储表示 按这种串的表示方法实现的串的 运算时，其基本操作为 “字符序列 的复制” 串的实际长度可在这个予定义长 度的范围内随意设定，超过予定义
8、长度的串值则被舍去，称之为“截断 ” 特点: typedef struct char *ch; / 若是非空串，则按串实用长度分配 /存储区，否则 ch 为NULL int curlen; / 串长度 String; 二、串的堆分配存储表示 通常，C语言中提供的串类型就是以 这种存储方式实现的。系统利用函数 malloc( ) 和 free( ) 进行串值空间的动态管 理，为每一个新产生的串分配一个存储区 ，称串值共享的存储空间为“堆”。 C语言中的串以一个空字符为结束符， 串长是一个隐含值。 这类串操作实现的算法为: 先为新生成的串分配一个存储空间，然后 进行串值的复制。 三、串的块链存储表
9、示 也可用链表来存储串值，由于串的数据 元素是一个字符，它只有 8 位二进制数 ，因此用链表存储时，通常一个结点中 存放的不是一个字符，而是一个子串。 存储密度 = 数据元素所占存储位 实际分配的存储位 #define CHUNKSIZE 80 / 可由用户定义块大小 typedef struct Chunk / 结点结构 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString; 例如: 在编辑系统
10、中，整个文本编辑区 可以看成是一个串，每一行是一个子串， 构成一个结点。即: 同一行的串用定长结构 (80个字符), 行和行之间用指针相联接。 实际应用时，可以根据问题所需来 设置结点的大小。 串的模式匹配 n定义 在串中寻找子串（第一个字 符）在串中的位置 n词汇 在模式匹配中，子串称为模 式，串称为目标。 n示例 目标 T : “Beijing” 模式 P : “jin” 匹配结果 = 3 第1趟 T a b b a b a 穷举的模式 P a b a 匹配过程 第2趟 T a b b a b a P a b a 第3趟 T a b b a b a P a b a 第4趟 T a b b a b a P a b a INDEX( S ,T) Seqstring *S ,*T ;/穷举的模式匹配 for ( int i = 0; i = S.curLen-T.curLen; i+ ) /逐趟比较 int j = 0; /从chi与模式T.ch比较 while ( j T.curLen ) if ( S.chi+j = T.chj ) j+; else break; if ( j = T.curLen ) return i; /pat扫描完, 匹配成功
