数据结构：顺序表（动态顺序表）

专栏说明：本专栏用于数据结构复习，文章中出现的代码由C语言实现，在专栏中会涉及到部分OJ题目，如对你学习有所帮助，可以点赞鼓励一下博主喔💓

---

• 博客主页：Duck Bro 博客主页
• 系列专栏：数据结构专栏
• 关注博主，后期持续更新系列文章
• 如果有错误感谢请大家批评指出，及时修改
• 感谢大家点赞👍收藏⭐评论✍

---

数据结构：顺序表（动态顺序表）

---

1. 概念与结构

1.1 概念

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

1.2 结构

静态顺序表：使用定长数组存储元素。

#define N 7
typedef int DataType;
typedef struct SeqList
{DataType a[N];int size;int capacity;
}SL;

动态顺序表：使用动态开辟的数组存储。

typedef int DataType;
typedef struct SeqList
{DataType* a;int size;int capacity;
}SL;

---

2. 接口实现

2.1 动态顺序表结构

//顺序表动态存储
typedef int DataType;
typedef struct SeqList
{DataType* a;	//指点动态开辟数组int size;		//有效数据个数int capacity;	//容量空间大小
}SL;

2.2 顺序表初始化

void SLInit(SL* pc)
{//断言assert(pc);//pc->a = NULL;pc->a = (DataType*)malloc(sizeof(DataType) * 4);//判断是否为空if (pc->a == NULL){//报错提示perror("SLInit faild");//退出程序exit(-1);}//顺序表内的数据个数pc->size = 0;//顺序表内的容量pc->capacity = 4;
}

2.3 顺序表销毁

void SLDestroy(SL* pc)
{//断言assert(pc);//释放内存free(pc->a);//将指针置为空pc->a = NULL;//设置数据个数和容量为0个pc->size = 0;pc->capacity = 0;
}

2.4 检查空间、扩容

void SLCheckCapacity(SL* pc)
{//断言assert(pc);//如果size==capacity,则进行二倍扩容if (pc->size == pc->capacity){DataType* temp = (DataType*)realloc(pc->a, pc->capacity * sizeof(DataType) * 2);//进行判断是否开辟成功if (temp == NULL){perror("SLCheckCapacity faild");exit(-1);}pc->a = temp;pc->capacity *= 2;}
}

2.5 顺序表尾插

void SLPushBack(SL* pc, DataType x)
{assert(pc);/*assert(pc);SLCheckCapacity(pc);pc->a[pc->size] = x;pc->size++;*/SLInsert(pc, pc->size, x);
}

2.6 顺序表尾删

void SLPopBack(SL* pc)
{assert(pc);/*assert(pc);assert(pc->size);pc->size--;*/SLErase(pc, pc->size - 1);
}

2.7 顺序表头插

