数据结构课件第4章串.ppt

《数据结构课件第4章串.ppt》由会员分享，可在线阅读，更多相关《数据结构课件第4章串.ppt（40页珍藏版）》请在三一文库上搜索。

1、计算机上的非数值处理的对象基本上都是字符串数据。字符串 (string) 一般简称为串。,1,第,4,章,串,4.1 串的逻辑结构,4.2 串的存储结构,例4-1 x = computer ,以下是串的 3 个例子：,2,例4-2 y = student-1 ,例4-2 z = data structure ,串的定义,串的基本操作,3,其中：,串是由零个或多个字符组成的有限序列。记为： s = a1 a2 an （ n 0 ）,s 是串的名，用单引号括起来的字符序列是串的值；,ai（1in）可以是字母、数字或其他字符；,n 是串中字符的数目，称为字符串的长度。,4.1.1 串的定义,零个字符

2、的串称为空串 (null string)，它的长度为零。用 “” 来表示空串。,4,当且仅当两个字符串的值相等时，也就是说，只有当两个字符串的长度相等，并且各个对应位置上的字符都相等时，则称这两个字符串是相等的。,串中的任意连续的字符组成的子序列称为该串的子串；包含子串的串相应地称为主串。,通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。,例4-4 假设 a 、b 、c 、d 为如下 4 个字符串： a = beijing，b = bei，c = jing，d = beijing 则：,a 的长度为 7，b 的长度为 3，c 的长度为

3、4，d 的长度为 8； b 和 c 都是 a 和 d 的子串，且 b 在 a 和 d 中的位置都是 1，而 c 在 a 中的位置是 4 ，在 d 中的位置是 5 。,串 a ，b ，c ，d 彼此都不相等。,5,6,7,4.1.2 串的基本操作,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集 (character set)。,但是，串的基本操作和线性表有很大的差别。在线性表的基本操作中，大多是以 “单个元素” 作为操作对象，比如：在线性表中查找某个元素、在线性表中求取某个元素、在线性表某个位置上插入一个元素以及删除一个元素等；而在串的基本操作中，通常以 “串的整体” 作为操作

4、对象，比如：在串中查找某个子串、在串中求取某个子串、在串的某个位置上插入一个子串以及删除一个子串等。,8,在串的 13 种基本操作操作中，以下 5 种操作构成串类型的最小操作子集，即：这些操作不可能利用其他操作来实现：, 串赋值 StrAsign 串比较 StrCompare 求串长 StrLength 串连接 StrCat 求子串 SubString,而其他串操作（除了串清除操作 StrClear 和串销毁操作 StrDestroy外）均可以在这个最小操作子集上实现。,9,如果在程序设计语言中，串只是作为输入或者输出的常量出现，则只需要存储此串的串值，即字符序列即可。但是在多数非数值处理的程

5、序中，串也以变量的形式出现。串有 3 种机内表示方法。,定长顺序存储结构,10,堆分配存储结构,块链存储结构,串的定长顺序存储表示类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照予定义的大小，为每个定长的串变量分配一个固定长度的存储区，则可以用定长数组描述。,予定义大小 MAXSTRLEN 为串变量分配一个固定长度的存储区,11,4.2.1 定长顺序存储结构,1. 定长顺序存储表示,# define MAXLEN 40 /* 用户可在 40以内定义最大串长*/ typedef struct char chMAXLEN; int len; S

6、String ; /*为定长顺序存储结构类型名*/,12,(1) 串联接 StrCat(SString *s,SString t), 算法思想 假设 SString *s,SString t 。将串t连接在串s的后面，需要进行相应的 “串值复制” 操作即可，对超长部分实施 “截断” 操作。 基于串 s和串 t 长度的不同情况，新串（存于s中） 值的产生可能有如下 3 种情况：,13,2. 基本操作在定长顺序存储上的实现,s-len+t.lenMAXLEN 得到的 串是正确的结果。,s-lenlen+t.lenMAXLEN 将 t一部分截断，得到的 新串只包含 t 一个子串。,s-len=MAX

