线性表的链式和顺序存储问题

横着走的螃蟹 发布于 2013/05/07 12:15
阅读 295
收藏 1
最近看数据结构,关于线性表的链式和顺序存储的利弊,其中书上和我查的资料上都说,链式存储在执行插入和删除操作时开销较小,作为一个完整的操作,链式存储和顺序存储插入和删除操作时间复杂度都是O(n),只不过一个是移动数据造成的时间复杂度,一个是查询节点造成的时间复杂度,我想问的是——书上说的链式插入删除开销较小,具体体现在哪?难道是空间复杂度?@中山野鬼 @宏哥 @数据结构大牛
加载中
0
宏哥
宏哥

顺序存储需要排序,要么数据排序,要么做索引, 代价当然高, 好处是查询快

两个凡是精神补充:

凡事都有代价

链式就和手表链条一样, 任何位置拆卸都是容易的。

http://www.codeforge.cn/read/11632/shmobjqueue.cpp__html  就是一个链式结构。

这个结构好处就是申请, 释放效率高, FIFO不需要排序。

 

横着走的螃蟹
横着走的螃蟹
谢宏哥指点迷津,宏哥你看我这样想对不:顺序存储排序一次后再插入的时候,要想找到元素适合位置得先执行比较操作,而链式插入到适合位置也是执行比较操作,就相当于链式存储的插入操作相对顺序没有增加额外的时间复杂度?
0
优游幻世
优游幻世
顺序存储插入和删除中间的数据后需要移动后面的数据吧
优游幻世
优游幻世
回复 @雪夜月独明 : 这里的开销较小指的是改变内存的操作较少的意思吧
横着走的螃蟹
横着走的螃蟹
是的,不过顺序找到要插入的某个定点时间复杂度是O(1),而链式找到某个点的时间复杂度是O(n)
0
就是不着调
就是不着调

顺序存储,像数组这样的.插入和删除操作涉及到数组元素的迁移.而且数组长度是固定的,如果插入元素时数组长度不够,还需要扩充长度,也就是需要创建一个新的更长的数组,将原来数组中的元素全部拷贝到新数组中.但是数组的查找很快.

链式存储 插入和删除时需要遍历.如果是双向链表,你可以在插入或删除时根据index选择从前面还是从后面遍历.这样一定程度上可以减少遍历次数.

0
中山野鬼
中山野鬼

,链式存储在执行插入和删除操作时开销较小,作为一个完整的操作,链式存储和顺序存储插入和删除操作时间复杂度都是O(n),只不过一个是移动数据造成的时间复杂度,一个是查询节点造成的时间复杂度,”

上面这个话没错哈。这是肯定的。

不过上面的言论有个问题,把寻址和插入、操作的事情混在一起谈了。实际上,如果顺序存储表,不需要通过索引,而直接根据数组下标就可以找到所应该存放的空间位置,那么就不会存在数据插入和删除的挪动问题。反之,则寻址复杂度和链式存储是一样的。哈。

横着走的螃蟹
横着走的螃蟹
鬼哥就是鬼哥,深入浅出,一针见血,谢啦
返回顶部
顶部