数据结构之顺序表

一、概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。

**2. 动态顺序表：使用动态开辟的数组存储。 **

二、具体代码实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空
间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表。

#pragma once

// SeqList.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLDateType;
typedef struct SeqList
{
    SLDateType* a;
    int size;
    int capacity;
}SeqList;

// 对数据的管理:增删查改 

//初始化
void SeqListInit(SeqList* ps);

//销毁
void SeqListDestroy(SeqList* ps);

//打印
void SeqListPrint(SeqList* ps);

//尾插
void SeqListPushBack(SeqList* ps, SLDateType x);

//头插
void SeqListPushFront(SeqList* ps, SLDateType x);

//查看顺序表容量，若满了就扩容
void CheckSeqlist(SeqList* ps);

//头删
void SeqListPopFront(SeqList* ps);

//尾删
void SeqListPopBack(SeqList* ps);

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

//SeqList.c
#include "SeqList.h"

void SeqListInit(SeqList* ps)
{
    int i = 0;
    ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 5);
    ps->capacity = 5;
    ps->size = 0;

    for (i = 0; i < ps->capacity; i++)
    {
        ps->a[i] = 0;
    }
}

void SeqListDestroy(SeqList* ps)
{
    ps->capacity = 0;
    ps->size = 0;
    free(ps->a);
}
    
    
void SeqListPrint(SeqList* ps)
{
    assert(ps);
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

void CheckSeqlist(SeqList* ps)
{
    assert(ps);
    if (ps->size == ps->capacity)
    {
        SLDateType* tmp = (SLDateType*)realloc(ps->a,sizeof(SLDateType) * (ps->capacity) * 2);
        ps->capacity *= 2;//若容量满了就扩容为原来的两倍
        if (tmp != NULL)
        {
            ps->a = tmp;
        }
    }
}

void SeqListPushBack(SeqList* ps, SLDateType x)
{
    assert(ps);
    CheckSeqlist(ps);
    ps->a[ps->size] = x;
    (ps->size)++;
}

void SeqListPushFront(SeqList* ps, SLDateType x)
{
    assert(ps);
    CheckSeqlist(ps);
    int j = ps->size;
    for (; j > 0; j--)
    {
        ps->a[j] = ps->a[j- 1];
    }
    ps->a[0] = x;
    ps->size++;
}

void SeqListPopFront(SeqList* ps)
{
    assert(ps);
    assert(ps->size > 0);
    int j = 0;
    for (j = 0; j < ps->size-1; j++)
    {
        ps->a[j] = ps->a[j + 1];
    }
    ps->size--;
}

void SeqListPopBack(SeqList* ps)
{
    assert(ps);
    assert(ps->size > 0);
    ps->size--;
}

int SeqListFind(SeqList* ps, SLDateType x)
{
    assert(ps);
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        if (ps->a[i] == x)
        {
            return i;
        }
    }
    return -1;
}

void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
    assert(ps);
    assert(pos <= ps->size && pos >= 0);
    CheckSeqlist(ps);
    int j = ps->size;
    for (; j >pos; j--)
    {
        ps->a[j] = ps->a[j - 1];
    }
    ps->a[pos] = x;
    ps->size++;
}

void SeqListErase(SeqList* ps, int pos)
{
    assert(ps);
    assert(pos < ps->size && pos >= 0);
    int j;
    for (j = pos; j < ps->size-1; j++)
    {
        ps->a[j] = ps->a[j + 1];
    }
    ps->size--;
}

//test.c
#include "SeqList.h"

int main()
{
    SeqList s;
    SeqListInit(&s);

    SeqListPushBack(&s, 10);
    SeqListPushBack(&s, 20);
    SeqListPushBack(&s, 30);
    SeqListPushBack(&s, 40);
    SeqListPushBack(&s, 50);
    SeqListPushFront(&s, 0);
    SeqListPrint(&s);

    SeqListPopFront(&s);
    SeqListPrint(&s);

    SeqListPopBack(&s);
    SeqListPrint(&s);

    SeqListInsert(&s, 1, 1);
    SeqListPrint(&s);

    SeqListErase(&s, 1);
    SeqListPrint(&s);

    SeqListDestroy(&s);

    return 0;
}

三、顺序表的问题及思考

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
   200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

下面即将学习的链表就可以进一步优化顺序表。