学习任务:

视频学习

什么是数据结构

常用的数据结构

软件是由程序、数据、文档组成,程序是为数据处理服务,一个程序如果要提高它的数据处理性能,除了依赖高性能的硬件以外其程序本身的设计也很重要,再好的计算机硬件遇到设计差的程序和架构其性能依然不会达到预期,关于架构的设计待项目实战阶段再详细讨论,下边讨论下程序的设计。

程序设计=数据结构+算法,编写程序是为了数据的分析与处理,数据需要存储在计算机中然后进行分析与处理,数据结构正是解决数据在计算机中存储的问题,算法是用于数据分析与处理,两者相辅相成缺一不可。但要注意具体的算法是依赖某种数据结构的,如下图:使用数组存放了若干数据,数组就是一种数据结构,针对数组结构的冒泡排序的代码就是算法。

image-20201007103608546

关于常用的算法随着课程的深入逐一介绍,此处仅讨论数据结构,引用百度百科对数据结构的定义:

image-20201007104055917

解释数据结构的定义如下:

1)数据结构是计算机存储、组织数据的方式;是数据元素之间相互的关系的集合。

数据结构是数据元素之间存在的关系,可从物理结构和逻辑结构两个方面来看:

物理结构是计算机底层存储数据的方式,数据本身以二进制方式存储,数据之间的关系有顺序和非顺序两种,顺序关系是数据元素之间的存储位置相邻,比如数组元素之间的存储位置是相邻的,非顺序结构是数据元素之间的存储位置是不相邻的。

逻辑结构是数据元素之间的逻辑关系,它与数据元素在计算机中的存储位置无关,从整体上划分为线性结构与非线性结构。

线性结构是数据元素之间是线性关系,其特点是有一个开始结点、一个结束结点,每个结点最多有一个前趋结点和一个直接后继结点。队列是一个线性结构,下图是一个队列的结构图:

image-20201007192935357

上图中,b的前趋结点是a,直接后继结点是c。

非线性结构的特点是一个结点可能有多个直接前趋结点和多个直接后继结点,树型结构是非线性结构,下图是一个树的结构图:

image-20201007193744524

上图中,a没有前趋结点,直接后继结点是b和c。

2)数据结构与算法相辅相成,算法是基于数据结构来设计,数据结构设计的好坏影响算法的优劣,只有两者搭配合理并与需求相符方可提供高效的存储效率并解决实际问题。

同一个数据结构可以有多种算法,不同的算法面对不同的应用场景,比如:对数组中的数据进行排序,有冒泡排序,选择排序、快速排序算法等,冒泡排序适用数据量小且基本有序的场景下,快速排序适用数据量大且更随机的场景。

数据结构从逻辑上分为线性结构和非线性结构,线性结构中常用的数据结构有:数组、队列、栈、链表,非线性结构常用的数据结构有:树、图、堆、哈希表等。

下边介绍几种常用的数据结构,具体的应用方法可以参考具体的章节内容:

1)数组(Array):

数组是由内存中连续的单元存储数据元素,每个元素通过下标进行访问。

image-20201008171410870

根据下标遍历及查找数组元素非常快,但是删除或插入元素的速度慢,因为每插入或删除一个元素就需要移动其它一部分元素,所以数组适用于删除元素、插入元素较少的场景。

2)队列(Queue)

队列是一种线性表,队列在队尾添加元素,在队头删除元素,队列具有先进先出的特点,可以结合日常生活中排队的例子去理解。

image-20201007192935357

队列在日常应用中较多,比如:各办公场合的叫号系统,任务处理系统都使用了队列这种数据结构。

3)栈(Stack)

栈是一种线性表,栈有栈顶和顶底,只能在栈顶操作,操作包括:入栈和出栈,栈具有后进先出的特点,可以结合Java方法栈执行的过程去理解。

image-20201008172929248

栈在日常应用中较多,比如:函数的递归调用、编辑器的操作与撤销等。

4)链表(Linked List)

链表也是一种线性结构,链表是内存中不连续的单元通过指针串起来的链儿,每个单元是怎么通过指针串起来呢?每个单元包括数据域和指针域,数据域存储的是具体的数据,指针域存储的是前边或后边元素的地址。

链表有单向链表、双向链表和循环链表,下图是一个单向链表:

image-20201011161331363

上图中是在d1和d2中间插入一个元素,将d1指针域的值改为d4的地址,d4指针域的值为d2的地址,插入d4后组成了一个新的链表。

链表适用于频繁插入删除操作的场景,插入或删除一个元素只需要更改相关元素指针域的值即可。

5)树(Tree)

树是一种非线性结构,它由一到多个结构组成的具有层次结构的集合,对树的理解可以结合日常生活中单位的组织机构去理解。

下图是一个由7个结点组成的树型结构,它共有三层。

image-20201008181539102

常见的树型结构有平衡二叉树、红黑树、B+树等。

树的应用领域较多,比如:磁盘文件组织结构,软件的树型菜单等。

6)哈希表(Hash)

哈希表也叫散列表,顾名思义数据是散列存放在内存中,它是通过哈希函数计算一个关键值(key),这个关键值是一个整数,用它除以数组的长度求余从而找到该数据在哪一个桶或槽中,再将数据放入该桶或槽的链表中。

image-20201008182517249

散列表的存储和查找效率很高,通过哈希函数计算一个整数可以很快定位到数据的位置。

7)图(Graph)

图是一种非线性结构,它是由若干顶点的集合和连接顶点的边组成:

image-20201008184448895

图包括有向图、无向图,图的应用领域有:城市道路工程,快递路线等。

8)堆(Heap)

堆是用数组实现的完全二叉树,堆分为最大堆和最小堆两种。最大堆的父节点的值比每一个子节点的值都要大,最小堆中父节点的值比每一个子节点的值都要小。

image-20201008192058331

堆的应用领域主要有:堆排序、优先级队列等。

提问-攀博课堂
我要提问 不会就问,有效沟通
关注公众号,加入微信群交流提问。 攀博课堂官方公众号
问答列表,查看本知识点所有问题