- 1、本文档共86页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第4章 串和数组;串是由零个或多个字符组成的有限序列。记作str=a0a1…an-1(n≥0)。
串中所包含的字符个数n称为串长度,当n=0时,称为空串。
一个串中任意连续的字符组成的子序列称为该串的子串。
包含子串的串相应地称为主串。
若两个串的长度相等且对应字符都相等,则称两个串相等。; 【例4.1】设s是一个长度为n的串,其中的字符各不相同,则s中的所有子串个数是多少?;ADT String
{
数据对象:
D={ai | 0≤i≤n-1,n≥0,ai为字符类型}
数据关系:
R={r}
r={ai,ai+1 | ai,ai+1∈D, i=0,…,n-2}
基本运算:
StrAssign(cstr):由字符串常量cstr创建一个串,即生成其值等于cstr的串。
StrCopy():串复制,返回由当前串复制产生一个串。
getsize():求串长,返回当前串中字符个数。
geti(i):返回序号i的字符。
seti( i,x):设置序号i的字符为x。
Concat(t):串连接,返回一个当前串和串t连接后的结果。
SubStr(i,j):求子串,返回当前串中从第i个字符开始的j个连续字符组成的子串。
InsStr(i,t):串插入,返回串t插入到当前串的第i个位置后的子串。
DelStr(i,j):串删除,返回当前串中删去从第i个字符开始的j个字符后的结果。
RepStr(i,j,t):串替换,返回用串t替换当前串中第i个字符开始的j个字符后的结果。
DispStr():输出字符串。
};串的实现方式;和顺序表一样,用一个data数组和一个整型变量size来表示一个顺序串,size表示data数组中实际字符的个数。
为了简单,data数组采用固定容量为MaxSize(可以模仿顺序表改为动态容量方式)。;;;def SubStr(self,i,j): #求子串的运算算法
s=SqString() #新建一个空串
assert i=0 and iself.size and j0 and i+j=self.size #检测参数
for k in range(i,i+j): #将data[i..i+j-1]-s
s.data[k-i]=self.data[k]
s.size=j
return s #返回新建的顺序串;def Strcmp(s,t): #比较串s和t的算法
minl=min(s.getsize(),t.getsize()) #求s和t中最小长度
for i in range(minl): #在共同长度内逐个字符比较
if s[i]t[i]: return 1
elif s[i]t[i]: return -1
if s.getsize()==t.getsize(): #s==t
return 0
elif s.getsize()t.getsize(): #st
return 1
else: return -1 #st;串的实现方式;;链串的结点类型LinkNode(结点大小为1);一个链串用一个头结点head来唯一标识,链串类LinkString;;;def InsStr(self,i,t): #串插入运算的算法
s=LinkString() #新建一个空串
assert i=0 and iself.size #检测参数
p,p1=self.head.next, t.head.next
r=s.head #r指向新建链表的尾结点
for k in range(i): #将当前链串的前i个结点复制到s
q=LinkNode(p.data)
r.next=q; r=q #将q结点插入到尾部
p=p.next; while p1!=None: #将t中所有结点复制到s
q=LinkNode(p1.data)
r.next=q; #将q结点插入到尾部
p1=p1.next
while p!=None: #将p及其后的结点复制到s
q=LinkNode(p.data)
r.next=q; r=q #将q结点插入到尾部
p=p.next
s
文档评论(0)