第四章 串和数组（一） 1/.

Presentation on theme: "第四章 串和数组（一） 1/."— Presentation transcript:

1 第四章 串和数组（一） 1/

2 串 教学目标 掌握串的定义 掌握串的表示及其操作实现 掌握字符串的朴素模式匹配算法 教学内容 串类型的定义 串的表示与实现 定长顺序存储表示
堆分配存储表示 串的块链存储表示 字符串的朴素模式匹配算法 2/ 计算机科学与技术系

3 串 串和线性表的区别 串的数据对象约束为字符集。
线性表的基本操作大多以“单个元素”为操作对象，而串的基本操作通常以“串的整体”作为操作对象。 如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。 3/

4 4.1串类型定义 是由零个或多个字符组成的有限序列，一般记为： s = ‘ a1a2…an ’ (n0)
长度为0的串称为空串。 注意区分空串与空格串的区别。 4/

5 4.1串类型定义 串的相关概念： 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串相应地称为主串。
位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。 串相等：仅当两个串的长度相等，并且对应位置的字符都相等。 5/

6 4.1串类型定义 对于串可以定义以下运算： 串赋值：StrAssign(&T ，chars)； 串比较：StrCompare(S，T);
求串长：StrLength( S )； 串联接：Concat( &T，S1，S2 )； 求子串：SubString( &Sub，S，pos, len ) 6/

