线性表的顺序存储

谁践踏了优雅 2022-06-16 03:43 205阅读 0赞

数据结构是指数据元素的集合及元素间的相互关系和构造方法，结构就是元素之间的关系。在数据结构  
中，元素之间的相互关系是数据的逻辑结构，按照逻辑关系的不同将数据结构分为线性结构和非线性结  
构，其中线性结构包括线性表、栈、队列、串，非线性结构主要包括树和图。数据元素及元素之间关系  
的存储形式成为存储结构，可以分为顺序存储和链接存储两种基本的方式。  
算法与数据结构密切相关，数据结构是算法设计的基础，合理的数据结构可使算法简单而高效。  
1. 线性结构  
线性结构的特点是数据元素之间一种线性结构，数据元素一个接着一个地排列，这种结构主要是用于客  
观世界中具有单一前驱和后继的数据关系。  
1.1线性表  
线性表是最简单，最基本，也是最常用的一种线性结构，它有两种存储方法，一个是顺序存储和链式存  
储，主要的基本操作是插入，删除，查找。  
1.2.线性表的定义  
一个线性表是N个元素的有限序列（n>=0），通常表示为(a1,a2,a3...an）。其特点是非空的线性表中：  
1）存在唯一的一个称作‘第一个’的元素  
2）存在唯一的一个称作是“最后一个”的元素  
3）除了第一个元素外，序列中的每个元素均只有一个直接前驱  
4）除了最后一个元素外，序列中的每个元素均只有一个直接后继。  
  
1.3.线性表的存储结构  
1）线性表的存储存储  
线性表的顺序存储是用一组地址连续的存储单元存储线性表中的数据元素，从而是的逻辑上相邻的两个  
元素在物理位置上也相邻，在这种存储方式下，元素间的逻辑关系无需占用额外的空间来存储。  
一般地，以LOC（a1）表示线性表中第一个元素的存储位置，L表示的是每个元素所占空间的大小，则顺

序存储结构中，第i个元素a1的存储位置为LOC(ai)=LOC(a1)+(i-1)\*L

![Center][]

线性表采用顺序存储结构的优点是可以随机存取表中的元素，存储密度大，按照序号查找元素的速度很快。缺点是插  
入和删除操作需要移动元素，插入前要移动元素，以诺触控的存储单元，然后再插入元素，删除元素时  
同样也是需要移动元素，以填充被删除的元素空出来的存储位置。  
在表长为n的线性表中插入新元素时，共有n+1个插入位置，在位置1（元素a1所在的位置）插入元素时，  
需要移动n个元素，在位置n+1（an所在位置之后）插入元素时则不需要移动元素，因为等概率下插入一  
个元素时平均移动元素的次数为n/2  
在表长为n的线性表中删除元素时，共有n个可以删除的元素，删除元素a1时需要移动n-1个元素，删除元

素an时不需要移动元素，因此，等概率下删除一个元素时平均的移动元素次数为(n-1)/2

参考资料：数据库系统工程师教程。之前学过数据结构，现在想重新再看一遍。

[Center]: /images/20220616/35eaa2cafcc64da3b0736fcf5a528344.png