【软考】9.2 串/数组/矩阵/广义表/树

这篇具有很好参考价值的文章主要介绍了【软考】9.2 串/数组/矩阵/广义表/树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

《字符串》

  • 一种特殊的线性表,数据元素都为字符
  • 模式匹配:寻找子串第一次在主串出现的位置
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构
  • 模式匹配算法

1. 暴力破解法(布鲁特-福斯算法)

  • 主串与子串一个个匹配
  • 效率低
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构

2. KMP算法

  • 主串后缀和子串前缀能否找到一样的元素,能就把子串移上去,不用再对比,从主串当前中断的位置开始对比
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构
  • abaac:P1P2P3P4P5
    1. j=1 ——> next[1]=0
    1. j=2,1<k<2,其他情况 ——> next[2]=1
    1. j=3,1<k<3:k=2,‘P(2-1)’=‘P(3-1)’ ——> ‘P1’=‘P2’——> a=b,其他情况 ——> next[3]=1
    1. j=4,1<k<4:
      k=2,‘P(2-1)’=‘P(4-2+1)’ ——> ‘P1’=‘P3’——> a=a ——>next[4]=2;
      k=3,‘P1P(3-1)’=‘P(4-3+1)P(4-1)’ ——> ‘P1P2’=‘P2P3’——> ab=ba ,其他情况;
    1. j=5next[5]=2
  • 即 next = 01122
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构

《数组》

  • 适用于采用顺序结构
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构
  • 数组存储地址的计算
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构

《矩阵》

【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构文章来源地址https://www.toymoban.com/news/detail-718279.html

  • 直接带算式
  • a[1,1]——> B[1] ——> i=1,j=1,k=1;
  • A[0,0]——>B[1];A[0,1]——>B[2];
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构

《广义表》

  • 长度:最外层包含的元素个数
  • 深度:单边括号的个数;原子的深度为0,空表深度为1
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构

《树与二叉树》

  • 线性表的每个节点只有一个入度和一个出度
  • 树的每个节点只有一个入度,多个出度
  • 度:一个结点的子树个数
  • 叶子结点:度为0的结点
  • 树的高度(深度):一棵树的最大层数
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构
  • 二叉树
  • 二叉树:每一个结点的度 ≤2
  • 满二叉树:除了最后一层的叶子结点外,每一个结点的度都是2
  • 一共有k层,第 k-1 层是满的,第 k 层:
  • (完全二叉树)从左到右是不间断的(如左4右5,左6)
  • (非完全二叉树)从左到右是可间断的(如左4右5,右6)
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构
  • 二叉树的性质
  • 二叉树第 i 层 至多有 2^(i -1) 个节点
  • 深度为k的二叉树(满二叉树)至多有 (2^k) -1 个节点
  • 终端节点数为n0,度为2的节点数为n2,则 n0 = n2 +1
    【软考】9.2 串/数组/矩阵/广义表/树,数据库/数据结构,链表,矩阵,数据结构

到了这里,关于【软考】9.2 串/数组/矩阵/广义表/树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构【数组、串、广义表】

    一、数组 1.概念:线性表是通过数组实现的,数组是线性表的推广,数组只有存取元素和修改元素的操作(除了初始化和销毁); 2.数组的存储结构:一个数组的所有元素在内存中占用一段连续的存储空间(顺序存储); 以行为主顺序优先存储; 以列为主顺序优先存储。

    2024年02月15日
    浏览(40)
  • 数据结构--串、数组、广义表

    也叫字符串 抽象类型定义 存储结构(顺序表较为常用) 顺序存储结构 为了方便一些操作,通常串的数组的第一个位置不放元素,而是从ch【1】开始存放元素 链式存储结构 如果一个结点的数据域只放一个字符,那么会导致存储密度异常的底,解决这个问题:在数据域放更多的

    2024年02月15日
    浏览(38)
  • 数据结构—数组和广义表

    4.2数组 数组: 按一定格式排列起来的,具有 相同类型 的数据元素的集合。 **一维数组:**若线性表中的数据元素为非结果的简单元素,则称为一维数组。 **一维数组的逻辑结构:**线性结构,定长的线性表。 **声明格式:**数据类型 变量名称 [长度] ; 例如:int num[5] = {0,1

    2024年02月15日
    浏览(45)
  • 数据结构之串|数组|广义表

    总结:

    2024年01月16日
    浏览(43)
  • 数据结构与算法·第5章【数组和广义表】

    两种顺序映象的方式: 以行序为主序(低下标优先); 以列序为主序(高下标优先)。 而 n n n 维数组: LOC(x1, x2, ..., xn) = LOC(0, 0, ..., 0) + [(x1 × b1 + x2) × b2 + x3] × b3 + ... + xn 数据类型定义 其中: A.bounds是每一维可以放多少元素: a[A.bounds[0]][A.bounds[1]][A.bounds[2]]…… A.constants是指向每

    2024年02月08日
    浏览(46)
  • 数据结构--》数组和广义表:从基础到应用的全面剖析

            数据结构为我们提供了组织和处理数据的基本工具。而在这个广袤的数据结构领域中,数组和广义表是两个不可或缺的重要概念。它们作为线性结构的代表,在算法与应用中扮演着重要的角色。         无论你是初学者还是进阶者,本文将为你提供简单易懂、

    2024年02月08日
    浏览(45)
  • 数据结构与算法分析 第七章 串、数组和广义表 作业讲解

     参考教材: 《数据结构(C语言版 第2版)》 严蔚敏,李冬梅,吴伟民编著,人民邮电出版社,2022年版。 截图未标明出处均为原创或取自《数据结构(C语言版 第2版)》~   本文对应的作业题讲解视频:   数据结构与算法分析作业讲解视频合集 https://www.bilibili.com/video/BV1N

    2024年02月04日
    浏览(46)
  • 数据结构与算法教程,数据结构C语言版教程!(第五部分、数组和广义表详解)三

    数组和广义表,都用于存储逻辑关系为“一对一”的数据。 数组存储结构,99% 的编程语言都包含的存储结构,用于存储不可再分的单一数据;而广义表不同,它还可以存储子广义表。 本章重点从矩阵的角度讨论二维数组的存储,同时讲解广义表的存储结构以及有关其广度和

    2024年01月21日
    浏览(48)
  • 数据结构与算法教程,数据结构C语言版教程!(第五部分、数组和广义表详解)五

    数组和广义表,都用于存储逻辑关系为“一对一”的数据。 数组存储结构,99% 的编程语言都包含的存储结构,用于存储不可再分的单一数据;而广义表不同,它还可以存储子广义表。 本章重点从矩阵的角度讨论二维数组的存储,同时讲解广义表的存储结构以及有关其广度和

    2024年01月23日
    浏览(49)
  • 【软考数据库】第六章 数据库技术基础

    目录 6.1 基本概念 6.1.1 关于数据的基本概念 6.1.2 数据库管理系统的功能 6.1.3 数据各个发展阶段的特点 6.1.4 数据库系统的体系结构 6.2 数据模型 6.2.1 三级模式两级映像 6.2.2 数据模型_模型分类 6.2.3 数据模型_组成要素 6.2.4 概念模型中的基本概念 6.2.5 数据模型 6.3 数据存储与查

    2024年02月05日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包