《数据结构chap串学习.pptx》由会员分享，可在线阅读，更多相关《数据结构chap串学习.pptx（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、目录4.1串的类型的定义4.2 串的表示和实现结束放演第1页/共22页4.1串类型的定义4.1.1 基本概念 1串的定义串的定义 串(string)是由零个或多个字符组成的有限序列，记作s=a1a2an（n=0），其中s为串的名字，用成对的单引号括起来的字符序列为串的值，但两边的单引号不算串值，不包含在串中。ai(1in)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。2空串空串不含任何字符的串称为空串，它的长度n=0，记为s=，通常记为。第2页/共22页3空白串空白串(空格串空格串)含有一个或多个空格的串，称为空白串，它的长度n=串中空格字符的个数，例如：s=，长度为1。4子串
2、、主串子串、主串 若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。另外，空串是任意串的子串，任意串是自身的子串。问题：若一个串的长度为n，则它的子串数目和真子串个数分别为多少(除串本身以外的子串都称为真子串)？第3页/共22页5.子串在主串中的位置 既子串的第一个字符在主串中的位置表示。例如：串s1=CD在s=ABCDECFG中的位置6.串相等 两个串的长度相等当且仅当两个串的值相等 各个对应位置的字符都相等第4页/共22页串的基本操作Str
3、Assign(&T,chars)生成一个值等于chars的串TSubString(&sub,s,pos,len)用sub 返回串S的第pos个字符起长度为len 的子串Concat(&T,s1,s2)T为s1,s2连接而成的新串Replace(&S,T,V)用V替换S中出现的所有与T相等的不重叠子串。Index(S,T)若S中存在串T值相同的子串，返回其在主串S中第一次出现的位置，否则函数返回值为0Strcompare(S,T)ST 返回值0 S=T 返回值=0 ST 返回值0第5页/共22页例:S=I am a Student T=Good Q=workerStrlength(S)=14Su
4、bString(S,8,7)=StudentIndex(S,a)=3 Index(S,T)=0Replace(S,Student,Q)=I am a worker Concat(SubString(S,6,2),Concat(T,SubString(S,7,8)=Concat(a,Concat(Good,Student)=a Good Student第6页/共22页4.1.2 串的抽象数据类型的定义描述串的抽象数据类型的定义描述 P71注意：串的逻辑结构与线性表及相似，但基本操作和线性表有很大差别，操作对象而言，线性表为单个对象作为操作对象，而串以串的整体（子串）作为操作对象。串类型的最小操作
5、子集：StrAssign、StrCompare、StrLength、Concat、SubString 例如：算法 4.1第7页/共22页4.2 串的表示和实现4.2.1 定长顺序存储表示4.2.2 串的指针表示4.2.3 串的块链存储表示4.2.4 串的堆分配存储表示第8页/共22页4.2.1 定长顺序存储表示4.2.1.1 定义 定长顺序存储表示,也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：#define MAXSTRLEN 255/一个固定长度的存储区 /串的长度在这个范围内随意，超过这
6、个长 /度的串值则被舍去，既串被截断 typedef unsigned char sstringMAXSTRLEN+1;/0号单元存放串的长度 sstring s;/s是一个可容纳255个字符的顺序串 第9页/共22页01 2345678910.MAXSIZE-110abcdefghij 012345678910.MAXSIZE-1abcdefghijk0 串的顺序存储方式1串的顺序存储方式2 -定长顺序存储方式第10页/共22页4.2.1.2 运算1.串联接Concat(&T,S1,S2)Status Concat(SString&T,SString S1,SString S2)/用T返回由
7、S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE。if(S10+S20=MAXSTRLEN)/未截断 T1.S10 =S11.S10;TS10+1.S10+S20 =S21.S20;T0=S10+S20;uncut=TRUE;else if(S10MAXSTRLEN)T 1.S10 =S11.S10;T S10+1.MAXSTRLEN =S21.MAXSTRLEN S10 ;T0=MAXSTRLEN;uncut=FLASE;else T 0.MAXSTRLEN =S11.MAXSTRLEN ;/T0=S10=MAXSTRLEN uncut=FLASE;return uncut
8、e;/Concat第11页/共22页2.求子串SubString(&Sub,S,pos,len)Status SubString(SString&Sub,SString S,int pod,int len)/用Sub返回串S的第pos个字符起长度为len的子串 /其中，1=pos=StrLengh(S)且0=len=StrLength(S)-pos+1 if(posS0|lenS0 pos+1)return EEROR;Sub1.len=Spos.pos+len-1;Sub0=len;return OK;/SubString第12页/共22页4.2.1.3 优缺点 优点：连续顺序存储，特别适合
9、于子串的搜索 缺点：a.对串进行插入或删除子串操作时，要移动大量字符，耗时太多 b.串的长度必须预先确定，这不容易做到。第13页/共22页4.2.2 串的指针表示 例如：S=“abcdef”的存储结构具体形式见图4-4。a S b c d e f 图 4-4 S 串的链式存储示意图 charnext第14页/共22页优缺点：优点：a.在对串进行子串的插入和删除时，只要修改相应的指针就可 以完成 b.对串的长度没有限制，在存储空间足够大的情况下，可以表 示任意长度的串 缺点：a.以增加存储空间为代价 b.沿着指针作在子串的顺序搜索需要比定长顺序表示下子串的 搜索花更多的时间第15页/共22页4.
10、2.3 串的块链存储表示 （很少使用，前面两种的折中方式）例如：串S=“abcdef”的存储结构具体形式见图4-5。每块大小为4，划分成两块，并且链表带头结点。a b c d e f S 头结点 图4-5 S串的结点大小为 4的链式存储#第16页/共22页4.2.4 串的堆分配存储表示 （根据串的具体长度分配空间，应用最多）（已分配区域）free（未分配区域）storestoreMAXSIZE;图4.8 堆结构示意图50705021sCh lengthMAXSIZE第17页/共22页1.特点 所有串的串值都存储在地址连续的一个存储单元序列中，而每个串的首地址是在算法执行过程中动态分配的，串的操
11、作仍是基于”字符序列的复制“进行。2.串的堆分配存储表示 typedef struct int length;/串长 char*ch;/若是非空串，则按串长分配存储区，否则ch为NULL HString;第18页/共22页Status StrInsert(HString&S,int pos,HString T)/1=pos=StrLength(S)+1,在串S的第pos个字符之前插入串T if(posS.lenth+1)return ERROR;/pos不合法 if(T.length)if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char);exit(OVERFLOW);for(i=S.length-1;i=pos-1;-i)S.chi+T.length=S.chi;S.chpos-1.pos+T.length-2=T.ch0.T.length-1;S.length+=T.length;return OK;/StrInsert第19页/共22页注意：第pos个字符的时间存储位置：定长顺序 pos 实际串存储位置下标从1开始 堆分配存储 pos-1 下标从0开始第20页/共22页作业：4.5 4.6第21页/共22页感谢您的观看。第22页/共22页