python数据结构教程第二课
字符串是计算机数据处理过程中最重要，也是最基础的内容，学好它会帮助我们的编程更加高效简洁
一.简介
二.字符串的抽象数据类型
三.字符串的匹配算法
1 朴素匹配算法
2 KMP匹配算法
四.字符串类的链表实现
五.正则表达式
1.什么是正则表达式
2.python的正则表达式
一.简介
在计算机领域中，基本的文字符号称为字符，符号的序列称为字符串，有穷的一组字符构成的集合称为字符集，在实际中经常使用的字符集有ASCII字符集或者Unicode字符集，python2.5以后默认的字符集就是ASCII字符集。
二.字符串的抽象数据类型（ADT）
一个字符串类型应当有的方法有切片，按位取元素、返回字符串长度、字符串拼接等，其基本ADT如下：
ADT String:
String(self,sseq) #基于字符序列sseq建立一个字符串
is_empty(self) #判断本字符串是否空串
len(self) #返回字符串长度
char(self,index) #返回位于index位置的字符
substr(self,a,b) #取得位置在[a,b]区间的子字符串
match(self,str) #查找str在串中出现的第一个位置
concat(self,str) #将本字符串与str拼接成新串
subst(self,str1,str2) #将字符串里的str1替换为str2
上列match(self,str)中，self被称为目标串，str被称为模式串。
这里要提及的是，在python内部已经有了较为完善的字符串类型str，所以本篇介绍的重点不在于字符串本身类型的实现，而在与基于字符串类型的重要操作和算法，接下来会列出python中str类型的一些常用方法，然后依次介绍字符串的重要操作——字符串匹配，字符串类型的链表实现以及进阶内容——正则表达式。
str类的常用方法如下：
str1 = str('hello world!') #建立新串
str2 = str1[0:6] #从旧串切片或的新串
str3 = str2 + str1 #两个串的连接
for char in str3: #支持yield操作
print(char, end = '') #输出str3
print() #换行
print(len(str3)) #取字符串长度
stra = '**##'
strb = '1111'
strc = strb.join(stra) #插入操作，stra为分隔符
print(strc)
上列代码的输出为：
hello hello world!
18
*1111*1111#1111#
三.字符串的匹配算法
字符子串匹配是字符串操作中非常重要的一个，同时它也是很多更高级字符串操作的基础，这里介绍两种，一种是基本的、通俗的朴素匹配算法，另一种是高级的KMP算法
1.朴素匹配算法
朴素匹配算法采用最直观可行的策略：
1）使用模式串与目标串从左到右逐个字符匹配
2）发现不匹配时，转去考虑目标串的下一个位置是否与模式串匹配
3）匹配成功则结束算法
朴素匹配算法非常简单，容易理解，但其效率很低，这里直接给出匹配算法
def naive_matching(t,p):
m,n = len(p),len(t)
i,j = 0,0
while i < m and j < n: #i==m说明找到匹配
if p[i] == t[j]: #字符相同则考虑下一对字符
i,j = i+1,j+1
else: #字符不同则考虑t中的下一位置
i,j = 0,j-i+1
if i == m: #找到匹配，返回位置
return j - i
return -1 #无匹配值，返回-1
仔细分析上面的代码，可以发现其效率低下的原因在于执行中可能出现回朔，即：匹配中一旦遇到不同，模式串就回到目标串中前面的下一个位置，从那里再次从头开始比较字符。这相当于把每次的字符比较看成完全独立的操作，完全没有利用字符串本身的特点，也没有充分利用前面已经做过的字符比较中得到的信息，这里再介绍一种高效的匹配算法
2.KMP匹配算法
与朴素匹配算法相比，KMP匹配算法的效率又了本质的提高，其主要优势在于，克服了朴素匹配算法中的回朔现象。我们可以这么考虑：当一次匹配失败之后，模式串并不返回目标串的前面从下一位置重新开始，而是停留在失败的位置i，尝试模式串前面某一位置k与目标串的这一位置继续进行比较，这样就可以充分利用上一次比较的信息
模式串中每一个位置i的元素都对应着自己失败后应该跳转的位置k，我们称这个表为pnext，同时应当指出的是，pnext与目标串无关，可以依靠模式串本身的信息建立
现在假设我们已有了pnext表，给出KMP算法的函数代码：
def matching_KMP(t,p,pnext):
j,i = 0,0
n,m = len(t),len(p)
while j < n and i < m: #i==m说明找到匹配
if i == -1 or t[j] == p[i]:
j,i = j+1,i+1 #比较下一字符
else: #失败则根据pnext表查找模式串跳转位置
i = pnext[i]
if i == m: #找到匹配，返回下标
return j-i
return -1 #无匹配，返回-1
上列代码第五行，判断条件有 i == -1是因为，在一些匹配失败的情况下，可能存在匹配失败的字符之前所做的匹配都不包含利用价值，这种情况就需要从头开始，因此在pnext[0]中存入 -1
接下来，我们讲述pnext表的构建
这里先给出前缀、后缀的定义：
假设有串‘abcab’
则将‘a’、‘ab’、‘abc’、‘abca’称为母串的前缀
又将‘b’、‘ab’、‘cab’、‘bcab’称为母串的后缀
模式串中位置k匹配失败后，调转的位置取决于前k-1个字符中，最长相等前后缀的大小，如上‘abcdabcgd’建立的pnext表为：[-1, 0, 0, 0, -1, 0, 0, 3, 0]
这里使用递推的思想求解pnext表：
1）当位于k的元素值与位于i的元素值相等时，如果k+1等于i+1则我们可以知道k+1对应的跳转位置就为i+1的跳转位置，如果k+1不等于i+1，则k+1的跳转位置对应于i+1
2）当位于k的元素值与位于i的元素值不相等时，i的值跳转到pnext[i]
3）k为匹配错误位置，i为前k-1个元素中的最大相等前后缀长度，pnext[0] = -1
由上面的步骤我们可以得到pnext的求解函数
def gen_pnext(p):
k,i,m = 0,-1,len(p)
pnext = [-1]*m #所有初始值设为-1
while k < m-1:
if i == -1 or p[k] == p[i]: #
i,k = i+1,k+1
if p[k] == p[i]:
pnext[k] = pnext[i]
else:
pnext[k] = i
else:
i = pnext[i]
return pnext
下面使用KMP算法举个例子：
stra = 'hello! this is KMP_matching'
strb = 'this'
pnext = gen_pnext(strb)
k = matching_KMP(stra,strb,pnext)
print(stra)
print(strb)
print('\"'+strb+'\"'+' in '+'\"'+stra+'\"' +'\'s ' + str(k))
结果为：
hello! this is KMP_matching
this
"this" in "hello! this is KMP_matching"'s 7
四.字符串类的链表实现
利用单链表实现字符串类可以更方便的实现字符串的插入删除操作，接下来给出使用链表实现的字符串类源码，包含了字符串类的一些基本方法：
import copy #导入复制库
#链表的结点类
class Node:
def __init__(self,char,next_ = None):
self.char = char
self.next = next_
'''字符串的链表类构造，实现了字符串的初始化、输出、求长度、朴素匹配算法、按位置返回字符、子串替换、KMP匹配算法、字符移除等方法'''
class strllist:
def __init__(self,string = None): #初始化
self.head = Node()
if string is None:
self.num = 0
elif string =='':
self.head.char =''
self.num = 1
else:
self.head.char = string[0]
p = self.head
i = 1
while i < len(string):
t = Node(string[i])
p.next = t
p = p.next
i += 1
self.num = len(string)
def __len__(self): #返回串长度
return self.num
#朴素匹配算法的链表实现
def naive_matching(self,string):
p = self.head
q = self.head
m = len(string)
i = 0
k = 1
while p is not None and i < m:
if p.char == string[i]:
p = p.next
i += 1
else:
i = 0
q = q.next
p = q
k += 1
if i == m:
return k
else:
return -1
#返回第i个字符
def go_loc(self,i):
k = 1
p = self.head
while k < i:
p = p.next
k += 1
return p
#将字符串里的stra替换为strb
def replace(self,stra,strb):
while self.naive_matching(stra) != -1:
i = self.naive_matching(stra)
if i == 1:
p = self.go_loc(len(stra)+1)
bllist = strllist(strb)
self.head = bllist.head
q = self.go_loc(len(strb))
q.next = p
else:
p = self.go_loc(i-1)
q = self.go_loc(i+len(stra))
bllist = strllist(strb)
p.next = bllist.head
t = bllist.go_loc(len(strb))
t.next = q
#字符串输出
def printall(self):
p = self.head
while p is not None:
print(p.char,end = '')
p = p.next
print()
#静态方法，求串的pnext表
@staticmethod
def gen_pnext(p):
m = len(p)
pnext = [-1] * m
i,k = 0,-1
while i < m-1:
if k == -1 or p[i] == p[k]:
i,k = i+1,k+1
if p[i] == p[k]:
pnext[i] = pnext[k]
else:pnext[i] = k
else:
k = pnext[k]
return pnext
#KMP匹配算法
def matching_KMP(self,string,pnext):
p = self.head
m = len(string)
i = 0
k = 1
while p is not None and i < m:
if i == -1 or p.char == string[i]:
i += 1
p = p.next
k += 1
else:
i = pnext[i]
if i == m:
return k - i
return -1
#移除串里的stra
def remove(self,stra):
while self.naive_matching(stra) != -1:
i = self.naive_matching(stra)
if i == 1:
self.head = self.go_loc(len(stra)+1)
else:
p = self.go_loc(i-1)
q = self.go_loc(i+len(stra))
p.next = q
举例：
a = strllist('abcdefg abcdefg')
b = str('a')
a.printall()
a.remove(b)
a.printall()
结果：
abcdefg abcdefg
bcdefg bcdefg
五.正则表达式
1.什么是正则表达式
正则表达式，又称为规则表达式（Regular Expression，常简写为regex、regexp或RE），正则表达式是对字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。
给定一个正则表达式和另一个字符串，我们可以达到如下的目的：
- 给定的字符串是否符合正则表达式的匹配
- 可以通过正则表达式，从字符串中获取我们想要的特定部分
正则表达式的特点是： - 灵活性、逻辑性和功能性非常强
- 可以迅速地用极简单的方式达到字符串的复杂控制
- 对于刚接触的人来说，比较晦涩难懂
正则表达式是字符串操作中较高级与复杂的部分，这里只简单介绍python的正则表达式与基本应用
2.python的正则表达式
python的正则表达式包re规定了一组特殊字符，称为元字符，在匹配字符串的时候，它们起着特殊的作用，元字符一共有14个：
. ^ $ * + ? \ | { } [ ] ( )
在普通字符串里除了转义字符 \ 其余的都是普通字符，只有在它们出现在re包提供的一些特殊操作时，这些字符才有特殊意义
python re包的主要操作：
#生成正则表达式对象
r1 = re.complie(pattern, flag = 0)
#在string里检索pattern对象
re.search(pattern, string, flag = 0)
#检查string里是否存在与pattern匹配的前缀
re.match(pattern,string,flag = 0)
'''以pattern为分隔符将string分段，maxsplit指明最大分割数，flags = 0表示处理完整个string'''
re.split(pattern, string,maxsplit=0,flags = 0)
先前介绍了python re包里的一些元字符，接下来将具体介绍各种元字符的意义
1）字符组描述符 […]：
表示与方括号中列出的任一字符匹配，字符的排序不重要
[abc] 可与 a 或 b 或 c 匹配
[0-9a-zA-Z] 可匹配所有数字和字母
a[1-9][0-9] 可匹配a10,a11,a12…a99
[^…] 表示对^之后的字符组求补
2）圆点字符 . :
圆点字符是通配符，可以匹配任意字符
a…b 可以匹配以a开头以b结尾的任意4字符
3）转义字符 \ :
转义字符定义了一些常用的字符组，如：
\d 与十进制数字匹配
\D 与非十进制的所有字符匹配
\s 与空白字符匹配
\S 与非空白字符匹配
\w 与字母数字符匹配
4）重复描述符 ：
模式 a 要求该匹配模式可以匹配a的0次或任意多次重复
如：
import re
re.split('a*','abbaaabbbddbbabbaddaaaddaa')
得到：
['', 'bb', 'bbbddbb', 'bb', 'dd', 'dd', '']
5）可选描述符 ?:
模式a? 可以与空串或与a匹配，如：
-?\d+可表示所有整数
6） 确定次数重复 {n}:
a{n} 与a的n次重复匹配
7）重复次数范围描述符 {m,n}:
a{m,n}可以与a的m次到n次重复匹配
8）选择描述符 |：
a|b|c表示可与a或b或c中的任意一个匹配
9）首位描述符
行首描述符：‘^a’只能与位于行首的前缀子串a匹配
行尾描述符: ‘$a’只能与位于行尾的后缀子串a匹配
串首描述符：‘\A’开头的模式只能与整个被匹配串的前缀匹配
串尾描述符: ‘\Z’结束的模式只能与整个被匹配串的后缀匹配