深入解析数据结构之顺序表

---

一、线性表

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

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

补充一下：逻辑结构是人为想象出来的结构，就像平时买菜排队肯定不会是一条直线，但可以认为是一条直线

---

二、顺序表

2.1 概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，也就是说顺序表的底层是数组，顺序表是用数组来实现的

那么顺序表和数组有什么关系呢？

总结下来就是这样的：

2.2 分类

2.2.1 静态顺序表

概念：使用定长数组存储元素

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

2.2.2 动态顺序表

2.3 动态顺序表的实现

这里用vs创建了3个文件，功能分别如下

这里三个文件的代码如下：



看似没有问题，但是这里进行初始化测试的时候出现了报错

这里本意是要将s1传到SLTnit进行初始化，但是传递参数有两种情况，一种是传值，另一种是传址，这里s1是一个没有初始化的变量，直接传给s，就是一个传值调用，而s1没有值，编译器不知道传了个什么东西过去，所以报错

也就是不希望s是个变量，而是希望s也指向0x100这片空间，所以这里使用传址



调试结果也符合传址调用

2.3.1 尾插

这里说一下尾插，顾名思义，在尾部插入数据
size指向顺序表的有效数据个数的下一个位置，如图size和capacity的位置
在顺序表中插入数据有两种场景

该图就是在size这里插入x，插入后有效数据个数++，size向后挪一下

第二种情况如图：

当size和capacity相等的时候，说明空间不够，这时候想再加数据就需要扩容
这里增容之所以成倍增加，一方面是增容使用的realloc函数的方式分两种情况和三步走
深入解析动态内存函数

另一方面则是一个概率学问题

尾插的完整代码如下：






在平时要写一个程序来实现多种功能的时候建议每实现一个功能测试一下，不然后面代码量堆起来出了问题就不太好找了

2.3.2 头插

函数声明：

//头插
void SLPushFront(SL* ps, SLTDataType x);

接下来要写的是头插，空间够的情况下，就是整体数据往后挪，要插入的数据放到最前面

这里将i定为下标，可以让i等于size，每次将i-1位置的数字放到i处，挪完之后i–，然后依次循环

当i等于0时结束循环

当插入新数据时候空间不够，则还需要上述的增容操作，所以这里将增容部分的代码封装为一个函数

代码演示，只放测试文件函数和函数定义的部分

这个代码有缺陷的，如果传一个空指针去插入数据，空指针是无法解引用的

SLPushFront(NULL, 5);

程序可以运行，但退出码是负的，则程序存在问题

//温柔的处理方式，传空指针过去直接退出，不会报错
if (ps == NULL)
{return;
}

此时运行退出码就是0了，代码运行正常，除此之外还有一种方式
使用assert

assert(ps != NULL); //等价于assert(ps）

指针篇（2）- const修饰，野指针，assert断言，指针的使用和传址调用

2.3.3 尾删

函数声明：

//尾删
void SLPopBack(SL* ps);

size直接控制着顺序表中的元素个数，所以删除操作直接对size操作就可

代码演示

这里加了一串代码循环遍历将顺序表中的数据打印出来

size已经为0，再删除一次就会断言报错

2.3.4 头删

函数声明：

//头删
void SLPopFront(SL* ps);

头删即将后面的数据整体向前挪动一位，依旧使用循环，当i等于size-1时，跳出循环，之后size- -

代码演示

2.3.5 查找指定位置数据

函数声明：

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

在顺序表中查找值为x的数据，如果查找到了，返回当前数据在顺序表中的下标，如果没有查找到，则返回一个无效的下标，有效的下标大于等于0。只要小于0，下标就是无效的

代码演示

2.3.7 在指定位置之后插入数据

函数声明：

//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLTDataType x);

代码演示

2.3.5 在指定位置之前插入数据

函数声明

//指定位置之前插⼊
void SLInsert(SL* ps, int pos, SLTDataType x);

在顺序表指定的位置pos之前去插入删除数据x，SLFind函数的返回值可以作为该函数的第二个参数，也就是在pos这个位置去插，pos且pos之后的数据整体向后移动一位，然后将8放入，这里不断循环，将i-1位置的数据给i，当i等于pos时候，循环结束

代码演示

乍一看这一串代码没有问题

这里有效数据个数大于空间大小肯定是有问题的，所以还要在此之前判断空间是否够，这里有时候不一定报错，直接看退出码是否为0
这样就对了

2.3.7 删除指定位置的数据

这里删除数字一就是将2，3数据向前移就可以了，依旧是使用循环，循环终止条件是i<size-1

函数声明

//删除pos位置的数据
void SLErase(SL* ps, int pos);

代码演示

2.3.8 修改指定位置数据

这个就不用写了，很简单

2.3.9 顺序表的销毁

以上就是对顺序表增删查改的全部内容了，因为顺序表的底层是数组，数组是向操作系统realloc出来的，在使用结束之后需要把内存还给操作系统

函数声明：

//销毁顺序表
void SLDestroy(SL* ps);

三、顺序表操作完整源码

