顺序存储查找优 顺序存储的优点

一、栈只能顺序存储,这句话对吗,为什么

栈只能顺序存储，这句话不对。栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)。

一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈也称为后进先出表。线性表可以顺序存储，也可以链式存储，因此栈也可以采用链式存储结构。

扩展资料：

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。

在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。

栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息：

1、函数的返回地址和参数。

2、临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。

链式存储结构的特点：

1、比顺序存储结构的存储密度小(链式存储结构中每个结点都由数据域与指针域两部分组成，相比顺序存储结构增加了存储空间)。

2、逻辑上相邻的节点物理上不必相邻。

3、插入、删除灵活(不必移动节点，只要改变节点中的指针)。

4、查找节点时链式存储要比顺序存储慢。

5、每个节点是由数据域和指针域组成。

6、由于簇是随机分配的，这也使数据删除后覆盖几率降低，恢复可能提高。

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。

采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

参考资料：百度百科-栈

参考资料：百度百科-链式存储结构

参考资料：百度百科-顺序存储结构

二、顺序表的缺点

顺序表的缺点如下：

插入和删除操作需要移动大量元素。当线性表长度变化较大时,难以确定存储空间的容量。插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低。

由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。不可以增长长度，有空间限制，当需要存取的元素个数可能多于顺序表的元素个数时，会出现＂溢出＂问题。当元素个数远少于预先分配的空间时，空间浪费巨大。

更多介绍如下：

顺序表的优点是便于随机存储，缺点是不便于插入删除等操作，因为插入删除一个元素需要移动其后的所有元素，但是链表不存在这个问题，链表只要改变指针就行，时间复杂度小，所以链表于顺序表恰恰相反，优点是便于插入删除等操作，缺点是随机存储没有顺序表方便。

存储空间是连续的，通常用数组实现。因此，可以通过索引查找，优点是查找修改速度比较快，然而由于顺序存储，带来的缺点是，增加和删除要移动数据，操作比较麻烦，速度也较慢。

链表：存储空间是不连续的，每个元素通过指针连接起来的，正好不顺序表相反，查找比较耗时，但增加删除元素比较快，可在常数时间内完成。

链式的要比顺序的方便（因为插入的话顺序表也很方便，问题是顺序表的插入要执行更大的空间复杂度，包括一个从表头索引以及索引后的元素后移，而链表是索引后，插入就完成了）

例如：当你在字典中查询一个字母j的时候，你可以选择两种方式，第一，顺序查询，从第一页依次查找直到查询到j。第二，索引查询，从字典的索引中，直接查出j的页数，直接找页数，或许是比顺序查询最快的、

三、顺序存储的优点

顺序存储的优点有：

1、空间利用率高。（局部性原理，连续存放，命中率高）

2、存取速度高效，通过下标来直接存储。

3、无需为表示结点间的逻辑关系而增加额外的存储空间。

4、可方便地随机存取表中的任一元素。

顺序存储缺点

1、插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低。

2、由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。

3、不可以增长长度，有空间限制，当需要存取的元素个数可能多于顺序表的元素个数时，会出现＂溢出＂问题。当元素个数远少于预先分配的空间时，空间浪费巨大。

四、b树和b+树都能有效的支持顺序查找

b树和b+树都能有效的支持顺序查找。

B树（B-Tree）是一种自平衡的多路搜索树，它广泛应用于数据库和文件系统的索引结构。在B树中，每个节点可以存储多个键值对，并且拥有多个子节点。这使得B树在插入、删除和搜索操作中具有较好的平衡性，从而减少了I/O操作次数。

在B树中，每个节点中的键值对按照升序排列，并且每个节点中的键值对数量有一定限制。这种结构使得B树非常适合于顺序查找。在顺序查找过程中，从根节点开始，按照键值对的顺序依次访问子节点和键值对，直到找到目标键值对或者到达叶子节点。

由于B树具有较好的平衡性，因此顺序查找的时间复杂度相对稳定，能够较好地支持大规模数据的查找操作。B+树（B+-Tree）是B树的一种变种，它也具有平衡多路搜索树的特点。与B树不同的是，B+树中的所有键值对都存储在叶子节点中，并且每个节点中的键值对数量限制更严格。

这种结构使得B+树在范围查询和顺序查找方面表现得更加优秀。在顺序查找过程中，B+树的查找效率与B树相似。从根节点开始，沿着树的路径依次访问子节点和键值对，直到找到目标键值对或者到达叶子节点。由于B+树的叶子节点之间存在指针链接。

B-树的删除：

如果该关键字所在的结点不是最下层的非叶子结点，则先需要把此关键字与它在B-树中后继对换位置，即以指针Pi所指子树中的最小关键字Y代替Ki，然后在相应的结点中删除Y。

如果该关键字所在的结点正好是最下层的非叶子结点，这种情况下，会有以下两种可能：若该关键字Ki所在结点中的关键字个数不小于┌m/2┐，则可以直接从该结点中删除该关键字和相应指针即可。