void SLPushFront(SL* pc, DataType x)
{assert(pc);断言//assert(pc);检查空间是否足够//SLCheckCapacity(pc);end为顺序表中最后一个数据的下标//int end = pc->size - 1;将所有数据进行后移//while (end >= 0)//{//	pc->a[end + 1] = pc->a[end];//	--end;//}//pc->a[0] = x;//pc->size++;SLInsert(pc, 0, x);}

2.8 顺序表头删

void SLPopFront(SL* pc)
{assert(pc);/*assert(pc->size > 0);int begin = 1;while (begin < pc->size){pc->a[begin - 1] = pc->a[begin];begin++;}pc->size--;*/SLErase(pc, 0);
}

2.9 顺序表查找

int SLFind(SL* pc, DataType x)
{assert(pc);for (int i = 0; i < pc->size; i++){if (x == pc->a[i]){return i;}}return -1;
}

2.10 在pos位置插入x

void SLInsert(SL* pc, int pos, DataType x)
{assert(pos >= 0 && pos <= pc->size);SLCheckCapacity(pc);int end = pc->size - 1;while (end >= pos){pc->a[end + 1] = pc->a[end];end--;}pc->a[pos] = x;pc->size++;
}

2.11 删除pos位置值

void SLErase(SL* pc, int pos)
{assert(pc);assert(pos>=0&&pos<pc->size);int begin = pos + 1;while (begin < pc->size){pc->a[begin-1] = pc->a[begin];begin++;}pc->size--;
}

2.12 修改pos位置值

void SLModify(SL* pc, int pos, DataType x)
{assert(pc);assert(pos <= 0 && pos < pc->size);pc->a[pos] = x;}

2.13 打印顺序表

void SLPrintf(SL* pc)
{//断言assert(pc);//遍历int i = 0;for (i = 0; i < pc->size; i++){printf("%d ", pc->a[i]);}printf("\n");
}

3. 详细代码页

3.1 SeqList.h

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DataType;
typedef struct SeqList
{DataType* a;int size;int capacity;
}SL;//顺序表初始化
void SLInit(SL* pc);
//顺序表销毁
void SLDestroy(SL* pc);
//容量检查,并进行扩容
void SLCheckCapacity(SL* pc);
//打印顺序表中的数据 遍历顺序表
void SLPrintf(SL* pc);//顺序表头插
void SLPushFront(SL* pc, DataType x);
//顺序表尾删
void SLPopBack(SL* pc);
//顺序表尾插
void SLPushBack(SL* pc, DataType x);
//顺序表头删
void SLPopFront(SL* pc);//查找位置
int SLFind(SL* pc ,DataType x);
//顺序表pos位置前插入X
void SLInsert(SL* pc, int pos,DataType x);
//顺序表删除pos位置值
void SLErase(SL* pc,int pos);
//修改pos位置值
void SLModify(SL* pc, int pos,DataType x);

3.2 SeqList.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"void SLInit(SL* pc)
{//断言assert(pc);//pc->a = NULL;pc->a = (DataType*)malloc(sizeof(DataType) * 4);//判断是否为空if (pc->a == NULL){//报错提示perror("SLInit faild");//退出程序exit(-1);}//顺序表内的数据个数pc->size = 0;//顺序表内的容量pc->capacity = 4;
}void SLDestroy(SL* pc)
{//断言assert(pc);//释放内存free(pc->a);//将指针置为空pc->a = NULL;//设置数据个数和容量为0个pc->size = 0;pc->capacity = 0;}void SLCheckCapacity(SL* pc)
{//断言assert(pc);//如果size==capacity,则进行二倍扩容if (pc->size == pc->capacity){DataType* temp = (DataType*)realloc(pc->a, pc->capacity * sizeof(DataType) * 2);//进行判断是否开辟成功if (temp == NULL){perror("SLCheckCapacity faild");exit(-1);}pc->a = temp;pc->capacity *= 2;}
}void SLPrintf(SL* pc)
{//断言assert(pc);//遍历int i = 0;for (i = 0; i < pc->size; i++){printf("%d ", pc->a[i]);}printf("\n");
}void SLPushFront(SL* pc, DataType x)
{assert(pc);断言//assert(pc);检查空间是否足够//SLCheckCapacity(pc);end为顺序表中最后一个数据的下标//int end = pc->size - 1;将所有数据进行后移//while (end >= 0)//{//	pc->a[end + 1] = pc->a[end];//	--end;//}//pc->a[0] = x;//pc->size++;SLInsert(pc, 0, x);}void SLPopBack(SL* pc)
{assert(pc);/*assert(pc);assert(pc->size);pc->size--;*/SLErase(pc, pc->size - 1);
}void SLPushBack(SL* pc, DataType x)
{assert(pc);/*assert(pc);SLCheckCapacity(pc);pc->a[pc->size] = x;pc->size++;*/SLInsert(pc, pc->size, x);
}void SLPopFront(SL* pc)
{assert(pc);/*assert(pc->size > 0);int begin = 1;while (begin < pc->size){pc->a[begin - 1] = pc->a[begin];begin++;}pc->size--;*/SLErase(pc, 0);
}void SLInsert(SL* pc, int pos, DataType x)
{assert(pos >= 0 && pos <= pc->size);SLCheckCapacity(pc);int end = pc->size - 1;while (end >= pos){pc->a[end + 1] = pc->a[end];end--;}pc->a[pos] = x;pc->size++;
}void SLErase(SL* pc, int pos)
{assert(pc);assert(pos>=0&&pos<pc->size);int begin = pos + 1;while (begin < pc->size){pc->a[begin-1] = pc->a[begin];begin++;}pc->size--;
}int SLFind(SL* pc, DataType x)
{assert(pc);for (int i = 0; i < pc->size; i++){if (x == pc->a[i]){return i;}}return -1;
}void SLModify(SL* pc, int pos, DataType x)
{assert(pc);assert(pos <= 0 && pos < pc->size);pc->a[pos] = x;}

3.3 main.c

#include "SeqList.h"
void test1()
{//测试创建顺序表初始化 销毁SL s;SLInit(&s);SLDestroy(&s);
}void test2()
{//测试顺序表尾插插SL s1;SLInit(&s1);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);//SLPushFront(&s1, 4);//SLPushFront(&s1, 4);//SLPopBack(&s1);//SLPopBack(&s1);SLPopBack(&s1);SLPopBack(&s1);SLPushBack(&s1, 67);SLPushBack(&s1, 67);SLPushBack(&s1, 67);SLPrintf(&s1);SLDestroy(&s1);
}void test3()
{//测试顺序表尾插插SL s1;SLInit(&s1);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPrintf(&s1);//SLPushFront(&s1, 4);SLPushFront(&s1, 66);SLPrintf(&s1);SLDestroy(&s1);
}void test4()
{//测试顺序表尾插插SL s1;SLInit(&s1);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);SLPushBack(&s1, 5);//SLInsert(&s1, 2, 7);int x = 0;scanf("%d", &x);int pos = SLFind(&s1, x);if (pos != -1){SLInsert(&s1, pos, 50);}SLPrintf(&s1);SLDestroy(&s1);
}
void test5()
{//测试顺序表尾插插SL s1;SLInit(&s1);SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushBack(&s1, 5);//SLInsert(&s1, 2, 7);SLPopBack(&s1);SLPopFront(&s1);SLPrintf(&s1);SLDestroy(&s1);
}
int main()
{//test1();//test2();//test3();//test4();test5();return 0;
}

---