【数据结构】——顺序表-阿里云开发者社区

前言：

数据结构是由“数据”和“结构”两词组合而来。

什么是数据？

常见的数值1、2、3、4.....、教务系统⾥保存的⽤⼾信息（姓名、性别、年龄、学历等

等）、网页里肉眼可以看到的信息（文字、图片、视频等等），这些都是数据

什么是结构？

当我们想要使⽤大量使⽤同⼀类型的数据时，通过⼿动定义⼤量的独立的变量对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起，结构也可以理解为组织数据的方式

简而言之

能够存储数据（如顺序表、链表等结构）
存储的数据能够方便查找

那么为什么需要数据结构呢？

假定数组有10个空间，已经使用了5个，向数组中插入数据步骤：

求数组的长度，求数组的有效数据个数，向下标为数据有效个数的位置插入数据（注意：这里是

否要判断数组是否满了，满了还能继续插⼊吗）.....

假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。

结论：

最基础的数据结构能够提供的操作已经不能完全满⾜复杂算法实现。

顺序表

线性表

线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串等

线性表在了逻辑上是线性结构，也就是说是一条直线。但是在物理结构上并不一定是连续的，线性表在物理结构上存储时，通常以数组和链式结构的形式存储。

知识补充：

逻辑结构和物理结构

1.逻辑结构：

所谓逻辑结构就是数据与数据之间的关联关系，准确的说是数据元素之间的关联关系。

注：所有的数据都是由数据元素构成，数据元素是数据的基本构成单位。而数据元素由多个数据项构成。

逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。也可以统一的分为线性结构和非线性结构。

2.物理结构：

数据的物理结构就是数据存储在磁盘中的方式。官方语言为：数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。

而物理结构一般有四种：顺序存储，链式存储，散列，索引

顺序表

顺序表的底层结构就是数组，对数组的封装，实现了常用的增删改查等接口

顺序表可以分为静态顺序表和动态顺序表

静态顺序表

静态顺序表是使用定长的数组来存储元素

#define N 10
typedef int Type;
//静态顺序表
struct SeqList
{
  Type arr[N];//定长数组
  int size;//有效数据个数
};

使用动态顺序表缺陷：空间给小了不够用，空间给多了造成空间浪费

动态顺序表

动态顺序表的实现

静态顺序表是定长数组，而动态顺序表是可增容的，不会浪费空间也不会出现空间不够的场景，这里来实现动态顺序表存储整形数据：

首先就是顺序表的一些功能

这里将其写入SeqList.h 的头文件中

SeqList.h头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Type;
typedef struct SeqList//动态顺序表
{
  Type* arr;
  int size;
  int num;
}SL;
//动态顺序表
// 初始化
void SLInit(SL* p);
//销毁
void SLDesTroy(SL* p);
//输出
void SLPrint(SL* p);
//顺序表扩容
void SLExps(SL* p);
//从头部插入数据
void SLAddHand(SL* p, Type x);
//从头部删除数据
void SLDelHand(SL* p);
//从尾部插入数据
void SLAddEnd(SL* p, Type x);
//从尾部删除数据
void SLDelEnd(SL* p);
//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t);
//从任意位置删除数据
void SLDeleve(SL* p, int t);
//查找数据
int SLFind(SL* p, Type f);

要存储一些数据，顺序表具备以上功能（对于整型）

顺序表初始化

顺序表初始化，其实就是将动态顺序表中指针置为NULL，有效数据和空间容量置为0；

代码如下：

// 初始化
void SLInit(SL* p)
{
  p->arr = NULL;
  p->size = 0;
  p->num = 0;
}

在初始化完成后s中的数据。

顺序表销毁

在使用完顺序表后，就要销毁顺序表，因为动态顺序表内存是动态开辟的，所以需要对动态内存进行释放，并将有效数据和空间容量个数置为0；

代码如下：

//销毁
void SLDesTroy(SL* p)
{
  if (p->arr != NULL)
  {
    free(p->arr);
    p->arr = NULL;
  }
  p->size = 0;
  p->num = 0;
}

顺序表销毁之后，指针置为NULL，有效数据和空间容量的为0；

顺序表输出

现在如果顺序表中有数据，我们需要查看数据，就要用到顺序表的输出

