文档介绍：一个数据结构有两个要素:
数据元素的集合;
关系的集合。
Data_Structure=(D,R)
其中D是数据元素的有限集,R是D上的关系的有限集。
数据的逻辑结构
数据的逻辑结构—指数据结构中元素之间的逻辑关系。它是从具体问题中抽象出来的数学模型。是独立于计算机存储器(与具体的计算机无关)。可分为如下几种基本类型:
集合结构:
线性结构:
树型结构:
图形结构:
数据的存储结构
数据的存储结构—数据的逻辑结构在计算机存储器中的存储方式,又称物理结构。可分为如下两种类型。
顺序存储结构:
链式存储结构:
数据的逻辑结构
数据的存储结构
数据的运算:检索、排序、插入、删除、修改等
线性结构
非线性结构
顺序存储
链式存储
线性表
栈
队
树形结构
图形结构
数据结构的三个方面:
算法分析和评价
对算法的分析和评价,一般应考虑正确性、可维护性、可读性、运算量、占用存储空间等诸多因素。其中评价算法的3条主要标准是:
(1)算法实现所耗费的时间(时间复杂度)。
(2)算法实现所耗费的存储空间,其中主要考虑辅助存储空间(空间复杂度)。
(3)算法应易于理解、易于编码、易于调试等。
常见的渐进时间复杂度有:
O(1) :常量时间阶 O (n):线性时间阶
O(㏒n) :对数时间阶 O(n㏒n) :线性对数时间阶
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)
例如:一个程序的实际执行时间为
T(n)=++
则T(n)=O(n3)
算法的空间复杂度
空间复杂度:是指算法编写成程序后,在计算机中运行时所需存储空间大小的度量。记作: S(n)=O(f(n))
其中: n为问题的规模(或大小)
线性表的逻辑结构
线性表(Linear List) :是由n(n≧0)个数据元素(结点)a1,a2, …an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。
A=(a1,a2,…,ai,ai+1,…,an) (n≧0),其中称ai是ai+1的直接前驱元素,ai+1是ai的直接后继元素。
线性表的存储结构
分为顺序存储结构和链式存储结构:
顺序存储结构:顺序表
链式存储结构:链表
顺序表
定义:顺序表是指按顺序存储结构存储的线性表,顺序表中的结点在内存中占用一段连续的存储单元。
顺序表存储结构如图所示:
Loc(ai)=add+(i-1)len (1≤i≤n)