5:数据结构--5.1:线性结构,5.2:数组与矩阵

这篇具有很好参考价值的文章主要介绍了5:数据结构--5.1:线性结构,5.2:数组与矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 转上一节:

课程内容提要:

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

5:知识点考点详解  

5.1:线性结构

考点1:线性表

1:线性表

顺序表:数据在内存中紧邻。

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

(1)顺序存储方式:数组的内存是连续分配的,并且是静态分配的,即在使用数组之前需要分配固

定大小的空间。 

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

(2)链表(linked-list)存储方式:链表的内存是不连续的,前一个元素存储地址的下一个地址中存

储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的所有元素串起来。

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程 链表:

头指针:指向头结点的指针变量。

头结点:首结点之前的那个结点,存放链表首地址。

首结点:第一个有效结点。

尾结点:最后一个有效结点。

尾指针:指向尾结点的指针变量。

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

特点:

①n个结点离散分布,彼此通过指针相联系。

②除头结点和尾结点外,每个结点只有一个前趋结点和一 一个后继结点。头结点没有前趋结点,

尾结点没有后继结点。

③头结点并不存放有效数据,只存放链表首地址。其头结点的数据类型和首结点类型一样。

④加头结点的目的是方便对链表的操作,比如在链表头部进行结点的删除、插入。

链表的每个结点实际上是- -个结构体变量,它由若干成员组成,包括数据部分和存地址的指针变

量。例如:

 struct student

{

long num;

float score;

         struct student *next;

};

其中:next是成员名,是指针类型,

它指向struct student数据类型。

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

[链表的分类]

单链表 

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

循环链表

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

[链表的基本操作]

单链表删除结点

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

单链表插入结点

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

双向链表删除结点

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

双向链表插入结点

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

线性表--顺序存储与链式存储对比

 5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

考点2:栈与队列

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

思考:元素按照a、b、c的次序进入栈,请尝试写出其所有可能的出栈序列。 

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

队空条件: head=tail

队满条件: (tail+ 1)%size=head

队列长度: (tail-head+size)%size

循环队列的优点:

元素入队时只修改队尾指针,元素出队时只修改队头指针。 

考点3:串

串的定义:是仅由字符构成的有限序列,是-种线性表。- 般记为S=aja...an',其中,S是串名,单引

号括起来的字符序列是串值。

串的存储

(1)顺序存储

(2)链式存储

串的几个基本概念

(1)空串与空格串

●空串:长度为零,不包含任何字符。

●空格串:由-个或多个空格组成的串。虽然空格是一个空白字符,但它也是一一个字符,在计算串

长度时要将其计算在内。

(2)子串与子序列

●子串:由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。子串在主串中的

位置是指子串首次出现时,该子串的第一个字符在主串中的位置。空串是任意串的子串。

●子序列:一个串的"子序列”(subsequence) 是将这个串中的一些字符提取出来得到一个新串,并且

不改变它们的相对位置关系。

(3)串比较与串相等

●串比较:两个串比较大小时以字符的ASCII码值(或其他字符编码集合)作为依据。实质上,比较操作

是从两个字符串的第一个字符开始进行,字符的码值大者所在的串为大;若其中-一个串先结束,则以

串长较大者为大。

●串相等:指两个串长度相等且对应序号的字符也相同。

1.串的基本操作:

(1)赋值操作StrAssign(s,t):将串s的值赋给串t。

(2)连接操作Concat(s,t):将串t接续在串s的尾部,形成-个新的串。

(3)求串长StrLength(s):返回串s的长度。

(4)串比较StrCompare(s,t):比较两个串的大小。返回值-1、0和1分别表示st三种情况。

(5)子串SubString(s, start,len):返回串S中从start开始的、长度为len的字符序列。

2:模式匹配

模式匹配:子串的定位操作通常称为串的模式匹配。(子串也称为模 式串)

朴素的模式匹配算法(布鲁特-福斯算法) :其基本思想是从主串的第一个字符起与模式串的第一个字

符比较, 若相等,则继续逐一对字符进行后续的比较,否则从主串第二个字符起与模式串的第一个

字符重新比较,直到模式串中每个字符依次与主串中-个连续的字符序列相等时为止,此时称为匹

