程序猿必修课之数据结构(九)串

原文://www.greatytc.com/p/d0ad73bd638f

你还在为开发中频繁切换环境打包而烦恼吗?快来试试 Environment Switcher 吧!使用它可以在app运行时一键切换环境,而且还支持其他贴心小功能,有了它妈妈再也不用担心频繁环境切换了。https://github.com/CodeXiaoMai/EnvironmentSwitcher

上一章:程序猿必修课之数据结构(八)队列

串的定义

串(String)是由零个或多个字符组成的有限序列,又名字符串。

从定义中可以看出:、

  • 串的字符数目是“有限”的,零个字符的串叫“空串(null string)”。
  • 它是一个序列,相邻字符之间具有前驱和后继关系。

空格串

只包含空格的串叫“空格串”,它和空串的区别是:空格串是有内容有长度的,而且可以不止一个空格。

子串与主串

串中任意个数的连续字符组成的子序列称为该串的子串,相应的,包含子串的串称为主串。

子串在主串中的位置就是子串的第一个字符在主串中的序号。

串的比较

数字可以比较大小,串同样可以比较大小,只不过串的比较是通过比较组成串的字符之间的编码来进行的,而字符的编码指的是字符在对应字符集中的序号。

比较两个串是否相等,必须满足两个条件:

  1. 两个串的长度相等
  2. 两个串的各个对应位置的字符都相等。

编码知识

计算机中的常用字符是使用标准的 ASCII 编码,它由 7 位二进制数表示一个字符,总共可以表示 128 个字符。后来发现缺少一些特殊符号,于是扩展 ASCII 码产生,它由 8 位二进制数表示,总共可以表示 256 个字符,这足够以英语为主的语言和特殊符号进行输入、存储、输出等操作的字符需要了。但是对于以汉字为代表的象形文字来说,显然 256 个字符是不够的,因此后来就有了 Unicode 编码。

串的抽象数据类型

ADT 串(string)

Data 串中相邻元素具有前驱和后继关系

Operation
    
    copy(t, s): 由串 s 复制得到 t。
    clear(s): 串 s 存在,将串清空。
    isEmpty(s): 若串 s 为空,返回 true,否则返回 false
    length(s): 返回串 s 的无数个数,即串的长度
    compare(s, t): 若 s > t,返回值为正数;若 s == t,返回 0;若 s < t,返回负数。
    contat(t, s1, s2): 将 s1 和 s2 拼接成 t 返回。
    subString(sub, s, pos, len): 若串存在, 1 <= pos <= length(s),且 0 <= len <= length(s) - pos + 1,用 sub 返回串 s 的第 pos 个字符起长度为 len 的子串。 
    index(s, t, pos): 串 s 和 t 存在, t 是非空串, 1 <= pos <= length(s)。若主串 s 中存在和串 t 值相同的子串,则返回它在主串 s 中第 pos 个字符之后第一次出现的位置,否则返回 -1。
    replace(s, t, v): 串 s、t 和 v 存在,t 是非空串。用 v 替换主串 s 中出现的所有与 t 相等的子串。
    insert(s, pos, t): 串 s 和 t 存在, 1 <= pos < length(s) + 1。在串 s 的第 pos 个字符之前插入串 t。
    delete(s, pos, len): 串 s 存在,1 <= pos <= length(s) - len + 1。从串 s 中删除第 pos 个字符起长度为 len 的子串。

endADT

串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的,按照预定义的大小,为每个定义的串分配一个固定长度的存储区(一般是用定长数组)。

但是串的顺序存储方式存在一些问题,对于字符串的操作,比如拼接、插入、替换等,都有可能使得串的升序超过数组的长度。

串的链式存储结构

串的链式存储结构与线性表是相似的,但由于串结构的特殊性,结构中的每个元素数据是一个字符,如果一个结点对应一个字符,就会造成很大的空间浪费,因此,一个结点可以存储一到多个字符,最后一个结点若未被占满,可以用其他非串值字符补全。一个结点存多少个字符会直接影响着串处理的效率,需要根据实际情况做出选择。

串的链式存储结构除了在串的拼接等操作时方便之外,总的来说不如顺序存储灵活,性能也不如顺序存储结构好。

KMP模式匹配算法

下一章:程序猿必修课之数据结构(十)树1

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,639评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,277评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,221评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,474评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,570评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,816评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,957评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,718评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,176评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,511评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,646评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,322评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,934评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,755评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,987评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,358评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,514评论 2 348

推荐阅读更多精彩内容

  • 第一章 绪论 什么是数据结构? 数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 5,758评论 0 19
  • 1 数据2 算法3 线性表4 栈5 队列6 串朴素模式匹配算法 -子串的定位操作:从主串中找到子串KMP模式匹配算...
    oldSix_Zhu阅读 1,493评论 0 4
  • VisuAlgo!一,Date Structure的核心技术是分解和抽象二,基本概念和常用术语 三,逻辑结构1,逻...
    斜杠青年许晏铭阅读 874评论 0 0
  • 课程介绍 先修课:概率统计,程序设计实习,集合论与图论 后续课:算法分析与设计,编译原理,操作系统,数据库概论,人...
    ShellyWhen阅读 2,265评论 0 3
  • Part1 11、许多次告别 作者本篇描述了两次告别,一次是她家中养过的一只小鸟,另一次是她外婆。我记忆中最深刻的...
    虞筱xie阅读 129评论 0 1