数据结构详解---顺序表

🌏个人博客主页：意疏-CSDN博客

希望文章能够给到初学的你一些启发～ 如果觉得文章对你有帮助的话，点赞 + 关注+ 收藏支持一下笔者吧～

阅读指南：

开篇说明

数据结构是组织和存储数据的一种方式，它不仅定义了数据的类型，还规定了数据之间的关系以及对数据进行操作的方法。线性表是一种基本的数据结构，用于存储一组有序的数据元素。线性表中的元素具有线性关系，即每个元素有且只有一个前驱和一个后继（除了第一个元素没有前驱和最后一个元素没有后继）。线性表可以分为顺序存储结构和链式存储结构两种实现方式。

在本篇中，我们将深入探讨线性存储中顺序表的实现细节、基本操作（如插入、删除、查找），通过这些内容的学习，希望我们可以一起进步。

线性表的定义

线性表：是具有相同数据类型为n(n>=0)个数据元素的有限序列，它是典型的线性结构。除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。
这里首先要强调的是，首先它是一个序列，也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继。元素的个数是有限的。
如用数字语言来进行定义，**若将线性表记为（

       a 
      
     
       1 
      
     
    
   
     a_1 
    
   
 a1​，…， 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​-1，a， 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​+1，…， 
  
   
    
     
     
       a 
      
     
       n 
      
     
    
   
     a_n 
    
   
 an​）

则表中

       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​-1领先于 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​， 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​领先于 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​+1，我们称 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​-1是 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​的直接前驱， 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​+1是 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​的直接后继元素。当i = 1,2，n-1时， 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​有且仅有一个直接后继，当i = 2,3，n时， 
  
   
    
     
     
       a 
      
     
       i 
      
     
    
   
     a_i 
    
   
 ai​有且仅有一个直接前驱。**

• 这里是示例图：所以线性元素的个数 n n(>=0) 定义为线性表的长度，当n=0时，称为空表。

在非空表中的每个数据元素都有一个确定的位置，如

      a 
     
    
      1 
     
    
   
  
    a_1 
   
  
a1​是第一个数据元素， 
 
  
   
    
    
      a 
     
    
      n 
     
    
   
  
    a_n 
   
  
an​是最后一个数据元素， 
 
  
   
    
    
      a 
     
    
      i 
     
    
   
  
    a_i 
   
  
ai​是第i个数据元素，称i为数据元素 
 
  
   
    
    
      a 
     
    
      i 
     
    
   
  
    a_i 
   
  
ai​在线性表中的位序。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

• 线性表的抽象数据类型定义如下： 在实际问题中，关于线性表的更复杂操作，完全可以用这些基本的操作组合来实现。
• 例如，实现两个线性表集合A和B的并集操作。即要使得集合A = A ∪ \cup ∪ B简单来说就是把存在集合B但不存在A中的数据元素插入到A中即可。我们只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入A即可。****我们假设 L a L_a La​表示集合A， L b L_b Lb​表示集合B，则实现的代码如下：

这里，我们对于union操作，用到了前面线性表基本操作ListLength、GetElem、LocateElem、ListInsert等，其实复杂的操作，其实就是把基本操作组合起来实现的。

线性表的顺序存储结构（顺序表）

我们来看一下线性表的两种物理结构的第一种：顺序存储结构。
线性表的顺序存储结构是指：用一段地址连续的存储单元依次存储线性表的数据元素，从而使逻辑上相邻的两个元素在物理位置上也相邻。

线性表（

      a 
     
    
      1 
     
    
   
  
    a_1 
   
  
a1​， 
 
  
   
    
    
      a 
     
    
      2 
     
    
   
  
    a_2 
   
  
a2​，…， 
 
  
   
    
    
      a 
     
    
      n 
     
    
   
  
    a_n 
   
  
an​）的顺序存储示例图如下：

线性表的顺序存储结构，就是在内存中找地方，通过占位的形式，把一定内存空间给占掉了，然后把相同数据类型的数据元素依次存放在这片空地中。线性表的每个数据元素的类型都相同，所以可以用C语言的一维数组来实现顺序存储结构。即把第一个数据元素存储到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

。数组的分配，在正常情况下是静态分配，但我们也可以动态分配。

