字符串.ppt

《字符串.ppt》由会员分享，可在线阅读，更多相关《字符串.ppt（31页珍藏版）》请在三一文库上搜索。

1、数据结构 第四章 字符串,本章内容 4.1 串的基本概念 4.2 串的存储结构 4.3 串的基本运算的实现,4-3,4.1 串的基本概念,串(String)的概念 串是由零个或多个字符组成的有限序列。记作： S=a1 a2 an(n0) 其中S是串名，用双引号括起来的字符序列为串值，引号是界限符，ai(1in)是一个任意字符(字母、数字或其他字符)，它称为串的元素，是构成串的基本单位，串中所包含的字符个数n称为串的长度，当n=0时，称为空串。,4-4,4.1 串的基本概念,将串值括起来的双引号本身不属于串，它的作用是避免串与常数或与标识符混淆。例如，A=123是数字字符串，长度为3，它不同于整

2、常数123。 【空白串】：仅由一个或多个空格组成的串称为空白串。 【空串】:长度为零的串，除串结束符外，不包括任何其他字符 注意：空串和空白串的不同，例如 和 分别表示长度为1的空白串和长度为0的空串。,4-5,4.1 串的基本概念,子串的概念：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符首次出现在主串中的位置来表示。 例如，设有两个字符串C和D： C=This is a string. D=is 则它们的长度分别为17、2；D是C的子串，C为主串。D在C中出现了两次，其中首次出

3、现所对应的主串位置是3。因此，称D在C中的序号(或位置)为3。 若两个串的长度相等且对应字符都相等，则称两个串是相等的。当两个串不相等时，可按“字典顺序”区分大小。,4.1 串的基本概念,两个串相等，当且仅当这两个串的值相等。 例，串 bei jing 与串 beijing 不相等 。 例，串 eij 是串 beijing 的子串， beijing 称为主串。 例，字符 n 在串 beijing 中的位置为 6 。 例，子串 eij 在串 beijing 中的位置为2。,4-6,4-7,4.1 串的基本概念,串也是线性表的一种，因此串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符

4、集。 串的运算： 串赋值 StrAssign(&T,chars) 初始条件：chars是字符串常量。 操作结果：生成一个其值等于chars的串T。 StrCopy(&T, S) 初始条件：串S存在。 操作结果：由串S复制得串T。,4-8,4.1 串的基本概念,StrEmpty(S) 初始条件：串S存在。 操作结果：若S为空串，则返回TRUE，否则返回FALSE。 StrCompare(S,T) 初始条件：串S和T存在。 操作结果：若ST，则返回值大于0；若S=T，则返回值等于0 若ST，则返回值小于0。 StrLength(S) 初始条件：串S存在。 操作结果：返回S的元素个数，称为串的长度。

5、,4-9,4.1 串的基本概念,ClearString(&S) 初始条件：串S存在。 操作结果：将S清空为空串。 Concat(&T,S1,S2) 初始条件：串S1和S2存在。 操作结果：用T返回由S1和S2联接而成的新串。 SubString(&Sub,S,pos,len) 初始条件：串S存在,1=pos=StrLength(S) 0=len=StrLength(S) - pos + 1 操作结果：用Sub返回串S的第pos个字符起长为len的子串。,4-10,4.1 串的基本概念,Index(S, T, pos) 初始条件：串S和T存在，T是非空串，1=pos=StrLength(S) 操

6、作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符后第一次出现的位置；否则函数值为0。 Replace(&S, T, V) 初始条件：串S,T和V存在。 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。 StrInsert(&S, pos,T) 初始条件：串S和T存在,1=pos=StrLength(S)+1 操作结果：在串S的第pos个字符之前插入串T。,4-11,4.1 串的基本概念,StrDelete(&S, pos, len) 初始条件：串S存在，0=len=StrLength(S) - pos + 1 操作结果：从串S中删除第pos个字符起长度为l

7、en的子串。 DestroyString(&S) 初始条件：串S存在。 操作结果：串S被销毁。,4-12,4.2 串的存储结构,顺序存储 块链存储,4-13,4.2 串的存储结构,4.2.1 串的顺序存储 顺序串：串的顺序存储结构简称为顺序串。 与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列的。因此可用高级语言的字符数组来实现，按其存储分配的不同可将顺序串分为静态存储分配的顺序串和动态存储分配的顺序串两类。,4-14,4.2 串的存储结构,1. 静态存储分配的顺序串（定长顺序存储） 所谓静态存储分配，是指按预定义的大小为每一个串变量分配一个固定长度的存储区，即串值空间的大小

8、在编译时刻就已确定，是静态的。所以串空间最大值为MAXSIZE时，最多只能放MAXSIZE-1个字符。其类型描述如下： #define MAXSIZE 256 /该值依赖于应用，由用户定义 typedef struct char chMAXSIZE; /256个字符依次存储在ch0chMAXSIZE1中 int len; SString; /SString是顺序串类型，则串的最大长度不能超过255 SString s; /定义串变量s,4-15,4.2 串的存储结构,在直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。例如，C语言中以字符0

9、表示串值的终结。 C语言中串的静态存储结构如下图所示：,C语言中串的静态存储结构,4-16,4.2 串的存储结构,2. 动态存储分配的顺序串(堆分配存储) 堆分配存储仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得的。 系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。 假设以一维数组heapMAXSIZE表示可供字符串进行动态分配的存储空间，并设一整型变量free指向heap中未分配区域的开始地址。在程序执行过程中，当生成一个新串时，就从free指示的位

