《《数据结构C语言版》---第04章课件》由会员分享，可在线阅读，更多相关《《数据结构C语言版》---第04章课件（37页珍藏版）》请在金锄头文库上搜索。
1、1,第4章 串,主要知识点,串的基本概念和C语言的串函数 串的存储结构 动态数组实现的顺序串 串的模式匹配算法BF算法,2,4.1 串,1、串的基本概念,1)串(又称字符串)是由n(n0)个字符组成的有限序列。（它是数据元素为单个字符的特殊线性表。）,记为： s =“s0,s1, ,sn-1” (n0 ),3,)串长 串中字符的个数（n0）。 )空串 串中字符的个数为0 时称为空串 。 )空白串由一个或多个空格符组成的串。 )子串 串S中任意个连续的字符序列叫S的子串; S叫主 串。,)子串位置子串的第一个字符在主串中的序号。 )字符位置字符在串中的序号。 )串相等 串长度相等，且对应位置上字
2、符相等。（即两个串中的字符序列一一对应相等。）,4,问：空串和空白串有无区别？ 答：有区别。 空串(Null String)是指长度为零的串； 而空白串(Blank String),是指包含一个或多个空白字符 (空格键)的字符串.,注：串与字符的区别 “a” 串，长度为的串。（它不仅要存储字符a，还要存储该串的长度数据） a字符a。(只存储字符a),5,数据集合：串的数据集合可以表示为字符序列 s0,s1, ,sn-1，每个数据元素的数据类型为字符类型。 操作集合： (1)初始化串Initiate(S) (2)赋值 Assign(S,T) (3)求串长度Length(S),2、串的抽象数据类型
3、,6,(4)比较 Compare(S,T) :有相等和不相等两种比较结果，还有大于、等于和小于三种比较结果 (5)插入 Insert(S,pos,T) (6)删除 Delete(S,pos,len) (7)取子串 SubString(S,pos,len) (8)查找子串Search(S,start,T) (9)替换子串Replace(S,start,T,V),7,相同之处：都是线性结构 不如之处： （1）线性表的数据元素类型为任意类型；而串的数据元素类型为字符类型 （2）线性表的插入和删除操作都是只对一个实践元素；而串的插入和删除操作都是对一个子串进行的 （3）串还有一些不同于线性表的其他操作
4、 因此，专门设计串为一个专门的数据结构。 现有的所有高级程序设计语言，如C+，Java等，都提供了专门的串操作函数或串类。,3、串和线性表的比较,8,3、C语言的串函数,串长度：int strlen(char *str); 串拷贝：char *strcpy(char *str1,char *str2); 串比较：int strcmp(char *str1,char *str2); 字符定位：char *strchr(char *str,char ch); 子串查找: char *strstr(char *s1,char *s2); 串连接：char *strcat(char *str1,cha
5、r *str2); ,注：用C语言处理字符串时，要调用标准库函数 #include,9,例:名和姓的对换问题。英国和美国人的姓名是名在前姓在后，但在有些情况下，需要把姓名写成姓在前名在后中间加一个逗号的形式。编写一个程序实现把名在前姓在后的姓名表示法转换成姓在前名在后中间加一个逗号的姓名表示法。,算法思想：因为C语言自动在串末尾添加结束标记0,所以实现方法是:首先把把原姓名串name的空格改写为0(注意此时0后边，即指针p+1指示的是原字符串name的姓部分；此时的name表示的是原name的名部分)，再把原name的姓、逗号和名逐步添加到newName中，最后再恢复name为开始时的状态。
6、设计函数如下：,10,void ReverseName(char *name, char *newName) char *p; p = strchr(name, ); /p指在空格 位置 *p = NULL; /把空格换为NULL，因此name的长度只包括名 strcpy(newName, p+1); /newName等于name的姓 strcat(newName, ,); /newName等于姓加逗号 strcat(newName, name); / newName等于姓加逗号加名 *p = ; /恢复name为开始时的状态 ,11,4.2 串的存储结构,1、串的顺序存储结构,串的顺序存储结
7、构就是用一个字符类型的数组存放串的所有字符，此时，表示串的长度的方法有两种：,一种方法是设置一个串的长度参数，此种方法的优点是便于在算法中用长度参数控制循环过程,另一种方法是在串值的末尾添加结束标记，此种方法的优点是便于系统自动实现。,12,(1)静态数组结构：用静态内存分配方法定义的数组。由于此时数组元素的个数是在编译是确定的，在运行时是不可改变的，所以也称为定长数组结构。,其类成员变量包括： typedef struct char strMaxSize; int length; String;,而由于不同的内存分配方式定义的数组决定了串的顺序存储结构也有两种：,13,(2)动态数组结构：用
8、动态内存分配方法定义的数组。此时数组元素的个数是在用户申请动态数组空间时才确定的,因此，动态数组结构体定义中要增加一个指出动态数组个数的域。,typedef struct char *str; int maxLength; int length; DString;,其中，str指向动态数组的首地址， maxLength表示动态数组的最大个数， length表示串的当前长度，必须满足length maxLength,14,2、串的链式存储结构,(1)单字符结点链 typedef struct Node char str; struct Node *next; SCharNode;,它分为单字符结
9、点和块链两种。,15,(2)块链 typedef struct Node char strNumber; struct Node *next; NCharNode;,结论：实际应用中仅动态数组方法应用较多，其他方法基本不用 讨论：为什么？,16,4.3 串操作的实现,串的动态数组结构体定义为： typedef struct char *str; int maxLength; int length; DString;,17,（1）初始化操作 void Initiate(DString *S, int max, char *string) int i, m; S-length = strlen(s
10、tring); if(S-length max) m = S-length; else m = max; S-maxLength = m; S-str = (char *)malloc(sizeof(char)*m); for(i = 0; i length; i+) S-stri = stringi; ,18,方法二： typedef struct char *str; int length; DString; void Initiate(DString *S, char *string) int i; S-length = strlen(string); S-str = (char *)m
11、alloc(sizeof(char)* S-length); for(i = 0; i length; i+) S-stri = stringi; ,19,（2）插入子串操作 int Insert(DString *S, int pos, DString T) int i; char *p; if(pos length + T.length S-maxLength) p = (char *)realloc(S-str, (S-length+T.length)*sizeof(char); for(i = S-length-1; i = pos; i-) S-stri+T.length = S-s
12、tri; for(i = 0; i strpos+i = T.stri; S-length = S-length + T.length; return 1; ,20,（3）删除子串操作 int Delete(DString *S, int pos, int len) int i; if(S-length S-length) printf(“参数pos和len不合法”); return 0; else for(i = pos+len; i length-1; i+) S-stri-len = S-stri; S-length = S-length - len; return 1; ,21,（4）
13、取子串操作 int SubString(DString *S, int pos, int len, DString *T) int i; if(pos S-length) printf(参数pos和len出错！); return 0; else for(i = 0; i stri = S-strpos+i; T-length = len; return 1; ,22,（5）撤消操作 void Destroy(DString *S) free(S-str); S-maxLength = 0; S-length = 0; ,23,例4-3 编写一个程序测试上述动态数组存储结构下串操作函数的正确性。
14、 #include #include #include #includeDString.h void main(void) DString myString1, myString2, myString3; int i, max1 = 1, max2 = 1, max3 = 1; /*测试初始化函数*/ Initiate(,24,/*测试插入函数*/ Insert( ,25,程序运行输出为： Data Structure Structure 注意： （1）max1、max2 、max3 都很小，但程序初始化时能根据当前需要的字符串长度申请空间 （2）插入子串时，原先长度不够，程序可以根据实际需要
15、的字符个数重新申请内存空间,26,4.3 串的模式匹配算法,串的查找操作也称做串的模式匹配操作，其中Brute-Force算法和KMP算法是两种最经常使用的顺序存储结构下的串的模式匹配算法。,27,(1)Brute-Force算法的设计思想： 将主串S的第一个字符和模式T的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串S的下一字符起，重新与T第一个字符比较。 直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 1。,1、 Brute-Force算法,28,(2) Brute-Force算法的实现,int BFIndex(DString S, int start, DString T) int i = start, j = 0, v; while(i S.length ,29,(3)BF算法的时间复杂度,若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*mO(n*
