线性表 顺序表/数组
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了线性表 顺序表/数组,现在分享给大家,供学习和参考。文章包含550字,纯文字阅读大概需要2分钟。
教程信息
一、数组/顺序表的特点
1、空间上
数组中的结点必须是在连续的内存空间内,且必须为数组预留大量空间,一般都会造成浪费
2、时间上
(1)数组可以通过索引直接访问元素,时间复杂度为O(1),速度很快
(2)数组的插入和删除比较复杂,需要挪动大量元素
①在数组末尾插入/删除一个数的时间复杂度是 O(1),不需要移动元素
②如果需要在数组的其他位置插入/删除元素,需要大量元素后移/前移,时间复杂度是O(n)
(3)数组的元素查找可以通过各种类型的查找算法实现,时间复杂度各不相同
二、C/C++中的数组/顺序表
1、C/C++中可以使用普通数组来表示顺序表
(1)顺序表的索引访问,时间复杂度为O(1)
a[0]、a[1]、a[2]、a[3]、a[4]、……、a[n-1]
(2)顺序表的插入与删除,时间复杂度为O(n)【开头和结尾时间复杂度为O(1)】
①插入
for (int i = n; i > index; i--) array[i] = array[i - 1]; array[index] = value; // 在指定位置插入新元素
②删除
for (int i = index; i < n; i++) array[i] = array[i + 1];
2、C++的STL中有vector容器来表示顺序表
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供线性表 顺序表/数组的全部内容,希望教程文章能够帮你了解学习线性表 顺序表/数组,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaozhongji-266.html