数据结构——第1章 绪论

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

目录
  • 1.1 数据结构的研究内容
  • 1.2 基本概念和术语
    • 1.2.1 数据、··元素、··项和··对象
    • 1.2.2 数据结构
    • 1.2.3 数据类型和抽象数据类型
  • 1.3 抽象数据类型的表示与实现
  • 1.4 算法和算法分析
    • 1.4.1 算法的定义与特性
    • 1.4.2 算法的时间复杂度
    • 1.4.3 算法的空间复杂度
  • 1.5 小结

1.1 数据结构的研究内容

1.2 基本概念和术语

1.2.1 数据、··元素、··项和··对象

数据:是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素:是数据的基本单位,也称元素/记录,用于完整地描述一个对象。如学生表中的一名学生。

数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。如学生基本信息表中的学号、姓名、性别等。

数据对象:是性质相同的数据元素的集合,是数据的一个子集。如整数数据对象、字母字符数据对象、由多个数据项组成的复合数据元素。

1.2.2 数据结构

数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系,包括逻辑结构和存储结构。

一、逻辑结构

从逻辑关系上描述数据,与数据的存储无关,独立于计算机,数据元素和关系两要素

  1. 集合结构

数据元素之间只有“属于同一集合”的关系。
如确定一名学生是否为班级成员,只需将班级看作一个集合结构。

  1. 线性结构

数据元素之间存在一对一的关系。
如将学生信息数据按照其入学报道的时间先后顺序进行排列。

  1. 树结构

数据元素之间存在一对多的关系。
如在班级的管理体系中,班长管理多个组长,每位组长管理多名组员。

  1. 图结构或网状结构

数据元素之间存在多对多的关系。
如多位同学之间的朋友关系,任何两位同学都可以是朋友。

总结
数据结构——第1章 绪论

二、存储结构

数据对象在计算机中的存储表示,也称物理结构。把数据对象存储到计算机时,通常既要存储各数据元素的数据,又要存储数据元素之间的逻辑关系。

  1. 顺序存储结构

借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系,要求所有的元素依次存放在一片连续的存储空间中,数据从低地址向高地址方向储存,通常借助数组类型来描述。

  1. 链式存储结构

无需占用一整块存储空间,但为了表示数据元素(结点)之间的关系,需要给每个结点附加指针字段,用于存放后继元素的存储地址,通常借助指针类型来描述。每个结点占用两个连续的存储单元。

1.2.3 数据类型和抽象数据类型

  1. 数据类型

在程序设计语言中,每一个数据都属于某种数据类型。类型规定了数据的取值范围、存储方式以及允许进行的运算,数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

如C语言中的整型变量,其值集为某个区间上的整数,定义在其上的操作为加减乘除和取模等算术运算。

  1. 抽象数据类型

就是指由用户定义的、表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称,具体包括...三部分(如下)

定义格式:

ADT 抽象数据类型名
{
    数据对象:<定义>
    数据关系:<定义>//采用数学符号和自然语言描述
    基本操作:<定义>
}ADT 抽象数据类型名

基本操作的定义格式:

基本操作名(参数表)
//赋值参数只为操作提供输入值,以“&”开头,除此之外还将返回操作结果
	初始条件:<描述>//操作执行之前数据结构和参数应满足的条件,为空则省略
	操作结果:<描述>//操作完成后,数据结构的变化状况和应返回的结果

1.3 抽象数据类型的表示与实现

运用抽象数据类型描述数据结构,有助于在设计一个软件系统时,不必首先考虑其中包含的数据对象,以及操作在不同处理器中的表示和实现细节,而是在构成软件系统的每个相对独立的模块上定义一组数据和相应的操作,把这些数据的表示和操作细节留在模块内部解决,在更高的层次上进行软件的分析和设计,从而提高软件的整体性能和利用率。

在C++中,用类的声明表示抽象数据类型,用类的实现来实现抽象数据类型。因此,C++中实现的类相当于数据的存储结构以及在存储结构上实现的对数据的操作。

(有在尽量缩减篇幅了其实,觉得这些很有助于理解就保留了)

以复数为例,

//定义部分
ADT Complex
{
    数据对象:D={e1,e2|e1,e2∈R,R是AXT实数集}
    数据关系:S={<e1,e2>|e1是复数的实部,e2是复数的虚部}
    基本操作:
        Create(&C,x,y)
          操作结果:构造复数C,其实部和虚部分别被赋以参数x和y的值。
        Add(C1,C2)
          初始条件:C1,C2是复数。
          操作结果:返回两个复数C1和C2的和。
}ADT Complex

//表示部分
typedef struct      //复数类型
{
    float Realpart; //实部
    float Imagepart;//虚部
}Complex;

//实现部分
void Create(&Complex C,float x,float y)
{
    //构造一个复数
    C.Realpart=x;
    C.Imagepart=y;
}

Complex Add(Complex C1,Complex C2)
{
    //求两个复数C1和C2的和
    Complex sum;
    sum.Realpart=C1.Realpart+C2.Realpart;
    sum.Imagepart=C1.Imagepart+C2.Imagepart;
    return sum;
}

1.4 算法和算法分析

1.4.1 算法的定义与特性

算法是为了解决某类问题而规定的一个有限长的操作序列。
有穷性、确定性、可行性、输入和输出。

1.4.2 算法的时间复杂度

描述的是算法执行时间开销和问题规模n之间的关系。包含最好、平均和最坏时间复杂度。时间复杂度通常包括:常量阶、线性阶、平方阶、对数阶等。

求下面语句的执行次数:

for(i=1;i<=n;i++)//n+1
for(i=1;i<=n;i++)
  求这一句x++;//n
for(i=1;i<=n;i++)
  这一句for(j=1;j<=n;j++)//n(n+1)
