数据: 是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
数据元素: 是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。
数据项: 一个元素可以由多若干个数据组成。数据项是数据不可分割的最小单位。
数据对象: 是性质相同的数据元素的集合，是数据的子集。
数据结构: 是相互之间存在一种或多种特定关系的数据元素的集合。
根据视点不同，数据结构分为逻辑结构和物理结构(存储结构)。其中逻辑结构是指对象中数据元素之间的相互关系，物理结构指数据的逻辑结构在计算机中的存储形式。
逻辑结构下分四种: 1.集合结构: 集合结构中的数据元素除了同属于一个集合外，之间没有任何关系。2.线性机构: 一对一。3.树形机构: 一对多。4.图形结构: 多对多。
物理结构下分两种: 1.顺序存储: 把数据元素存放在地址连续的存储单元里，其数据见的逻辑关系和物理关系是一致的。2. 链式存储: 存储单元可连续或不可连续。
数组与链表的区别
（1）存储位置上：数组逻辑上相邻的元素在物理存储位置上也相邻，而链表不一定；
（2）存储空间上：链表存放的内存空间可以是连续的，也可以是不连续的，数组则是连续的一段内存空间。一般情况下存放相同多的数据数组占用较小的内存，而链表还需要存放其前驱和后继的空间。
（3）长度的可变性：链表的长度是按实际需要可以伸缩的，而数组的长度是在定义时要给定的，如果存放的数据个数超过了数组的初始大小，则会出现溢出现象。
（4）按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)；
（5）按值查找时，若数组无序，数组和链表时间复杂度均为O(1)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；
（6）插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可；
（7）空间分配方面： 数组在静态存储分配情形下，存储元素数量受限制，动态存储分配情形下，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块连续存储空间将导致分配失败； 即数组从栈中分配空间，对于程序员方便快速,但自由度小。链表存储的节点空间只在需要的时候申请分配，只要内存中有空间就可以分配，操作比较灵活高效；即链表从堆中分配空间, 自由度大但申请管理比较麻烦。
网友评论