数据结构课件-第四章-串

第四章 串,学习要点 掌握串的基本操作以及串操作在不同存储结构下的实现。 理解串的模式匹配算法。,4.1 串类型的定义,1串的定义 串( string) 是由零个或多个字符组成的有限序列，一般记作S=“a1a2a3an” ，其中S为串的名字，用双引号括起来的字符序列是串值，但两边的双引号不算作串值，不包含在串中。ai(1in)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。 2空串 长度为零的串称为空串(Empty String)，它不包含任何字符，记为s=“”。通常将仅由一个或多个空格组成的串称为空白串(Blank String)。 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。,一、串和基本概念,3子串、主串 若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。 例如,串s1=“abcd”，s2=“fabcdef”，则s1为s2的子串，s2相对于s1为主串。 再如,串s1 =“is”，s2 =“This is a string”，则s1为s2的子串， s2相对于s1为主串。 s1在s2中出现了两次，其中首次出现所对应的主串位置是3。因此，称s1在s2中的序号为3。 另外: 空串是任意串的子串，任意串是其自身的子串。,二、串的基本操作,1. 串赋值 StrAssign(s,t) 表示将字符序列t赋给名为s串。 2. 求子串 SubStr (sub,s,i,len) 用sub返回串s的第i个字符起长度为len的子串。 3.求串长度 StrLength (s) 求s串的长度，即返回串s中元素的个数。 4.串联接 StrConcat(s,t) 表示将s串和t串联接起来，使t串接入s串的后面。 5.串的比较 StrCmp(s,t) 例如： result= StrCmp (“baker”,”Baker”) result0 result= StrCmp (“12”,”12”); result=0 result= StrCmp (“Joe”,”Joseph”); result0,6.判等 StrEqual(s,t) 若s和t长度相等，两个串对应位置的字符也相等，返回真值，否则返回假。 7.求子串位置 StrIndex(s,t) 若串t是串s的子串，则返回子串t在主串s中首次出现的位置；若串t不是串s的子串，则返回-1。 8.串替换 StrRep (s,t,r) 将s串中所有的子串t用串r代替。 9.串插入 StrInsert (s,t,i) 在串s的第i个位置插入串t。 10.串删除 StrDelete(s,i,len) 删除串s中从第i个字符开始连续的len个字符。,由串的定义可知，串是一种特殊的线性表，其中的每一个数据元素均是一个字符。其存储结构与线性表的存储结构类似,只不过由于组成串的结点是单个字符。串的存储结构有静态顺序存储结构、动态顺序存储结构和链式存储结构。,4.2 串的存储表示,4.2.1 串的定长顺序存储,串的顺序存储结构，也称为顺序串,可以用一组连续的存储单元来存储串的字符序列。 #define MAXLEN 256 char strMAXLEN;,1.与第二章介绍的顺序表类似，单独定义一个成员存放串的长度。 typedef struct char dataMAXLEN; int length; SeqString,如何标识 实际长度？,下标：,2.在串尾存储一个不会在串中出现的特殊字符作为串的结束符 在C语言中以字符0作为串的结束标志，这个结束标志不计入串长，但是它要占用一个字符空间。所以在这种定义下，一个串的长度小于等于MAXLEN-1。,串s=“abcde” 的顺序表示：,3.用str0存放串的长度，char strMAXLEN+1; 串值存放在str1strMAXLEN中，字符的序号与存储位置的下标值一致。,1. 求串长 功能：返回串s中元素的个数,顺序存储字符串的基本操作的实现,void StrLength(char s) int i=0; while(si!=0) i+; return i; ,2. 串的连接 功能： 把s1和s2连接成一个串，其中s1在前，s2在后,void StrConcat(char *s1,char *s2) int i,len1=StrLength(s1),len2=StrLength(s2); if(len1+len2)MAXLEN-1) printf(“长度不够!n“); else for (i=0;ilen2;i+) s1len1+i=s2i; s1len1+len2='0' ,/依次把s2的元素插入s1后,3. 求子串 功能： 从串s中的第i个字符开始，把连续len个字符组成的子串赋给另一个串。,void SubStr (char sub,char s,int i,int len) int k,slen=StrLength(s); if(i+len-1)slen|islen|len0) printf(“参数错误!/n“); else for (k=0;klen;k+) subk=si-1+k; subk='0' ,void StrInsert(char *s,char *t,int i) int k,slen=StrLength(s),tlen=StrLength(t); if (islen+1|tlen+slenMAXLEN-1) printf(“Error! n“); else for (k=slen;k=i-1;k-) stlen+k=sk; for (k=0;ktlen;k+) si-1+k=tk; ,4. 插入子串 功能：把串t插入到串s中第i个字符开始的位置,/空出字符串t的空间,/用循环将t填入到字符串s中,5. 删除子串 功能：从串s中删除第i个字符开始，长度为j的子串,void StrDelete(char *s,int i,int j) int k,slen=StrLength(s); if (i+j-1slen) printf(“Error! n“); else for (k=i+j-1;sk!='0'k+) sk-j=sk; sk-j='0' ,思考：假设串采用顺序存储，设计以下算法。 （1）把串R中所有字符按反序存放在R。 （2）从R中删除其值等于ch的所有字符。,一堆分配存储 堆式存储结构仍然用一组地址连续的存储单元存放串值，但它们的存储空间是在程序执行的过程中动态分配而得的。 堆存储结构的基本思想是：系统中将一个容量很大、地址连续的存储空间作为串值的可利用空间，称为堆空间。每当建立一个新串时，系统就从这个可利用空间中分配一个大小和串长相同的空间存储新串的串值。 系统根据每个串的长度，动态的为每个串在堆空间里申请相应大小的存储区域，这个串顺序存储在所申请的存储区域中，当操作过程中若原空间不够了，可以根据串的实际长度重新申请，拷贝原串值后再释放原空间。,4.3 串的堆式存储结构,设堆空间：char storeMAXSIZE; 自由区指针：int free; 类型定义： typedef struct int straddr; int length; HString 其串操作仍是基于“字符序列的复制”进行的,1.串赋值,void StrAssign(HString *s1,HString *s2) int i=0,len=s2-length; if(lenMAXSIZE) print(“错误，不能赋值！”) else for(i=0;istraddr=free; s1-length=len; free=free+len; ,2.求子串,void SubStr(HString *sub,HString s,int i,int len) if(lens.length-i+1) print(“参数错误，不能求子串！”) else sub-straddr=s.straddr+i-1; sub-length=len; ,HeapString *Concat(HeapString *S1,HeapString *S2) HeapString *T; int n; n=S1-length+S2-length; if(!(T-straddr=(char*)malloc(n*sizeof (char) printf (“ERROR!“); else strcpy(T-straddr,S1-straddr); strcat(T-straddr,S2-straddr); T-length=n; free(S1-straddr); free(S2-straddr); return (T); ,可以将整个内存看作一个堆空间，需要时，从内存分配串长大小的空间。例：实现两个串的连接,typedef struct char * straddr; int length; HeapString,4.4 串的块链存储表示,一结点大小为1的链式存储 和前面介绍到的单链表一样，每个结点为一个字符，链表也可以带头结点。 S=abcde的存储结构具体形式见下图。,S串的链式存储示意图,二结点大小为K的链式存储 在单链表中，如果每个结点仅存放一个字符，那么结点的指针域会很多，造成系统空间浪费 。因此采用了一种每个结点可存放多个字符的结构以提高链表的存储密度。这种结构称为块链。,head,当链表中的最后一个节点未被串值占满，通常补上0或其他的非串值字符。,结点大小为3的块链,串的块链式存储形式定义 :,#define blocksize 10 /* 用户自定义块的大小 */ typedef struct Blocknode char chblocksize; struct Blocknode *next; BlockNode; typedef struct BlockNode *head; /* 串的头指针 */ BlockNode *tail; /* 串的尾指针 */ int curlen; /* 串的当前长度 */ LString;,LString *concat(LString*s1，LString*s2) BlockNode *p，*q; p=s1-tail ; q=s2-head; p-next=q; s1-tail=s2-tail; s1-curlen+=s2-curlen; return(s1); ,例：实现两个串的连接（块链大小为1）,注：若块链大小超过1，则在串连接时，还应处理最后一个串中无效字符。,串的链式存储结构的特性： 串的链接存储结构有时称为链串。 链串的存储形式与一般的链表类似，是将存储区分成许多结点，每个结点有一个存放字符的数据域和一个存放指向下一个结点的指针域。 链串中的一个存储结点可以存储1个或多个字符，通常将链串中每个存储结点所存储的字符个数称为结点大小。 串值的存储密度=串值所占的存储位/实际分配的存储位 存储密度小，运算处理方便，如结点大小为1时，各种操作同单链表，但存储空间占用量大；存储密度大时，运算处理不方便。,一模式匹配 子串的定位运算通常称为串的模式匹配，是串处理中最重要的运算之一。设串S=“a1a2an”，串T=“b1b2bm”(mn)，子串定位是要在主串S中找出一个与子串T相同的子串。通常把主串S称为目标串，把子串T称为模式串，把从目标串S中查找模式为T的子串的过程称为“模式匹配”。 匹配有两种结