7 4.1串类型定义 // 子串定位运算 int Index(String S, String T, int pos){ String sub;
if( pos>0 ) { n=StrLength(S); m=StrLength(T); i=pos; while( i <= n-m+1 ){ SubString( sub, S, i, m ); if( StrCompare(sub,T) != 0 ) i++; else return i; } return 0; 7/

8 4.2 字符串的存储及其实现 定长顺序存储表示 串的块链存储表示 堆分配存储表示

9 4.2串的表示与实现 定长顺序表示（静态存储分配） 用定长的字符数组来描述串的定长顺序存储结构。 #define MAXSTRLEN 256
typedef char SString[MAXSTRLEN+1]; 当串值长度超过数组长度时，串值将被“截断” 9/

10 4.2串的表示与实现 串长的表示方法： 在下标为0的数组分量中存放串的长度值 在串尾加一个结束标记（不计入长度）
定义一个含有两个成员的结构体类型 10/

11 4.2串的表示与实现 #define MAXNUM 1000 // 串允许的最大字符个数 typedef struct {
char c[MAXNUM]; int length; // 串的长度 }SqString, 11/

12 // 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE
Status Concat(SString &T, SString S1, SString S2){ int i; if(S1[0]+S2[0] <= MAXSTRLEN){ // 未截断 for(i=1;i<=S1[0];i++) T[i]=S1[i]; for(i=1;i<=S2[0];i++) T[S1[0]+i]=S2[i]; T[0]=S1[0]+S2[0]; return TRUE; } else if(s1[0]<MAXSTRLEN) { // 截断S2 for( i=1; i<=S1[0]; i++ ) for(i=1; i<= MAXSTRLEN-S1[0]; i++) T[0]=MAXSTRLEN; return FALSE; } else //截断S1 { for( i=0; i<=MAXSTRLEN; i++ ) T[i]=S1[i]; return FALSE; } } 12/

13 if(pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
// 用Sub返回S中从第pos个字符开始长度为len的字符序列。 Status SubString(SString &Sub, SString S, int pos,int len) { int i; if(pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1) return ERROR; for(i=1;i<=len;i++) Sub[i]=S[pos+i-1]; Sub[0]=len; return OK; } 13/

14 4.2串的表示与实现 堆分配存储表示 这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但存储空间的长度是在程序执行过程是根据串的实际长度而动态分配的。 typedef struct{ char *ch; int length; } HString; 14/

15 4.2串的表示与实现 串的堆分配存储结构的优点： 有顺序存储结构的优点，可随机存取字符。 对串长没有限制，显得灵活。 15/

16 // 生成一个其值等于串常量chars的串T Status StrAssign(HString &T, char *chars) {
int i, j; if(T.ch) free(T.ch); // 释放T原有空间 i = strlen(chars); // 求chars的长度i if( !i ) { // chars的长度为0 T.ch=NULL; T.length=0; } else{ // chars的长度不为0 T.ch=(char*)malloc(i*sizeof(char)); // 分配串空间 if(!T.ch) exit(OVERFLOW); for( j=0; j<i; j++ ) // 拷贝串 T.ch[j] = chars[j]; T.length = i; return OK; 16/

17 Status StrInsert(HString &S, int pos, HString T) {
// 在串S的第pos个字符之前插入串T Status StrInsert(HString &S, int pos, HString T) { int i; if( pos<1 || pos>S.length+1 ) // pos不合法 return ERROR; if( T.length ) { // T非空,则重新分配空间,插入T S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)); if(!S.ch) exit(OVERFLOW); for( i=S.length-1; i>=pos-1; --i ) // 为插入T而腾出位置 S.ch[i+T.length] = S.ch[i]; for( i=0; i<T.length; i++ ) S.ch[pos-1+i]=T.ch[i]; // 插入T S.length += T.length; } return OK; 17/

18 // 用Sub返回串S的第pos个字符起长度为len的子串。
Status SubString(HString &Sub, HString S,int pos,int len) { int i; if( pos<1 || pos>S.length || len<0 || len>S.length-pos+1) return ERROR; if( Sub.ch ) free(Sub.ch); // 释放旧空间 if( !len ) { // 空子串 Sub.ch=NULL; Sub.length=0; } else{ // 完整子串 Sub.ch=(char*)malloc(len*sizeof(char)); if(!Sub.ch) exit(OVERFLOW); for(i=0;i<=len-1;i++) Sub.ch[i]=S.ch[pos-1+i]; Sub.length=len; return OK; 18/

19 // 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0 int StrCompare(HString S, HString T){
int i; 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; } 19/

20 4.2串的链式存储结构 顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。 一个链串由头指针唯一确定。 这种结构便于进行插入和删除运算，但存储空间利用率太低。 20/

21 4.2串的链式存储结构 为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小。 21/

22 4.2串的链式存储结构 串的块链存储表示： #define CHUNKSIZE 4 // 可由用户定义的块大小
typedef struct Chunk { char ch[CHUNKSIZE]; struct Chunk *next; } Chunk ; typedef struct { Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 } LString ; 22/

23 4.2串的链式存储结构 串的存储密度表示为： 说明：存储密度小，运算方便，但存储效率低 23/

24 4.3 字符串的模式匹配 寻找字符串p在字符串t中首次出现的起始位置称为字符串的模式匹配，其中称p为模式(pattern），t为正文(text)，t的长度远远大于p的长度。

25 朴素的模式匹配算法 朴素模式匹配算法的基本思想是：用p中的每个字符去与t中的字符一一比较： 正文t： t1 t2 …… tm……tn 模式p： p1 p2 …… pm 如果t1=p1,t2=p2,…..tm=pm，则模式匹配成功；否则将p向右移动一个字符的位置，重新用p中的字符从头开始与t中相对应的字符依次比较，即： t1 t2 t3 …… tm tm+1……tn p1 p2…… pm-1 pm 如此反复，直到匹配成功或者p已经移到使t中剩下的字符个数小于p的长度的位置，此时意味着模式匹配失败，表示t中没有子串与模式p相等，我们约定返回-1代表匹配失败。

26 朴素模式匹配算法的具体实现如下： Int Index(SString S, SString T, int pos) {
i=pos; j=1; while ( i<=S[0] && j<=T[0] ) { if (S[i] = = T[j] ) {++i, ++j} //继续比较后续字符 else {i=i-j+2; j=1;} //指针回溯到 下一首位，重新开始匹配 } if(j>T[0]) return i-T[0]; //子串结束，说明匹配成功 else return 0; }//Index 26/

27 小结 串的定义 串的存储结构及操作实现 字符串的朴素模式匹配算法 27/

28 作业 1.设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回正数；若S1=S2时则返回0；若S1<S2时则返回负数。 2.用顺序存储结构实现在字符串S中删除所有其值等于ch的字符的算法。 28/