第一章:数据结构绪论

[[数据结构 - 第1章] 绪论

目录

  • [1 数据结构有什么用?]
  • [2 基本概念和术语]
  • [3 逻辑结构与存储结构]

    • [3.1 逻辑结构]
    • [3.2 存储结构]
  • [4 抽象数据类型]

    • [4.1 数据类型]
    • [4.2 抽象数据类型]
  • [5 总结]
    • *

1 数据结构有什么用?

先思考这个问题,假如你开发一个客服电话系统,其中有一个菜单排队模块,功能主要是要设计一张客户排队表,每有一个客户来电,就需要添加记录客户的编号、姓名、电话等信息,并能够实现查询和删除,你将如何设计这张客户排队表?

这时候就要用到数据结构了,一般最先想到的就是使用数组,但是实际数组并不理想,因为要考虑溢出,又要考虑新增(插入)和删除后的数据移动。如果比较熟练掌握数据结构的话,就该想到使用数据结构中的 “队列结构”,很适合这种情况。

2 基本概念和术语

下面介绍一些数据结构中的基本概念和术语。

1. 数据

数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型,还包括字符及声音、图像、视频等非数值类型。

比如我们现在常用的搜索引擎,一般会有网页、图片、视频等分类。 MP3 就是声音数据,图片当然是图像数据,视频就不用说了,而网页其实指的就是全部数据的搜索,包括最重要的数字和字符等文字数据。

2. 数据元素

数据元素:是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。 也被称为记录。比如,在人类中,什么是数据元素呀?当然是人了。

3. 数据项

数据项:一个数据元素可以自若干个数据项组成。比如人这样的数据元素,可以有眼、耳、鼻、嘴、 手、脚这些数据项,也可以有姓名、年龄、性别、出生地址、联系电话等数据项,具体有哪些数据项,要视你做的系统来决定。

4. 数据对象

数据对象:是性质相同的数据元素的集合,是数据的子集。

什么叫性质相同呢,是指数据元素具有相同数量和类型的数据项,比如,还是刚才的例子,人都有姓名、生日、性别等相同的数据项。

既然数据对象是数据的子集,在实际应用中,处理的数据元素通常具有相同性质, 在不产生混淆的情况下,我们都将数据对象简称为数据。

好了,有了这些慨念的铺垫,我们的主角登场了。说了数据的定义,那么数据结构中的结构又是什么呢?

5. 数据结构

结构,简单的理解就是关系,比如分子结构,就是说组成分子的原子之间的排列方式。严格点说,结构是指各个组成部分相互搭配和排列的方式,在现实世界中,不同数据元素之间不是独立的,而是存在特定的关系,我们将这些关系称为结构。那数据结构是什么?

数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。

为编写出一个 "好" 的程序,必须分析待处理对象的特性及各处理对象之间存在的关系。这也就是研究数据结构的意义所在。

3 逻辑结构与存储结构

按照视点的不同, 我们把数据结构分为逻辑结构和存储结构。

3.1 逻辑结构

逻辑结构:是指数据对象中数据元素之间的相互关系。逻辑结构分为以下四种:

  • 集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。
  • 线性结构:线性结构中的数据元素之间是一对一的关系。
  • 树形结构:树形结构中的数据元素之间存在一种一对多的层次关系。
  • 图形结构:图形结构的数据元素是多对多的关系。

3.2 存储结构

说完了逻辑结构,我们再来说说数据的存储结构(很多书中也叫做物理结构)。

存储结构:是指数据的逻辑结构在计算机中的存储形式。

数据元素的存储结构形式有两种:顺序存储链式存储

1. 顺序存储结构

顺序存储结构:是把数据元素放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。

这种存储结构其实很简单,说白了, 就是排队占位。大家都按顺序排好,每个人占一小段空间,大家谁也别插谁的队,数组就是这样的顺序存储结构。

可实际上,总会有人插队,有人会放弃排队。所以这个队伍当中会添加新元素,也有可能会去掉老元素,整个结构时刻都处于变化中。显然,面对这样时常要变化的结构,顺序存储是不科学的。这时候就要考虑用到链式存储结构了。

2. 链式存储结构

链式存储结构:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关联数据元素的位置。

显然,链式存储就灵活多了,数据存在哪里不重要,只要有一个指针存放了相应的地址就能找到了。

逻辑结构是面向问题的,而物理结构就是面向计算机的,其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

4 抽象数据类型

4.1 数据类型

数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

数据类型是按照值的不同进行划分的。在高级语言中,每个变量、常量和表达式都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。

C 语言中,按照取值的不同,数据类型可以分为两类:

  • 原子类型:是不可以再分解的基本类型,包括整型、实型、字符型等。
  • 结构类型:由若干个类型组合而成,是可以再分解的。例如,整型数组是由若干整型数据组成的。

4.2 抽象数据类型

抽象是指抽取出事物具有的普遍性的本质。它是抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。抽象是一种思考问题的方式,它隐藏了繁杂的细节,只保留实现目标所必需的信息。对已有的数据类型进行抽象,就有了抽象数据类型。

抽象数据类型不仅仅指那些已经定义并实现的数据类型,还可以是计算机编程者在设计软件程序时自己定义的数据类型。例如 “超级玛丽” 中的马里奥,定义的操作:走(前进、后退、上、下)、跳、打子弹等。

事实上,抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题, 然后建立一个计算机能处理的数据模型,并把每个功能模块的实现细节作为一个独立的单元,从而使具体实现过程隐藏起来。

描述抽象数据类型的标准格式:

5 总结

本章介绍了数据结构的一些相关概念。

由这些概念,给出了数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。同样是结构,从不同的角度来讨论,会有不同的分类:

Image placeholder
Alex
未设置
  72人点赞

没有讨论,发表一下自己的看法吧

推荐文章
流畅的Python读书笔记 --- 第一章 Python数据模型

近期开始读“流畅的Python”这本书,想把自己的读书笔记分享给大家,希望能帮到也对这本书感兴趣但是没时间看的各位。(文章中大部分的话和图片摘录总结自“流畅的Python”一书,以及python官方网

【数据结构】2_数据的艺术

程序设计的挑战 利用计算机解决现实生活中的问题 生活中的不同个体之间存在联系 用计算机程序描述生活中个体间的联系 问题:如何描述生活中的个体?数据的概念程序的操作对象,用于描述客观事物数据的特点 可以

python set (集合)数据结构

set(集合)是一个非常有用的数据结构。它与列表(list)的行为类似,区别在于set不能包含重复的值。这在很多情况下非常有用。例如你可能想检查列表中是否包含重复的元素,你有两个选择,第一个需要使用f

Python入门教程_5. 数据结构

这个章节将更详细地描述一些你已经了解的内容,并且添加了一些新的内容。 5.1.深入列表对象 List数据类型包含更多的方法,下面是List对象包含的所有方法: list.append(*x*) 将一个

数据结构与算法分析——开篇以及复杂度分析

开篇 你也许已经发现了,工作了几年,原以为已经是一只老鸟。但看到刚参加工作的同事,你发现,原来自己一直在原地踏步。跟新人相比,你的唯一优势就是对业务更熟悉而已,别的就没有什么优势了。 怎样才能够让自己

数据结构与算法分析——开篇以及复杂度分析

开篇你也许已经发现了,工作了几年,原以为已经是一只老鸟。但看到刚参加工作的同事,你发现,原来自己一直在原地踏步。跟新人相比,你的唯一优势就是对业务更熟悉而已,别的就没有什么优势了。怎样才能够让自己更上

JavaScript 的数据结构和算法

现在有个还不是好的项目,未来会成为好的项目的项目想介绍给大家。传送门https://github.com/MasterShu/JavaScript-Da...这个是本人在维护的一个项目。主要是使用Ja

数据结构与算法分析——链表

链表链表是一种常见的数据结构,是一组有序的数据,每个链表中的数据项称为元素。它跟数组很像,二者对比学习会更容易理解和记忆。数组是内存中连续的一块,不会间断。链表在内存中不一定是连续的一块。如果内存只剩

数据结构与算法分析——队列

定义队列,和栈类似,也是一种操作受限的线性表数据结构。与栈结构不同的是,可以对队列2端操作,要求数据从一端进(入队),从另一端出(出队)。队列遵循"先进先出"的原则,即最先进队列的数据元素,同样要最先

数据结构与算法分析——栈

定义栈是一种操作受限的线性表,只支持在一端进行插入和删除操作(入栈和出栈)。后进先出、先进后出是它最大的特点。当某个数据集合只在一端插入和删除数据,并满足先进后出的特性时,就可以选择栈这种数据结构。实

【数据结构】3_程序设计的灵魂

学员间的对话 木暮:我发现三井真是牛,只用一行就实现了strlen 宫城:那么强!他是怎么做的呢? 木暮:不知道,我看了一下,没看懂。。。 宫城:牛人就是牛人啊! 问题:程序是否越短越好?是否别人看不

【数据结构】1_进阶高手的大门

理解程序的本质问题:为什么会有各种各样的程序存在?程序的本质是什么?程序是为了解决实际问题而存在的,从本质而言,程序是解决问题的步骤描述。一小步的进阶:理解实际问题 确认问题类型 如:数值计算,求最

java与数据结构

数组与链表数组 数组是数据结构中的基本模块之一 数组是一种基本的数据结构,用于按顺序存储元素的集合。但是元素可以随机存取,因为数组中的每个元素都可以通过数组索引来识别。 数组可以有一个或多个维度

redis数据结构(二) - 字符串

基于redis5.0的版本。字符串编码:字符串对象的编码可以是int,raw或者embstr。1.rawraw就是redisObject+sds,即redisObject的ptr指针指向一个sds对象

Redis的数据结构和内部编码

redis是单线程,一次只执行一条命令,那为什么可以这么快: 纯内存 非阻塞IO 避免线程切换和竞态消耗 在使用过程中要注意: 一次只运行一条命令 避免长(慢)命令,例如keys、flushall、f

【数据结构】 10_C++异常简介

C++内置了异常处理的语法元素try...catch... try语句处理正常代码逻辑 catch语句处理异常代码逻辑 try语句中的异常由对应的catch语句处理 try { doubler=

【数据结构】11_异常类构建

异常的类型可以是自定义类类型 对于类类型异常的匹配依旧是至上而下严格匹配 赋值兼容性原则在异常匹配中依然适用 一般而言 匹配子类异常的catch放在上部 匹配父类异常的catch放下下部 现代

直击DTCC2019现场:数据库智能化运维探索与实践

5月10日,第十届中国数据库技术大会(DTCC2019)正在火热进行中。作为本届大会讨论的焦点之一,“数据库智能运维”专场人气爆棚,来自京东物流、腾讯、字节跳动、京东商城、便利峰的行业专家出席现场,他

对话OceanBase资深总监韩鸿源:数据库是技术能力,云是使用方式,两者不应是竞争关系

5月10日,在第十届中国数据库技术大会(DTCC2019)上,蚂蚁金服的金融级分布式关系数据库OceanBase2.0,在经过200名数据库领域三年以上的从业者投票和专业评委的评选下,高分荣获了“年度

盘点2018:数据库领域关键词“自研” ”融合“ ”崛起“

尽管2019年已然开始,但只要农历春节还没过,就意味着2018年还没有真正结束。回望过去一年,数据库领域发生了哪些有代表性的事件?这些事件背后预示哪些趋势?尽管2019年已然开始,但只要农历春节还没过

地震局网络安全观:数据是核心,合规是基线

近年来,我国地震多发,大小地震给震区人民带来了不小的恐慌和经济损失。而前不久的四川宜宾地震期间出现了一个小插曲让大家记忆犹新:成都市地震预警系统在地震到达成都前提前触发警报,成都市13个区县电视预警系

解DBA之惑:数据库承载能力评估及优化手段

作为DBA,有时会被挑战类似这样的问题:如果现有业务规模增加10倍、100倍,数据库是否能够支撑?下个月我们搞大促,数据库这边没问题吧?计划进行去O工作,代码逻辑不变,数据库从Oracle切换到MyS

腾讯林晓斌:数据库的高易用性如何实现?

腾讯云基于QQ、微信、腾讯游戏等海量业务的技术锤炼,从基础架构到精细化运营,从平台实力到生态能力建设,腾讯云将之整合并面向市场,使之能够为企业和创业者提供集云计算、云数据、云运营于一体的云端服务体验。

2019年度IT168技术卓越奖名单:数据中心类

光阴如梭,一年的工作转瞬又将成为历史,2019年即将过去,崭新的2020年即将来临。新的一年意味着新的起点新的机遇新的挑战,众多企业“决心再接再厉,更上一层楼”,努力打开新局面。作为读者们的老朋友,2

2019年度IT168技术卓越奖名单:数据库类

岁末年关,一年一度的IT168技术卓越奖评选如约而至。在数据智能时代,数据是生产资料是富含价值的新石油,海量数据的并发以及实时性要求,对于向下攫取硬件性能向上承载应用的数据库而言是挑战更是机遇,国内数

{