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

红太狼 2023-07-15 15:18 36阅读 0赞

**顺序表定义：**  
线性表的顺序存储又称顺序表。一组地址连续存放的存储单元依次存放线性表的元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。（逻辑顺序与物理顺序相同）  
数组静态分配：

#define MaxSize 50
    typedef struct{ 
    Elemtype data[MaxSize];
    int length;
    }SqList;

数组动态分配：

#define MaxSize 50
    typedef struct{ 
    Elemtype *data;
    int length;
    }SqList;

> 动态分配的语句  
> C：L.data=(Elemtype\*)malloc(sizeof(Elemtype)\*InitSize);  
> C++：L.data=new ElemType\[InitSize\];

**顺序表的基本操作实现（C++）:**  
插入操作：

bool ListInsert(SqList &L,int i,ElemType e){ 
      if(i<1||i>L.length+1)
      return false;
       if(L.length>=MaxSize)
       return false;
      for(int j=L.Length;j>=i;j--)
       L.data[j]=L.data[j-1];
       L.data[i-1]=e;
       L.length++;
      return true;
    }

> 插入操作的时间复杂度  
> 最好时间复杂度：O(1)  
> 平均时间复杂度：O(n)  
> 最坏时间复杂度：O(n)

删除操作：

bool ListDelete(SqList &L,int i,ElemType &e){ 
    if(i<1||i>L.length)
    return false;
    e=L.data[i-1];
    for(int j=i;j<L.length;j++)
    L.data[j-1]=L.data[j];
    L.length--;
    return true;
    }

> 删除操作的时间复杂度  
> 最好时间复杂度：O(1)  
> 平均时间复杂度：O(n)  
> 最坏时间复杂度：O(n)

按值查找操作：

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(1)  
> 平均时间复杂度：O(n)  
> 最坏时间复杂度：O(n)