数据结构之线性表（顺序表示）

叁歲伎倆 2022-02-26 16:29 312阅读 0赞

### 定义 ###

**线性表**是具有**相同**数据类型的 n ( n > = 0 ) n(n>=0) n(n>=0)个数据元素的**有限序列**。其中 n n n为表长，当 n = 0 n=0 n=0时，线性表是一个空表。 若用 L L L命名线性表，则一般表示如下：  
 L = ( a 1 , a 2 , . . . , a i , a i + 1 , . . , a n ) L = (a\_1,a\_2,...,a\_i,a\_\{i+1\},..,a\_n) L=(a1,a2,...,ai,ai\+1,..,an)  
其中， a 1 a\_1 a1是唯一的第一个数据元素，又称为**表头元素**； a n a\_n an是唯一的最后一个元素，又称为**表尾元素**。除第一个元素外，每个元素**有且仅有**一个直接前驱。除最后一个元素外，每个元素**有且仅有**一个直接后继。

**特点：**

1.  表中元素个数有限且具有逻辑上的有序性
2.  表中元素数据类型相同
3.  表中元素具有抽象性，仅讨论元素逻辑关系，不考虑元素内容

**划分：**

1.  **顺序存储：** 顺序表
2.  **链式存储：**

>  *  单链表 （**指针实现**）
>  *  双链表（**指针实现**）
>  *  循环链表（**指针实现**）
>  *  静态链表（**借助数组实现**）

注意：

1.  **线性表是逻辑结构**，表示元素之间一对一的相邻关系
2.  **顺序表和链表是指存储结构**

### 线性表的基本操作 ###

*  `InitList(&L)`：初始化表
 *  `Length(L)`：求表长
 *  `LocateElem(L,e)`：按值查找
 *  `GetElem(L,i)`：按位查找
 *  `ListInsert(&L,i,e)`：插入操作
 *  `ListDelete(&L,i,&e)`：删除操作
 *  `PrintList(L)`：输出
 *  `Empty(L)`：判空
 *  `DestroyList(&L)`：销毁

### 线性表的顺序存储 ###

线性表的顺序存储又称**顺序表**，它是一组**地址连续**的存储单元，它的逻辑顺序和物理顺序相同。  
**注意：线性表中的位序是从1开始的，而数组中元素的下标是从0开始的。**

假定线性表的元素类型为**ElemType**，那么线性表的顺序存储类型可以描述如下：

#define MaxSize 50          //定义线性表的最大长度
    typedef struct{
        
        ElemType data[MaxSize]; //顺序表的元素
        int length;             //顺序表的当前长度
    }SqList;                    //顺序表的类型定义

一维数组可以是静态分配的（**数据可能溢出**），也可以是动态分布的。C的初始动态分配语句为：

L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize)

#define InitSize 100       //表长的初始定义
    typedef struct{
                    
        ElemType *data;       // 动态分布数组的指针
        int MaxSize,length;   // 数组的最大容量和当前个数
    }SeqList;

1.  **插入操作**  
    在顺序表L的第i个位置插入新的元素e

bool ListInsert(SqList &L,int i,ElemType e){
        
        if(i<1||i>L.length+1)           //判断i范围是否有效
            return false;
        if(L.length>=MaxSize)          //若当前空间已满，则不能插入
            return false;
        for(int j=L.length;j>=i;j--)  //将第i个元素及后面的元素后移
            L.data[j]=L.data[j-1]
        L.data[i-1]=e;               //插入元素e
        L.length++;                  //表长加1
        return true;
    }

1.  **删除操作**  
    删除表L中第i个位置的元素，删除的元素用变量e返回

bool ListDelete(SqList &L,int i,&e){
        
        if(i<1||i>L.length)           //判断i范围是否有效
            return false;
        e=L.data[i-1];               //将被删除的元素赋值给e
        for(j=i;j<L.length;j++)      //将第i个位置后的元素前移
            L.data[j-1]=L.data[j]
        L.length--;                 //表长减1
        return true;
    }

1.  **按值查找**  
    在表L中查找第一个元素值等于e的元素，并返回其位序

int LocateElem(SqList &L, ElemType e){
        
        int i;
        for(i=0;i<L.length;i++)
            if(L.data[i]==e)
                return i+1;
        return 0;
    }

**总结：上述三种操作的时间复杂度均为O(n)。**

**顺序表的特点：**

1.  **随机访问**，通过首地址和元素序号可以在O(1)的时间内找到指定元素
2.  存储密度高，每个节点只存储数据元素
3.  逻辑相邻元素物理上也相邻，**插入和删除需要移动大量元素**