资源描述：
《最新第四章 串教案教学提纲.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章串★本章主要讲授内容
1、串的定义和基本操作
2、串的顺序存储结构
3、串的链式存储结构
4、模式匹配算法及其改进算法
★★课时分配：1、2，两个学时，3两个学时,4四个学时，上机6个学时
★★★重点、难点：模式匹配及其算法第一节．串的定义和基本运算
串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。
串一般记作：
s="a1a2...an"(n30)
其中，s是串的名称，用双引号（"
2、"）括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n被称作串的长度。当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串。
s1=""
s2=""
s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。
概念：
子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。
例如，有下列四个串a，b，c，d：
a="WelcometoBeijing"
b="Welcome"
c="Bei"
d=
3、"welcometo"
子串的位置：子串在主串中第一次出现的第一个字符的位置。
两个串相等：两个串的长度相等，并且各个对应的字符也都相同。
例如，有下列四个串a，b，c，d：
a="program"
b="Program"
c="pro"
d="program"
串的基本操作：
（1）创建串StringAssign(s,string_constant)
（2）判断串是否为空StringEmpty(s)
（3）计算串长度Length(s)
（4）串连接Concat(s1,s2)
（5）求子串SubStr(s1,s2s
4、tart,len)
（6）串的定位Index(s1,s2)
例如1：将s2串插入到串s1的第i个字符后面。
SubStr(s3,s1,1,i);
SubStr(s4,s1,i+1,Length(s1)-i);
Concat(s3,s2);
Concat(s3,s4);
StringAssign(s1,s3);
例如2：删除串s中第i个字符开始的连续j个字符。
SubStr(s1,s,1,i-1);
SubStr(s2,s,i+j,Length(s)-i-j+1);
Concat(s1,s2);
StringAssi
5、gn(s,s1);第二节．串的存储结构
2．1顺序存储结构
串的顺序存储结构与线性表的顺序存储类似，用一组连续的存储单元依次存储串中的字符序列。在C语言中，有两种实现方式：
第一种是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下所示：
#defineMAX_STRING255
//0号单元存放串的长度，字符从1号单元开始存放
typeunsignedcharString[MAX_STRING];
第二种是在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的存储单元
6、，并以一个特殊的字符作为字符串的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源的利用率。类型定义如下所示：
typedefstruct{
char*str;
intlength;
}STRING;
不同的定义形式，算法中的处理也略有不同。下面我们将给出在第二种顺序存储方式下串的几个基本操作的算法。
（1）串的赋值
intStringAssign(STRING*s,char*string_constant)
{
if(s->str)free(s->str);//若s已经存在，
7、将它占据的空间释放掉
for(len=0,ch=string_constant;ch;len++,ch++);//求string_constant串的长度
if(!len){s->str=(char*)malloc(sizeof(char));s->str[0]=' ';s->length=0;}//空串
else{
s->str=(char*)malloc((len+1)*sizeof(char));//分配空间
if(!s->str)returnERROR;
s->str[0..len]=string_con
8、stant[0..len];//对应的字符赋值
s->length=len;//赋予字符串长度
}
returnOK;
}（2）判断串是否为空
intStringEmpty(STRINGs)
{
if(!s.length)returnTRUE;
elsereturnFALSE;
}
（3）求串的长度
intLength(STRINGs)
{
returns.
