【五分钟】001-数据结构概论

2021年3月3日 2289点热度 0人点赞 0条评论
内容目录

学习要求

概念和术语

数据结构的基本概念:数据、数据元素、数据结构、数据的逻辑结构、物理结构、算法等。

基本概念和术语

【1】

数据 (Data) 是信息的载体,能够被计算机识别、存储和加工处理。

数据元素(Data Element) 是数据的基本单位,有时数据元素也称为元素、节点、顶点、记录。

数据结构(Data Structure) 指的是数据之间的相互关系,即数据的组织形式。数据结构异步包括以下三个方面的内容:

数据结构一般包括以下三个方面的内容:数据的逻辑结构、数据的存储结构、数据的运算。

​ ① 数据的逻辑结构(Logical Structure),表示数据元素之间的逻辑关系。数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的。

​ ② 数据的存储结构(Storage Structure),表示数据元素及其关系存储在计算机存储器。数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。

​ ③ 数据的运算,即对数据施加的操作。(最常用的检索、插入、删除、更新、排序等。)

常常将数据的逻辑结构简称为数据结构。

【2】

数据类型(Data Type)是高级程序设计语言提供的一种概念。所谓数据类型,是一个值的集合在这些值上定义的一组操作的总称。例如 C 语言中的 int 类型,以及 int 表示的最大最小值范围、int 可以进行加减乘除等操作。

数据类型有两种,一种是原子类型,一种是结构类型。原子类型其值不可拆解,例如大多数语言中都有的浮点型(float、double)、整形(int、long)等。结构类型其值可以被分解为若干个成分,如 C 语言的 数值、结构等类型。

【3】

抽象数据类型(Abstract Data Type,ADT)指抽象数据的组织和与之相关的操作。它可以看作是数据在逻辑结构及其在逻辑结构上定义的操作。抽象数据类型可以看作是描述问题的模型,它独立于具体实现。它的优点是将数据和操作封装在一起,使得用户程序只能通过在 ADT 里定义的某些操作来访问其中的数据,从而实现了信息隐藏。

ADT 相对于是在概念层/抽象层上描述问题,在面向对象语言中,相对于接口、抽象类。而类则是在实现层上描述问题,类是 ADT 的实现。

ADT 的主要意义是将数据和操作封装起来,使得用户程序只能在 ADT 里定义的某些操作来访问其中的数据,从而实现了信息隐藏。

谈一下 C# 中的属性。C# 、Java 中都有属性这一概念,例如 C# 定义一个属性:public int a{get;set;}。在 C# 中,真正存储数据的都是字段,属性是我们字段定义的一种存取操作设计。因此,一个类中,字段属于数据,属性可以看作是数据的操作。

【4】

在数据结构中,为了表示数据的存储,出现了很多种结构形式。无论哪种存储结构,都是由多个元素组成的,这些元素之间的逻辑关系可以有统一的术语表示。

A - B - C

一个数据结构中,最先开始的第一个结点,称为开始结点。而最后一个称为终端结点;对于数据结构中的任何一个结点 A,如果 A 在 B 的前面并且两者相邻,则称 A 为 B 的直接前趋(Immediate Predecessor);如果一个 结点 C,C 与 B 相邻且 C 在 B 的后面,则称 C 为 B 的直接后继(Immediate Successor)。开始结点没有直接前趋;终端结点没有直接后继。

【5】

数据的逻辑结构有两大类:

(1)线性结构

如果结构是非空集(即具有元素),具有以下特征:

​ ① 集合中必存在唯一一个开始结点。

​ ② 集合中必存在我要一个终端结点。

​ ③ 除最后一个元素外,其它数据元素都有唯一一个直接后继。

​ ④ 除第一个元素外,其它数据都有唯一一个直接前趋。

(2)非线性结构

非线性结构中每个结点都可能有多个直接前趋和直接后继。

注意,数据的逻辑结构有两大类,线性结构、非线性结构;而数据的逻辑结构有四种:

​ 1.集合结构:数据元素之间都没有逻辑关系。

​ 2.线性结构:数据元素之间存在着“一对一”的线性关系的数据结构。1:1.

​ 3.树形结构:数据元素之间定义了层次关系。1:N。

​ 4.图状结构(网格结构):数据元素之间定义了网状关系。M:N。

【6】

数据的存储结构有四种基本方法:

顺序存储方法、链接存储方法、索引存储方法、散列存储方法。

(1)顺序存储方法:

把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来
体现。通常借助程序语言的数组描述,存储时使用一块连续的空间。

(2)链接存储方法:

该方法不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系由附加的指针字段表示。通常借助于
程序语言的指针类型描述。

(3)索引存储方法:

该方法通常在储存结点信息的同时,还建立附加的索引表。索引表由若干索引项组成,若每个结点在索引表中都有一个索引项,则该索引表称之为稠密索引,稠密索引中索引项的地址指示结点所在的存储位置。

若一组结点在索引表中只对应一个索引项,则该索引表称为稀疏索引,稀疏索引中索引项的地址指示一组结点的起始存储位置。索引项的一般形式是:(关键字、地址)。

关键字是能唯一标识一个结点的那些数据项。

稠密索引_稀疏索引

图来源:https://blog.csdn.net/weixin_43507410/article/details/112463344

(4)散列存储方法:

该方法的基本思想是:根据结点的关键字直接计算出该结点的存储地址。散列又称为哈希、Hash。

测试

注:当前没有学到的内容,专题后面的文章会继续学到。读者答题不需要纠结。


1.下列选项中,属于逻辑结构的是

A.线性表

B.链表

C.顺序栈

D.循环队列

逻辑结构:集合、线性(如线性表)、图、树;

存储结构:顺序、链接(如链表)、索引、散列;

栈、链,都是存储结构;循环队列是一种顺序存储结构。

逻辑结构有线性结构(线性表)、非线性结构。


2.数据结构分为逻辑结构和存储结构,下列数据结构中不属于存储结构的是

A.线性链表
B.二叉链表
C.栈与队列
D.循环队列

线性链表是线性表的链式存储结构;二叉链表是二叉树的链式存储结构;栈与队列分别是特殊的线性表;循环队列是队列的一种顺序存储结构。可知,线性链表、二叉链表、循环队列均属于存储结构,而栈与队列属于逻辑结构。


3.针对线性表逻辑上相邻的两个元素,下列叙述中,正确的是(  )

A.采用顺序存储时一定相邻,采用链式存储时也一定相邻
B.采用顺序存储时一定相邻,采用链式存储时不一定相邻
C.采用顺序存储时不一定相邻,采用链式存储时一定相邻
D.采用顺序存储时不一定相邻,采用链式存储时也不一定相邻


4.下列选项中,不属于线性结构的是

A.网

B.栈

C.队列

D.线性表


5.下列选项中,不属于线性结构的是

A.网 B.栈 C.队列 D.线性表

栈、队列、线性表都是线性结构。


6.下列选项中,与数据存储结构直接相关的是

A. 线性表

B. 双向链表

C. 二叉树

D. 有向图

答案:1,A;2,C;3,B;4,A;5,A;6,B。

痴者工良

高级程序员劝退师

文章评论