7、LEN 得到的 新串并非联接结果，而和 s相等。,14,s串长s-len,t串长t.len,新串s的串长s-len+t.len,MAXLEN,s,剩 余 空 间,15,s-len+t.lenMAXLEN,剩 余 空 间,s串长s-len,t串长t.len,s,新串s长,MAXLEN,t中被截去的字符序列,16,S-lenlen+t.lenMAXLEN,s串长s-len,t串长t.len,s,MAXLEN,新串s的长度,t串被全部截去,17,s-len=MAXLEN,Int strCat( SString *s, SString t) /* 用 s返回由 s和 t联接而成的新串。*/ / *如果

8、没有截断，则返回flag=1，否则返回 flag=0。*/,if (s-len+t.lenlen;ilen+t.len;+) s-chi= t.chi-s-len; s-len+=t.len; flag=1; if 结束, 算法编写,18,else if (s-lenlen; ichi= t.ch i-s-len; s-len=MAXLEN; flag=0; ,else flag=0; /* s-len= MAXLEN t被完全截断（仅取 S）*/ return(flag); ,19,(2) 求子串 SubString ( SString *Sub, SString S, pos, len )

9、, 算法思想 求子串的过程即为复制字符序列的过程，将串 S 中下标是pos 的字符开始、长度为 len 的字符序列复制到串 Sub 中。,求子串的操作不会出现截断的情况，但有可能产生用户给出的参数不符合操作的初始条件的情况，当参数非法时，返回 0。,20,SubString ( SString *Sub, SString S, int pos, int len) /* 用 Sub 返回串 S 的下标 pos 起长度为 len 的子串。*/,if ( pos s.len| len s.len-pos ) sub-len=0; return(0); , 算法编写,else for (i=0;ich

10、i=s.chi+pos; sub-len=len; return(1); , /* SubString;,21,StrIndex (SString S, int pos, SString t) /* 求从主串s的下标pos起,串t第一次出现的位置, 成功返回位置序号,不成功返回-1*/,int i, j, start; if(t.len=0) return (0); start=pos; i=start, j=0; while (is.len&jt.len),(3)定位函数,if (s.chi=t.chj) (i+; j+;) else start+; i=start;j=0; ,If (j=

11、t.len) return (start); else return(-1),22,3. 定长顺序存储结构串操作的特点, 如果在操作的过程中出现串值序列的长度超过上界 MAXLEN 时，约定使用 “截尾” 法处理。,克服第点弊病的方法是：不限定串长的最大长度，即动态分配串值的存储空间。,23, 实现串操作的基本操作为 “字符序列的复制” ，操作的时间复杂度基于复制的字符序列的长度。,堆分配存储表示的特点是，仍然以一组地址连续的存储单元存储串值的字符序列，但是它们的存储空间是在程序执行过程中动态分配而得的。,在 C 语言中，存在一个称之为 “堆” 的自由存储区，并且由 C 语言的动态分配函数 m

12、alloc( ) 和 free( ) 来管理。,约定字符串常量以在串值后面加 “0” 表示串值的终结。,24,4.2.2 堆分配存储结构,自由存储区 “堆” 示意图,使用 malloc 函数动态分配存储空间,基址 T.ch,使用 free 函数释放存储空间,25,1. 堆分配存储表示,typedef struct char *ch; /* 若是非空串，则按串长分配存储区，否则 ch 为 NULL*/ int len; HString ; /*串的堆分配存储结构的类型名*/,26,(1)堆串赋值函数,StrAssign ( HString *s , char *tral ) /* 串常量 tra

13、l的值赋给堆串s */,int len, i=0; if (s-ch!=NULL ) free (s-ch); /*释放 s原有空间*/ While (tral i!=0) i+; /* 求 tral的长度 i*/ len=i;,if ( len), (s-ch = ( char * ) malloc (len) ; /*为堆分配存储空间*/ if ( s-ch=NULL) return(0); for(i=0; ichi=trali; else s-ch = NULL /* 串 tral为空串*/ s-len=len; retrun(1); ,27,2. 基本操作在堆分配存储上的实现,(2)

14、 求串长,int StrLength ( HString S ) / 返回 S 的元素个数 return S.len; / StrLength,28,(3) 串比较,int StrCompare ( HString S, HString T ) / S 和 T 从第一个字符开始比较，直到出现第一个不相等的字符： / 如果 S i T i ，则 S T，返回值 0； / 如果 S i T i ，则 S T，返回值 0； / S 和 T 长度相等，所有字符相等时，S = T，返回值 = 0。,for ( i = 0; i S.len ,return S.len T.len; / StrCpmpar

15、e,29,(4) 清空串,Status ClearString ( HString &S ) / 将 S 清为空串,if ( S.ch ) free ( S.ch ); S.ch = NULL; / if 结束,S.len = 0; return OK; / ClearString,30,(5) 串插入(在S中下标为pos前插入串t),0,pos,s-len-1,t-len-1,0,s-len+t-len-1,pos+t-len,31,StrInsert ( HString *s, int pos, HString *t) /*在串 s的下标 pos 之前插入串 t。*/,if ( pos s

16、-len) return ERROR;,if (t-len ) /* 如果 T 非空，则重新分配空间，插入t*/,return (TRUE); /*StrInsert*/,if ( ! (s-ch = ( char * ) realloc (s-ch, (s-len +t-.len ) exit (FALSE); /* 存储分配失败*/,for ( i = s-len-1; i = pos-1; i- ) /*为插入 T 而腾出位置*/ s-ch i+t-len = s-ch i ;,For(i=pos;ilen;i+) s-chi=t-chi-pos /* 插入 T*/ s-len + =t

17、-len; /* 更新串 S 的长度*/ /* if 结束*/,32,3. 堆分配存储结构串操作的特点,33,堆分配存储结构表示时串操作的基本操作仍然是基于 “字符序列的复制” 进行的，操作的时间复杂度基于复制的字符序列的长度。 定长顺序存储表示和堆分配存储表示通常为高级程序设计语言所采用。由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，在操作中对串长又没有任何限制，更显灵活。因此，在串的处理应用程序中常常被采用。,和线性表的链式存储结构相类似，也可以采用链表方式存储串值。由于串结构的特殊性 结构中的每个数据元素是一个字符，则用链表存储串值时，存在一个 “结点大小” 的问题，即每个结点

18、可以存放一个字符，也可以存放多个字符。,34,4.3.2 块链存储结构,结点大小为 1（即每个结点存放一个字符）的链表：,结点大小为 4（即每个结点存放四个字符）的链表：,35,为了便于进行串的操作，当以链表存储串值时，除了头指针外还可以附设一个尾指针展示链表中的最后一个结点，并给出当前串的长度。称如此定义的串存储结构为块链结构。,1. 块链存储表示,# define BLOCK_SIZE 4 / 可由用户定义块大小,typedef struct Block / 块结构定义 char ch BLOCK_SIZE ; / 块内字符数组 struct Block *next; / 指针，指向下一个块 Block;,typedef struct / 块链结构定义 Block *head, *tail; / 串的头指针和尾指针 int len; / 串的当前长度 BLString; / 块链结构的类型名,36,head,BLOCK_SIZE = 4,tail,len,37,38,2. 块链存储的存储密度,串值的存储密度：,存储密度小（即结点中所含字符少时），运算处理方便，但是存储占用量大。 存储密度大（即结点中所含字符多时） ，存储占用量小，但是运算处理不便。,39,在链式存储结构中，结点大小的选择和顺序存储结构的格式选择一样重要，它直接影响串处理的效率。,40,