[经济学]第4章 串.pptVIP

第4章 串 4.1 串的定义 元素是字符的线性表/若干个字符组成的有限序列。 记作： s= ‘a1a2...an’ (n?0) n为串的长度 n=0，空串 1. 求串长 length(s) 2. 赋值（=） assign (s,ss) ss为串常量 copy（s,t) t为串变量 3. 串连接 （+） concat(s,s1,s2) 例1：将t串插入到串s的第pos个字符前面。 substr(sub1,s,1,pos-1); substr(sub2,s,i,length(s)-pos+1); concat(sub1,sub1,t); concat(s,sub1,sub2); 例2：删除串s中第i个字符开始的连续len个字符。 substr(sub1,s,1,pos-1); substr(sub2,s,pos+len,length(s)-pos-len+1); concat(s,sub1,sub2); 4.2.1 顺序表示 -- 顺序串 一、静态 不确定串的最大长度，根据需要，随时分配 * * s1= ‘’ s2=‘ ’ s1是一空串；而s2中有3个空格字符，它的长度等于3，称此为空格串 例：s=‘abc defg’ s1=‘bc’ s2=‘ ’ s3=‘c de’均是s子串 s4=‘cde’不是s子串 每个元素形式:‘ ai’ 如‘a’、 ‘ 3’、 ‘ #’等 子串：串中连续的一段（ ‘aiai+1...ai+k’ ）。其在主串中的位置为i。 一、定义 一个大于0的数 s1s2 一个小于0的数 s1s2 0 s1= =s2 二、 基本操作 s1+s2 s 如： ‘abc ’+ ‘defg’=‘abc defg’ 4. 求子串 substr(sub, s, pos, len) 1≤pos ≤ length(s) 0≤len ≤ length(s)-i+1 5. 串比较 strcmp(s1,s2)= 替换 replace(s,s1,s2) 用s2替换s中所有与s1相等的不重叠的子串 0 t不是s子串 t第一个字符在s中的序号 t是s子串 s=‘abababa’ s1=‘aba’ s2=‘c’ replace(s,s1,s2) s=‘cbc’ 6. 插入insert(s,pos,t) 1≤pos ≤ length(s)+1 删除delete((s,pos,len) 1≤pos ≤ length(s) 0≤len ≤ length(s)-i+1 串的定位 index(s,t) //或index(s,t,pos) 返回值 1~5为基本操作 4. 2 串的表示和实现 类型定义 #define MAXLEN 串最大长度 typedef struct { char ch[MAXLEN] ； int length； }Sstring； 或 typedef unsigned char Sstring[MAXLEN+1]； ≤255 2、基本操作的实现 ① 联接 concat(Sstring s,Sstring s1,Sstring s2) 返回值 TRUE 未截断 FALSE 截断 Status { s[1..s1[0]]=s1[1..s1[0]]; if(s1[0]+s2[0]=MAXLEN) { s[s1[0]+1..s1[0]+s2[0]]=s2[1..s2[0]]; s[0]=s1[0]+s2[0]; return TRUE; } else { if(s1[0]MAXLEN) s[s1[0]+1..MAXLEN]=s2[1..MAXLEN-s1[0]] s[0]=MAXLEN; return