谈顺序存储与链式存储的异同.doc

《谈顺序存储与链式存储的异同.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、谈顺序存储与链式存储的异同[摘要]顺序和链式存储是线性表不同的存储方式，各有优劣，而不同存储方式所对应的算法操作也不同，实现的效率也有差异通过对两种存储方式及三种基本操作进行对比分析，加深学习者对线性表存储结构与对应算法关系的理解，学会对时空效率的权衡，使用户能选择合适的存储结构和算法[关键词]线性表顺序存储链式存储算法1.顺序和链式存储结构比较(1)顺序存储可以用公式loc(ai)=loc(a1)+(i-1)*L(i是顺序存储表中的第i个数据元素,L是存储数据单元的字节长度)进行随机存取顺序存储表中的第i个数据元素，链式存储不能进行随机存储，每次访问数据元素都

2、需要从头指针开始进行。(2)顺序存储不需要为表示表中元素之间的逻辑关系增加额外的存储空间一个存储单元就存储一个数据元素,即存储密度大;链式存储数据元素之间的逻辑关系与物理存储位置不对应，需要增设指示结点之间关系的指针域，因而在存储空间要付出代价。(3)顺序存储采用静态分配内存空间,存储容量难以事先确定,分配过大或过小都不好;链式存储的存储空间采用动态分配,存储空间的利用率很高,不会存在分配不够用或者浪费的情况。(4)在顺序存储表上进行大量的插入和删除操作时，需要移动大量的数据元素，使操作运行时间长；链式存储进行插入和删除数据元素时，不需要移动大量的数据元素，只需

3、要修改指针。2.三种基本算法操作比较2.1顺序存储结构2.1.1插入算法(1)不用查找插入位置i，只需要判断i的合法位置，其范围是1L.listsize说明线性表满了，不能进行插入数据元素操作，要增加存储空间的分量和者作错误处理。(3)将线性表的最后一个数据元素到第i-1个数据元素依次往后移动一个数据单元，空出第i-1个位置的数据单元；(4)把新的数据元素插入到刚才空出来的数据单元中；(5)线性表长度增加12.1.2删除算法(1)不用查找删除位置i，也不用另外判断线性表是否为空，

4、只要取值为1

5、顺序存储和存储的数据元素有序，查找时把给定的关键字与表中的中间位置元素进行比较，若相等就查找成功，若关键字比中间位置大，则下次在右半部分查找，若比中间位置上的数据元素小，则下次在左半部分查找依次重复，直到找完查找区间的所有数据元素也没有找到与关键字相等的数据元素存在，则查找失败。(3)索引查找是把顺序表(主表)中的数据元素等分成相等的几部分(子表)，使后一个子表的所有数据元素均大于前一个子表的最大数据元素，并用每一个子表的最大关键字建立索引表。进行查找时，将给定关键字先与索引表中的关键字进行比较，确定此关键字属于哪一个子表，再在这个子表上进行查找。2.2链式存储

6、结构2.2.1插入算法(1)链式存储的线性表做插入操作，不判断线性表是否满，但是要从头指针开始，通过循环语句while(n&&jnext&&j

7、是1

8、事先确定其大小以及随机读