常用数据结构:线性结构-1
上一篇 /
下一篇 2012-05-04 11:17:40
/ 个人分类:杂谈
数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图:
51Testing软件测试网
h*`Re%P~
常用的线性结构有:线性表,栈,队列,循环队列,数组。线性表中包括顺序表、链表等,其中,栈和队列只是属于逻辑上的概念,实际中不存在,仅仅是一种思想,一种理念;线性表则是在内存中数据的一种组织、存储的方式。
W$W#t,Nw9vw0 顺序表
/uvEK:ha(r0 顺序表将元素一个接一个的存入一组连续的存储单元中,在内存物理上是连续的。如下图:
5Q:n!h0hdECx&u0
2j Rc!?no0
顺序表存储密度较大,节省空间;但需要事先确定容量,在时间性能方面,读运算较快,时间复杂度为O(1);查找运算为O(n/2),和链表同样;插入运
算和删除运算如果要操作中间一个元素,比如3,那么就需要把3后面的元素全部进行移动,因此时间复杂度相对链表要大一些,插入时间复杂度最好为O(0)或
最坏为O(n);删除时间复杂度为O([n-1]/2);
9y1X u;Y/]2p9x0 链表