数据结构
数据结构(Data Structure)是指数据与数据之间的关系。在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构(Structure)。
例如，有一张学生选课表，这个表就是数据；成绩表中记录了班级每个学生选课的成绩，每个学生的姓名为一行组成一条记录。每个记录由姓名、学号、课程成绩等字段组成，每个记录就是一个结点也称为数据元素；每个字段就是数据项。姓名字段取值范围为字符型，而课程成绩字段取值为整型。学生选课成绩表的数据是一组学生成绩信息，这组信息具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系，按照学号升序排列。
数据结构的逻辑结构和存储(物理)结构
逻辑结构
数据元素之间的逻辑关系称为数据的逻辑结构。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关。
逻辑结构通常有以下4种。
·集合结构：在集合结构中，数据元素间的关系是“属于同一个集合”。集合结构是元素关系极为松散的一种结构。
·线性结构：该结构的数据元素之间存在着一对一的关系，即一个数据元素只与另一个数据元素有关系。
·树性结构：该结构的数据元素之间存在着一对多的关系，即一个数据元素只与另外多个数据元素有关系。
·图性结构：该结构的数据元素之间存在着多对多的关系，即数据元素之间有多个关系。图形结构也称作网状结构。
4种逻辑结构示意图
存储结构
数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。
如线性结构，既要存储数据元素A，B，C，D又要存储他们之间的关系AB，BC，CD那么，是用一片连续的内存单元来存放这些记录（如用数组表示），还是随机存放各结点数据再用指针进行链接呢？这就是物理结构的问题。根据分析该结构是线性关系，故采用数组来存储。
数据的存储结构可采用顺序存储或链式存储的方法。
顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
链式存储方法是对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，由此得到的存储表示称为链式存储结构。链式存储结构通常借助于程序设计语言中的指针类型来实现。
除了通常采用的顺序存储方法和链式存储方法外，有时为了查找的方便还采用索引存储方法和散列存储方法。
线性结构和非线性结构
“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。
这句话的理解是：
- 双向链表有两个直接后继，它们只是存储层次上的，不是逻辑层次上的，因为数据元素之间还是一对一的关系。
- 二叉树同样也有两个直接后继，但它是逻辑层次上的。为什么？因为数据元素之间一对多的关系。
数据结构中数据的逻辑结构分为线性结构和非线性结构。
线性结构
数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。
常用的线性结构有：线性表，栈，队列，双队列，数组，串。
线性表与线性结构的关系
线性表是最基本、最简单、也是最常用的一种线性结构。
线性结构的特点是数据元素之间是一种线性关系，数据元素"一个接一个的排列"。
线性表是由同一类型的数据元素构成的线性结构。
这句话的我的理解是线性结构中的数据元素是同一类型就可以说是线性表。
线性结构的逻辑存储
线性结构的逻辑存储有两种表示：顺序表示和链式表示
顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。
链式表示：指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针 。
顺序表:
顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
顺序结构：
将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。
采用顺序存储结构的线性表简称为“ 顺序表”。
非线性结构
相对应于线性结构，非线性结构的逻辑层次是一个结点元素可能对应多个直接前驱和多个后继。
常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
用来描述复杂度O(nlog2n)是什么意思？
O()代表不超过括号内数值的最大整数值。
n*log2(n) n乘以n的以2为底的对数
网友评论