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

谈顺序存储与链式存储的异同
[摘要]顺序和链式存储是线性表不同的存储方式，各有优劣，而不同存储方式所对应的算法操作也不同，实现的效率也有差异通过对两种存储方式及三种基本操作进行对比分析，加深学习者对线性表存储结构与对应算法关系的理解，学会对时空效率的权衡，使用户能选择合适的存储结构和算法
[关键词]线性表顺序存储链式存储算法
1.顺序和链式存储结构比较
(1)顺序存储可以用公式loc(ai)=loc(a1)+(i-1)*L(i是顺序存储表中的第i个数据元素,L是存储数据单元的字节长度)进行随机存取顺序存储表中的第i个数据元素，链式存储不能进行随机存储，每次访问数据元素都需要从头指针开始进行。
(2)顺序存储不需要为表示表中元素之间的逻辑关系增加额外的存储空间一个存储单元就存储一个数据元素,即存储密度大;链式存储数据元素之间的逻辑关系与物理存储位置不对应，需要增设指示结点之间关系的指针域，因而在存储空间要付出代价。
(3)顺序存储采用静态分配内存空间,存储容量难以事先确定,分配过大或过小都不好;链式存储的存储空间采用动态分配,存储空间的利用率很高,不会存在分配不够用或者浪费的情况。
(4)在顺序存储表上进行大量的插入和删除操作时，需要移动大量的数据元素，使操作运行时间长；链式存储进行插入和删除数据元素时，不需要移动大量的数据元素，只需要修改指针。
2.三种基本算法操作比较
2.1顺序存储结构
2.1.1插入算法
(1)不用查找插入位置i，只需要判断i的合法位置，其范围是1<i<L.length+1，否则不合法；
(2)判断线性表是否满,若L.length>L.listsize说明线性表满了，不能进行插入数据元素操作，要增加存储空间的分量和者作错误处理。
(3)将线性表的最后一个数据元素到第i-1个数据元素依次往后移动一个数据单元，空出第i-1个位置的数据单元；
(4)把新的数据元素插入到刚才空出来的数据单元中；
(5)线性表长度增加1
2.1.2删除算法
(1)不用查找删除位置i，也不用另外判断线性表是否为空，只要取值为1<i<L.length就包括了线性表判空操作和删除位置的合法性判断了，否则不
合法。
(2)将线性表的第个数据元素到最后一个数据元素依次往前移动一个数据单元，就算删除了第i个数据元素。
(3)线性表长度减1。(虽然最后一个数据元素仍然存在，但已经不是操作中的有用数据了)
2.1.3查找算法
顺序存储可以根据存储数据元素要求的不同而分
成以下几种查找算法：
(1)顺序查找算法对数据元素有序、无序没有要求，只要把给定的关键字与线性表中的数据元素逐个进行比较，若相等查找就成功，若找遍整个线性表中的数据元素都没有找到与关键字相等的数据元素，则查找失败。
(2)折半查找是要求顺序存储和存储的数据元素有序，查找时把给定的关键字与表中的中间位置元素进行比较，若相等就查找成功，若关键字比中间位置大，则下次在右半部分查找，若比中间位置上的数据元素小，则下次在左半部分查找依次重复，直到找完查找区间的所有数据元素也没有找到与关键字相等
的数据元素存在，则查找失败。
(3)索引查找是把顺序表(主表)中的数据元素等分成相等的几部分(子表)，使后一个子表的所有数据元素均大于前一个子表的最大数据元素，并用每一个子表的最大关键字建立索引表。进行查找时，将给定关键字先与索引表中的关键字进行比较，确定此关键字属于哪一个子表，再在这个子表上进行查找。
2.2链式存储结构
2.2.1插入算法
(1)链式存储的线性表做插入操作，不判断线性表是否满，但是要从头指针开始，通过循环语句while(n&&j<i-1)循环查找第i-1个节点。
(2)判断i的合法性，i的合法范围是1<i<n,否则就不合法。
(3)申请一个节点的存储空间，并用一个指针变量指向这个节点，把需要插入的数据元素赋值给这个节点的数据域中。
(4)修改插入数据元素的指针，完成插入操作。
2.2.2删除算法
(1)链式存储的线性表做删除操作前，要从头指针开始，通过循环语句while(p->next&&j<i-1)循环查找需要删除的第i个节点
(2)判断第i个节点的合法性，i的合法范围是1<i<n，否则不和法。
(3)修改删除数据元素的指针，完成删除操作
(4)释放删除结点的存储空间。
2.2.3查找算法
链式存储可以根据存储数据元素要求的不同而分成以下几种链表形式的查找算法：
(1)单链表。只能从头指针开始，一个结点接着一个结点地顺序查找，不能找节点前驱，只能找结点后继结点。
(2)循环链表。可以从头指针开始，也可以从尾指针开始顺序地查找结点的后继元素。
(3)双向链表。从头指针开始顺序查找结点，即可以查找结点的前驱元素，也可以查找结点的后继元素。
3.插入和删除算法
3.1顺序和链式存储比较