0

Image Description

荆文征

Zhidu Inc.


你好,再见

大话数据结构 - 串 (5)

  • 小酒馆老板
  • /
  • 2018/1/3 10:7:0


H2


H3

栈的定义

早先的计算机在被发明是,只要作用是做一些科学和工程的计算工作,也就是现在我们理解的计算器,只不过它比小小计算器功能更强大,速度更快一些。后来发现,在计算机上做的非数值处理的工作越来越多,使得我们不得不需要引入对字符的处理。于是就有了字符串的概念。
比如我们现在常用的搜索引擎,当我们在文本框中输入“数据”时,他已经把我们想要的“数据结构”列在下面了。显然网站这里做了一个字符串查找匹配的工作。

今天我们就来研究“串”这样的数据结构。

串(String)是由零个或者多个字符组成的优先序列,又名叫字符串。

一般记为s=”a1a2…..an”(n>=0),其中,s是串的名称,用双引号(有些书中也有单括号)扩起来的字符序列是串的值,注意单引号不属于串的内容。ai(1<=i<=n)也可以字母,数字或其他字符,i就是该在字符在传中的位置。串中的字符数目n称为串的长度, 定义中谈到“有限”是指长度n是一个有限的数值。零个字符的串称为空串(null string),他的长度为零,可以直接用两双引号““””表示,也可以用希腊文字“Φ”表示。所谓的序列,说明穿的相邻字符之间具有前驱后继的关系。
还有一些概念徐耀解释。
空格穿,只包含空格的串。注意他与空串的区别,空格串是有内容和长度的,而且可以不止一个空格。
子串和主串,串中任意个数的连续字符组成的子序列成为该串的子串,相应的,包含子串的串称为主串。
子串在主串的位置就是子串的第一个字符在主串中的序号。
开头我提到的“over”,“end”,”lie”其实可以认为是“lover”,“friend”,“believe”这些单词字符串的子串。


H2

串的比较

两个数字,很容易比较大小。2比1大,这完全正确,可是两个字符串如何比较?比如“silly”,“stupid”这样的同样表达“愚蠢”的字符串,他们在计算机的大小其实取决与他们挨个字母的前后顺序。它们的第一个字母都是“s”,我们认为不存在大小差异,而第二个字母,由于“i”字母比“t”字母要靠前,所以“i”<”t”,于是我们说“silly”<“stupid”。
事实上,串的比较是通过组成串的子复之间的编码来进行的,而字符的编码指的是字符在对应字符集中的序号。
计算机的额常用字符串使用标准的ASCII编码,更准确一点,有7为二进制表示一个字符,总共可以表示128个字符。后来由于一些特殊字符的出现,128个不够用,于是扩展ASCII编码由8为二进制表示一个字符,总共可以表示256个字符,这已经足够满足以英语为主的语言和特殊字符进行输入和输出等操作的字符需要了。可以,但我们国家就有除汉语外的满,回,藏,蒙古,维吾尔等多个少数民族文字,换做全世界估计要有成百上重语言和文字,显然这个256个字符是不够的,因此后来就有了 Unicode 编码,比较常用的是由 16位的二进制数表示一个字符,这样总共就可以表示216个字符,约是65万多个字符,足够表示世界上搜有的语言的所有字符了。当然,为了和ASCII码兼容,Unicode的前256个字符和ASCII码完全相同。
所以如果我们要在C语言中比较两个串是否相等,必须是他们串的长度以及它们各个位置相等是。
那么对于来两个串不相等是,如何判定它们的大小呢,我们这样定义:
给定两个串:s=“a1,a2…an”,t=“b1,b2,…bm”,当满足以下条件之一时,s<t

  1. n<m,切ai=bi(i=1,2..n)。
    例如当s=“hap”,t=“happy”,就有s<t.因为t比s又多出了两个字符
  2. 存在某个k<=min(m,n),使得ai=bi(i=1,2….,k-1),ak<bk
    例如当s=“happen”,t=“happy”,因为两串的前4个字母均相同,而两川的第五个字母(k值),字母e的ASCII是101,而字母y的ASCII码是121,显然e<y,所以s<t。


    H2

    串的抽象数据类型

    串的逻辑结构和线性表很相似,不同之处在于串针对的是字符集,也就是传中的元素都是字符,哪怕是传中的字符是“123”这样的数字组成,或者“2010-10-10”这样的日期组成的,他们只能理解为长度为3和长度为10 的字符串,每个元素都是字符而已。
    因此对于串的基本操作与线性表还是有很大差别的。线性表更关注的是但个元素的操作,比如查找一个元素,插入或删除一个元素,但串中更多的是出查找子串位置,得到指定位置的子串,替换子串的操作。

    protocol String{
    
    ///               __,
    ///              (          o   /) _/_
    ///               `.  , , , ,  //  /
    ///             (___)(_(_/_(_ //_ (__
    ///                          /)
    ///                         (/
    func StrAssign(chars:[Character]) -> String
    // 。。。。略
    }
    

    H2

    串的存储结构

    穿的存储结果与线性表相同,分为两种。


    H3

    串的顺序存储结构

    串的顺序春初结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区。一般是用给定长数组来定义。
    既然是定长数组,就存在一个与定义的最大字符串,一般可以讲世纪的串长度值保存在数组的0下标位置,由的书中也会定义存储在数组的最后一个小婊位置。但也有些编程语言不这么干,觉的存个数组占个空间嫌麻烦。它规定在串值后面加一个不计入串长度的结束标记字符,比如“\0”来表示串值的中介,这个时候,你要想知道此时的串长度,就需要遍历计算一下才知道了,其实这还是需要占用一个空间,何必呢。
    刚才讲的串的顺序存储方式其实是有问题的,因为字符串的操作没比如两川的链接Concat,新串的插入StrInsert,以及字符串的替换Replace,都有可能是德川序列的长度超过了数组的长度MaxSize。


    H3

    串的链式存储结构

    对于串的链式存储结构,与线性表是相思的,但由于串结构的特殊性,结构中的每个元素数据是一个字符,如果也简单的应用链表春初船只,一个节点对应一个字符,就会存在很大的空间浪费。因此,一个节点可以存放一个字符,也可以考虑存放多个字符,最后一个节点若是未被占满时,可以用“#”或者其他非传旨字符不全。


    Image Description
    串链式存储结构示意图


    当然,这里一个节点存多少字符才合适就变得很重要,这会直接影响着串处理的效率,需要根据实际情况做出选择。
    单穿的链式存储结构在链接串与串操作时有一定方便之外,总的来说不如顺序存储灵活,性能也不如顺序存储结构好。


    H2

    朴素的模式匹配算法

    记得我在刚做软件开发的时候,徐耀阅读一些英文的文章或帮助。此时才发现学习英语不只是为了过四六级,工作中他还是挺重要的。而我哪只为应付考试的英语,早已经忘记的差不多了。于是我想在短时间内突击一下,很明显,找一本词典从头开始被不是什么好的办法。要被也得被那些最常用的,最少是计算机文献中长哟过的,于是我就想自己写一个程序,只要输入一些英文的文档,就可以计算出这当中所用频率最高的词汇是哪些。那他们都备好了,基本上阅读就不成问题了。
    当然说说容易,要实现这一个需求,还是有不少困难的,有兴趣的同学,不妨去试试看。不过这里面最重要的就是找一个单词在一篇文章(相当于一个大字符串)中的定位问题。这种子串的定位操作通常称为串的模式匹配。应该是串中最重要的操作之一。
    假设我们要从下面的主串S=”goodgoodle”中,找到T=”google”这个子串的位置。我们通常需要下面的步骤。

