第4章_串(免费阅读).pptVIP

int BF(char S[ ], char T[ ]) { i=1; j=1; while (i=S[0]j=T[0]) { if (S[i]==T[j]) { i++; j++; } else { i=i-j+2; j=1; } } if (jT[0]) return (i-j+1); else return 0; } 特殊线性表——串 模式匹配——BF算法 int BF(char S[ ], char T[ ]) { i=1; j=1;start=1; while (i=S[0]j=T[0]) { if (S[i]==T[j]) { i++; j++; } else { start++; i=start; j=1; } } if (jT[0]) return start; else return 0; } 特殊线性表——串 模式匹配——BF算法 设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况： ⑴ 最好：不成功的匹配都发生在串T的第一个字符。 例如：S=aaaaaaaaaabcdccccc T=bcd 第4章 特殊线性表—串 本章的基本内容是： 三种特殊的线性表——栈、队列、串 从数据结构角度看，栈和队列是操作受限的线性表，他们的逻辑结构相同。 串是重要的非数值处理对象，它是以字符作为数据元素的线性表。 特殊线性表——串 串的逻辑结构 非空串通常记为： S= s1 s2 …… sn 其中：S是串名，双引号是定界符，双引号引起来的部分是串值 ，si（1≤i≤n）是一个任意字符。 串：零个或多个字符组成的有限序列。 串长度：串中所包含的字符个数。 空串：长度为0的串，记为： 。 特殊线性表——串 串的逻辑结构 串的数据对象约束为某个字符集。 微机上常用的字符集是标准ASCII码，由 7 位二进制数表示一个字符，总共可以表示 128 个字符。扩展ASCII码由 8 位二进制数表示一个字符，总共可以表示 256 个字符，足够表示英语和一些特殊符号，但无法满足国际需要。Unicode由 16 位二进制数表示一个字符，总共可以表示 216个字符，即6万5千多个字符，能够表示世界上所有语言的所有字符，包括亚洲国家的表意字符。为了保持兼容性，Unicode字符集中的前256个字符与扩展ASCII码完全相同。 S1=ab12cd S2=ab12 S3=ab13 S4=ab12φ S5= S6=φφφ 特殊线性表——串 串的逻辑结构 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串。 子串的位置：子串的第一个字符在主串中的序号。 串的比较：通过组成串的字符之间的比较来进行的。 给定两个串：X=x1x2…xn和Y=y1y2…ym，则： 1. 当n=m且x1=y1，…，xn=ym时，称X=Y； 2. 当下列条件之一成立时，称X＜Y： ⑴ n＜m且xi=yi（1≤ i≤n）； ⑵存在k≤min(m,n)，使得xi=yi(1≤i≤k-1)且xk＜yk。 特殊线性表——串 串的逻辑结构 例：S1=ab12cd ，S2=ab12，S3=ab13 串的基本操作： ⑴ strlen (s)：求串s的长度。 ⑵ strassign (s1, s2)：赋值，将s2的值赋值给串s1。 ⑶ strcat (s1, s2,)：连接，将串s2放在串s1的后面连接成一个新串。 ⑷ substr (s, i, len)：求子串，返回从串s的第i个字符开始取长为 len 的子串。 ⑸ strcmp (s1, s2)：串比较，若s1=s2，返回0；若s1s2, 返回-1；若s1s2, 返回1。 ⑹ index (s, t)：定位，返回子串t在主串s中首次出现的位置。若t不是s的子串，则返回0。 特殊线性表——串 ⑺ insert (s, i, t)：插入，将串t插入到串s中的第i个位置。 ⑻ delete (s, i, len)：删除，在串s中删除从第i个字符开始的连续len个字符。 ⑼ replace (s, t, r)：替换，在串s中用串r替换所有与串t相等的子串。 特殊线性表——串 串的操作通常以串的整体作为操作对象。 与