配成功。如果不能在主串中找到与模式串相同的子串,则匹配失败。

5.2:数组与矩阵

考点一:数组

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

注:下标一般从0开始。

已知5行5列的二维数组a中的各元素占两个字节,求元素a[2][3]按行优先存储的存储地址? 

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

考点二:矩阵 

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程 稀疏矩阵的表示形式:三元组表(行号,列号,元素值),例:(1,1,5) ,(1,2,10) 等。

三元组表的顺序存储结构称为三元组顺序表,常用的三元组表的链式存储结构是十字链表。

5:数据结构--5.1:线性结构,5.2:数组与矩阵,软考中级软件设计师,数据结构,软件工程

A[i]lj]

上三角元素A[i][j](i<=j)

下三角元素A[i][j](i>=j))

 文章来源地址https://www.toymoban.com/news/detail-845318.html

到了这里,关于5:数据结构--5.1:线性结构,5.2:数组与矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构— 数组、特殊矩阵、稀疏矩阵

    💟作者简介:大家好呀!我是 路遥叶子 ,大家可以叫我 叶子 哦! ❣️     📝个人主页:【路遥叶子的博客】 🏆博主信息: 四季轮换叶 , 一路招摇胜!      专栏 【数据结构-Java语言描述】  【安利Java零基础】 🐋希望大家多多支持😘一起进步呀!~❤️ 🌈若有帮助

    2024年02月02日
    浏览(24)
  • [数据结构] 数组与特殊矩阵

    偷懒,先写了数组,队列要画图,所以今天就先不写了 数组是由n个相同类型的数据元素构成的有限序列。每个数据元素被称为 一个数组元素 ,每个元素在n个线性关系中的序号称为该元素的 下标 ,下标的取值范围称为数组的 维界 。 数组与线性表的关系:数组是线性表的

    2024年02月19日
    浏览(15)
  • 12-数据结构-数组、矩阵、广义表

    目录 数组、矩阵、广义表   一、数组         二.矩阵 三、广义表         这一章节理解基本概念即可。数组要看清其实下标是多少,并且二维数组,存取数据,要先看清楚是按照行存还是按列存,按行则是正常一行一行的去读写,按列则是,从左至右,一列一列的弄。

    2024年02月13日
    浏览(13)
  • 数据结构学习笔记——多维数组、矩阵

    数组是由n(n≥1)个 相同数据类型 的数据元素组成的有限序列,在定义数组时,会为数组分配一个固定大小的内存空间,用来存储元素,数组在被定义后,其维度不可以被改变。 数组在确定其维度和维界后,元素的个数是固定的,所以不能进行插入和删除运算。数组中最常

    2024年02月03日
    浏览(24)
  • 【数据结构】——串,数组,矩阵的相关习题

    1、数组通常具有的两种基本操作是()。 A、查找和修改 B、查找和索引 C、索引和修改 D、建立和删除 解析: (A) 基本操作是查找和修改,其中每个元素都可以通过其索引来访问,这是从数组的第一个元素开始计算的。除了访问和修改数组元素之外,还可以执行其他一些操

    2024年02月12日
    浏览(10)
  • 数据结构之数组、矩阵和广义表

      数据结构是程序设计的重要基础,它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发,分析和研究计算机加工的数据的特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法,为提高利用

    2024年01月22日
    浏览(20)
  • 24考研数据结构-数组和特殊矩阵

    数据结构是计算机科学中的基础概念,它涉及组织和存储数据的方式以及对数据的操作。在数据结构中,数组和特殊矩阵是两种常见的数据组织形式。本文将对数组和特殊矩阵进行介绍,并讨论它们在实际应用中的特点和用途。 数组是一种线性数据结构,它由相同类型的元素

    2024年02月14日
    浏览(15)
  • 【数据结构】数组和字符串(三):特殊矩阵的压缩存储:三角矩阵、对称矩阵——一维数组

    【数据结构】数组和字符串(一):矩阵的数组表示   矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造

    2024年02月08日
    浏览(20)
  • 【数据结构】数组和字符串(二):特殊矩阵的压缩存储:对角矩阵——一维数组

    【数据结构】数组和字符串(一):矩阵的数组表示   矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造

    2024年02月08日
    浏览(18)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包