代码如下：

//输出
void SLPrint(SL* p)
{
  for (int i = 0; i < p->size; i++)
  {
    printf("%d ", p->arr[i]);
  }
  printf("\n%d %d\n", p->size, p->num);
}

测试看一下输出

这里将有效数字和空间容量也输出出来以便查看，下面插入数据以后就不在进行输出了

顺序表扩容

我们要像顺序表中插入数据，这必然会涉及到扩容的问题

代码如下：

//顺序表扩容
void SLExps(SL* p)
{
  int num = (p->num == 0) ? 4 : 2 * p->num;
  Type* tmp = (Type*)realloc(p->arr, num * sizeof(Type));
  assert(tmp);
  p->arr = tmp;
  p->num = num;
}

如果首次扩容，即p->num等于0，这样习惯给它赋值成4，以后每次扩容以倍数增加（这里使用2倍，也可以使用3倍）。

扩容以后再测试看一下输出结果（查看有效数据和空间容量）

这里首次扩容，空间容量为4。

注：扩容主要使用在插入数据判断空间大小不够时

顺序表头插

现在需要从顺序表头部（起始位置）插入数据，这里就需要将有效数据向后移动一位，再进行插入数据以防数据丢失。

当然，再插入数据之前需要判断空间是否足够

代码如下：

//从头部插入数据
void SLAddHand(SL* p, Type x)
{
  if (p->size >= p->num)
  {
    SLExps(p);
  }
  for (int i = p->size; i > 0; i--)
  {
    p->arr[i] = p->arr[i - 1];
  }
  p->arr[0] = x;
  p->size++;
}

测试以下代码是否正确

顺序表头删

从起始位置删除数据，就需要把有效数据向前移动一位，并且有效数据个数-1；

代码如下：

//从头部删除数据
void SLDelHand(SL* p)
{
  for (int i = 0; i < p->size - 1; i++)
  {
    p->arr[i] = p->arr[i + 1];
  }
  p->size--;
}

测试：

顺序表尾插

现在从尾部插入数据，很简单直接在数据末尾插入数据，然后有效数据+1；

当然，也需要进行判断空间是否足够

代码如下：

//从尾部插入数据
void SLAddEnd(SL* p, Type x)
{
  if (p->size >= p->num)
  {
    SLExps(p);
  }
  p->arr[p->size] = x;
  p->size++;
}

测试：

顺序表尾删

从尾部删除数据很简单马，可以直接让有效数据个数-1；

代码如下:

//从尾部删除数据
void SLDelEnd(SL* p)
{
  p->size--;
}

测试：

顺序表任意位置插入

从任意位置插入数据，需要将指定位置数据以后的有效数据向后移动一位，再进行插入

代码：

//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t)
{
  if (p->size >= p->num)
  {
    SLExps(p);
  }
  for (int i = p->size; i > t; i--)
  {
    p->arr[i] = p->arr[i - 1];
  }
  p->arr[t] = x;
  p->size++;
}

这里就不输出有效数字个数和空间容量了

测试：

顺序表任意数据删除

从任意位置删除数据，将该位置后的数据向前移动一位

代码如下：

//从任意位置删除数据
void SLDeleve(SL* p, int t)
{
  for (int i = t; i < p->size - 1; i++)
  {
    p->arr[i] = p->arr[i + 1];
  }
  p->size--;
}

测试：

顺序表查找

现在我们需要在顺序表中查找数据

这里也可以写函数返回数据的下标

代码：

//查找数据
void SLFind(SL* p, Type f)
{
  for (int i = 0; i < p->size; i++)
  {
    if (p->arr[i] == f)
    {
      printf("查找的数据下标为：%d\n", i);
      return;
    }
  }
  printf("所查找的数据不存在\n");
}

测试：

到这里，顺序表的知识就完成了，学完这些，我们也要写顺序表的实践，就是通讯录——在下一篇进行实现。

代码总览：

SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Type;
typedef struct SeqList//动态顺序表
{
  Type* arr;
  int size;
  int num;
}SL;
 
