北京师范大学《数据结构——C语言描述》教学课件：第四章 串

第四章串 41串及其运算 是由零个或多个字符组成的有限序列,一般记为 sa1a2an3(n≥0) 其中,s是串名,用单引号(也可以是用双引号括起来的) 括起来的字符序列是串的值。a1可以是字母、数字或其他 字符;串中字符的个数n成为串的长度

4.1 串及其运算 是由零个或多个字符组成的有限序列，一般记为 s=“a1a2…an”(n0) 其中，s是串名，用单引号（也可以是用双引号括起来的） 括起来的字符序列是串的值。ai可以是字母、数字或其他 字符；串中字符的个数n成为串的长度。 第四章 串

子串:串中任意个连续的字符组成的子序列。 主串:包含子串的串相应地称为主串 位置:字符在序列中的序号。子串在主串中的位置则以子 串的第一个字符在主串中的位置来表示 相等:两个串的长度相等,并且对应位置的字符都相等。 注意区分空串与空格串的区别

子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串相应地称为主串。 位置：字符在序列中的序号。子串在主串中的位置则以子 串的第一个字符在主串中的位置来表示。 相等：两个串的长度相等，并且对应位置的字符都相等。 注意区分空串与空格串的区别

串的逻辑结构和线性表的区别: 串的数据对象约束为字符集。 2.线性表的基本操作大多以“单个元素”为操作对象,而 串的基本操作通常以“串的整体”作为操作对象。 对于串可以定义以下运算: 1.置串为一个空串; 2.判断一个串是否为空串 3.求一个串的长度; 4.将两个串拼接在一起构成一个新串; 5.在一个串中,求从串的第i个字符开始连续j个字符所 构成的子串; 6.如果串S2是S1的子串,则可求串S2在串S1中第一次出 现的位置

串的逻辑结构和线性表的区别: 1. 串的数据对象约束为字符集。 2. 线性表的基本操作大多以“单个元素”为操作对象，而 串的基本操作通常以“串的整体”作为操作对象。 对于串可以定义以下运算： 1. 置串为一个空串； 2. 判断一个串是否为空串 3. 4. 5. 在一个串中，求从串的第i个字符开始连续j个字符所 6. 如果串S2是S1的子串，则可求串S2在串S1中第一次出 现的位置

4.2串的存储表示 1.定长顺序表示 # define maXnum1000/米串允许的最大字符个数*/ struct Seqstring/*顺序串的类型*/ char c[MAXNUMI int n: I SeqString, *PSeqString

1. 定长顺序表示 #define MAXNUM 1000 /* 串允许的最大字符个数 */ struct SeqString /* 顺序串的类型 */ { char c[MAXNUM]; int n; }SeqString, *PSeqString; 4.2串的存储表示

算法4.1求顺序表示的串的子串 PSegString subStr seg (pseqstring s, int i, int j) 所指的顺序串中第i(1>0)个字符开始连续j个字符所构成的子串 PSeqstring s1 in t Im, s1= createNullStr seq() f (s1==NULL) return NULL f(i>0&&in&j>0) if( s>nn-i+ for(k=0; kc[k]=s->c[i+k-1]; 1>c[j=\0’; 1->n else s1->c[0]=\0’; return(s1)

PSeqString subStr_seq(PSeqString s,int i,int j) /* 求从s所指的顺序串中第i(i>0)个字符开始连续j个字符所构成的子串 */ { PSeqString s1; int k,m; s1 = createNullStr_seq( ); if (s1==NULL) return NULL; if ( i>0 && in && j>0 ) { if ( s->n n -i+1; for (k=0;kc[k]=s->c[i+k-1]; s1->c[j]='\0' ; s1->n =j; } else s1->c[0]='\0' ; return(s1); } 算法4.1 求顺序表示的串的子串

算法4.2创建空顺序串 PSeaString createNullStr seq( void PSeqstring pstr pstr=(PSeqString) malloc(sizeof (struct SegString)) if (pstr==NULL printf( out of space!! \n") e⊥se pstr->n=0 return pstr

PSeqString createNullStr_seq( void ) { PSeqString pstr; pstr=(PSeqString)malloc(sizeof(struct SeqString)); if (pstr==NULL) printf("Out of space!!\n"); else pstr->n = 0; return pstr; } 算法4.2 创建空顺序串

2.变长顺序表示 typedef struct char ch length: JHString; void StrAssign(HString*str, char *chars) void StrCopy(hstring dest, HString src) void StrCopyN(HStringdest, HString Src, int n) BOOL ISStrEmpty(HString str) int StrCompare(HString strl, HString str2) int StrEngth(HString str) void Clear String(HString * str); Status StrCat(HString*dest, HString str1, HString str2)

typedef struct { char *ch; int length; }HString; void StrAssign(HString *str, char *chars); void StrCopy(HString *dest, HString src); void StrCopyN(HString *dest, HString src, int n); BOOL IsStrEmpty(HString str); int StrCompare(HString str1, HString str2); int StrLength(HString str); void ClearString(HString *str); Status StrCat(HString *dest, HString str1, HString str2); …… 2. 变长顺序表示

void StrAssign (HString *str, char*chars)i char *p=chars int length, 1; if(str->ch) /*释放已有空间 free(str->ch); str->ch= NULL: str->length =0; whil(p!=#)p++;/求串长* length=p-chars-l if(length==0) str->length=0 else{重新申请空间 str->length=length str->ch=(char *)malloc(sizeof(char)"length); for(i=0; ichi= charsi /s End of StrAssigno/

void StrAssign(HString *str, char *chars) { char *p = chars; int length, i; if(str->ch) /* 释放已有空间 */ { free(str->ch); str->ch = NULL; str->length = 0; } while(*p!=‘#’) p++ ; /* 求串长 */ length = p - chars - 1; if(length == 0) str->length = 0; else{ /* 重新申请空间*/ str->length = length; str->ch = (char *)malloc(sizeof(char)*length); assert(str->ch); for(i=0; ich[i] = chars[i]; } } /* End of StrAssign() */

void StrCopy(HString *dest, HString src) char int if(dest->ch free(dest->ch); dest->ch= NULL; p=(char *)malloc(sizeof(char)*src length); for(i=0; ich=p dest->length=srclength;

void StrCopy(HString *dest, HString src) { char *p; int i; if(dest->ch) { free(dest->ch); dest->ch = NULL; } p = (char *)malloc(sizeof(char) * src.length); assert(p); dest->ch = p; dest->length = src.length; for(i=0; ich = p; dest->length = src.length;

提取子串的算法示例 pos=2, len=3 pos=5, len=4 in fini ty infinity 超出 f i n ity pos+len -1 posten -1 curLen-1 ≥ curlen

提取子串的算法示例 pos+len -1 pos+len -1  curLen-1  curLen i n f i n i t y i n f i n i t y pos = 2, len = 3 pos = 5, len = 4 f i n i t y 超出