10、置起为新串分配一个所需大小的存储空间，同时记录该串的相关信息。这种存储结构称为堆结构。动态分配存储空间的顺序串也叫堆串。堆串可定义如下： typedef struct int length; int start; HeapString;,4-17,4.2 串的存储结构,在C语言中，有一个称为“堆”的自由存储空间，并可利用malloc()和free()等动态存储管理函数，根据实际需要动态分配和释放字符数组空间，如下图所示。其类型可描述如下： typedef struct char *ch; /指示串的起始地址，可按实际的串长分配存储区 int len; HString; HString s; /

11、定义一个串变量,顺序串的动态存储结构,4-18,4.2 串的存储结构,在程序中，可根据实际需求为这种类型的串变量动态分配存储空间，这样做非常有效、方便，只是在程序执行过程中要不断地生成新串和销毁旧串。,4-19,4.2 串的存储结构,4.2.2 串的链式存储 顺序串上的插入和删除操作极不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串，如下图所示。,结点大小为1的链串s,4-20,4.2 串的存储结构,链串的类型描述： typedef struct node char ch; struct node *next; /next为指向结点的指针 LStr

12、ing; LString s; /定义一个串变量s 一个链串由头指针惟一确定。 这种结构便于进行插入和删除运算，但存储空间利用率太低。,4-21,4.2 串的存储结构,为了提高存储密度，可使每个结点存放多个字符。如图所示，通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。,结点大小为4的链串,4-22,4.2 串的存储结构,对于结点大小不为1的链串，其类型定义只需对上述的结点类型做简单的修改即可。 #define nodesize 80 typedef struct node char

13、 datanodesize; struct node *next; LString; 虽然增大结点的数据域使得存储密度增大，但是做插入、删除运算时，需要考虑结点的分拆与合并，可能会引起大量字符的移动，给运算带来不便。,4-23,4.2 串的存储结构,链串的插入,4-24,4.3 串的基本运算的实现,1. 求子串运算(采用静态存储顺序串) int StrSub(SString *sub, SString s, int pos, int len) /用sub返回串s中序号pos开始的长度为len 的子串 int i; if (poss.len | lens.len-pos) sub-len=0;

14、return(0); /子串起始位置及长度是否合适 else for(i=0;ichi=s.chi+pos; sub-len= 0; /子串结束 sub-len=len; return(1); ,4-25,4.3 串的基本运算的实现,2. 定位运算(采用静态存储顺序串) 串的定位运算也称为串的模式匹配，是一种重要的串运算。 设s和t是给定的两个串，在主串s中找到等于子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回1。t也称为模式。 【算法思想】首先将s0与t0进行比较，若不同，就将s1与t0进行比较，直到s的

15、某一个字符si和t0相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即sij+1，t返回到t0，继续开始下一趟的比较，重复上述过程。若t中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是ij，否则，匹配失败。 设主串s=“ababcabcacbab”，模式t=“abcac”，匹配过程如下图所示。,简单模式匹配的匹配过程,4-27,4.3 串的基本运算的实现,模式匹配算法 int StrIndex(SString s,int pos,SString t) /求串t在串s中的位置 int i,j;

16、if(t.len=0) return(0); i=pos;j=0; while(i=t.len) return(i-j); /匹配成功，返回存储位置 else return(-1); ,4-28,4.3 串的基本运算的实现,3插入运算(采用动态存储串) StrInsert(HString *s, int pos, HString t) /在串s的第pos个字符之前插入串t char *temp; int i; if(poss-len) return(0); /pos不合理 if(t.len) /t非空 temp=(char*)malloc(s-len+t.len)*sizeof(char);

17、/临时变量，暂存插入后的结果 if(temp=NULL) return(0); for(i=0;ichi; for(i=0;ilen;i+) tempi+t.len=s-chi; s-len+=t.len; free(s-ch); /释放原串s s-ch=temp; /s获得相加结果 return(1); ,4-29,4.3 串的基本运算的实现,4连接运算(采用动态存储串) StrCat(HString *s,HString t) /将串t连接在串s的后面 char *temp; int i; temp=(char *) malloc(s-len+t.len)*sizeof(char); if

18、(temp=NULL) return(0); for(i=0;ilen;i+) tempi=s-chi; /复制s串 for(i=s-len;ilen+t.len;i+) /复制t串 tempi=t.chi-s-len; s-len+=t.len; free(s-ch); s-ch=temp; return(1); ,4-30,4.3 串的基本运算的实现,5串定位(采用链串存储) LString *lindex(LString s,LString t) /求串t在串s中的位置，返回指向t串起始位置的指针 LString *loc,*p,*q; loc=s; p=loc;q=t; while(p ,4-31,习 题 4,1. 简述下列每对术语的区别：空串和空白串，串常量和串变量，主串和子串，静态分配的顺序串和动态分配的顺序串。 2. 设s=I am a student，q=programer。给出下列操作的结果： StrLength(s) SubString(sub1,s,1,7) Index(s, a,4) Replace(s, student,q) 结果: （1）14 （2）sub1 =I am a （3）6 （4） s=I am a programer,