北京企业网站制作哪家好,网站建设价格差别,购物网站有哪些?,建设银行网站图片13.数据结构#xff08;软考#xff09;
13.1:线性表
13.1.1 顺序表 顺序存储方式:数组的内存是连续分配的并且是静态分配的#xff0c;即在使用数组之前需要分配固定大小的空间。 时间复杂度#xff1a; 读#xff1a;O(1) 查询#xff1a;1#xff0c;(n1)/2#x…13.数据结构软考
13.1:线性表
13.1.1 顺序表 顺序存储方式:数组的内存是连续分配的并且是静态分配的即在使用数组之前需要分配固定大小的空间。 时间复杂度 读O(1) 查询1(n1)/2n 插入1(n1)/2n 删除1(n1)/2n-1 优势在于读操作。 13.1.2 链表 链表(linked-list)存储方式:链表的内存是不连续的前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的所有元素串起来。 尾结点:最后一个有效结点。 首结点:第一个有效结点。 头结点:第一个有效结点之前的那个结点存放链表首地址。 头指针:指向头结点的指针变量。 尾指针:指向尾结点的指针变量。 特点: ①n个结点离散分布彼此通过指针相联系。 ② 除头结点和尾结点外每个结点只有一个前驱结点和一个后续结点。头结点没有前驱结点尾结点没有后继结点。 ③头结点并不存放有效数据只存放链表首地址。其头结点的数据类型和首结点类型一样。 ④加头结点的目的是方便对链表的操作比如在链表头部进行结点的删除、插入。 13.1.2.1 单项链表 插入 删除当前节点的下一个节点 删除当前节点 这里做了处理为将当前节点赋值为下一个节点值然后山出下一个节点 13.1.2.2 双向链表 插入 删除 13.1.3 顺序存储与链式存储对比 13.2:栈和队列 13.3:串 1.串的定义: 串是仅由字符构成的有限序列是一种线性表。一般记为S“abcdef”其中S是串名单引号括起来的字符序列是串值。 2.串的几个基本概念 (1)空串与空格串 空串:长度为零不包含任何字符。 空格串:由一个或多个空格组成的串。虽然空格是一个空白字符但它也是一个字符在计算串长度时要将其计算在内。 (2)子串与子序列 子串:由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串子串在主串中的位置是指子串首次出现时该子串的第一个字符在主串中的位置。空串是任意串的子串。 子序列:一个串的“子序列”(subsequence)是将这个串中的一些字符提取出来得到一个新串,并且不改变它们的相对位置关系。 (3)串比较与串相等 串比较:两个串比较大小时以字符的ASCII码值(或其他字符编码集合)作为依据。实质上比较操作从两个的第一个字符开始进行字符的码值大者所在的串为大;若其中一个串先结束则以串长较大者为大。 串相等:指两个串长度相等且对应序号的字符也相同。 3、串的基本操作: (1)赋值操作StrAssign(s,t):将串s的值赋给串t。 (2)连接操作Concat(s,t):将串t接续在串s的尾部形成一个新的串。 (3)求串长StrLength(s):返回串s的长度。 (4)串比较StrCompare(s,t):比较两个串的大小。返回值-1、0和1分别表示st和st三种情况。st. (5)求子串SubString(s,start,len):返回串S中从start开始的、长度为len的字符序列。 4、串的存储 (1)顺序存储 (2)链式存储 模式匹配:子串的定位操作通常称为串的模式匹配。(子串也称为模式串) 朴素的模式匹配算法(布鲁特-福斯算法):其基本思想是从主串的第一个字符起与模式串的第一个字符比较若相等则继续逐一对字符进行后续的比较否则从主串第二个字符起与模式串的第一个字符重新比较直到模式串中每个字符依次与主串中一个连续的字符序列相等时为止此时称为匹配成功。如果不能在主串中找到与模式串相同的子串则匹配失败。 改进的模式匹配算法(KMP算法): 其改进之处在于-每当匹配过程中出现相比较的字符不相等时不需要回退到主串的字符位置指针而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离再继续进行比较。 在KMP算法中依据模式串的next函数值实现子串的滑动。若令next[i]k则next[]表示当模式串中的p;与主串中相应字符不相等时令模式串的pnexu与主串的相应字符进行比较。(jnext[j])next函数的定义如下: KMP是进行字符串模式匹配运算效率较高的算法。根据对 next 函数的定义模式串前两个字符的 next 值为 0、1。 对于第3 个字符 “a”其在模式串中的前缀为“ab”从该子串找不出前缀和后缀相同的部分因此根据定义该位置字符的next 值为 1。 对于第4个字符“a”其在模式串中的前缀为“ aba”:音量:8%1只有长度为1的前缀“a” 和后缀“a”相同根据定义该位置字符的 next 值为 2。 对于第5个字符 “a”其在模式串中的前缀为“abaa0”该子串只有长度为 1的前缀“a” 和后缀相同根据定义该位置字符的 next 值为 2。 综上可得模式串“abaac”的 next 函数值为 01122. 一、对于公式 1、由(1)式当j1时next[1]0; 2、当j1时由(2)式max{k|13、取值范围j、k都为正整数且1j5【可根据下面的具体过程理解公式】二、本题计算如下:2、1),电( nety,.lplp2Lpk1PIp2Lp1p1,为第一个字母a;pik1pj-k2Lpj-1p2p3Lp2p2为第二个字母ba!b此时找不到k不满足条件由(3)式next[3]1. 4、j4满足1(1)当k2,plp2Lpk-1p1p2Lp1p1为第一个字母apj-klpjk2Lpj-1p3p4Lp3p3为第三个字母a满足p1p2Lpk-1pj-klpj-k2Lpj-1。(2)当k3p1p2Lpk-1p1p2Lp2p1p2为第一二字母abpj-klpj-k2Lpj1p2p3Lp3p2p3为第二三个字母ba不满足p1p2Lpk-1pj-klpj-k2Lpj-1。综上可得当j-4时满足条件的最大k值为2next[4]2。 5、j5满足1(1)当k2p1lp2Lpk-1plp2Lp1p1为第一个字母apj-klpjk2Lpj-1p4p5Lp4p4为第四个字母a满足plp2Lpk-1pj-klpj-k2Lpj-1。(2)当k3p1p2Lpk-1p1p2Lp2p1p2为第一二字母abpj-klpj-k2Lpj1p3p4Lp4p3p4为第三四个字母aa不满足p1p2Lpk-1pj-klpj-k2Lpj-1。(3)当k4p1p2Lpk-1p1p2Lp3p1p2p3为第一二三字母aba,pj-klpj-k2Lpj1p2p3Lp4p2p3p4为第二三四个字母baa不满足p1p2Lpk-1pj-klpj-k2Lpj-1综上可得当j5时满足条件的最大k值为2next[5]2。根据上面的分析过程可以得出next0函数值为01122.
