顺序存储结构的线性表

线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素。

# define MAXSIZE 20

typedef int ElemType;

typedef struct
{
    ElemType data[MAXSIZE];
    int length;
} SqList;

取元素操作

# define OK 1
# define ERROR 0
# define TRUE 1
# define FALSE 0

// 操作结果：用e返回线性表第i个元素
int 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;
}

插入操作

// 操作结果：在线性表第i个位置插入一个e
int ListInsert(SqList *l, int i, ElemType e)
{
    int temp;
    // 线性表已满
    if (l->length == MAXSIZE)
    {
        return ERROR;
    }
    // 插入位置不合法
    if (i < 0 || i > l->length + 1)
    {
        return ERROR;
    }
    // 若插入的位置不在尾部则先把插入位置后的所有元素向后移动
    if (i <= l->length)
    {
        for (temp = l -> length - 1; temp >= i - 1; temp--)
        {
            l->data[temp + 1] = l->data[temp];
        }
    }
    l->data[i - 1] = e;
    l->length++;
    return OK;
}

删除操作

// 操作结果：删除线性表第i个元素
int ListDelete(SqList *l, int i)
{
    int temp;
    // 线性表为空
    if (l->length == 0)
    {
        return ERROR;
    }
    // 删除位置不合理
    if (i <= 0 || i > l->length)
    {
        return ERROR;
    }
    // 若删除的位置不在尾部则将所有元素后移
    if (i <= l->length)
    {
        for (temp = i; temp <= l->length - 1; temp++)
        {
            l->data[temp] = l->data[temp + 1];
        }
    }
    l->length--;
    return OK;
}

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

1. 物理位置可以表示逻辑关系
2. 存取时间复杂度为O(1)

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

1. 删除和插入需要移动大量元素
2. 不容易设置存储空间容量