• 我们首先来看静态分配：
• 静态分配：数组大小和空间已经固定，一旦空间占满，再加入新的数据，就会产生溢出，导致程序崩溃（空间固定）

#defineMaxSize100//存储空间初始分配量typedefstruct{
    ElemType data[MaxSize];//数组存储数据元素，最大值为MAXSIZEint length;//线性表当前长度} SeqList;

这里我们可以发现描述顺序存储结构需要三个属性：
**1. 存储空间的起始位置：数组

data

，它的存储位置就是存储空间的存储位置。**
**2. 线性表的最大存储容量：数组长度

MaxSize

。**
**3. 线性表的当前长度：

length

。**

这里我们需要注意的是：
数组的长度与线性表的长度两者的区分:
数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不会变的。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是会变化的。
在任何时刻，线性表的长度都需要小于等于数组的长度。

• 我们再来看动态分配：
• 动态分配：存储数据的空间在程序执行中动态语句分配，一旦空间占满，可以另外开辟更大空间，用来替换原始空间。（空间不固定）

#defineInitS100typedefstruct{
    ElemType *data;//包含的数组int length;//当前表中有几个元素} SeqList;

顺序存储结构的插入与删除（顺序表）

获得元素操作
对于线性表的顺序存储结构来说，如果我们要实现GetElem操作，即将线性表L中的第i个位置元素值返回。就程序而言，只要i的数值在数组下标范围内，就是把数组第i－1下标的值返回即可。

• 例

#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefint Status;//Status是函数的类型，其值是函数结果状态代码，如OK等。//初始条件：顺序线性表L已存在，1<=i<=ListLength (L)。//操作结果：用e返回L中第i个数据元素的值。
Status GetElem(SqList L,int i, ElemType *e){if(L.length ==0|| i <1|| i > L.length)return ERROR;*e = L.data[i-1];return OK;}

• 注： 这里返回值类型是Status 是一个整型，返回OK代表1，ERROR代表0。

插入操作

我们要实现ListInsert（*L，i，e），就是将线性表L中的第i个位置插入新元素e。
插入算法的思路：

1. 如果插入位置不合理的话，抛出异常。
2. 如果线性表长度大于或等于数组长度，则抛出异常或动态增加容量。
3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
4. 将要插入的元素填到位置 i 处。
5. 表长加1。

• 代码如下：

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
Status ListInsert(SqList *L,int i, ElemType e){int k;if(L-> length == MAXSIZE)//顺序线性表已满return ERROR;if(i <1|| i > L-> length +1)//当i不在范围内时，返回错误return ERROR;if(i <= L-> length)//若插入位置不在表尾{for(k = L-> length; k >= i-1; k--)//将后面的元素后移一位
            L-> data[k+1]= L-> data[k];}
    L-> data[i-1]= e;//插入新元素
    L-> length++;//表长加1return OK;}

删除操作

删除算法的思路：

1. 如果删除位置不合理的话，抛出异常。
2. 取出删除元素
3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。
4. 表长减1。

• 代码如下：

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
Status ListDelete(SqList *L,int i, ElemType *e){int k;if(L-> length ==0)//线性表为空时，返回错误return ERROR;if(i <1|| i > L-> length)//删除位置不正确return ERROR;*e = L-> data[i-1];//返回被删除元素的值if(i <L-> length)//若插入位置不在表尾{for(k=i;k = L-> length; k++)//将删除位置后继元素前移
            L-> data[k-1]= L-> data[k];}
    L-> length--;//表长减1return OK;}

线性表顺序存储结构的优缺点

优点

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
• 可以快速地存取表中任一位置的元素。

缺点

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的‘碎片’

你好，我是意疏。一起进步。

意气风发，漫卷疏狂
学习是成长的阶梯，每一次`的积累都将成为未来的助力。我希望通过持续的学习，不断汲取新知识，来改变自己的命运，并将成长的过程记录在我的博客中。

如果我的博客能给您带来启发，如果您喜欢我的博客内容，请不吝点赞、评论和收藏，也欢迎您关注我的博客。
您的支持是我前行的动力。听说点赞会增加自己的运气，希望您每一天都能充满活力！
愿您每一天都快乐，也欢迎您常来我的博客。我叫意疏，希望我们一起成长，共同进步。

我是意疏 下次见！