数据结构---顺序表

专栏：数据结构
个人主页：HaiFan.
专栏简介：从零开始，数据结构！！

前言

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

1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用动态开辟的数组存储。

接口实现

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

typedef int SLDataType;typedef struct SeqList
{SLDataType* val;int cnt;int capacity;
}SL;void SListInit(SL* ps);//对顺序表进行初始化
void SListDestory(SL* ps);//使用动态分配函数开辟的空间需要free掉
void SListPrint(SL* ps);//打印出顺序表中的内容void SListCheckCapacity(SL* ps);//检查顺序表中的空间是否够用void SListPushBack(SL* ps,SLDataType x);//顺序表尾部插入
void SListPopBack(SL* ps);//尾部删除void SListPushFront(SL* ps, SLDataType x);//头部插入
void SListPopFront(SL* ps);//头部删除int SListFind(SL* ps,SLDataType x);//查找元素void SListInsert(SL* ps, int pos, SLDataType x);//在任意位置插入元素void SListErase(SL* ps, int pos);//删除任意位置的元素

要说明的是，这里为什么要把int重命名成SLDataType，因为元素的类型是可以变化的，想改变元素的类型，只需要在typedef这里改一下即可，就不需要在更改其他的数据了。

cnt是用来记录顺序表中的元素有多少个

capacity是用来检查顺序表中的空间是否够用

SListInit初始化和SListDestory销毁

顺序表初始化要把结构体中的val开辟一点空间。

void SListInit(SL* ps)
{ps->val = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps->val == NULL){perror("malloc fail");exit(-1);}ps->capacity = 4;ps->cnt = 0;
}

---

在程序结束的时候，要把动态开辟的空间给销毁，用了多少空间，还给系统多少空间。

void SListDestory(SL* ps)
{free(ps->val);ps->val = NULL;ps->capacity = ps->cnt = 0;
}

SListPrint打印表中的元素

打印表中的元素，要实现这个只需要一个for循环就能解决。

void SListPrint(SL* ps)
{for (int i = 0; i < ps->cnt; i++){cout << ps->val[i] << ' ';}puts("");
}

cnt是用来记录表中的元素个数的，

SListCheckCapacity检查表中空间

在进行增加元素的时候，要先对表中的空间进行一个检查，判断空间的大小是否足够在容纳一个元素。

