【概念】
逻辑结构就是你学的章节大标题:(线性结构)线性表、栈、队列;(非线性结构)集合、树、图
数据的存储结构主要有:顺序、链式、索引、散列
【方法】
给出的一个结构,若能用多种(n>=2种)不同的方式存储,那就是逻辑结构;反之就是存储(物理)结构,已经采用了一种具体的存储方法。
【举栗子】
线索二叉树: (这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树) 二叉树是一种逻辑结构,但线索二叉树是加上线索后的【链表结构】,因此是存储结构。
静态链表:是用【一片连续的空间(数组,顺序)】来存储实现的,故静态链表是存储结构(称为用数组实现的链式存储结构)。
有向图:可以用【邻接表】或【邻接矩阵】两种实现,故有向图是逻辑结构。
二叉树:可以用【数组】或【指针(链式)】实现,故二叉树是逻辑结构。
散列表:用的是【散列(哈希)】存储,即根据元素的关键字直接计算出该元素的存储地址,故是存储结构。
循环队列:用【数组】求余实现,故是存储结构。
顺序表:用【数组】实现,故是存储结构。
栈是一种抽象的数据类型,可以采用顺序存储或者链式存储,只表示逻辑结构。
链接:https://www.zhihu.com/question/401303485/answer/1470339656
补充:
顺序表,哈希表和单链表是三种不同的数据结构,即描述逻辑结构,有描述存储结构和数据运算。
有序表指的是关键字有序的线性表,进描述元素之间的逻辑关系,它可以链式存储,也可以顺序存储,所以属于逻辑结构。
二叉树和二叉排序树(不同的数据结构它们的逻辑结构和物理结构完全有可能相同) 二叉排序树(BST)
- 线性表:逻辑结构, 就是对外暴露数据之间的关系,不关心底层如何实现,数据结构的逻辑结构大分类就是线性结构和非线性结构而顺序表、链表都是一种线性表。
- 顺序表、链表:物理结构,他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。
二叉排序树又称二叉查找树。二叉排序树或是一棵空树,或是一棵具有下列特性的非空二叉树:
1)若左子树非空,则左子树上所有结点关键字值均小于根结点的关键字值。
2)若右子树非空,则右子树上所有结点关键字值均大于根结点的关键字值。
3)左、右子树本身也分别是一棵二叉排序树
左子树结点值 < 根结点值 < 右子树结点值,对二叉排序树进行中序遍历,可以得到一个递增的有序序列。
大题计算步骤算法时间复杂度:O(nlog2n)
【文章原创作者:武汉网站建设 http://www.wh5w.com欢迎留下您的宝贵建议】