美文网首页
数据结构-数组

数据结构-数组

作者: bug_f4b1 | 来源:发表于2019-05-19 15:45 被阅读0次

    数组概念:

    数组是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型结构的数据。

    关键词:

    线性:顾名思义,线性表就是数据排成像一条线一样的数据结构。每个线性表上的数据最多只有前后两个方向。其实除了数组,链表,队列,栈等也是线性表结构

    线性表结构

    而与它相对立的概念就是非线性表,比如说二叉树,堆,图。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。

    第二个是连续的内存空间和相同类型的数据。正是因为这两个限制,它才有了一个堪称“杀手锏”的特性:“随机访问”。但有利就有弊,随机访问对应的就是查询很快,但是当插入和删除的时候,为了保证连续性,需要对数据进行大量的迁移工作。

    接下来我们来看下插入操作

    数组长度为n,现在我们要将一个数据插入到数组中的第k个位置。为了把第k个位置空出来,就需要把k后面所有的数据依次往后面移动一位,如果我们是在数组开头插入数据,那么就需要把所有的数据都顺序往后面移动,这个时候时间复杂度就是O(n),如果是在数组末尾插入一个数据,那么就不需要移动数据,时间复杂度就是O(1),所以最坏情况下的时间复杂度是O(n),

    最好情况下的时间复杂度是O(1),但是其实在真正的工作当中,出现这两种情况的几率很小,大多数都是在数组开头到结尾的位置插入数据,那么平均算下来时间复杂度就是O(n)。

    我们再来看删除操作

    跟插入数据类似,如果我们要删除第k个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了。

    和插入类似,如果删除数组末尾的数据,则最好情况时间复杂度为O(1),如果删除开头的数据,则最坏情况时间复杂度为O(n);平均情况时间复杂度也为O(n)。

    实际上在某些特殊情况下,我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行,删除的效率是不是会提高很多呢?

    数组a[10]中存储了8个元素:a,b,c,d,e,f,g,h。现在我们要依次删除a,b,c三个元素

    为了避免搬移三次数据,我们可以给这三个数据打上已删除的标示,当数组没有更多空间存储数据时,我们在触发一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。

    内容小结

    我们今天学习了数组。它可以说是最基础,最简单的数据结构了。数组用一块连续的内存空间,来存储相同类型的一组数据,最大的特点就是支持随机访问,但插入,删除操作也因此变得比较低效,平均情况时间复杂度为O(n)。在平时的业务开发中,我们可以直接使用编程语言中提供的容器类,但是,如果是特别底层的开发,直接使用数组可能会更合适。

    相关文章

      网友评论

          本文标题:数据结构-数组

          本文链接:https://www.haomeiwen.com/subject/jmlqzqtx.html