0.的基本操作 第四章串 示例」用串的基本操作(1)至(5)实现定位函数ndex(s,t)。 int Index( string s, string t 若串s中存在和t相等的子串,则返回第一个子串在主串中的位置,否则返三 回零 n= Length(s);m= Length(t);i=1;//m不等于0 while( i s n-m+1 if( Equal( Substr(s, i, m )t)) return i 1se1+十 return 0 F//index 第11页
第四章 串 第11页 示例1 用串的基本操作(1)至(5)实现定位函数Index(s,t)。 int Index( string s, string t ) /*若串s中存在和t相等的子串，则返回第一个子串在主串中的位置，否则返 回零*/ { n = Length(s); m = Length(t); i = 1; //m不等于0 while( i ≤ n-m+1 ) if( Equal( Substr( s, i, m ), t )) return i; else i++; return 0; } //index ⚫ 串的基本操作
0的基本操作 第四章串 c中预定义字符串标准函数和标准过程 字符串标准函数 一函数名意义 结果类型 strcat连接字符串序列 char strcpy复制一个字符串char* sten返回串的动态长度mt 还有: strcmp, strcmpi, strrchr, 参见: String. h 第12页
第四章 串 第12页 C中预定义字符串标准函数和标准过程 字符串标准函数 函数名 意 义 结果类型 strcat 连接字符串序列 char * strcpy 复制一个字符串 char * strlen 返回串的动态长度 int 还有：strcmp, strcmpi, strrchr, … … 参见： String.h ⚫ 串的基本操作
0的链式存储结构 第四章串 用线性链表的方式存储串值一H,一一 结点大小问题 )结点大小等于1,即一个结点存放一个字符 head DATA「-S 优点:便于实现插入、删除等操作 点:浪费存储空间,存储利用率最多12 2)结点大小等于4,即一个结点存放4个字符 head DATA、 TRUCTU4RES■ 优点:存储效率较高 点:实现插入、删除等操作较复杂 第13页
第四章 串 第13页 用线性链表的方式存储串值 结点大小问题 ⚫ 串的链式存储结构 D A T A S ^ head 1）结点大小等于1，即一个结点存放一个字符 优点：便于实现插入、删除等操作 缺点：浪费存储空间，存储利用率最多1/2 DATA STR UCTU RES ^ head 2）结点大小等于4，即一个结点存放4个字符 优点：存储效率较高 缺点：实现插入、删除等操作较复杂 ^ H
0的链式存储结构 第四章串 用块链结构存储串值 为便于进行串的操作,当以链表存储串值时,给出头、尾 指针,加当前串的长度。称如此定义的串存储结构为块链结构 设尾指针的目的是为了便于进行联接操作 块链结构的说明 # define CHUNK size1000用户定义的结点大小 typedef struct i char ch[ CHUNK SIZE];块大小 chunk *next ∥指针 1 chunk; typedef struct chunk*head,*七ai1; ∥、尾指针 int length ∥长度 F STrings STring clsti 第14页
第四章 串 第14页 用块链结构存储串值 为便于进行串的操作，当以链表存储串值时，给出头、尾 指针，加当前串的长度。称如此定义的串存储结构为块链结构 。 设尾指针的目的是为了便于进行联接操作。 块链结构的说明 #define CHUNK_SIZE 1000 //用户定义的结点大小 typedef struct { char ch[CHUNK_SIZE]; //块大小 chunk *next; //指针 } chunk; typedef struct { chunk *head，*tail; //头、尾指针 int length; //长度 } LString; LString clst; ⚫ 串的链式存储结构
第四章串 0的式存储结构 用块链结构存储串值三 块链结构示意图 DATA STRUCTU RES#A 一头尾长度 clst 15 串值所占存储空间 存储密度= 实际分配的存储空间 这种存储方式对某些操作比较方便,总的来说仍较复杂 第15页
第四章 串 第15页 clst 15 DATA STR UCTU RES# ^ 头 尾 长度 块链结构示意图 ⚫ 串的链式存储结构 用块链结构存储串值 串值所占存储空间 存储密度 = —————————— < 1 实际分配的存储空间 这种存储方式对某些操作比较方便，总的来说仍较复杂