extension String{


    /// 朴素方式 查询字符串是否包含 另一个字符串 并且给出第一个 匹配的位置
    ///
    /// - Parameters:
    ///   - string: 另一个字符串
    ///   - pos: 偏移量 默认为 0
    /// - Returns: 返回 元组 (是否存在,偏移量)
    func contain_N(str:String,pos:Int=0) -> (contain:Bool,index:Int){

        // 偏移量 是否超过了 最后剩下位数还没有找到 那么就放弃查找
        // 例如 "abc" "ac" 当偏移量 为 2 时 大于了 那么没有寻找下去的必要了
        if pos > (self.count - str.count) {

            return (false,0)
        }

        // 挨个匹配
        for (index,chat) in str.enumerated() {

            if let result = self.char(byIndex: pos+index) , result == chat{

                continue
            }

            return self.contain_N(str: str, pos: pos+1)
        }

        // 完成匹配 返回 争取已经返回 pos 偏移量
        return (true,pos)
    }


    /// 返回 字符串的 个数,方便查看
    var count:Int{

        return self.lengthOfBytes(using: String.Encoding.utf8)
    }

    /// 提取 String Index 中的 字符
    func char(byIndex index:Int) -> Character? {

        if index >= self.count {

            return nil
        }

        return self[self.index(self.startIndex, offsetBy: index)]
    }
}

///// 测试

let mainString = "aixabc"
let subString =  "abc"

mainString.contain_N(str: subString)

/// Log: (contain true, index 3)

简单说就是,就是对主串的每一个字符作为子串开头,与要匹配的字符串进行匹配。对主串做大循环,每个字符串开头做T的长度的小循环,知道匹配成功或者全部遍历完成。

这种方法的时间复杂度是O(mn) m和n分别为字符串的长度。 所以有没有办法可以更快的解决这个匹配呢?


H2

KMP模式匹配算法

你可以忍受朴素模式的滴小阿妹?也许不可以,也许无所谓。但在很多年前我们的科学家,觉的像这种有多个0和1重复字符的字符串,却要挨个遍历的算法是非常糟糕的事情,于是就有三位前辈,D.E.Knuth、J.H.Morris和V.R.Pratt(其中Knuth和Pratt共同研究,Morris独立研究)发表 一个模式匹配算法,可以大大避免重复便利的情况,我们把它称为克努特-莫里斯-普拉特算法,简称KMP算法。


H3

KMP模式匹配算法原理

为了能讲清楚KMP算法,我们不直接讲带啊吗,那样很容易造成理解困难,还是从这个算法的研究角度来理解为什么他比朴素算法要好。
如果主串 S=”abcdefghab”,其实还可以更长一些,我们就省略掉只保留前9位,我们要匹配的T=”abcdex”,那么如果用前面的算法的话,前5个字母,两个字符串完成相同,知道第6个字木,f与x不等。


Image Description
朴素算法示意图

算法以后会补上,目前没有看懂

专栏: 数据结构
标签: 数据结构 计算机基础