《数据结构》算法实现及解析- 数据结构04

2017/12/271本章主题串的各种基本运算及其实现教学目的了解数据结构的基本概念，理解常用术语教学重点L掌握串的基本概念及其基本运算L掌握串的存储结构主要内容1串的基本概念2串的存储结构3串的基本运算及其实现4文本编辑第4章串2017/12/272在计算机的应用中，非数值处理问题的应用越来越多。如在汇编程序和编译程序中，源程序和目标程序都是作为一种字符串数据进行处理的。在事务处理系统中，用户的姓名和地址及货物的名称、规格等也是字符串数据。字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。在线性表的基本操作中，大多以“单个元素”作为操作对象，而在串中，则是以“串的整体”或一部分作为操作对象。因此，线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。本章学习导读2017/12/273串是一种特殊的线性表，它的数据对象是字符集合。411串的定义串（或字符串）是由零个或多个字符组成的有限序列。一般记作SC0C1C2CN1N0其中S为串名，用双引号括起来的字符序列是串的值；CI0IN1可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目N称为串的长度。零个字符的串称为空串，通常以两个相邻的双引号来表示空串如S，它的长度为零；仅由空格组成的的串称为空格串如S；41串及其运算2017/12/274若串中含有空格，在计算串长时，空格应计入串的长度中如SIMASTUDENT的长度为13。注意在C语言中，用单引号引起来的单个字符与单个字符的串是不同的，如S1A与S2A两者是不同的，S1表示字符，S2表示字符串。当两个串的长度相等且各对应位置上的字符都相同时，这两个串是相等的。串中任意个连续字符组成的序列称为该串的子串。包含子串的串被称为主串。例如，“COM“、“OM“、“A“和“MAN“都是“COMMANDER“的子串。子串在主串中的位置是指子串中第一个字符在主串中的位置序号。如子串“MAN“在主串“COMMANDER“中的位置为4。2017/12/275串是一种简单的数据结构，它的逻辑结构与线性表十分相似，区别仅在于串的数据对象是字符集。串的基本运算与线性表的基本运算有很大差别。通常在串的基本运算中，以“串的整体”作为操作对象；而在线性表的基本运算中，大多以“单个元素”作为操作对象。412串的基本运算串的常用基本运算主要有1STRASSIGNS,CHARS功能赋值运算将串常量CHARS的值赋给串变量S。例如执行STRASSIGNS，“ABCD“运算之后，S的值为“ABCD“。2017/12/2762ASSIGNS,T功能赋值运算。将串变量T的值赋给串变量S。例如T“ABCD“，则执行ASSIGNS,T运算之后，S的值为“ABCD“。3EQUALS,T功能判相等运算。若S与T的值相等则运算结果为1，否则为0。4LENGTHS功能求串长运算。求串S序列中字符的个数，即串的长度。5CONCATS,T功能联接运算。将串T的第一个字符紧接在串S的最后一个字符之后，联接得到一个新串。例如S“MAN“,T“KIND“，则执行CONCATS,T运算后得到的新串为“MANKIND“。2017/12/2776INSERTS,POS,T功能插入运算，当1POSLENGTHS1时，在串S的第POS个字符之前插入串T。7DELETES,POS,LEN功能删除运算。当1POSLENGTHS且0LENLENGTHSPOS1时，从串S中删去从第POS个字符起长度为LEN的子串。8REPLACES,POS,LEN,T功能置换运算。当1POSLENGTHS且0LENLENGTHSPOS1时，用串T替换串S中从第POS个字符起长度为LEN的子串。对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见文件。2017/12/278定义下列几个变量CHARS120“DIRTREEFORMAT”,S220“FILEMEM”CHARS330,PINTRESULT1求串长LENGTHINTSTRLENCHARS/求串的长度例如PRINTF“D”,STRLENS1输出13（2）串复制COPYCHARSTRCPYCHARTO,CHARFROM该函数将串FROM复制到串TO中，并且返回一个指向串TO的开始处的指针。例如STRCPYS3,S1/S3“DIRTREEFORMAT”2017/12/2793联接CONCATENATIONCHARSTRCATCHARTO,CHARFROM该函数将串FROM复制到串TO的末尾，并且返回一个指向串TO的开始处的指针。例1、求子串求子串的过程即为复制字符序列的过程，将串S中的第POS个字符开始长度为LEN的字符复制到串T中。VOIDSUBSTRSTRINGSUB,STRINGS,INTPOS,INTLENIFPOSSTRLENS1|LEN0NSTRLENSMSTRLENTIPOSWHILEI/定义能处理的最大的串长度TYPEDEFSTRUCTCHARSTRMAXLEN/定义可容纳MAXLEN个字符的字符数组INTCURLEN/定义当前实际串长度STRING2017/12/2713以下给出采用顺序存储结构时串的联接运算。（1）CONCATS,TSTRINGCONCATSTRINGS,STRINGT/将串T的第一个字符紧接在串S的最后一个字符之后STRINGCHINTICHCURLENSCURLENTCURLEN/将SSTR0SSTRSCURLEN1复制到CHFORI0IT，则输出正数；如果STRETURN1ELSERETURNSSTRITSTRI/ST或S/定义结点的大小TYPEDEFSTRUCTCHUNK/结点结构CHARSTRCHUNKSIZESTRUCTCHUNKNEXTLSTRING一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。2017/12/2719对于结点大小不为1的链串，其类型定为义只需对上述的结点类型做简单的修改即可，如结点大小为4的定义为DEFINENODESIZE80TYPEDEFSTRUCTNODECHARDATA4STRUCTNODENEXTLSTRING采用链式存储结构（结点大小为1），实现串的联接、求子串以及串的置换基本运算见教科书P83。2017/12/2720423串的堆分配存储结构及其基本运算的实现1堆分配存储结构堆存储结构的特点是，仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。所以也称为动态存储分配的顺序表。每当产生一个新串时，系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间。在C语言中，存在一个称为“堆”的自由空间，由动态分配函数MALLOC分配一块实际串长所需的存储空间，如果分配成功，则返回这段空间的起始地址，作为串的基址。由FREE释放串不再需要的空间。2017/12/27212基本运算在堆分配存储结构上的实现在C和C语言中可利用MALLOC和FREE两个函数实现动态存储分配。函数MALLOC为每个新产生的串分配一块实际所需大小的空间，若分配成功，则返回一个指向该空间起始地址的指针，作为新串的基址。另外为了便于串的运算，在存储结构中包含串的长度。C语言对堆分配存储结构的定义如下TYPEDEFSTRUCTCHARSTRINTCURLENHSTRING2017/12/2722堆分配存储中求子串和串的联接运算（1）SUBSTRS,POS,LENHSTRINGSUBSTRHSTRINGIFPOSSCURLEN1|LENSCURLENRETURNERROR/参数不正确时返回错误提示IFSUBSTRFREESUBSTR/释放旧空间IFLEN/空子串SUBSTRNULLSUBCURLEN0ELSESUBSTRCHARMALLOCLENSIZEOFCHARFORI0ITCURLENRETURNITCURLEN/匹配成功，返回模式串T在串S中的起始位置ELSERETURN0/匹配失败返回02017/12/2727一般情况下，上述算法的实际执行效率与字符TSTR0在串S中是否频繁出现有密切关系，例如，S是一般的英文文稿，T“HELLO”，S中有5的字母是“H”，则在上述算法执行过程中，对于95的情况可以只进行一次对应位的比较就将T向右移动一位，时间复杂度下降为OSCURLEN，这时算法接近最好情况。然而，在有些情况下，该算法效率却很低。如当S“AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB“，T“AAAAAAB“每次都是在模式串的最后位置上字符不匹配即TCURLEN/定义最大串存储空间INTINDEX_KPMSTRINGS,STRINGTINTI,J,NEXTMAXLENGETNEXTT，NEXT/先求得模式串的NEXT函数值I0/指向串S的第1个字符J0/指向串T的第1个字符WHILEITCURLENRETURNITCURLEN/匹配成功ELSERETURN0/匹配失败2017/12/273244串的应用文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串的输入、查找、修改、删除、输出等。为了编辑方便起见，用户可以通过换页符和换行符将文本划分为若干页或将每页划分为若干行。可将整个文本看成是一个文本串，页是文本串的子串，而行则是页的子串。2017/12/2733假设有下列一段C源程序MAINFLOATA,B,MAXSCANF“F,F“,IFABMAXAELSEMAXB若用N表示换行符，该文本串在内存中的存储映像如下表所示文本串的内存存储映像2017/12/2734为了管理文本串中的页和行，在进入文本编辑时，编辑程序先为文本串建立相应的页表和行表，即建立各子串的存储映像。页表的每一项列出页号和该页的起始行号，行表的每一项则指示每一行的行号、起始地址和该行子串的长度。以表42为例，假设文本串只占一页，起始行号为100，起始地址为200，则该文本串的行表如下所示。行表2017/12/2735下面来讨论文本的编辑。（1）插入一行时，首先在文本末尾的空闲工作区写入该行的串值，然后，在行表中建立该行的信息，插入后，必须保证行表中行号从小到大的顺序。若插入行145，则行表中从150开始的各行信息必须向下平移一行。（2）删除一行时，则只要在行表中删除该行的行号，后面的行号向前平移。若删除的行是页的起始行，则还要修改相应页的起始行号（改为下一行）。（3）修改文本时，在文本编辑程序中设立了页指针，行指针和字符指针，分别指示当前操作的页、行和字符。若在当前行内插入或删除若干字符，则要修改行表中当前行的长度。如果该行的长度超出了分配给它的存储空间，则应为该行重新分配存储空间，同