本篇文章将结合《算法》第4版、业界大牛的博客和自己的理解,具体描述数据结构的一些概念,如有错误,请大佬指出。如有侵权,请联系我删除,谢谢。
数据结构
1.基础概念
数据结构是指反映数据元素之间关系的数据元素的集合。而数据元素具有广泛含义,一般来说,现实世界中客观存在的一切个体都可以是数据元素。它可以是一个数字或者一个字符,也可以是一个具体的事物,或者其他更为复杂的信息。
数据结构作为数据元素的集合,包括逻辑结构和存储结构两种。
(1)数据的逻辑结构
指反映数据元素之间逻辑关系(即前后件关系)的数据结构。包括数据元素的集合和数据元素之间前后关系这2个要素。
(2)数据的存储结构
又称数据的物理结构,指数据的逻辑结构在计算机存储空间中的存放方式。因为计算机中存放数据元素的位置很可能不是连续的,所以在存储的时候,不仅要存放数据的信息,还要存放数据间的前后件的信息。只有这样才能更好地表示计算机存储空间中数据之间的逻辑关系。
数据结构的存储方式包括顺序存储、链式存储、索引存储和散列存储等,采用不同的存储结构使得数据处理的效率不同,所以在处理数据的时候,要选择合适的存储结构。
2.图形表示
前后件关系是数据元素之间最基本的关系。前后件关系中,每一个二元组都可以用图形来表示。用中间标有元素值的方框来表示数据元素,称为数据结点,简称结点。对于每一个二元组,需要用一条有向线段从前件指向后件。
例如,一年四季的数据结构可以用如图所示的图形来表示。
用图形表示数据结构更为直观易懂,在没有歧义的情况下,前件结点到后件结点连线上的箭头可以省去。
3.线性和非线性结构
根据数据结构中各数据元素之间前后关系的复杂程度,一般可将时间结构分为两大类型:线性结构和非线性结构。
若一非空的数据结构有且只有一个根结点,并且每个结点最多有一个直接前驱和一个直接后继,则称线性结构,也称线性表。不满足以上条件的称为非线性结构。
注意:空的数据结构,可能是线性结构,也可能是非线性结构,要根据对该数据结构的运算规则来判断。
这一篇讲的是数据结构的基本要点,内容不多,也容易理解。下一篇讲线性表的一些概念和运算。敬请期待哦<( ̄︶ ̄)>。