Mark'sBLOG
CARD
jinyaoMa
issue, func, flow, std, solve
16 | 9 | 25
SKIN
SETTINGS
Night Shift
Disable Canvas
简体中文
中文
|
English
|
日本語
PAGE CONTENT
数据结构之基础
2020-04-18
2020-04-20
933
6 min.

数据结构基础,了解数据结构的分类,认识一下抽象数据类。

# 顺序结构

内存中元素紧挨在一起的数据结构为顺序结构。在 C 语言中,声明一个整数结构类型长度为 5 的数组时,内存中会留出 5 个整数长度的连续空间用于存储数组。实际上,数组的指针可以说是指向在数组中的第一个元素。当要修改第 4 个元素时,计算机是找到了数组指针地址,跳跃 3 个整数长度的距离,从而找到第 4 个元素的位置。

# 链式结构

内存中元素可连续也可不连续,通过指针寻找和连接元素的数据结构为链式结构。在 Java 语言中,链表(Linked List)和树(Tree)都属于链式结构。他们属于抽象的结构类型,类型所包含的元素被称为节点(Node)。链表节点中的值可以为整数类、浮点类、字符串等,包括抽象数据类;但链表节点中还会包含有节点的一个后继元素指针。树节点对比链表节点的不同在于树节点中可以包含有多个后继元素指针。总结起来就是链式结构节点在内存中连续摆放不是必须的,当计算机查找某个节点时,会走遍目标节点前的所有节点,从而顺着第一个节点的指针找到目标指针。

# 比较顺序结构和链式结构

顺序结构和链式结构在内存中的不同

  • 顺序结构在内存中有固定最大长度,而链式结构在内存中没有,所以在流动数据多的情况下,链式结构对空间利用更灵活。
  • 顺序结构在内存中是元素之间是连续的,而链式结构在内存中很可能是不连续的,所以在查找元素时,通过地址计算公式查找,顺序结构的效率更高。
  • 在首部添加元素或删除中间某个元素的情况下,链式结构的效率会更高,因为对比顺序结构,链式结构不需要重新排列。
  • 顺序结构最大长度难以确定的情况下,会产生太多的储存空间 “碎片”,而链式结构原本就是 “碎片化” 的。

# C 语言数据类型

原子 / 基本类型:short, int, long, float, double, char 结构 / 构造类型:数组,struct, union, enum 其他:指针,空(void)

# 抽象数据类型(Abstract Data Type)

区别于基本数据类型,基本数据类型有设定数据占用空间的极限、数据表示的方式和内存中结构的特性;抽象数据类型基于基本数据类型形成更复杂的数据类型,例如链表(Linked List)和树(Tree)都属于抽象数据类。颜色(Color)、坐标(Point)等结构类也都属于抽象数据类。

所谓抽象数据类型就是把数据类型和相关操作捆绑在一起。

Color 抽象数据类: 由 Red、Green 和 Blue,3 个范围为 0-255 的整数值表示颜色范围,加上一个范围为 0-1 的浮点型 Alpha 数值表示透明度。

Point 抽象数据类: 由 x、y 和 z,3 个整数值表示三维空间中的坐标。

# 抽象数据类型伪代码

ADT 抽象数据类型名
Data
  数据元素之间逻辑关系的定义
Operation
  操作
endADT

本文参考: 【C 语言描述】《数据结构和算法》(小甲鱼)

The post above ended Thanks for your reading
Come on! Write some comments, and your suggestions will improve the quality of my creative!
FRIEND ME
QQ
WeChat
Post Author: jinyaoMa
Post Link: /
Copyright Notice: All articles/posts in this website are licensed under BY-NC-SA unless stating additionally.
Enable Read Mode
COMMENTS
DEFAULT