for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
    这一句x++;//n²
for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
    for(k=1;k<=n;k++)
      这一句x++;

结果是这个\(\sum_1^n\) * \(\sum_1^i\) * j

for(i=1;i<=n;i=i*2)
{
  x++;
  s=0;
}

结果是这个\(log_2n\)

相应的,整个程序的时间复杂度就取决于最大阶,如:

for(i=1;i<=n;i++)//n+1
  for(j=1;j<=n;j++)//n(n+1)

n+1+n(n+1)=n+1+n²+n ---- O(n²)

1.4.3 算法的空间复杂度

程序执行时,除了需要寄存本身所有指令、常数、变量和输入的数据外(取决于问题本身),还需要一些对数据进行操作的辅助存储空间。空间复杂度考虑的就是在算法实现中考虑的辅助空间大小。

1.5 小结

1)数据结构是一门研究非数值计算程序设计中操作对象,以及这些对象之间的关系和操作的学科。

2)数据结构包括两个方面的内容:数据的逻辑结构和存储结构。同一逻辑结构采用不同的存储方法,可以得到不同的存储结构。

  1. 逻辑结构是从具体问题抽象出来的数学模型,从逻辑关系上描述数据,它与数据的存储无关。根据数据元素之间关系的不同特性,通常有四类基本逻辑结构:集合、线性、树形、图状结构。
  2. 存储结构是逻辑结构在计算机中的存储表示,分为顺序和链式两类。

3)抽象数据类型是指由用户定义的、表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称,包括数据对象、数据关系、基本操作三部分。

4)算法是为了解决某类问题而规定的一个有限长的操作序列。算法有五个特性:有穷性、确定性、可行性、输入和输出。一个算法的优劣应从正确性、可读性、健壮性和高效性四个方面来评价。

5)算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度,以考察算法的时间和空间效率。一般情况下,将算法的时间复杂度作为分析的重点。算法执行时间的数量级称为算法的渐近时间复杂度,T(n)=O(f(n)),它表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,简称时间复杂度。文章来源地址https://www.toymoban.com/news/detail-825024.html

到了这里,关于数据结构——第1章 绪论的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 关于【Stable-Diffusion WEBUI】方方面面研究(内容索引)

    关于Stable-Diffusion WEBUI,我发现网上各种教程真的很多。 写得很好很详细的也不少,读了感觉比我写的好多了,无论是原理和相关论文还是操作和细节。 所以准备记录下Stable-Diffusion WEB UI的方方面面,以及哪里去看相关的资料。 同时自己写的东西也有点乱,得整理一下。呃在

    2024年02月05日
    浏览(54)
  • 技术写作与内容研究:主题得分、关键词搜索量、社区和论坛策略

    内容研究涉及对特定主题进行系统的调查,以收集可靠和相关的信息。这个过程对于技术作者来说至关重要,因为它有助于生成有价值的、准确的、信息丰富的和引人入胜的内容。它超越了基本的互联网搜索,包括阅读技术文档、采访专家、进行调查和分析数据。内容研究应

    2024年02月04日
    浏览(45)
  • AIGC内容分享(四):金融行业AIGC落地方法论的探索和研究

    目录 摘要 大模型解决领域应用问题的本质及要求 (一)领域应用的本质是复杂决策 (二)领域应用的专业性要求较高 (三)金融领域应用对大模型有更高要求 金融行业如何选择AIGC的适用场景 (一)使用AIGC需解决的三大问题 (二)如何突破AIGC在当前行业的应用难

    2024年02月02日
    浏览(32)
  • 计算机毕业论文内容参考|基于神经网络的网络安全态势感知技术研究

    基于神经网络的网络安全态势感知技术研究 随着互联网的快速发展,网络攻击的

    2024年02月03日
    浏览(64)
  • 微软亚洲研究院多模态模型NÜWA:以自然语言创造视觉内容

    此前我们曾提出了一个问题:从文字脚本生成创意视频一共分几步?微软亚洲研究院的开放领域视频生成预训练模型给出了答案:只需一步。现在,我们追问:除了文字生成视频之外,还有哪些途径可以生成视频?我们能否使用自然语言对视觉内容进行编辑?微软亚洲研究院

    2024年02月04日
    浏览(36)
  • 数据结构与算法 --- 数据结构绪论

    早期人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机解决问题,应该是先从具体问题中抽象出一个适当的数据模型,设计出一个解此数据模型的算法,然后再编写程序,得到一个实际的软件。 可现实中,我们更多的不是解决数值计算的问

    2024年02月14日
    浏览(53)
  • 数据结构学习之数据结构绪论

      《大话数据结构》是程杰老师著作的一本书,作者将跟着程杰老师写的这本书,记录自己数据结构学习之旅。   数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。   我的理解,数据结构就是数据和数据之

    2024年02月04日
    浏览(88)
  • 【数据结构与算法】1.数据结构绪论

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 数据结构是计算机中存储、组织数据的方式。 数据结构是一种具有一定逻辑关系,

    2024年01月23日
    浏览(53)
  • 【数据结构】实验一:绪论

    实验一  绪论 一、实验目的与要求 1)熟悉C/C++语言(或其他编程语言)的集成开发环境; 2)通过本实验加深对算法时间复杂度的理解; 3)结合具体的问题分析算法时间复杂度。 二、实验内容 设计程序实现统计一个班的学生成绩(学生的人数可以设置3000、5000、8000、1000

    2024年02月15日
    浏览(39)
  • 数据结构 - 绪论

    数据 Data :信息的载体。能被计算机识别并处理的符号的集合。 数据元素 Data element :数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素往往由若干 数据项 组成。数据项是组成数据元素的不可分割的最小单位。 如学生的信息记录就是一个数据元素,它由学

    2023年04月18日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包