数据结构课件 chapter04串.ppt

第四章 串、数组和广义表 本章目录 4.1 串的定义和操作 4.2 串的存储结构 4.3 串的模式匹配算法 4.4 串操作应用举例 4.5 数组 4.6 矩阵的压缩存储 4.7 广义表 4.8 小结 串的定义 定义：串（string），或称字符串，是由零个或多个字符组成的有限序列。一般记为： s=“a0a1a2…an-1”(n=0) s是串名。 字符序列”a0a1a2…an-1”是串的值，必须用双引号作为定界符。 ‘ai’是串中的某个字符，引用时用单引号作为定界符。 串中字符的数目n称为串长。串长为0（n=0）的串称为空串（null string）。 串的定义 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串。 子串在主串中的位置：子串的第一个字符在主串中的位置（字符在串中的位置：字符在串中的序号）。 例如：串A=“China Beijing”，B=“Beijing”，C=“China”，D=“ina B”，E=“iij” 其中，B、C、D、E中哪些是A的子串，哪些不是。 如果是A的子串，则在A中的位置分别是多少。 串的定义 两个串相等 两个串的长度相等 对应位置的字符相同 注意 空串：n=0的串。 空格串：由一个或多个空格组成的串。 空串的长度一定为0，空格串的长度一定大于0，但具体值由空格的个数决定。 串的顺序存储 串的顺序存储是用一组地址连续的存储单元存储串中的字符序列。 Q：串是若干个字符组成的一个字符序列，那么对于一个串，如何判断串的结束呢？ A1：字符串结束标志“\0”。 A2：用数组下标为0的元素存放串的实际长度。 串赋值：assign(s,t) 将一个值t赋给串s void assign(char s[ ],char t) {int i; printf(“Please input the position:”); scanf(“%d”,i); s[i]=t; } 求串长：strlen(s) 求出给定串s的长度（实际长度） int strlen(char s[ ]) {int len=0,i=0; while(s[i]!=‘\0’) {len++; i++; } return len; } 串复制：strcopy(s,t) 将串t复制给串s void strcopy(char s[ ],char t[ ]) {int tlen,i; tlen=strlen(t); /*调用函数strlen求出串t的实际长度*/ for(i=0;itlen;i++) s[i]=t[i]; /*将串t中的每个字符对应赋值给串s*/ s[tlen]=‘\0’; } 串相等：equal(s,t) 两个串的长度相等 对应位置上的字符相同 构造函数 int equal(char s[ ],char t[ ]) {int slen=strlen(s),tlen=strlen(t),i; if(stlen!=tlen) return 0; else {for(i=0;islen;i++) {if(s[i]!=t[i]) {return 0; break;} else continue; } if(i==slen) return 1; } } 串连接：strcat(s1,s2) 将s1和s2连接，结果放在s1中。 void strcat(char s1[ ],char s2[ ]) {int len1=strlen(s1),len2=strlen(s2),i,j; for(i=len1,j=0;jlen2;i++,j++) s1[i]=s2[j]; s1[i]=‘\0’; } 串连接：strcat(s,s1,s2) 将s1和s2连接，结果放在s中。 void strcat(char s[ ],char s1[ ],char s2[ ]) {int len1=strlen(s1),len2=strlen(s2),i=0,j; j=0; while(s1[j]!=‘\0’) {s[i]=s1[j]; i++; j++;} j=0; while(s2[j]!=‘\0’) {s[i]=s2[j]; i++; j++;} s[i]=‘\0’; } 求子串：substr(s,i,k) 返回串s的第i个位置开始的k个字符组成的串 char *substr(char s[ ],int i,int k) {char *t; int j,n; for