第4章串和数组.ppt

1、17:49:40,第4章 串和数组 String and Array (课后复习版) 主讲：顾为兵 作者声明：课件仅限本班教学参考用，不对外发布,17:49:40,第五章 串和数组(String and Array) 5.1 串的定义 5.2 串的表示与实现 5.3 模式匹配算法 5.4 数组,17:49:40,5.1 串的定义,定义：串是由n(n0)个字符组成的有限序列，记为： s=“a0a1.an-1” n-串长 空串： n=0, s“ ” 空格串： n0, s=“”,串是一种特殊的线性表-每个数据元素都是字符,17:49:40,串的基本运算: 串赋值：StrAssign( m = Str

2、length(T); i = pos; while( i=n-m ) SubString (sub, S, i, m); if ( StrCompare(Sub, T) != 0 ) i+; else return i; /匹配成功，返回子串的位置 return -1; /S中不存在与T相等的子串 ,17:49:40,每种高级语言都提供一组字符串操作函数 C语言在函数库string.h中，定义了很多字符串函数，比如： 串比较：strcmp(s1, s2), strncmp(s1, s2, len) 串复制：strcpy(s1, s2), strdup(s) 串连接：strcat(s1, s2)

3、, strncat(s1, s2, len) 串查找：strchr(s, c) 串长度：strlen(s) 。,17:49:40,第五章 串和数组(String and Array) 5.1 串的定义 5.2 串的表示与实现 5.3 模式匹配算法 5.4 数组,17:49:40,5.2 串的表示与实现 5.2.1 定长顺序存储 5.2.2 堆分配存储 5.2.3 链式存储,17:49:40,5.2.1 定长顺序存储 用定长静态数组存储串： #define maxsize 255 /串的最大长度 char s1maxsize+1; char s2100; 程序运行期间，数组的大小已经固定，不能变

4、化,17:49:40,0号单元存放串的长度,串长超过255的部分将被截断,S,串长的表达方式1：,串长的表达方式2：,用特殊的符号作为串的结束符,S,17:49:40,基本运算举例： int strlen（char *S) /求串S的长度 int n=0; char *p=S; while(*p+!=0) n+; return n; ,17:49:40,基本运算举例： void strcat（char *T, char *s1, char *s2) /将串s1和s2联结，结果存放入字符串T中 j=0; k=0; while(s1j!=0) Tk+=s1j+; /抄s1 j=0; while(s

5、2j!=0) Tk+=s2j+; /抄s2 Tj=0; 要注意字符数组的越界问题，由调用这个函数的用户来保证,17:49:40,5.2 串的表示与实现 5.2.1 定长顺序存储 5.2.2 堆分配存储 5.2.3 链式存储,17:49:40,5.2.2 堆(Heap)分配存储 运行时，用动态分配的数组来存储串。 C语言中, 用new申请，delete释放空间。 运行期间可以根据实际需要申请空间,17:49:40,基本运算举例： void strcat（char * ,17:49:40,串操作举例： StrDelete Status StrDelete(char * ,17:49:40,5.2

6、串的表示与实现 5.2.1 定长顺序存储 5.2.2 堆分配存储 5.2.3 链式存储,17:49:40,5.2.3 链式存储,head,用普通链表，存储密度低,用块链结构，操作困难,17:49:40,第五章 串和数组(String and Array) 5.1 串的定义 5.2 串的表示与实现 5.3 模式匹配算法 5.4 数组,17:49:40,5.3 朴素的模式匹配算法 Index( S, T, pos ) S-主串 T-模式串 pos-从第pos个字符开始匹配 在主串S中，自pos位置开始，查找与模式串T相等的子串。如果这样的子串存在，返回其第一次出现的位置。,17:49:40,模式串

7、T,主串S,17:49:40,模式串P,主串S,17:49:40,模式串P,主串S,17:49:40,模式串P,主串S,17:49:40,一般而言：,i+,j=0,17:49:40,P96算法5.6朴素的模式匹配算法 int Index(char *S, char *T, int pos) /检测主串S在位置pos之后是否存在与T相同的子串 /存在，则返回该子串的位置；否则，返回1 int i=pos, j=0; while(Si+j ,17:49:40,朴素算法的时间分析： 最好的情形：每次都是在j0时失配, 如,设在第 i 个位置上匹配成功，共进行了i+m次比较；i的可能取值范围是0.n-m, 故平均比较次数为： 时间复杂度为O(n+m),主串,模式串,前i1次匹配进行了i1次比较；第i次匹配进行了m次比较,长度n,长度m,17:49