第四章 串
4.1 串类型的定义
4.2 串的表示和实现
4.2.1 定长顺序存储表示
4.2.2 堆分配存储表示
4.2.3 串的块链存储表示
4.1 串类型的定义一、串和基本概念串 (String)是零个或多个字符组成的有限序列。
一般记作 S=“a1a2a3… an”，其中 S 是串名，双引号括起来的字符序列是串值； ai(1≦i≦n) 可以是字母、
数字或其它字符；串中所包含的字符个数称为该 串的长度 。长度为零的串称为 空串 (Empty String)，
它不包含任何字符。
通常将仅由一个或多个空格组成的串称为 空白串
(Blank String)
注意：空串和空白串的不同，例如,,和,” 分别表示长度为 1的空白串和长度为 0的空串。
串中任意个连续字符组成的子序列称为该 串的子串,包含子串的串相应地称为 主串 。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为 子串在主串中的序号（或位置） 。例如，设 A和 B分别为
A=“This is a string” B=“is”
则 B是 A的子串,A为主串。 B在 A中出现了两次，其中首次出现所对应的主串位置是 3。因此，称 B在 A中的序号（或位置）为 3
特别地，空串是任意串的子串，任意串是其自身的子串。
通常在程序中使用的串可分为两种,串变量和串常量 。串常量和整常数、实常数一样，在 程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句
Error(“overflow”)中,overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如 C中，可定义
char path[]=“dir/bin/appl”;
这里 path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。
二、串的抽象数据定义串的抽象数据类型定义台书 P71
三、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在
C语言中常用的串运算，其它的串操作见文件。
定义下列几个变量：
char s1[20]=“dirtreeformat”;
char s2[20]=“file.mem”;
char s3[30],*p;
int result;
(1)求串长 (length)
int strlen(char *s); //求串的长度例如,printf(“%d”,strlen(s1));//输出 13
(2)串复制 (copy)
char *strcpy(char *to,char *from);
该函数将串 from复制到串 to中，并且返回一个指向串 to的开始处的指针。
例如,strcpy(s3,s1) //s3=“dirtreeformat”
(3)串联接 (concatenation)
char strcat(char *to,char *from)
该函数将串 from复制到串 to的末尾，并且返回一个指向串 to的开始处的指针。
例如,strcat(s3,”/”); strcat(s3,s2);
//s3=“dirtreeformat/file.mem”
(4)串比较（ compare)
int strcmp(char *s1,char *s2);
该函数比较串 s1和串 s2的大小，当返回值小于 0，等于
0或大于 0时分别表示 s1<s2,s1=s2或 s1>s2。例如：
result=strcmp(“baker”,”Baker”)； //result>0
result=strcmp(“12”,”12”); //result=0
result=strcmp(“Joe”,”Joseph”); //result<0
（ 5）字符定位 (index)
char * strchr(char *s,char *c);
该函数是找 c在字符串 s中第一次出现的位置，若找到则返回该位置，否则返回 NULL。
例如,p=strchr(s2,”.”);//p 指向,file”之后的位置
if (p) strcpy(p,”.cpp”); //s2=“file.cpp”
上述串的操作是最基本的，其中后四个还有变种形式：
strncpy,strncat,strncmp,strnchr。串的其余操作可由这些基本操作组合而成。
例 1、求子串求子串的过程即为复制字符序列的过程，将串 S中的第 pos个字符开始长度为 len的字符复制到串 sub中,
void substr(string sub,string s,int pos,int len)
{
if(pos<0 || pos>strlen(s)-1en || len<0)
error(“parameter error”)
strncpy(sub,&s[pos],len);
}
例 2、串的定位 index(s,t,pos)
在主串 s中，若 pos>0,则在第 pos个字符的字符中的从第 i个字符起、长度和串 T
相等的子串和 T比较，若相等，则求得函数值为 i，否则值增 1直至 S中不存在和串 T相等的子串为止且返回 0；若 pos<=0，则返回
0值,
int index(string s,string t,int pos){
if(pos>0){
n=strlen(s);m=strlen(t);i=pos;
while (i<n-m+1){
substr(sub,s,i,m);
if (strcmp(sub,t)!=0) ++i;
else return(i);}
}
return(0);
}
4.2 串的表现和实现因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法，下面分别介绍。
4.2.1定长顺序存储表示定长顺序存储表示,也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：
#define maxstrlen 256；
typedef char sstring[maxstrlen]；
sstring s； //s是一个可容纳 255个字符的顺序串。
一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如,C语言中以字符
‵ \0′ 表示串值的终结，这就是为什么在上述定义中，
串空间最大值 maxstrlen为 256，但最多只能存放 255个字符的原因，因为必须留一个字节来存放 ‵ \0′ 字符。
若不设终结符，可用一个整数来表示串的长度，那么该长度减 1的位置就是串值的最后一个字符的位置。此时顺序串的类型定义和顺序表类似：
typedef struct{
char ch[maxstrlen];
int length;
}sstring; //其优点是涉及到串长操作时速度快。
4.2.2堆分配存储表示这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在 C语言中，利用动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形式。
typedef char * string;
//c中的串库相当于此类型定义
typedef struct{
string ch;
int length;
}hsring;
例 1、在主串 s中在第 pos个字符起，插入字符串 t
status sinsert(hstring s,int pos,hstring t)
{
if(pos<1 || pos>s.length+1)
return error;
if(t.length)
{ k=s.length+t.length＋ 1；
s.ch=(char*)realloc(s.ch,k*sizeof(char));
if(! s.ch)
exit(“overflow”);
for(i=s.length-1;i>pos-1;--i)
s.ch[i+t.length]=s.ch[i];
for(i=pos-1,j=0;i<=pos+t.length-2;++i)
{s.ch[i]=t.ch[j];++j;}
s.length+=t.length;
}
return ok;
}
例 2、求串长 (length)
int strlen(hstring s)
{
return s.length;
}
例 3、字符串清空
status clearstring(hstring s)
{
if (s.ch) {free(s.ch);s.ch=NULL;}
s.length=0;
}
例 4、生成一个其值等于串常量 chars的串 t
status strassign(hstring t,char *chars)
{
if (t.ch) free(t.ch);
for(i=0;(chars[i]),++i);
if(!i)
{
t.ch=null; t.length=0;
}
Else
{ P=(char*)malloc(I*sizeof(char)));
if(!P) exit(overflow);
t.ch= P;
t.ch[0..i-1]=chars[0..i-1]; t.length=i;
} }
例 5,串比较（ compare)
int strcmp(hstring s,hstring t);
该函数比较串 s和串 t的大小，当返回值小于 0，
等于 0或大于 0时分别表示 s<t,s=t或 s>t。
int strcmp(hstring s,hstring t)
{
for(i=0;i<s.length && i<t.length;++i)
if (s.ch[i]!=t.ch[i])
return(s.ch[i]-t.ch[i]);
return s.length-t.length;
}
4.2.3 串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。
typedef struct node{
char data;
struct node *next;
}lstring;
一个链串由头指针唯一确定。
这种结构便于进行插入和删除运算，但存储空间利用率不高。
为了提高存储密度，可使每个结点存放多个字符。
通常将结点数据域存放的字符个数定义为 结点的大小,显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结，例见书 78页。
对于结点大小不为 1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。
#define nodesize 80
typedef struct node{
char data[nodesize];
struct node *next;
}lstring;
小 结树 图一个前驱，
多个后继多个前驱，
多个后继栈 队列插入、删除在同一端的线性表插入、删除在不同端的线性表线性表
N个数据元素的有限序列广义表
DE可以是表的线性表串
N个字符的存储序列数组
DE之间的关系在维数上扩充的线性表链表类型带头结点、循环、双向前驱、后继个数扩展结点变化操作受限元素受限维数扩展数据扩展
4.1 串类型的定义
4.2 串的表示和实现
4.2.1 定长顺序存储表示
4.2.2 堆分配存储表示
4.2.3 串的块链存储表示
4.1 串类型的定义一、串和基本概念串 (String)是零个或多个字符组成的有限序列。
一般记作 S=“a1a2a3… an”，其中 S 是串名，双引号括起来的字符序列是串值； ai(1≦i≦n) 可以是字母、
数字或其它字符；串中所包含的字符个数称为该 串的长度 。长度为零的串称为 空串 (Empty String)，
它不包含任何字符。
通常将仅由一个或多个空格组成的串称为 空白串
(Blank String)
注意：空串和空白串的不同，例如,,和,” 分别表示长度为 1的空白串和长度为 0的空串。
串中任意个连续字符组成的子序列称为该 串的子串,包含子串的串相应地称为 主串 。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为 子串在主串中的序号（或位置） 。例如，设 A和 B分别为
A=“This is a string” B=“is”
则 B是 A的子串,A为主串。 B在 A中出现了两次，其中首次出现所对应的主串位置是 3。因此，称 B在 A中的序号（或位置）为 3
特别地，空串是任意串的子串，任意串是其自身的子串。
通常在程序中使用的串可分为两种,串变量和串常量 。串常量和整常数、实常数一样，在 程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句
Error(“overflow”)中,overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如 C中，可定义
char path[]=“dir/bin/appl”;
这里 path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。
二、串的抽象数据定义串的抽象数据类型定义台书 P71
三、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在
C语言中常用的串运算，其它的串操作见文件。
定义下列几个变量：
char s1[20]=“dirtreeformat”;
char s2[20]=“file.mem”;
char s3[30],*p;
int result;
(1)求串长 (length)
int strlen(char *s); //求串的长度例如,printf(“%d”,strlen(s1));//输出 13
(2)串复制 (copy)
char *strcpy(char *to,char *from);
该函数将串 from复制到串 to中，并且返回一个指向串 to的开始处的指针。
例如,strcpy(s3,s1) //s3=“dirtreeformat”
(3)串联接 (concatenation)
char strcat(char *to,char *from)
该函数将串 from复制到串 to的末尾，并且返回一个指向串 to的开始处的指针。
例如,strcat(s3,”/”); strcat(s3,s2);
//s3=“dirtreeformat/file.mem”
(4)串比较（ compare)
int strcmp(char *s1,char *s2);
该函数比较串 s1和串 s2的大小，当返回值小于 0，等于
0或大于 0时分别表示 s1<s2,s1=s2或 s1>s2。例如：
result=strcmp(“baker”,”Baker”)； //result>0
result=strcmp(“12”,”12”); //result=0
result=strcmp(“Joe”,”Joseph”); //result<0
（ 5）字符定位 (index)
char * strchr(char *s,char *c);
该函数是找 c在字符串 s中第一次出现的位置，若找到则返回该位置，否则返回 NULL。
例如,p=strchr(s2,”.”);//p 指向,file”之后的位置
if (p) strcpy(p,”.cpp”); //s2=“file.cpp”
上述串的操作是最基本的，其中后四个还有变种形式：
strncpy,strncat,strncmp,strnchr。串的其余操作可由这些基本操作组合而成。
例 1、求子串求子串的过程即为复制字符序列的过程，将串 S中的第 pos个字符开始长度为 len的字符复制到串 sub中,
void substr(string sub,string s,int pos,int len)
{
if(pos<0 || pos>strlen(s)-1en || len<0)
error(“parameter error”)
strncpy(sub,&s[pos],len);
}
例 2、串的定位 index(s,t,pos)
在主串 s中，若 pos>0,则在第 pos个字符的字符中的从第 i个字符起、长度和串 T
相等的子串和 T比较，若相等，则求得函数值为 i，否则值增 1直至 S中不存在和串 T相等的子串为止且返回 0；若 pos<=0，则返回
0值,
int index(string s,string t,int pos){
if(pos>0){
n=strlen(s);m=strlen(t);i=pos;
while (i<n-m+1){
substr(sub,s,i,m);
if (strcmp(sub,t)!=0) ++i;
else return(i);}
}
return(0);
}
4.2 串的表现和实现因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法，下面分别介绍。
4.2.1定长顺序存储表示定长顺序存储表示,也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：
#define maxstrlen 256；
typedef char sstring[maxstrlen]；
sstring s； //s是一个可容纳 255个字符的顺序串。
一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如,C语言中以字符
‵ \0′ 表示串值的终结，这就是为什么在上述定义中，
串空间最大值 maxstrlen为 256，但最多只能存放 255个字符的原因，因为必须留一个字节来存放 ‵ \0′ 字符。
若不设终结符，可用一个整数来表示串的长度，那么该长度减 1的位置就是串值的最后一个字符的位置。此时顺序串的类型定义和顺序表类似：
typedef struct{
char ch[maxstrlen];
int length;
}sstring; //其优点是涉及到串长操作时速度快。
4.2.2堆分配存储表示这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在 C语言中，利用动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形式。
typedef char * string;
//c中的串库相当于此类型定义
typedef struct{
string ch;
int length;
}hsring;
例 1、在主串 s中在第 pos个字符起，插入字符串 t
status sinsert(hstring s,int pos,hstring t)
{
if(pos<1 || pos>s.length+1)
return error;
if(t.length)
{ k=s.length+t.length＋ 1；
s.ch=(char*)realloc(s.ch,k*sizeof(char));
if(! s.ch)
exit(“overflow”);
for(i=s.length-1;i>pos-1;--i)
s.ch[i+t.length]=s.ch[i];
for(i=pos-1,j=0;i<=pos+t.length-2;++i)
{s.ch[i]=t.ch[j];++j;}
s.length+=t.length;
}
return ok;
}
例 2、求串长 (length)
int strlen(hstring s)
{
return s.length;
}
例 3、字符串清空
status clearstring(hstring s)
{
if (s.ch) {free(s.ch);s.ch=NULL;}
s.length=0;
}
例 4、生成一个其值等于串常量 chars的串 t
status strassign(hstring t,char *chars)
{
if (t.ch) free(t.ch);
for(i=0;(chars[i]),++i);
if(!i)
{
t.ch=null; t.length=0;
}
Else
{ P=(char*)malloc(I*sizeof(char)));
if(!P) exit(overflow);
t.ch= P;
t.ch[0..i-1]=chars[0..i-1]; t.length=i;
} }
例 5,串比较（ compare)
int strcmp(hstring s,hstring t);
该函数比较串 s和串 t的大小，当返回值小于 0，
等于 0或大于 0时分别表示 s<t,s=t或 s>t。
int strcmp(hstring s,hstring t)
{
for(i=0;i<s.length && i<t.length;++i)
if (s.ch[i]!=t.ch[i])
return(s.ch[i]-t.ch[i]);
return s.length-t.length;
}
4.2.3 串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。
typedef struct node{
char data;
struct node *next;
}lstring;
一个链串由头指针唯一确定。
这种结构便于进行插入和删除运算，但存储空间利用率不高。
为了提高存储密度，可使每个结点存放多个字符。
通常将结点数据域存放的字符个数定义为 结点的大小,显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结，例见书 78页。
对于结点大小不为 1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。
#define nodesize 80
typedef struct node{
char data[nodesize];
struct node *next;
}lstring;
小 结树 图一个前驱，
多个后继多个前驱，
多个后继栈 队列插入、删除在同一端的线性表插入、删除在不同端的线性表线性表
N个数据元素的有限序列广义表
DE可以是表的线性表串
N个字符的存储序列数组
DE之间的关系在维数上扩充的线性表链表类型带头结点、循环、双向前驱、后继个数扩展结点变化操作受限元素受限维数扩展数据扩展
