数据结构ch04 串和数组.pptx

第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