数据结构-使用C语言 朱战立 第4章串

1第4章串（String）4.1串4.2串的存储结构4.3串基本操作的实现算法4.4串的模式匹配算法2记为：

s=“s0,s1,……,sn-1”(n≥0)

串名串值（用“”括起来）一、串的基本概念１、串（又称字符串）是由n(n≥0)个字符组成的有限序列。（它是数据元素为单个字符的特殊线性表。）4.1串隐含结束符‘\0’

，即ASCII码NUL为何要单独讨论“串”类型？1）字符串操作比其他数据类型更复杂（如拷贝、连接操作）2）程序设计中，处理对象很多都是串类型。一般是字母、数学、标点符号等可屏幕显示的字符3２、串长串中字符的个数（n≥0）。３、空串串中字符的个数为0时称为空串。４、空白串由一个或多个空格符组成的串。５、子串串S中任意个连续的字符序列叫S的子串;S叫主串。６、子串位置子串的第一个字符在主串中的序号。７、字符位置字符在串中的序号。８、串相等串长度相等，且对应位置上字符相等。（即两个串中的字符序列一一对应相等。）问：空串和空白串有无区别？答：有区别。空串(NullString)是指长度为零的串；而空白串(BlankString),是指包含一个或多个空白字符‘

’(空格键)的字符串.4

例1：现有以下4个字符串：a=“BEI” b=“JING”c=“BEIJING”d=“BEIJING”问：①他们各自的长度？a是c和d的子串，在c和d中的位置都是1②a是哪个串的子串？在主串中的位置是多少？a=3，b=4，c=7，d=8③空串是哪个串的子串？a是不是自己的子串？空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。注：串与字符的区别“a”串，长度为１的串。（它不仅要存储字符‘a’，还要存储该串的长度数据１）‘a’字符a。(只存储字符‘a’)

5数据集合：串的数据集合可以表示为字符序列s0,s1,……,sn-1，每个数据元素的数据类型为字符类型。操作集合：初始化串Initiate(S)赋值Assign(S,T)求串长度Length(S)比较Compare(S,T)插入Insert(S,pos,T)删除Delete(S,pos,len)取子串SubString(Spos,len)查找子串Search(S,start,T)替换子串Replace(S,start,T,V)二、串的抽象数据类型6三、C语言的串函数串长度：intstrlen(char*str);串拷贝：char*strcpy(char*str1,char*str2);串比较：intstrcmp(char*str1,char*str2);子串T定位：char*strchr(char*str,charch);子串查找：char*strstr(char*s1,char*s2);串连接：char*strcat(char*str1,char*str2);……注：用C处理字符串时，要调用标准库函数#include<string.h>7

设s=“IAMASTUDENT”,t=“GOOD”,q=“WORKER”。求：例1：Length(s)＝

Length(t)＝

SubString(s,7,7)=SubString(t,2,1)=Replace(s,0,‘STUDENT’,q)=144‘STUDENT’‘O’’IAMAWORKER’8解：因为SubString(s,5,2)＝‘A’；SubString(s,6,8)＝‘STUDENT’strcat(t,SubString(s,6,8))＝’GOODSTUDENT’所以：strcat(SubString(s,5,2),strcat(t,SubString(s,6,8)))＝‘AGOODSTUDENT’例2：设s=“IAMASTUDENT”,t=“GOOD”,求：

strcat(SubString(s,6,2),strcat(t,SubString(s,7,8)))＝？94.2 串的存储结构静态数组结构——用一组地址连续的存储单元存储串值的字符序列，存储空间不可改变。属静态存储方式。动态数组结构——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。串的链式存储表结构首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。串有两种存储表示方法：顺序存储链式存储10

1、静态数组结构特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。

串的静态数组结构体可定义为：typedefstruct{charstr[MaxSize];intlength;}String;11思路：利用malloc函数合理预设串长空间。typedefstruct{char*str;intmaxLength;intlength;}Dstring;２、动态数组结构特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。串的动态数组结构体定义如下：Str指向动态数组的首地址maxLength表示动态数组元素的最大个数Length表示串的当前长度12３、串的链式存储结构

