数据结构(05中文)教案第4`5章相关附件7072-1ppt.ppt

第四章串,4.1串类型的定义4.2串的表示和实现4.2.1定长顺序存储表示4.2.2堆分配存储表示4.2.3串的块链存储表示,4.1串类型的定义一、串和基本概念串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3an”，其中S是串名，双引号括起来的字符序列是串值；ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(EmptyString)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(BlankString)注意：空串和空白串的不同，例如“”和“”分别表示长度为1的空白串和长度为0的空串。,4.2.3串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。typedefstructnodechardata;structnode*next;lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。,为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。对于结点大小不为1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。#definenodesize80typedefstructnodechardatanodesize;structnode*next;lstring;,2串的有关术语1）子串串中任意连续的字符组成的子序列称为该串的子串;例：c=“DATASTRUCTURE”，f=“DATA”f是c的子串2）子串的位置子串t在主串S中的位置是指主串s中第一个与T相同的子串的首字母在主串中的位置;例：s=“ababcabcac”,t=“abc”子串T在主串S中的位置为33）串相等两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都相同；,4.1串的基本概念,3串的基本操作串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。1）串赋值操作assign(s,t)功能：将串t的值赋给串变量s；2）串相等判断equal(s,t)函数串的联接操作concat(s,t)把串t接在串s后面求串长操作lenght(s)5)求子串操作sub(s,start,len,t)若0=startlength(s)0=len=length(s)-start则t中值为从串s的第start个字符,起长度为len的字符序列,并且函数返回值为1,否则为0；,4.1串的基本操作,三、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见的文件。定义下列几个变量：chars120=“dirtreeformat”,s220=“file.mem”;chars330,*p;intresult;求串长(length)intstrlen(chars);/求串的长度例如：printf(“%d”,strlen(s1);输出13,（2）串复制(copy)char*strcpy(charto,charfrom);该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。例如：strcpy(s3,s1);/s3=“dirtreeformat”(3)联接(concatenation)charstrcat(charto,charfrom)该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。例如：strcat(s3,”/”)strcat(s3,s2);/s3=“dirtreeformat/file.mem”,上述串的操作是最基本的，其中后四个还有变种形式：strncpy，strncat，strncmp，strnchr。串的其余操作可由这些基本操作组合而成。例1、求子串求子串的过程即为复制字符序列的过程，将串S中的第pos个字符开始长度为len的字符复制到串T中。voidsubstr(stringsub,strings,intpos,intlen)if(posstrlen(s)-1|len0result=strcmp(“12”,”12”);result=0result=strcmp(“Joe”,”Joseph”);result0（5）字符定位(index)charstrchr(chars,charc);该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。例如：p=strchr(s2,”.”);p指向“file”之后的位置if(p)strcpy(p,”.cpp”);s2=“file.cpp”,下面是一些串的例子：（1）a=“Thisisastring”（2）b=“string”（3）c=“（4）d=“”（5）e=“你好”说明：串中包含的字符个数，称为串的长度。长度为0的串称为空串，它不包括任何字符;串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。,4.1串的基本概念,3串的基本操作串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。1）串赋值操作assign(s,t)功能：将串t的值赋给串变量s；2）串相等判断equal(s,t)函数串的联接操作concat(s,t)把串t接在串s后面求串长操作lenght(s)5)求子串操作sub(s,start,len,t)若0=startlength(s)0=len=length(s)-start则t中值为从串s的第start个字符,起长度为len的字符序列,并且函数返回值为1,否则为0；6）求子串位置操作index(s,t)功能：如果s中存在与t相同的子串,则返回s中第1个这样的子串的位置，若不存在返回0,4.1串的基本概念,4.1串的基本概念,7）替换操作replace(s,t,v)功能：由串v替换串s中出现的所有和t相同的不重叠子串；8）复制串操作strcopy(s,t)功能：由串变量s复制得到串变量t；9）判空操作empty(s)功能：若为空串，则返回1，否则返回010）串置空操作ClearString(s)功能：将s清为空串11)串插入操作StrInsert(s,start,t)功能：将串t插入到串s的第start字符之前12）串删除操作StrDelete(s,start,len)功能：从串s中删除第start个字符起长度len为的子串,4.2串存储和实现,1顺序存储结构顺序存储结构类似于C语言的字符数组，以一组地址连续的存储单元存放串值字符序列，其类型说明如下：#defineMAX255charchMAX,在数组ch中以字符0表示字符串的结束.特点是访问容易,但删除或插入麻烦,4.2串存储和实现,2链式存储结构链式存储结构类似线性链表，由于串结构的特殊性,要考虑每个结点是存放一个字符还是多个字符。一个字符的，插入、删除、求长度非常方便，但存储效率低。多个字符的，改善了效率，在处理不定长的大字符串时很有效，但插入、删除不方便，可用特殊符号来填满未充分利用的结点。,charstoreMAX;intfree;*/整型域：存放串长*/,3、堆分配存储堆分配存储类似于线性表的顺序存储结构，以一组地址连续的存储单元存放串值字符序列，其存储空间是在程序执行过程中动态分配的。一个串值的确定是通过串在堆中的起始位置和串的长度实现的。为此，串名