数据结构初阶——顺序表

   博客写到这里，关于C语言的相关内容就告一段落了，从这篇开始，跟我一起进入一个全新的领域吧。

   前面也为大家介绍了通讯录应该怎样去实现，其实顺序表也与通讯录差不多。顺序表是一种线性表，线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储，关于线性表后面也会介绍很多。

1. 顺序表的基本结构

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

顺序表一般可以分为：

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

   像通讯录第一次实现时定义了1000个。

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

** **动态的通讯录

2. 接口实现

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

   以后会经常用到typedef去对类型重命名，首先就要把顺序表的结构写出来，之后就来实现各种功能。

3. 增加数据

3.1 创建、初始化与销毁

   再增加数据之前，首先要在主函数创建一个顺序表，再对这个顺序表初始化。还是继续用模块化的方式。

函数的参数是结构体指针，所以实参传入的时候要对结构体变量取地址。

3.2 增加

对于增加有两种形式，一种是头插，另一种是尾插。

3.2.1 尾插

在开始插入时，我们要先对空间进行一个检查，检查空间是否足够我们插入数据。

在检查时，先使用临时变量newcapacity和tmp，如果空间不够，我们直接扩容一倍，在开始的时候，size和capacity都是0，那开始直接先给4个空间，最后检查无误后再赋值。

开始size是0，正好对应下标为0的位置，也就是第一个位置，之后size++，这时数据就可以存入了。

为了检测我们插入的数据是否真的存到了顺序表中，再写一个打印函数 。

之后就测试一下

** 3.2.2 头插**

头插不能在顺序表的头部插入，只能把所有的数据往后挪，再把数据插入。

问题就是需要拿几次，和在存放时的越界问题，但这里应该不会出现这种问题，当size和capacity的值相等的时候就会扩容。

4. 删除数据

4.1 尾删

尾删就简单很多，但还是得检查一下size，如果没用数据就不要删了，这种assert的方法比较“暴力”，但感觉方便。

这样就尾删了三个数据。

4.2 头删

可以看到什么都没有打印，前面一共有5个数据，尾删了三次，头删两次，所以最后什么也没有，可不是出错啊。

5. 随机插入

总之就是需要插入的时候就得判断需不需要扩容，既然pos是下标，就要判断pos的有效性。pos=0就是头插，pos=size就是尾插。之后也就可以复用。

一个头插一个尾插测试一下。

6. 随机删除

和插入之前的数据一样。

当然，随机删除也是可以复用的。

一个头删一个尾删来测试一下。

7. 查找

找到了返回下标，找不到返回-1，毕竟下标没用负数。

8. 修改

修改就可以使用查找函数，只有找到了才能修改，把SLFind的返回值传入再进行修改。

结尾总结

关于顺序表的大致实现就介绍到这里，数据结构介绍的还是数据存放的形式，顺序表是连续存放的，不存在空缺。Test.c文件中只是潦草的写了一些调试的代码，如果想变得更好，也可以像通讯录的时候写一个菜单，再写的时候一定要创建结构体变量再进行操作，最后把所有的代码放在下面。

Seqlist.h文件

#pragma once

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

typedef int SLDataType;

typedef struct Seqlist
{
    SLDataType* a;//指向动态开辟的数组
    int size;     //表中已存入数据的个数
    int capacity; //容量空间的大小
}SL;

//初始化
void SLInit(SL* ps);
//销毁
void SLDestory(SL* ps);
//打印
void SLPrint(SL* ps);

//尾插/头插/尾删/头删
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

//随机插入
void SLInsert(SL* ps, int pos, SLDataType x);
//随机删除
void SLErase(SL* ps, int pos);

//查找
int SLFind(SL* ps, SLDataType x);

//修改
void SLModify(SL* ps, int pos, SLDataType x);

Seqlist.c文件

#define _CRT_SECURE_NO_WARNINGS 1

#include "Seqlist.h"

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

void SLInit(SL* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->capacity = ps->size = 0;
}

void SLDestory(SL* ps)
{
    assert(ps);
    if (ps->a)
    {
        free(ps->a);
        ps->a = NULL;
        ps->capacity = ps->size = 0;
    }
}

void SLCheckCapacity(SL* ps)
{
    if (ps->capacity == ps->size)
    {
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            return;
        }
        ps->capacity = newCapacity;
        ps->a = tmp;
    }
}

void SLPushBack(SL* ps, SLDataType x)
{
    //assert(ps);
    //SLCheckCapacity(ps);

    //ps->a[ps->size] = x;
    //ps->size++;
    SLInsert(ps, ps->size, x);
}

void SLPushFront(SL* ps, SLDataType x)
{
    //assert(ps);
    //SLCheckCapacity(ps);

    //int end = ps->size;
    //while (end > 0)
    //{
    //    ps->a[end] = ps->a[end - 1];
    //    end--;
    //}
    //ps->a[end] = x;
    //ps->size++;
    SLInsert(ps, 0, x);
}

void SLPopBack(SL* ps)
{
    //assert(ps);
    //assert(ps->size > 0);
    //ps->size--;
    SLErase(ps, ps->size - 1);
}

void SLPopFront(SL* ps)
{
    //assert(ps);
    //assert(ps->size > 0);

    //int end = ps->size - 1;
    //for (int i = 0; i < end; i++)
    //{
    //    ps->a[i] = ps->a[i + 1];
    //}
    //ps->size--;
    SLErase(ps, 0);
}

void SLInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);

    //pos就是插入的下标
    int end = ps->size;
    while (end > pos)
    {
        ps->a[end] = ps->a[end - 1];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

void SLErase(SL* ps, int pos) 
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);

    for (int i = pos; i < ps->size - 1; i++)
    {
        ps->a[i] = ps->a[i + 1];
    }
    ps->size--;
}

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

void SLModify(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);

    ps->a[pos] = x;
}