它分为单字符结点和块链两种。(1)单字符结点链(2)块链typedefstructNode

typedefstructNod{{charstr;charstr[Number];structNode*next;structNode*next;}SCharNode;}NCharNode;13注意：若数据元素很多，用法2存储更优—称为块链结构链式存储特点:用链表存储串值，易插入和删除。法1：链表结点的数据分量长度取1（个字符）法2：链表结点（数据域）大小取n(例如n=4)

A

B

C

I

NULLheadheadABCDEFGHI###NULL144.3串基本操作的实现算法１、静态数组下串基本操作的实现算法typedefstruct/*结构体定义*/{ charstr[MaxSize]; intlength;}String;(1)初始化操作

voidInitiate(String*s){S->length=0;}15（2）插入子串操作intInsert(String*S,intpos,StringT)/*在串S的pos位置插入子串T*/{ inti; for(i=S->length-1;i>=pos;i--) S->str[i+T.length]=S->str[i]; //依次后移数据元素

for(i=0;i<T.length;i++) S->str[pos+i]=T.str[i];//插入

S->length+=T.length; //产生新的串长

return1;}16(3)删除子串操作intDelete(String*S,intpos,intlen)//删除串S从pos位置开始长度为len的子串值{ inti; for(i=pos+len;i<=S->length-1;i++) S->str[i-len]=S->str[i];//依次前移数据元素

S->length-=len;//产生新的串长度值

return1;}17２、动态数组下串基本操作的实现算法(1)初始化voidInitiate(DString*S,intmax,char*string){ inti; S->str=(char*)malloc(sizeof(char)*max);//申请动态数组空间 S->maxLength=max;//置动态数组元素最大个数 S->length=strlen(string);//置串的当前长度值 for(i=0;i<S->length;i++) S->str[i]=string[i];//赋串值}18(2)插入子串操作intInsert(DString*S,intpos,DStringT){ inti; char*p; for(i=S->length-1;i>=pos;i--)

S->str[i+T.length]=S->str[i];//依次后移数据元素

for(i=0;i<T.length;i++) S->str[pos+i]=T.str[i];//插入

S->length+=T.length;//产生新的串长度值

return1;}194.４串的模式匹配算法一、基本概念1、模式匹配（定位）设有主串S和子串T（将S称为目标串，将T称为模式串），在主串S中，从位置start开始查找，如若在主串S中找到一个与子串T相等的子串，则返回T的第一个字符在主串中的位置，否则返回-1。2、算法目的确定主串中所含子串第一次出现的位置（定位）3、算法种类

BF算法（又称古典的、经典的、朴素的、穷举的）

KMP算法20二、Brute-Force算法1、Brute-Force算法的设计思想：将主串S的第1个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的第2字符起，重新与T的第1个字符比较。依次类推，若从模式串s的第i个字符开始，每个字符依次和目标串t中的对应字符相等，则匹配成功。21abcba223、BF算法的时间复杂度讨论：若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m＝O(n*m)最好的情况是：一配就中！只比较了m次。最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，别忘了最后m位也各比较了一次，还要加上m！所以总次数为：(n-m)*m+m＝(n-m+1)*m串操作应用举例文本编辑程序用于源程序的输入和修改，公文书信、报刊和书籍的编辑排版等。常用的文本编辑程序有Word,Notepad,WPS,TC等，文本编辑的实质是修改字符数据的形式和格式，虽然各个文本编辑程序的功能不同，但基本操作是一样的，都包括串的查找、插入和删除等。2324

为了编辑方便，可以用分页符和换行符将文本分为若干页，每页有若干行。我们把文本当作一个字符串，称为文本串，页是文本串的子串，行是页的子串。我们采用动态数组结构来存储文本，同时设立页指针、行指针和字符指针，分别指向当前操作的页、行和字符，同时建立页表和行表存储每一页、每一行的起始位置和长度。假设有如下源程序：FUNCmax(x，