void SListCheckCapacity(SL* ps)
{if (ps->capacity == ps->cnt){SLDataType* tmp = (SLDataType*)realloc(ps->val, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->val = tmp;ps->capacity *= 2;}
}

如果val是NULL，先通过malloc开辟一段空间，如果val不是NULL，就让cnt和capacity进行是否相等判断，如果相等，就使用realloc函数对val进行扩容，扩容的时候，用一个临时的指针接收，然后在把临时的指针赋值给val。

当然，空间扩容了，capacity也别忘记扩大了。

SListPushBack尾插和SListPopBack尾删

尾插很简单，cnt不但可以用来记录元素的个数的，也可以当作要插入的元素的下标。

元素值：1 2 3

下标： 0 1 2

cnt的值：3

此时在下标为cnt(3)的地方插入一个值即可。

void SListPushBack(SL* ps, SLDataType x)
{SListCheckCapacity(ps);ps->val[ps->cnt] = x;ps->cnt++;
}

当然，在插入元素之前，要先检查表的空间。

---

删除元素也很简单，只需要cnt–即可。

void SListPopBack(SL* ps)
{assert(ps->cnt);ps->cnt--;
}

这里要添加一个断言，避免没有元素了还执行删除操作。

---

SListPushFront头插和SListPopFront头删

头插的话，需要先把每个元素都往后移动一位，把第一个元素的位置给腾出来，才能把x给插入。

void SListPushFront(SL* ps, SLDataType x)
{SListCheckCapacity(ps);for (int i = ps->cnt; i > 0; i--){ps->val[i] = ps->val[i - 1];}ps->val[0] = x;ps->cnt++;
}

当然，要先检查表中空间是否够用

---

头删的话，只需要把第一个元素等于第二个元素就行，即：下一个元素把上一个元素给覆盖了。

void SListPopFront(SL* ps)
{assert(ps->cnt);for (int i = 0; i < ps->cnt - 1; i++){ps->val[i] = ps->val[i + 1];}ps->cnt--;
}

SListFind查找元素

查找元素的话，只需要遍历一遍表中元素即可，找到相同的值，返回下标

int SListFind(SL* ps, SLDataType x)
{assert(ps->cnt);for (int i = 0; i < ps->cnt; i++){if (ps->val[i] == x){return i;break;}}return -1;
}

SListInset插入元素

插入元素分为两种情况，当要插入的位置等于cnt时，就是尾插。

否则，就要让pos之后的元素依次往后移动一位，把pos位置空出来，在进行插入操作。

void SListInsert(SL* ps, int pos, SLDataType x)
{SListCheckCapacity(ps);if (pos > ps->cnt){return;}else if (pos == ps->cnt){SListPushBack(ps, x);}else{for (int i = ps->cnt; i > pos; i--){ps->val[i] = ps->val[i - 1];}ps->val[pos] = x;ps->cnt++;}}

SListErase删除元素

删除元素也分为两种情况，当pos等于cnt-1的时候，就是尾删。

否则，就要让pos后的元素，依次往前移动一位，把pos给覆盖即可。

void SListErase(SL* ps, int pos)
{
assert(ps);

if (pos == ps->cnt - 1)
{SListPopBack(ps);
}
else if (pos > ps->cnt)
{exit(-1);
}
else
{for (int i = pos; i < ps->cnt - 1; i++){ps->val[i] = ps->val[i + 1];}ps->cnt--;
}

完整代码

.h文件

#pragma once#include <iostream>
#include <stdlib.h>
#include <assert.h>using namespace std;typedef int SLDataType;typedef struct SeqList
{SLDataType* val;int cnt;int capacity;
}SL;void SListInit(SL* ps);//对顺序表进行初始化
void SListDestory(SL* ps);//使用动态分配函数开辟的空间需要free掉
void SListPrint(SL* ps);//打印出顺序表中的内容void SListCheckCapacity(SL* ps);//检查顺序表中的空间是否够用void SListPushBack(SL* ps,SLDataType x);//顺序表尾部插入
void SListPopBack(SL* ps);//尾部删除void SListPushFront(SL* ps, SLDataType x);//头部插入
void SListPopFront(SL* ps);//头部删除int SListFind(SL* ps,SLDataType x);//查找元素void SListInsert(SL* ps, int pos, SLDataType x);//在任意位置插入元素void SListErase(SL* ps, int pos);//删除任意位置的元素

.cpp文件

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"void SListPrint(SL* ps)
{for (int i = 0; i < ps->cnt; i++){cout << ps->val[i] << ' ';}puts("");
}void SListInit(SL* ps)
{ps->val = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps->val == NULL){perror("malloc fail");exit(-1);}ps->capacity = 4;ps->cnt = 0;
}void SListDestory(SL* ps)
{free(ps->val);ps->val = NULL;ps->capacity = ps->cnt = 0;
}void SListCheckCapacity(SL* ps)
{if (ps->capacity == ps->cnt){SLDataType* tmp = (SLDataType*)realloc(ps->val, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->val = tmp;ps->capacity *= 2;}
}void SListPushBack(SL* ps, SLDataType x)
{SListCheckCapacity(ps);ps->val[ps->cnt] = x;ps->cnt++;
}void SListPopBack(SL* ps)
{assert(ps->cnt);ps->cnt--;
}void SListPushFront(SL* ps, SLDataType x)
{SListCheckCapacity(ps);for (int i = ps->cnt; i > 0; i--){ps->val[i] = ps->val[i - 1];}ps->val[0] = x;ps->cnt++;
}void SListPopFront(SL* ps)
{assert(ps->cnt);for (int i = 0; i < ps->cnt - 1; i++){ps->val[i] = ps->val[i + 1];}ps->cnt--;
}int SListFind(SL* ps, SLDataType x)
{assert(ps->cnt);for (int i = 0; i < ps->cnt; i++){if (ps->val[i] == x){return i;break;}}return -1;
}void SListInsert(SL* ps, int pos, SLDataType x)
{SListCheckCapacity(ps);if (pos > ps->cnt){return;}else if (pos == ps->cnt){SListPushBack(ps, x);}else{for (int i = ps->cnt; i > pos; i--){ps->val[i] = ps->val[i - 1];}ps->val[pos] = x;ps->cnt++;}}void SListErase(SL* ps, int pos)
{assert(ps);if (pos == ps->cnt - 1){SListPopBack(ps);}else if (pos > ps->cnt){exit(-1);}else{for (int i = pos; i < ps->cnt - 1; i++){ps->val[i] = ps->val[i + 1];}ps->cnt--;}}

test.cpp文件

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"void TestSeqList()
{SL s;SListInit(&s);SListPushBack(&s, 1);SListPushBack(&s, 2);SListPushBack(&s, 3);SListPushBack(&s, 4);SListPushBack(&s, 5);SListPrint(&s);SListPopBack(&s);SListPrint(&s);SListPushFront(&s, -1);SListPushFront(&s, -2);SListPushFront(&s, -3);SListPushFront(&s, -4);SListPushFront(&s, -5);SListPrint(&s);SListPopFront(&s);SListPrint(&s);int ret  = SListFind(&s, 4);cout << ret << endl;SListInsert(&s, 3, 100000);SListPrint(&s);SListErase(&s, 3);SListPrint(&s);SListDestory(&s);
}int main()
{TestSeqList();return 0;
}