函数声明：SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义动态顺序表结构
typedef int SLTDataType;
typedef struct SeqList {SLTDataType* arr;//存储数据int size;//有效数据个数int capacity;//空间大小
}SL;//创建一个结构体变量s，其类型为struct SeqList
//struct SeqList s;
//重命名
//typedef struct SeqList SL;
//SL s;//对顺序表进行初始化
void SLTnit(SL* ps);
//打印顺序表内容
void SLPrint(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);//尾插
//在顺序表中插入数据
//插入的数据类型要与顺序表的数据类型一致
void SLPushBack(SL* ps, SLTDataType x);
//头插
void SLPushFront(SL* ps, SLTDataType x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);
//查找
int SLFind(SL* ps, SLTDataType x);
//指定位置之前插⼊
void SLInsert(SL* ps, int pos, SLTDataType x);
//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLTDataType x);
//删除pos位置的数据
void SLErase(SL* ps, int pos);

函数定义：SeqList.c

#pragma once
#include"SeqList.h"
//初始化
//对SL进行初始化就是对结构体的三个成员进行初始化
void SLTnit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLDestroy(SL* ps)
{//检查顺序表内是否有数据if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}//SLCheckCapacity 函数的声明 / 定义需要指定参数类型，所以是 SL* ps
//这里的 SL* 是类型，ps 是参数名。
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容//如果开辟失败则返回NULL，而原来的arr中是有数据的//所以不能直接让arr接收，而是用一个临时变量SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));if (tmp == NULL){perror("realloc fail!");//0表示正常退出，非0表示异常退出exit(1);}ps->arr = tmp;ps->capacity = newCapacity;//capacity在代码中表示的是元素个数，而非字节数}}//尾插
//在顺序表中插入数据
//插入的数据类型要与顺序表中的数据类型一致
void SLPushBack(SL* ps, SLTDataType x)
{assert(ps != NULL);//空间不够//当调用这个函数时，只需要传递变量名即可，不需要再指定类型//ps是一个指向SL结构体的指针变量，所以调用时直接写SLCheckCapacity(ps)SLCheckCapacity(ps);//空间足够ps->arr[ps->size++] = x;
}//头插
void SLPushFront(SL* ps, SLTDataType x)
{////温柔的处理方式//if (ps == NULL)//{//	return;//}assert(ps != NULL); //等价于assert(ps）//空间不够SLCheckCapacity(ps);//空间足够//数据整体向后挪一位for (int i = ps->size;i > 0;i--){ps->arr[i] = ps->arr[i - 1];}//ps->arr[i]=xps->arr[0] = x;ps->size++;
}//尾删
void SLPopBack(SL* ps)
{assert(ps && ps->size);ps->size--;
}//头删
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--;
}//查找
int SLFind(SL* ps, SLTDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到了return i;}}//未找到return -1;
}//指定位置之前插⼊
void SLInsert(SL* ps, int pos, SLTDataType x)
{assert(ps);//0<= pos < ps->sizeassert(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++;
}//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLTDataType x)
{assert(ps);//0=< pos <ps->sizeassert(pos >= 0 && pos < ps->size);//判断空间是否足够SLCheckCapacity(ps);//pos+1及后面的数据向后挪动一位for (int i = ps->size;i > pos + 1;i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos + 1] = x;ps->size++;
}//删除pos位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);//pos:[0，ps->size)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--;
}

测试文件test.c

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"void test01()
{SL s1;SLTnit(&s1);//具备了一个空的顺序表SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);/*SLPrint(&s1);*///SLPushBack(&s1, 5);//SLPushFront(&s1, 1);//SLPushFront(&s1, 2);//2 1//SLPushFront(&s1, 3);//3 2 1//SLPushFront(&s1, 4);//4 3 2 1//SLPushFront(NULL, 5);//SLPopBack(&s1);//SLPrint(&s1);//1 2 3//SLPopBack(&s1);//SLPrint(&s1);//1 2 //SLPopBack(&s1);//SLPrint(&s1);//1 //SLPopBack(&s1);//SLPrint(&s1);//SLPopBack(&s1);//头删/*SLPopFront(&s1);SLPrint(&s1);SLPopFront(&s1);SLPrint(&s1);SLPopFront(&s1);SLPrint(&s1);SLPopFront(&s1);SLPrint(&s1);*///测试查找/*int pos = SLFind(&s1, 2);SLInsertAfter(&s1, pos, 100);SLPrint(&s1);SLInsertAfter(&s1, pos, 200);SLPrint(&s1);SLInsertAfter(&s1, pos, 300);SLPrint(&s1);SLInsertAfter(&s1, pos, 400);SLPrint(&s1);*///if (pos < 0)//{//	printf("未找到！\n");//}//else {//	printf("找到了！\n");//}/*SLInsert(&s1, pos, 100);SLPrint(&s1);SLInsert(&s1, pos, 200);SLPrint(&s1);SLInsert(&s1, pos, 300);SLPrint(&s1);SLInsert(&s1, pos, 400);SLPrint(&s1);*//*SLErase(&s1, pos);SLPrint(&s1);*/SLDestroy(&s1);
}//初始化测试
int main()
{test01();return 0;
}

---

总结

以上就是顺序表的全部内容了，喜欢的靓仔靓女们不要忘记一键三连给予支持哦~