预习篇之串、数组和广义表

(笔试重点 :笔试选择题:好像有算子串的个数吧,方正不多;编程题笔试偏多偏简单,算送分题多,就是那种一版会编程的读了题就能做的,eg:字符串局部位旋转,单词颠倒等 )

串(字符串):是零个或多个字符组成的有限序列,一般记为S=‘a1a2…..an’,属于取值受限的线性表”为任意串的子串。

主串:包含子串的串相应地称为主串

位置:字符在串中的序号称为该字符在串中的位置。

串相等:只有两个串的长度相等,且每个对应的字符都相等时才相等。

空格串:由一个或多个空格组成的串,非空串。

存储:

定长顺序串:存储分配是在编译时完成的,用一组地址连续的存储单元存储串的字符序列。(开始下标:0,;结束标志字“\0”)

堆分配存储(堆串),用称为“堆”的自由存储空间,并可用malloc()和free()函数完成动态存储管理。

串的块链存储表示(链表):

串的模糊匹配算法:朴素模式匹配算法(Brute-Force算法,简单匹配算法)、KMP算法

数组和广义表

(见过相关的选择题,出的不多,了解概念就好)

数组

定义:n(n>1)个相同类型数据元素a0,a1,…,an-1构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。是线性表在元素上的扩展。

矩阵的压缩存储:特殊存储(对称矩阵、三角矩阵、对角矩阵)

广义表

定义:是线性表的推广,是由零个或多个单元素或子元素所组成的有限序列

广义表的长度:表中所含元素的个数n

广义表的深度:广义表展开后所含的括号的最大层数

表头:非空时,称第一个元素a1为广义表的表头,可能是原子,也可能是广义表;

表位:其余元素组成的表(a2,a3…….an)称为广义表的表尾,一定是广义表。

存储:头尾链表存储表示、扩展线性存储表示、

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180409G1OR8400?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券