资源描述：
《《数据结构C语言版》----第04章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章串主要知识点串的基本概念和C语言的串函数串的存储结构动态数组实现的顺序串串的模式匹配算法——BF算法4.1串1、串的基本概念1)串(又称字符串)是由n(n≥0)个字符组成的有限序列。（它是数据元素为单个字符的特殊线性表。）记为：s=“s0,s1,……,sn-1”(n≥0)串名串值（用“”括起来）２)串长串中字符的个数（n≥0）。３)空串串中字符的个数为0时称为空串。４)空白串由一个或多个空格符组成的串。５)子串串S中任意个连续的字符序列叫S的子串;S叫主串。６)子串位置子串的第一个字符在主串中的序号。７)字符位置字符在串中的序号。８)串相等串长度
2、相等，且对应位置上字符相等。（即两个串中的字符序列一一对应相等。）问：空串和空白串有无区别？答：有区别。空串(NullString)是指长度为零的串；而空白串(BlankString),是指包含一个或多个空白字符‘’(空格键)的字符串.注：串与字符的区别“a”串，长度为１的串。（它不仅要存储字符‘a’，还要存储该串的长度数据１）‘a’ 字符a。(只存储字符‘a’)数据集合：串的数据集合可以表示为字符序列s0,s1,……,sn-1，每个数据元素的数据类型为字符类型。操作集合：(1)初始化串 Initiate(S)(2)赋值 Assign(S,T)(3)求串
3、长度 Length(S)2、串的抽象数据类型(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)相同之处：都是线性结构不如之处：（1）线性表的数据元素类型为任意类型；而串的数据元素类型为字符类型（2）线性表的插入和删除操作都是只对一个实践元素；而串的插入和删除操作都
4、是对一个子串进行的（3）串还有一些不同于线性表的其他操作因此，专门设计串为一个专门的数据结构。现有的所有高级程序设计语言，如C++，Java等，都提供了专门的串操作函数或串类。3、串和线性表的比较3、C语言的串函数串长度：intstrlen(char*str);串拷贝：char*strcpy(char*str1,char*str2);串比较：intstrcmp(char*str1,char*str2);字符定位：char*strchr(char*str,charch);子串查找:char*strstr(char*s1,char*s2);串连接：char*
5、strcat(char*str1,char*str2);……注：用C语言处理字符串时，要调用标准库函数#include例:名和姓的对换问题。英国和美国人的姓名是名在前姓在后，但在有些情况下，需要把姓名写成姓在前名在后中间加一个逗号的形式。编写一个程序实现把名在前姓在后的姓名表示法转换成姓在前名在后中间加一个逗号的姓名表示法。算法思想：因为C语言自动在串末尾添加结束标记‘ ‘,所以实现方法是:首先把把原姓名串name的空格改写为‘ ‘(注意此时‘ ‘后边，即指针p+1指示的是原字符串name的姓部分；此时的name表示的是原nam
6、e的名部分)，再把原name的姓、逗号和名逐步添加到newName中，最后再恢复name为开始时的状态。设计函数如下：voidReverseName(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等于姓加逗号加名*
7、p='';//恢复name为开始时的状态}4.2串的存储结构1、串的顺序存储结构串的顺序存储结构就是用一个字符类型的数组存放串的所有字符，此时，表示串的长度的方法有两种：一种方法是设置一个串的长度参数，此种方法的优点是便于在算法中用长度参数控制循环过程另一种方法是在串值的末尾添加结束标记，此种方法的优点是便于系统自动实现。(1)静态数组结构：用静态内存分配方法定义的数组。由于此时数组元素的个数是在编译是确定的，在运行时是不可改变的，所以也称为定长数组结构。其类成员变量包括：typedefstruct{charstr[MaxSize];intlength;
8、}String;而由于不同的内存分配方式定义的数组决定了串的顺序存储结构也有两种
