首页 / 算法 / 数组-数据结构和算法之美学习笔记
数组-数据结构和算法之美学习笔记
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数组-数据结构和算法之美学习笔记,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1805字,纯文字阅读大概需要3分钟。
内容图文
![数组-数据结构和算法之美学习笔记](/upload/InfoBanner/zyjiaocheng/617/d256e547cdb2432a94c102989cfe7ab3.jpg)
数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据
第一是线性表(Linear List)。顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构
![数组-数据结构和算法之美学习笔记 - 文章图片](/upload/getfiles/0001/2021/4/30/20210430075601837.jpg)
非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。
![数组-数据结构和算法之美学习笔记 - 文章图片](/upload/getfiles/0001/2021/4/30/20210430075604394.jpg)
连续的内存空间和相同类型的数据
正是因为这两个限制,它才有了一个堪称“杀手锏”的特性:“随机访问”。但有利就有弊,这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。
低效的“插入”和“删除”
插入操作:假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位
如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为 O(1)。但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是 O(n)。 因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为 (1+2+…n)/n=O(n)
删除操作:和插入类似,如果删除数组末尾的数据,则最好情况时间复杂度为 O(1);如果删除开头的数据,则最坏情况时间复杂度为 O(n);平均情况时间复杂度也为 O(n)。
**注意:**数组越界在 C 语言中是一种未决行为,并没有规定数组访问越界时编译器应该如何处理。因为,访问数组的本质就是访问一段连续内存,只要数组通过偏移计算得到的内存地址是可用的,那么程序就可能不会报任何错误
数组为何要从0开始编号?
从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。如果用 a 来表示数组的首地址,a[0]就是偏移为 0 的位置,也就是首地址,a[k]就表示偏移 k 个 type_size 的位置,所以计算 a[k]的内存地址只需要用这个公式:
a[k]_address = base_address + k * type_size
而如果从1开始编号,则该公式变为:
a[k]_address = base_address + (k-1)*type_size
多了一个减法指令,不够高效,所以要用从0开始
内容总结
以上是互联网集市为您收集整理的数组-数据结构和算法之美学习笔记全部内容,希望文章能够帮你解决数组-数据结构和算法之美学习笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。