杭州交通信息网轻度冠心病:求助一个线性表的问题？
来源：百度文库 编辑：杭州交通信息网 时间：2024/04/29 14:26:41
为什么线性表是链式存储时，查找第 i 个元素的时间同 i 值成正比
而 线性表是顺序存储时，查找第 i 个元素的时间同 i 值无关
而 线性表是顺序存储时，查找第 i 个元素的时间同 i 值无关
链式表的特点和优点就是插入和删除方便,但是要遍历也就是浏览就比较费时了.他是根据每个元素存储的下一位的地址来访问的.比如要访问第九个就必须从第一个开始,第一的问第二,第二问第三.比较费时
线性表特点和优点就是遍历方便.他遍历的时候只要输入你要查找的位置,他可以自己计算内存大小,直接访问,比如我一个对象数组,每个对象的大小是10字节.然后我要访问第三个.他就可以直接10*3,然后去访问那块内存再输出.
所以速度要快很多,尤其是元素比较多的时候.
无论你要访问哪里,我只需要一步定位.
链式存储的线性表，想要查找第i个元素，只能从表头开始一个一个节点的走下去，一直走到第i个，i越大，查找时间越长。
而顺序存储的表，由i值可知道他的存储位置，因此查找的时间与i无关。
以上。
不弹此调久矣的老狼
举个例子， 顺序存储相当于把你要的东西按顺序放在一个柜子的格子里， 每个格子都有自己的编号。 你想要第i件东西， 直接去第i个格子去拿就好了。
而链式存储， 怎相当于每件物品的地点随便放置， 但是除了物品外， 还有一张小纸条， 告诉你和它相临的下一件物品在哪里。 这样， 如果你想拿第i件物品， 你必须获得第i-1件物品的小纸条， 上面写着第i件物品在哪儿， 这样才能找到第i件物品， 而你去找第i-1件物品和与他捆绑的小纸条时， 又要先去找第i-2件物品上的小纸条， ... 依次类推， 你必须找到第一个物品， 然后从它的小纸条顺着往后找， 每次往后找一个， 直到找i-1次， 最后找到第i个物品。
我怎么觉得这话说反了