串的基本概念
1、串的基本概念
字符串（String）是由零个或多个字符组成的有限序列。记为: S = ′a1 a2 … an′( n ≥ 0 ) 其中 S 是串的名字,用单引号括起来的字符序列是串的值,每个 ai( 1 ≤ i≤ n)可 以是字母、数字或其他字符。 n 是串中字符的个数,称为串的长度,n=0 时的串称为空串( Null String)。
需要特别指出的是,串值必须用一对单引号括起来( C 语言中是双引号),但单引号是界限符,它不属于串,其作用是避免与变量名或常量混淆。
·子串:串中任意个连续的字符组成的子序列称为该串的子串。
·主串:包含子串的串相应地称为主串。可见,子串是主串的一部分。
· 子串在主串中的位置:通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置 来表示。
串相等:当且仅当两个串的值相等时,称这两个串是相等的,即只有当 两个串的长度相等,并且每个对应位置的字符都相等时才相等。
串也是一种特定的线性表,串的逻辑结构和线性表极为相似,其特定性仅在于串的数据对象限定为字符集。
2、串的抽象数据类型定义如下:
ADT String {
数据对象: D={ ai | ai∈ CharacterSet,记为 V,i=1 ,2 ,…, n,n≥ 0 }
结构关系: R={< ai,ai + 1 >| ai,ai + 1 ∈ V,i=1 ,…, n-1 ; n-1 ≥ 0 }
基本操作:
( 1 ) StrAsign( S,chars)
操作前提: chars 是字符串常量。
操作结果:生成一个值等于 chars 的串 S。
( 2 ) StrInsert( S,pos,T)
操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)+ 1 。
操作结果:在串 S 的第 pos 个字符之前插入串 T。
( 3 ) StrDelete( S,pos,len)
操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)+ 1 。
操作结果:从串 S 中删除第 pos 个字符起长度为 len 的子串。
( 4 ) StrCopy( S,T)
操作前提:串 S 存在。
操作结果:由串 T 复制得串 S。
( 5 ) StrEmpty( S)
操作前提:串 S 存在。
操作结果:若串 S 为空串,则返回 TRUE,否则返回 FALSE。
( 6 ) StrCompare( S,T)
操作前提:串 S 和 T 存在。 操作结果:若 S>T,则返回值>0 ;如 S=T,则返回值=0 ;若 S<T,则返回值<0 。
( 7 ) StrLength( S)
操作前提:串 S 存在。
操作结果:返回串 S 的长度,即串 S 中的字符个数。
( 8 ) StrClear( S)
操作前提:串 S 存在。
操作结果:将 S 清为空串。
( 9 ) StrCat( S,T)
操作前提:串 S 和 T 存在。
操作结果:将串 T 的值连接在串 S 的后面。
( 10 ) SubString( Sub,S,pos,len)
操作前提:串 S 存在,1 ≤ pos≤ StrLength( S)且 1 ≤ len≤ StrLength( S)- pos+1 。
操作结果:用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
( 11 ) StrIndex( S,pos,T)
操作前提:串 S 和 T 存在,T 是非空串,1 ≤ pos≤ StrLength( S)。
操作结果:若串 S 中存在和串 T 相同的子串,则返回它在串 S 中第 pos 个字符 之 后第一次出现的位置;否则返回 0 。
( 12 ) StrReplace( S,T,V)
操作前提:串 S、 T 和 V 存在且 T 是非空串。
操作结果:用 V 替换串 S 中出现的所有与 T 相等的不重叠的子串。
( 13 ) StrDestroy( S)
操作前提:串 S 存在。
操作结果:销毁串 S。
}ADT string
串的顺序存储结构
串的顺序存储结构有定长顺序串、堆串。
1、定长顺序串
定长顺序串是将串设计成一种静态结构类型,串的存储分配是在编译时完成的。
1）定长顺序串存储结构
定长顺序串类型定义如下:
#define MAXLEN 40 typedef struct { /*串结构定义*/ char ch[ MAXLEN]; int len; }SString;
其中 MAXLEN 表示串的最大长度,ch 是存储字符串的一维数组,每个分量存储一 个字符, len 是字符串的长度。
2）.定长顺序串基本操作的实现
( 1 )串插入函数
【问题分析】在进行顺序串的插入时,插入位置 pos 将串分为两部分(假设为 A、 B,长度为 LA、 LB)及待插入部分(假设为 C,长度为 LC),则串由插入前的 AB 变为 ACB,由于是顺序串, 插入会引起元素的移动。可能出现以下三种情况:
①插入后串长( LA+LC +LB)≤ MAXLEN,则将 B 后移 LC 个元素位置,再将 C 插入。
②插入后串长>MAXLEN 且 pos+LC≤ MAXLEN,则 B 后移时会有部分字符被舍弃。
③插入后串长> MAXLEN 且 pos +LC >MAXLEN,则 B 的全部字符被舍弃(不需后移),并 且 C 在插入时也有部分字符被舍弃。
【算法描述】
StrInsert(SString *s, int pos, SString t) /*在串 s 中下标为 pos 的字符之前插入串 t */ { int i; if (pos<0 || pos>s->len) return(0); /*插入位置不合法*/ if (s->len + t.len<=MAXLEN) { /*插入后串长≤MAXLEN*/ for (i=s->len + t.len-1;i>=t.len + pos;i--) s->ch[i]=s->ch[i-t.len]; for (i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i]; s->len=s->len+t.len; } else if (pos+t.len<=MAXLEN) {/*插入后串长>MAXLEN,但串 t 的字符序列可以全部插入*/ for (i=MAXLEN-1;i>t.len+pos-1;i--) s->ch[i]=s->ch[i-t.len]; for (i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i]; s->len=MAXLEN; } else { /*插入后串长>MAXLEN,并且串 t 的部分字符也要舍弃 for (i=0;i<MAXLEN-pos;i++) s->ch[i+pos]=t.ch[i]; s->len=MAXLEN; } return(1); }
实现顺序串插入的算法其实现复杂度为: O( s->len+t.len)。
2、堆串
字符串包括串名与串值两部分,而串值采用堆串存储方法存储,串名用符号表 存储。
堆串存储方法:仍以一组地址连续的存储单元顺序存放串中的字符,但它们的 存储空间是在程序执行过程中是动态分配的。
串名符号表:所有串名的存储映像构成一个符号表。借助此结构可以在串名和 串值之间建立一个对应关系,称为串名的存储映像。
1）堆串存储表示: C 语言已经有一个称为“堆”的自由存储空间,并可用函数 malloc()和函数 free()完成动态存储管理。
串的链式存储与串的应用
1、块链串
由于串也是一种线性表,因而也可以采用链式存储。因为串是一个特殊的线性表(表中每 个元素就是一个字符)。在具体实现时,一个链表存放一个串值,每个结点既可以存放一个字符, 也可以存放多个字符。每个结点称为块,整个链表称为块链结构,为便于操作,再增加一个尾指 针。
块链结构可定义如下：
#define BLOCK_SIZE 4 /*每结点存放字符个数 4*/ typedef struct Block{ char ch[BLOCK_SIZE]; struct Block *next; } Block; typedef struct { Block *head; Block *tail; int len; } BLString;
结点大小:链表中的结点分成两个域data和link,其中结点大小是指data域中存放字符的个数,链域大小是指 link 域中占用字符的个数。
存储密度=串值占用的存储位/实际为串分配存储位
显然,串的存储密度越小,运算处理就越方便,但存储占用的量较大。应根据具体情况来确 定使用串的何种存储结构。
结点大小等于 1 :当 BLOCK_SIZE 等于 1 时,每个结点存放 1 个字符,结构同线性链表,存 储结构可定义如下,插入、删除的处理方法和线性链表一样,算法处理简单,但存储密度较低。
结点大于 1 :当 BLOCK_SIZE 大于 1 时,每个结点存放多个字符,当最后一个结点未存满 时,不足处可用特定字符(如#)补齐。虽然存储密度相对结点大小等于 1 的存储方法来说,存储 密度较高,但此时插入、删除的处理方法比较复杂,需要考虑结点的分拆和合并。
2、串的应用举例:简单的行编辑器