//动态顺序表
// 初始化
void SLInit(SL* p);
//销毁
void SLDesTroy(SL* p);
//输出
void SLPrint(SL* p);
//顺序表扩容
void SLExps(SL* p);
//从头部插入数据
void SLAddHand(SL* p, Type x);
//从头部删除数据
void SLDelHand(SL* p);
//从尾部插入数据
void SLAddEnd(SL* p, Type x);
//从尾部删除数据
void SLDelEnd(SL* p);
//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t);
//从任意位置删除数据
void SLDeleve(SL* p, int t);
//查找数据
void SLFind(SL* p, Type f);

SeqList.c

#include"SeqList.h"
 
// 初始化
void SLInit(SL* p)
{
  p->arr = NULL;
  p->size = 0;
  p->num = 0;
}
//销毁
void SLDesTroy(SL* p)
{
  if (p->arr != NULL)
  {
    free(p->arr);
    p->arr = NULL;
  }
  p->size = 0;
  p->num = 0;
}
//输出
void SLPrint(SL* p)
{
  for (int i = 0; i < p->size; i++)
  {
    printf("%d ", p->arr[i]);
  }
  printf("\n");
  //printf("%d %d\n", p->size, p->num);
}
//顺序表扩容
void SLExps(SL* p)
{
  int num = (p->num == 0) ? 4 : 2 * p->num;
  Type* tmp = (Type*)realloc(p->arr, num * sizeof(Type));
  assert(tmp);
  p->arr = tmp;
  p->num = num;
}
//从头部插入数据
void SLAddHand(SL* p, Type x)
{
  if (p->size >= p->num)
  {
    SLExps(p);
  }
  for (int i = p->size; i > 0; i--)
  {
    p->arr[i] = p->arr[i - 1];
  }
  p->arr[0] = x;
  p->size++;
}
//从头部删除数据
void SLDelHand(SL* p)
{
  for (int i = 0; i < p->size - 1; i++)
  {
    p->arr[i] = p->arr[i + 1];
  }
  p->size--;
}
//从尾部插入数据
void SLAddEnd(SL* p, Type x)
{
  if (p->size >= p->num)
  {
    SLExps(p);
  }
  p->arr[p->size] = x;
  p->size++;
}
//从尾部删除数据
void SLDelEnd(SL* p)
{
  p->size--;
}
//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t)
{
  if (p->size >= p->num)
  {
    SLExps(p);
  }
  for (int i = p->size; i > t; i--)
  {
    p->arr[i] = p->arr[i - 1];
  }
  p->arr[t] = x;
  p->size++;
}
//从任意位置删除数据
void SLDeleve(SL* p, int t)
{
  for (int i = t; i < p->size - 1; i++)
  {
    p->arr[i] = p->arr[i + 1];
  }
  p->size--;
}
//查找数据
void SLFind(SL* p, Type f)
{
  for (int i = 0; i < p->size; i++)
  {
    if (p->arr[i] == f)
    {
      printf("查找的数据下标为：%d\n", i);
      return;
    }
  }
  printf("所查找的数据不存在\n");
}

测试代码（test.c）

#include"SeqList.h"
 
void Test()
{
  SL s;
  //初始化
  SLInit(&s);
  //SLPrint(&s);//打印
  //扩容
  //SLExps(&s);
  //SLPrint(&s);//打印
  头插
  //SLAddHand(&s, 520);
  //SLAddHand(&s, 1314);
  //SLPrint(&s);//打印
  头删
  //SLDelHand(&s);
  //SLPrint(&s);
  尾插
  //SLAddEnd(&s, 1314);
  //SLAddEnd(&s, 520);
  //SLPrint(&s);
  尾删
  //SLDelEnd(&s);
  //SLPrint(&s);
 
  //头插
  SLAddHand(&s, 1);
  SLAddHand(&s, 2);
  SLAddHand(&s, 3);
  SLAddHand(&s, 4);
  //4 3 2 1 
  //任意位置插入
  SLAddeve(&s, 9, 2);
  //4 3 9 2 1
  SLPrint(&s);
  //任意位置删除
  SLDeleve(&s, 2);
  SLPrint(&s);
  //4 3 2 1
  SLFind(&s, 9);
  SLFind(&s, 2);
  //销毁
  SLDesTroy(&s);
}
int main()
{
  Test();
  return 0;
}