【从零开始学数据结构①】：顺序表

学完c语言的基础语法，我们便要开始数据结构的学习，那么什么是数据结构呢，听我给你一一道来吧！

一.数据结构

1.什么是数据结构？

定义：数据结构是计算机存储、组织数据的方式。

2.为什么要使用数据结构？

在前面几章中我们学习到了数组这一概念，用下标来管理数据，但是你有没有想过，如果数据量过大，仅用数组便于管理和使用吗？

显然有些吃力了，那么这里便是为什么使用数据结构的原因了，以结构的形式进行数据管理。

二.顺序表

1.线性表

在了解顺序表前先让大家了解一下线性表 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使⽤的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表的定义

顺序表是一种线性表的顺序存储结构，底层结构为数组，即以一组地址连续的存储单元进行存储。

顺序表中可以存储任何类型的数据（整型，字符型，结构体，指针…）

3.顺序表的分类

（1）静态顺序表

静态顺序表，顾名思义大小是静态不可改变的，采用定长数组进行创建。

//静态顺序表
typedef int SLDataType;
//将数据类型更名，方便以后的数据类型变化
//例如：后需要存储char类型，这样就可以全部更改
#define N 10
//宏定义N的值为10，方便后续使用，只需改一处
typedef struct SeqList
//给机构体重新命名方便后续使用
{
SLDataType arr[N];//定长数组
int size;//有效数据个数
}SL;

静态顺序表的缺点：空间确定，给多了浪费，给少了不够。

（2）动态顺序表

与静态顺序表不同的则是拥有了动态改变内存大小的功能，运用malloc, realloc按需求进行申请内存或改变内存大小。

//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;
//因为动态申请内存，所以有首元素地址即可
int size;//有效数据个数(可以访问的元素个数)
int capacity;//空间大小
}SL;

三.动态顺序表的功能实现

因为顺序表是为了管理数据，所以应该有增删查找等功能，接下来我将从这几点来实现功能。

注：创建顺序表示，应该有三个文件

• 顺序表的头文件（SeqList.h）
• 顺序表的功能文件（SeqList.c）
• 顺序表的测试文件（test.c） 创建好以上文件我们就可以开始创建顺序表了，准备好开始上高速！

1.顺序表的定义

//SeqList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//把要是用的头文件都包含在SeqList.h中
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;
int size;
int capacity;
}SL;

2.顺序表的初始化

像创建其他变量一样，在定义完后我们需要对其进行初始化

可以在测试文件测试功能是否成功运行，注意每实现一个功能就进行一次测试，切记不要写了多个功能后一起测试，这样会使得我们不易找到错误！

先在头文件中声明后在功能文件实现完整功能。 注意：因为初始化需要改变实参所以要采用传递指针，而非简单传递值。

3.顺序表的销毁

为什么在这里先讲销毁呢？因为在顺序表中的内存是由动态申请来的，所以需要销毁申请的堆区内存。

在这里需要注意！内存在被回收后不会自动置为空指针，若不手动置空，则成了野指针！！有非法访问的可能。

4.顺序表数据的增添

那么接下来我们就要依次学习顺序表的增删查找功能了！

数据的增添又分为两种

• 头插（即在最开始添加数据）
• 尾插（即在末尾添加数据）
• 指定位置插入

在这里我们又易到难来展开讲解

a.尾插

在顺序表的末尾插入数据 核心思路：找到末尾下标，在此下标处插入数据 在插入数据前我们需要先检查空间是否足够，若不够则需要扩容

//检查空间是否充足
void SLCheck(SL *sp)
{
assert(sp);//确保参数不为空指针
if(sp->size == sp->capacity)
//当有效个数与空间容量相等时则证明空间不够
//此情况包含了size和capccity为0时的情况，十分巧妙
{
//空间不够时，按倍数进行扩增
int newcapcity = capacity == 0 ? 4 : sp->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(sp->arr, newcapacity * sizeof(SLDataType));
//检查是否扩容成功
if(tmp == NULL)
{
perror("realloc");
exit(1);
}
//由我们所定义的标识符所维护
sp->capacity = newcapacity;
sp->arr = tmp;
}
}

空间充足时开始插入数据：

//尾插
void SLPushBack(SL* sp, SLDataType x)
{
assert(sp);
//检查空间
SLCheck(sl);//传值即可，因为我们只需判断无需改变
sp->arr[sp->size] = x;
sp->size++;//增添一个数据后size自增
}

在test文件中我们可以检查一下尾插是否正确 在这里我们可以看到，申请的四个空间中已经插入了两个数据，但是我们发现这样检查不是很方便，所以我们可以写一个打印函数来将顺序表打印出来。

//打印顺序表
void SLPrint(SL* sl)
{
for(int i = 0; i < sl->size; i++)
{
printf("%d ", sl->arr[i]);
}
}

这样一来就可以直观的方便的看到数据的增添与删减变化，无需通过调试来检查。

b.头插

在顺序表的头部插入数据

核心思路:整体元素向后移动，然后将数据添加在首元素位置。

