欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构之线性表(顺序表示)

程序员文章站 2024-03-20 14:28:40
...

定义

线性表是具有相同数据类型的n(n>=0)n(n>=0)个数据元素的有限序列。其中nn为表长,当n=0n=0时,线性表是一个空表。若用LL命名线性表,则一般表示如下:
L=(a1,a2,...,ai,ai+1,..,an) L = (a_1,a_2,...,a_i,a_{i+1},..,a_n)
其中,a1a_1是唯一的第一个数据元素,又称为表头元素ana_n是唯一的最后一个元素,又称为表尾元素。除第一个元素外,每个元素有且仅有一个直接前驱。除最后一个元素外,每个元素有且仅有一个直接后继。

特点:

  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. 逻辑相邻元素物理上也相邻,插入和删除需要移动大量元素