数组、堆栈、队列、链表、树、哈希表
一. 数组
数组(Array)是最简单,也是最常用的数据结构了。其他一些数据结构,比如栈和队列都是由数组衍
生出来的。
每一个数组元素的位置称为下标或者索引(index)标识的。大多数编程语言的数组第一个元素
的下标是 0。
根据维度区分,数组是分为一维数组和多维数组(数组的元素为数组)
一维数组【int[] arr =new int[4];】:
二维数组【int[][] arr =new int[3][4];】:
数组的基本 *** 作
Insert - 在某个索引处插入元素
Get - 读取某个索引处的元素
Delete - 删除某个索引处的元素
Size - 获取数组的长度
这里解释一个概念问题。
一维数组是线性结构的,那么二维乃至多维数组是否是线性结构呢。
其实不是,如二数组是由多个一维数组组成的,不是线性结构。【如上图arr[0]对应的是另一个一维数组】
概念:
线性结构是一个有序数据元素的集合。 其中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。
非线性结构中各个数据元素不再保持在一个线性序列中,每个数据元素可能与零个或者多个其他数据元素发生联系。
结论:
常用的线性结构有:线性表,栈,队列,双队列,数组,串。
常见的非线性结构有:二维数组,多维数组,广义表,树(二叉树等),图。
二、栈
栈中的元素采用 LIFO (Last In First Out),即后进先出,线性结构。
使用场景,计算机的Ctrl+Z撤回,之前的状态保存在栈中。
栈的基本 *** 作
Push — 在栈的最上方插入元素
Pop — 返回栈最上方的元素,并将其删除
isEmpty — 查询栈是否为空
Top — 返回栈最上方的元素,并不删除
三、队列
队列(Queue)与栈类似,都是采用线性结构存储数据。它们的区别在于,栈采用 LIFO 方式,而队
列采用先进先出,即FIFO(First in First Out)。
队列的基本 *** 作
Enqueue — 在队列末尾插入元素
Dequeue — 将队列第一个元素删除
isEmpty — 查询队列是否为空
Top — 返回队列的第一个元素
链表(linked List)也是线性结构,类似,但内存分配方式、内部结构和插入删除 *** 作方式都不一样。
链表是一系列节点组成的链,每一个节点保存了数据以及指向下一个节点的指针。
链表头指针指向第一个节点,如果链表为空,则头指针为空或者为 null。
链表分为 2 种:
单向链表
双向链表
链表的基本 *** 作
InsertAtEnd — 在链表结尾插入元素
InsertAtHead — 在链表开头插入元素
Delete — 删除链表的指定元素
DeleteAtHead — 删除链表第一个元素
Search — 在链表中查询指定元素
isEmpty — 查询链表是否为空
五、树
树(Tree)是一个分层的数据结构,由节点和连接节点的边组成。
树是一种特殊的图,它与图最大的区别是没有循环。
树被广泛应用在人工智能和一些复杂算法中,用来提供高效的存储结构。
树有很多分类,这里简单列举,另外做解释:
N 叉树(N-ary Tree)
平衡树(Balanced Tree)
二叉树(Binary Tree)
二叉查找树(Binary Search Tree)
平衡二叉树(AVL Tree)
红黑树(Red Black Tree)
概念:哈希(Hash)将某个对象变换为唯一标识符,该标识符通常用一个短的随机字母和数字组成的字符串
来代表。
概念的说法有点模糊。具体例子为 value=f(key) 或者 存储地址=f(关键字),f()为哈希函数或者散列函数。
key不可重复,唯一的key对应一个自己value。只要集合中存在关键字和key相等的记录,则必在存储位置f(key)处。
即哈希表就是一种以键值对存储数据的结构,采用散列函数将记录存储在一块连续的存储空间中,这块连续的存储空间称为哈希表。
所得的存储地址称为哈希地址或散列地址。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)