与尾插相似，在插入数据时我们要先检查空间是否足够，若空间不足，则整体移动时可能造成越界非法访问内存。

接下来我们来写头插部分

思考一下： 要整体移动数据是应该从前往后覆盖还是从后往前覆盖呢？

很容易得出答案，那边是从后往前，如果从前往后的话，后一个数据会被前一个数据所覆盖而导致数据改变。 此时下标为1的位置如果要往后移动，则移动数值为1，而不是2，因为从前往后覆盖数值被改变。

从后往前： 这样就可以很好的避免数据丢失，若你学过内存函数，你是否想起一个函数叫memmove?用此函数也可以解决问题，比起for循环更有效率 。

那么下面我们就分别用for循环和memmove函数来进行练习。

for循环版本：

注意在写for循环时，我们的条件和调整部分可能还不知道，我们可以先写成伪代码，即没有条件只有结构的代码，将循环体的内容先写出，在得出循环条件以及调整条件。

memmove版本:

测试一下

c.指定位置插入

核心思路： 找到指定位置，并插入数据

同理：在找到指定位置后，需要将此元素后的所有元素都向后移动一位，故也有两种移动方法，for循环法和memmove法。

//指定位置插入数据（for循环版）
void SLPushInsert(SL* sl, int pos, SLDataType x)
{
assert(sl);//判断传入指针是否为空
//判断要插入位置是否合法
assert(pos >= 0 && pos <= sl->size);
SLCheck(sl);//判断空间是否足够
for(int i = sl->size; i > 0; i—)
{
sl->arr[i] = sl->arr[i – 1];
}
sl->arr[pos] = x;//插入数据
sl->size++;//别忘记有效数据个数加一
}

//指定位置插入数据（memmove版）
void SLPushInsert(SL* sl, int pos, SLDataType x)
{
assert(sl);
assert(pos >= 0 && pos <= sl->size);
SLCheck(sl);
memmove(sl->arr + 1; sl->arr; sizeof(SLDataType) * sl->size);
sl->arr[pos] = x;
sl->size++;
}

测试一下：

到这里了顺序表数据的增添就完成啦。

那么有了添加，接下来我们就来讲讲删除。

5.顺序表数据的删除

与插入数据一样，删除数据也有几种

• 头删（删除第一个数据）
• 尾删（删除末尾的数据）
• 指定位置删除（删除指定位置元素）

像增添数据一样，我们也将从易到难展开讲解

a.尾删

核心思想:抹除最后一个数据

看到这里你可能会想将数据直接删除，而我们前面讲到顺序表中有效数据个数是我们能访问到的元素，若把有效数据个数减一，则之前的数据无法被访问，即被删除。

下面看我演示：

void SLPopBack(SL* sl)
{
sl->size—;
}

尾删是不是很简单？那么我们再来看头删

b.头删

核心思想：首元素后面的元素一次往前移动一个位置,往前覆盖。

思考：移动时应从前往后，而非从后往前，防止数据丢失。

//头删
void SLPopFront(SL* sl)
{
assert(sl);
for(int i = 0; i < sl->size; i++)
{
sl->arr[i] = sl->arr[i + 1];
}
sl->size—;
}

头尾这类我们解决了那么再来看指定位置删除

c.指定位置删除

核心思想：指定位置处后的元素依次往前覆盖

//指定位置删除
void SLPopErase(SL* sl, int pos)
{
assert(sl);
assert(pos >= 0 && pos <= sl->size);
for(int i = pos; i < sl->size; i++)
{
sl->arr[i] = sl->arr[i + 1];
}
sl->size—;
}

到这里我们顺序表删除的功能就结束了！

接下来是查找信息

6.顺序表数据的查找

前面说到顺序表是以结构的形式进行数据管理，那么数据量大时，数据查找是必不可少的一个功能，那么我们开始编写数据的查找功能。

在我们写的顺序表中数据为整型，所以我们可以通过输入整型进行查询数据，大家在以后的学习中，数据类型可以为结构体等类型，所以要查找的数据也有很多种，在这里我们只用整型来演示。

核心思想：通过遍历来找寻给定数据

//顺序表的查询
void SLFind(SL* sl, SLDataType x)
{
assert(sl);
for(int i = 0; i < sl->size; i++)
{
if(sl->arr[i] == x)
{
printf("查找到数据，下标为：%d", i);
return;
}
}
printf("未查找到数据\\n");
}

7.顺序表数据的修改

核心思想：找到数据覆盖即可

//顺序表的修改
void SLModify(SL* sl, SLDataType x, SLDataType y)
{
assert(sl);
for (int i = 0; i < sl->size; i++)
{
if (sl->arr[i] == x)
{
sl->arr[i] = y;
}
}
}

到这里顺序表的定义和实现就都完成了，通过学习顺序表我们可以完成一个小项目，那便是通讯录。

通讯录的功能便是增删查改,只是将顺序表的数组改成了结构体，在结构体内存放姓名，联系方式方式等内容。

【从零开始学数据结构①】: 顺序表部分结束，我们下期再见！