数据结构课件 chapter04串.ppt

1、第四章 串、数组和广义表,本章目录,4.1 串的定义和操作 4.2 串的存储结构 4.3 串的模式匹配算法 4.4 串操作应用举例 4.5 数组 4.6 矩阵的压缩存储 4.7 广义表 4.8 小结,串的定义,定义：串（string），或称字符串，是由零个或多个字符组成的有限序列。一般记为： s=“a0a1a2an-1”(n=0) s是串名。 字符序列”a0a1a2an-1”是串的值，必须用双引号作为定界符。 ai是串中的某个字符，引用时用单引号作为定界符。 串中字符的数目n称为串长。串长为0（n=0）的串称为空串（null string）。,串的定义,子串：串中任意个连续的字符组成的子序列。

2、 主串：包含子串的串。 子串在主串中的位置：子串的第一个字符在主串中的位置（字符在串中的位置：字符在串中的序号）。 例如：串A=“China Beijing”，B=“Beijing”，C=“China”，D=“ina B”，E=“iij” 其中，B、C、D、E中哪些是A的子串，哪些不是。 如果是A的子串，则在A中的位置分别是多少。,串的定义,两个串相等 两个串的长度相等 对应位置的字符相同 注意 空串：n=0的串。 空格串：由一个或多个空格组成的串。 空串的长度一定为0，空格串的长度一定大于0，但具体值由空格的个数决定。,串的顺序存储,串的顺序存储是用一组地址连续的存储单元存储串中的字符序列。

3、 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”, ,求串长：strlen(s),求出给定串s的长度（实际长度） int strlen(char s ) int len=0,i=0; while(si!=0) len+; i+; return len; ,串复制：strcop

4、y(s,t),将串t复制给串s void strcopy(char s ,char t ) int tlen,i; tlen=strlen(t); /*调用函数strlen求出串t的实际长度*/ for(i=0;itlen;i+) si=ti; /*将串t中的每个字符对应赋值给串s*/ stlen=0; ,m,n,p,q,0,串相等：equal(s,t),两个串的长度相等 对应位置上的字符相同 构造函数 int equal(char s ,char t ) int slen=strlen(s),tlen=strlen(t),i; if(stlen!=tlen) return 0; else f

5、or(i=0;islen;i+) if(si!=ti) 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+) s1i=s2j; s1i=0; ,m,n,0,串连接：strcat(s,s1,s2),将s1和s2连接，结果放在s中。 void strcat(char s ,ch

6、ar s1 ,char s2 ) int len1=strlen(s1),len2=strlen(s2),i=0,j; j=0; while(s1j!=0) si=s1j; i+; j+; j=0; while(s2j!=0) si=s2j; i+; j+; si=0; ,a,b,c,d,m,n,0,求子串：substr(s,i,k),返回串s的第i个位置开始的k个字符组成的串 char *substr(char s ,int i,int k) char *t; int j,n; for(j=0,n=i;ni+k;j+,n+) *(t+j)=sn; *(t+j)=0; return t; ,c

7、,d,e,f,g,0,k=5,子串插入：insert(s,i,t),将子串t插入到主串s的第i个位置,m,n,c,d,e,0,子串插入：insert(s,i,t),将子串t插入到主串s的第i个位置 char *insert(char s ,int i,char t ) int m,n,slen=strlen(s),tlen=strlen(t); for(n=slen-1;n=i;n- -) sn+tlen=sn; /*将串s从第i个位置的元素后移tlen位*/ for(m=tlen-1,n=i+tlen-1;m=0;m- -,n- -) sn=tm; /*将串t自后向前依次插入到串s中*/ s

8、slen+tlen=0; return s； ,子串删除：delete(s,i,k),删除串s从第i个位置开始的k个字符 char *delete(char s ,int i,int k) int n=i+k; while(sn!=0) sn-k=sn; n+; sn=0; return s; ,g,h,0,串显示：display(s),显示串s中的所有字符 void display(char s ) int i=0; while(si!=0) printf(“%c”,si); i+; ,串的堆分配存储,串的堆分配存储方式的特点：串变量的存储空间是在程序执行过程中动态分配的，程序中出现的所有串

9、变量可用的存储空间是一个称之为“堆”的共享空间。 与顺序存储方式的比较 相同点：堆分配存储也是顺序存储 不同点：堆分配存储按照实际需要来分配存储空间,串的链式存储,已知串s=“abcdefghi”，请画出该串的链表。 存储密度=串值所占的存储位/实际分配的存储位,串的链式存储类型定义,typedef struct node char data; struct node *next; #define N 5 typedef struct node char chN; struct node *next; ,串的模式匹配算法,模式匹配：在主串中寻找给定串的位置（即给定串中第一个字符在主串中的位置）。 主串中存在给定串，则给定串必是主串的一个子串，称主串和给定串匹配。 主串中不存在给定串，称主串和给定串不匹配。 例如：s=“connection”，t=“nect” 则称主串s和给定串t匹配，起始位置为3。,Brute-Force算法（BF算法）,算法思想：从给定位置