有关线性表的顺序存储和链式存储

Klaus · 发表于 2013-11-5 15:32:26

线性表的顺序存储结构和链表存储结构在插入或删除时，时间复杂度都是O(n) QQ图片20131105153156.jpg

为什么说，“显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显啦~”

my_angel · 发表于 2013-11-5 15:33:15

自己看书。。。。基础到我不想说

Klaus · 发表于 2013-11-5 15:37:34

my_angel 发表于 2013-11-5 15:33

登录/注册后可看大图

自己看书。。。。基础到我不想说

:handshake就是看了还不很明白，它两时间复杂都一样

my_angel · 发表于 2013-11-5 16:41:08

Klaus 发表于 2013-11-5 15:37

登录/注册后可看大图

就是看了还不很明白，它两时间复杂都一样

时间复杂度完全不一样好不好，在频繁插入和删除的情况下差距更是差夸张。。。

19℃ · 发表于 2013-11-5 17:41:27

越频繁就越将优势积少成多

Klaus · 发表于 2013-11-6 13:03:47

my_angel 发表于 2013-11-5 16:41

登录/注册后可看大图

时间复杂度完全不一样好不好，在频繁插入和删除的情况下差距更是差夸张。。。

不都是O (n)吗，看小甲鱼的那个ppt,就我截的那个图

思来想去 · 发表于 2013-11-6 20:49:50

单链表通过指针直接加上或删除就行，而顺序结构需要一个数据一个数据的挪（当插入到第一个位置时，就要将所有的数据向后挪一位再插）。:titter:

好好学啊大K同学

friendan · 发表于 2013-11-7 20:54:56

顺序表插入数据：
这跟学校开会搬凳子差不多，如果我要在第50个位置开始插入100张凳子，
对不起，后面的哥哥姐姐们，麻烦你们都往后挪位置哈。

单链表插入数据：
后面的哥哥姐姐们，你们不用挪位置了，位置虽然乱点没关系，能做人就是了。
给你上张不用挪位置的图吧：

严肃，走神中 · 发表于 2013-11-14 18:10:24

单链除了查找复杂度高点，接下来的插入和删除就比较短了，
而顺序表的每次插入均是o（n）

账号		自动登录	找回密码
密码			立即注册