数据结构——顺序表2 – 一蓑烟雨任平生

上一篇文章说到可以用last来标记数组的最后一个元素，但是我们还是需要定义一个变量来存放数据，如果变量定义在子函数中，函数结束后，变量也随之消亡，这对于数据的存放显然是不安全的。

我们可以使用malloc函数在堆区给数据申请空间，只要这块空间没有被free，数据便会一直存在（程序没有结束的情况下），但是使用malloc为数组和last去分别申请空间还是不够方便，所以可以定义一个结构体类型同时为它们申请空间：

结构体

#define N 5
typedef struct seq
{
    int data[N];
    int last;
}seqlist_t;

针对顺序表的插入、删除、修改、查找、清空操作，可以分别用函数封装存放在单独的.c文件中，除了这些函数，还要定义函数为顺序表开辟堆区空间，另外，还要定义输出函数打印顺序表，这样才能直观地观察函数功能是否实现。

创建一个空的顺序表

seqlist_t *CreateEpSeqlist()
{
    seqlist_t *p = (seqlist_t *)malloc(sizeof(seqlist_t));
    if (NULL == p)
    {
        perror(p malloc error);
        return NULL;
    }
    p->last = -1;
    return p;
}

创建时，要将空间地址强制转换为我们创建的结构体的指针，还要对是否开辟成功做容错判断，开辟失败返回NULL，开辟成功则返回首地址，当然，创建的是空顺序表，有效元素个数为0，所以要将last初始化为-1。

为了满足算法的健壮性，在对数据做任何操作之前都要进行容错判断，比如插入时要看顺序表是否已经装满以及插入位置post是否合法。

判断顺序报表是否装满

int IsFullSeqlist(seqlist_t *p)
{
    return p->last + 1 == N;
}

顺序表满时返回1（真）。

插入函数

int InsertIntoSeqlist(seqlist_t *p, int post, int data)
{
    if (post > p->last + 1 || post < 0 || IsFullSeqlist(p))
    {
        perror(inset error);
        return -1;
    }
    for (int i = p->last; i >= post; i--)
        p->data[i + 1] = p->data[i];
    p->data[post] = data;
    p->last++;
    return 0;
}

插入位置可以是last的后一位，但不能是后两位，所以插入位置不能大于last+1且不能小于0，不满足条件输出插入错误。和上一篇文章插入的方法一样，只是这里访问的方法变成了用指针p来访问。

删除函数

int DeletePostSeqlist(seqlist_t *p, int post)
{
    if (post > p->last || post < 0 || IsEpSeqlist(p))
    {
        perror(delete error);
        return -1;
    }
    for (int i = post; i < p->last; i++)
        p->data[i] = p->data[i + 1];
    p->last--;
    return 0;
}

和插入相同，删除之前也要进行容错判断，删除位置post不能大于last且不能小于0，和插入函数不同的是删除需要判断顺序表是否为空，为空则输出删除错误。删除方法也是只需将删除位置之后的元素整体向前覆盖即可。

判断顺序表是否为空

int IsEpSeqlist(seqlist_t *p)
{
    return p->last == -1;
}

如果last值为-1，说明有效元素个数为0，顺序表为空。

清空顺序表

void ClearSeqList(seqlist_t *p)
{
    p->last = -1;
}

原理和判断顺序表是否为空相同，只需将last的值赋成-1即为清空顺序表。

修改指定位置数据

int ChangePostSeqList(seqlist_t *p, int post, int data)
{
    if (post > p->last || post < 0 || IsEpSeqlist(p))
    {
        perror(change error);
        return -1;
    }
    p->data[post] = data;
    return 0;
}

容错判断和删除相同，修改只需将修改的值赋给需要修改的位置即可。

查找指定数据的位置

int SearchDataSeqList(seqlist_t *p, int data)
{
    for (int i = 0; i <= p->last; i++)
    {
        if (data == p->data[i])
        {
            printf(%d\n, i);
            return i;
        }
    }
    printf(not found\n);
}

遍历顺序表中的值和需要查找的值一一比较，相同输出值的下标，遍历完成若没有相等的值输出not found。

遍历打印顺序表：

void ShowSeqlist(seqlist_t *p)
{
    if (IsEpSeqlist(p))
    {
        perror(empty);
        return;
    }
    for (int i = 0; i <= p->last; i++)
        printf(%d  , p->data[i]);
    printf(\n);
}

最后，将所有功能函数放到同一个.c文件中，结构体和函数的声明放到.h文件中，主函数单独放到main.c文件，然后用make工具进行管理。

结构体