数据结构——顺序表(附图文讲解|超详细)

文章目录

• • 一、前言
  • 二、顺序表
  • • 2.1 概念
    • • 线性表
      • 顺序表
    • 2.2 分类
    • • 2.2.1 静态顺序表
      • 2.2.2 动态顺序表
    • 2.3 动态顺序表的实现
    • • 2.3.1 准备工作
      • 2.3.2 顺序表的功能接口
      • • 1. 创建一个顺序表
        • 2. 顺序表的初始化
        • 3. 顺序表的销毁
        • 4. 顺序表的打印
        • 5. 顺序表的增容
        • 6. 顺序表的增加功能接口
        • 7. 顺序表的删除功能接口
        • 8. 顺序表的查找实现接口
  • 三、总代码
  • • SeqList.h
    • SeqList.c
    • test.c

一、前言

在数据结构中的学习中，线性表是最基础的结构，而顺序表是根据线性表的顺序存储实现的，也是我们第一个接触到的数据结构。

这篇博客我将从0到1详细讲解顺序表，保证看完就懂。

二、顺序表

2.1 概念

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串…

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

顺序表

顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储，顺序表是一种线性表。

总结：

顺序表和数组的关系：

2.2 分类

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

2.2.1 静态顺序表

概念：使⽤定⻓数组存储元素

静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费

2.2.2 动态顺序表

动态顺序表的结构更加灵活, 可以对结构进行增删查改等操作

2.3 动态顺序表的实现

2.3.1 准备工作

先创建三个文件

解释这三个文件的作用
1、头文件SeqList.h是来声明接口函数，定义顺序表，将几个公共用到的库函数集合起来
2、源文件SeqList.c是用来具体实现接口
3、源文件test.c用于接口的测试工作 ，即具体的使用场景

2.3.2 顺序表的功能接口

1. 创建一个顺序表

//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;
int capacity; //有效数据个数
int size; //空间容量
}SL;

2. 顺序表的初始化

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

3. 顺序表的销毁

//销毁
void SLDestroy(SL* ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->size = 0;
}

4. 顺序表的打印

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

5. 顺序表的增容

增容一般成倍数增加，一般是2、3倍，推荐2倍增容

若每次只增加一个空间，会存在频繁增容，程序执行效率低下

若每次增加的空间比较大，会存在空间的浪费

//增容
void SLCheckCapacity(SL* ps)
{
//当有效数据个数 == 空间容量时，说明空间满了，需要增容
if (ps->size == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//增容
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
}

6. 顺序表的增加功能接口

6.1 尾插接口

直接加在顺序表的最后面

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
//判断空间是否足够，不够就增容
SLCheckCapacity(ps);
//空间足够的情况下
ps->arr[ps->size++] = x;
}

6.2 头插接口

先将顺序表中的所有数据向后挪动一位，再将要增加的数据加在顺序表的最前面

//头插
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
//判断空间是否足够，不够就增容
SLCheckCapacity(ps);
//将顺序表中所有数据向后挪动一位
for (int i = ps->size; i > 0; i—)
{
ps->arr[i] = ps->arr[i – 1];//后移
}
//将要增加的数据加在最前面
ps->arr[0] = x;
++ps->size;
}

6.3 指定位置插入接口

先将指定的位置及之后的数据整体向后挪动一位，再将要增加的数据加在指定的位置

//pos位置插⼊数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);

SLCheckCapacity(ps);
//pos及之后的数据整体向后挪动一位
for (int i = ps->size; i > pos; i—)
{
ps->arr[i] = ps->arr[i – 1];
}
ps->arr[pos] = x;
++ps->size;
}

7. 顺序表的删除功能接口

7.1 尾删接口

直接将最后一个数据删除

//尾删
void SLPopBack(SL* ps)
{
//ps->size：顺序表为空
assert(ps && ps->size);
—ps->size;
}

7.2 头删接口

从第2个数据开始向前移动一位，是第1个数据被覆盖掉，只有一个数据的话直接删除这一个数

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

7.3 指定位置删除接口

指定位置之后的数据整体向前挪动一位

// 删除POS位置的数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);

//pos之后的数据整体向前挪动一位
for (int i = pos; i < ps->size–1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
—ps->size;
}

8. 顺序表的查找实现接口

一个一个进行比对

//查找
int SLFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
//找到了
return i;
}
}
//未找到
return –1;
}

三、总代码

SeqList.h

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

//定义动态顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;
int size; //有效数据个数
int capacity; //空间容量
}SL;

//打印
void SLPrint(SL* ps);
//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(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);
// 删除POS位置的数据
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLDataType x);

SeqList.c

#include"SeqList.h"

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

void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//增容
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
}

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
//判断空间是否足够,不够的话增容
SLCheckCapacity(ps);
//空间足够的情况下
ps->arr[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps != NULL);
//判断空间是否足够,不够的话增容
SLCheckCapacity(ps);
//将顺序表中所有数据向后挪动一位
for (int i = ps->size; i > 0; i—)
{
ps->arr[i] = ps->arr[i – 1];//后移
}
ps->arr[0] = x;
++ps->size;
}

//尾删
void SLPopBack(SL* ps)
{
assert(ps && ps->size);
—ps->size;
}

//打印
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\\n");
}
//头删
void SLPopFront(SL* ps)
{
assert(ps && ps->size);
for (int i = 0; i < ps->size–1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
—ps->size;
}

//指定位置之前插⼊数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);

SLCheckCapacity(ps);
//pos及之后的数据整体向后挪动一位
for (int i = ps->size; i > pos; i—)
{
ps->arr[i] = ps->arr[i – 1];
}
ps->arr[pos] = x;
++ps->size;
}
// 删除POS位置的数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);

//pos之后的数据整体向前挪动一位
for (int i = pos; i < ps->size–1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
—ps->size;
}
//查找
int SLFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
//找到了
return i;
}
}
//未找到
return –1;
}
//销毁
void SLDestroy(SL* ps)
{
assert(ps);
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}

test.c

#include"SeqList.h"
void slTest01()
{
SL sl;
SLInit(&sl);

//尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4); // ctrl + d == ctrl + c + v
printf("尾插: ");
SLPrint(&sl);

// 头插
SLPushFront(&sl, 10);
printf("头插: ");
SLPrint(&sl);

// 尾删
SLPopBack(&sl);
printf("尾删: ");
SLPrint(&sl);

// 头删
SLPopFront(&sl);
printf("头删: ");
SLPrint(&sl);

// 指定位置插入
SLInsert(&sl, 1, 15);
printf("指定插入: ");
SLPrint(&sl);

SLErase(&sl, 1);
printf("指定删除: ");
SLPrint(&sl);
}
int main()
{
slTest01(); //测试函数
return 0;
}