字符串的顺序存储 对于串长变化不大的字符串,可以有三种处理方案: (1)用S[]作为记录串长的存储单元( Pasca 口缺点:限制了串的最大长度不能超过256 (2)为存储串的长度,另辟一个存储的地方 口缺点:串的最大长度一般是静态给定的,不是动态申请数组空 (3)用一个特殊的末尾标记0(cC++) 口例如:C++语言的 string函数库(#nc|ude< string. h>)采 用这一存储结构 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 字符串的顺序存储 ◼ 对于串长变化不大的字符串，可以有三种处理方案： （1）用S[0]作为记录串长的存储单元 ( Pascal) ❑ 缺点：限制了串的最大长度不能超过256 （2）为存储串的长度，另辟一个存储的地方 ❑ 缺点：串的最大长度一般是静态给定的，不是动态申请数组空 间 （3）用一个特殊的末尾标记'\0‘ ( C/C++) ❑ 例如：C++语言的string函数库（＃include <string.h>）采 用这一存储结构
字符串类c class String 的存储结构 private: ∥具体实现的字符串存储结构 char *str: ∥字符串的数据表示 int size: ∥串的当前长度 例如, String s1= Hello", S1 str He size: 5 012345 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 字符串类class String的存储结构 H e l l o \0 0 1 2 3 4 5 H e l l o \0 0 1 2 3 4 5 … … size: 5 str: s1 … … size: 5 str: s1 private: // 具体实现的字符串存储结构 char *str; // 字符串的数据表示 int size; // 串的当前长度 例如， String s1 = "Hello";
字符串运算的算法实现 1.串长函数 int strlen(char *s); 2.串复制 char *strcpy(char *d, char*s); 3.串拼接 char*strcat(char *s1, char *S2) 4.串比较 int strcmp(char *s1, char*s2) 5.寻找字符 char strchr(char*d, char ch) char strrchr(char *d, char ch) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 字符串运算的算法实现 1. 串长函数 int strlen(char *s); 2. 串复制 char *strcpy(char *d, char*s); 3．串拼接 char *strcat(char *s1, char *s2); 4．串比较 int strcmp(char *s1, char *s2); 5. 寻找字符 char * strchr(char *d, char ch) char * strrchr(char *d, char ch)
C++标准串运算的实现 ∥字符串的复制 char *strcpy(char *d, char*s)i int i=0 while( s[]=t0)i d[]=s叮];i++; d[]="o; return d ∥问题? “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 C++标准串运算的实现 // 字符串的复制 char *strcpy(char *d, char *s) { int i =0; while (s[i] != '\0') { d[i] = s[i]; i++; } d[i] = '\0'; return d; } // 问题？
C++标准串运算的实现 ∥/字符串的比较 int strcmp(const char *s1, const char *s2)( inti=0: while(s2[]!="0&&s1[]="0){ if(s1[>s2[) return 1 else if (s1[] s2[i]) return -1 if(s1[]=="108&s2[l="0") return -1 else if s2[=="8&s1[l="0) return 1 return 0: “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 C++标准串运算的实现 // 字符串的比较 int strcmp(const char *s1, const char *s2) { int i = 0; while (s2[i] != '\0' && s1[i] != '\0' ) { if (s1[i] > s2[i]) return 1; else if (s1[i] < s2[i]) return -1; i++; } if (s1[i] == '\0' && s2[i] != '\0') return -1; else if s2[i] == '\0' && s1[i] != '\0') return 1; return 0; }