前言
- 为什么有顺序表？由于数组定义之后不能扩充，我们需要一种更方便的结构来装载数据，顺序表诞生了。
- 顺序表是线性表的一种，线性表的存储都是形成一条线的，顺序表不仅仅在逻辑上是用一条线链接，在内存中也是连续的一块空间，因此可以进行下标随机访问。
- 顺序表不同于数组，顺序表在空间不够的情况下可以选择进行扩充。
- 顺序表不同于数组，顺序表开辟在堆空间中，不用担心栈空间不够用。
- 相对麻烦的就是，先对顺序表进行操作必须要自己实现增删改查等函数。
- 如果学会了顺序表可以试着自主完成通讯录小程序⭐
PS:需要源码直接通过目录跳转到最后
顺序表主体结构
默认大小与扩容大小还有类型都可以是任意大小或类型
#define SLDataType int #define DEFAULT_SZ 5 //默认大小 #define DEFAULT_INC 3 //默认扩容大小 typedef struct SeqList { SLDataType* data; int sz; int capable; }SeqList;
用define定义数据可以方便修改
void SLInit(SeqList* SL); 顺序表初始化
void SLprint(SeqList* SL); 打印顺序表
void SLPushFront(SeqList* SL, SLDataType x); 顺序表投插
void SLPushBack(SeqList* SL, SLDataType x); 顺序表尾插
void SLPopFront(SeqList* SL); 顺序表头删
void SLPopBack(SeqList* SL); 顺序表尾删
void SLInsert(SeqList* SL, int pos, SLDataType x); ~指定位置插入
void SLEarse(SeqList* SL, int pos); 指定位置删除
int SLFind(SeqList* SL, SLDataType x); 查找指定数据下标
void SLModify(SeqList* SL, int pos, SLDataType x); 修改指定位置数据
void SLDestroy(SeqList* SL); 清楚数据包
为了代码方便阅读，讲顺序表操作函数全部放在Seqlist.c文件中，将头文件放在SeqList.h，测试文件test.c 🌞
顺序表操作函数实现
实现顺序：
为了方便调试，建议每写完1-2个函数就进行测试，初始化之后，首先实现print函数可以方便我们进行调试，建议按照顺序，插入-》打印-》查找-》删除-》销毁顺序表函数。
顺序表的初始化：
void SLInit(SeqList* SL) { assert(SL); //assert防止传进来的指针为空，进行断言 SL->capable = DEFAULT_SZ; SL->sz = 0; int* ptr = malloc(sizeof(int) * DEFAULT_SZ); //为顺序表开辟一段空间 if (ptr == NULL) //预防开辟失败进行判断 { perror("malloc:"); } SL->data = ptr; printf("初始化成功\n"); }
必须先进性初始化，给顺序表开辟一个堆空间，并对其默认长度与默认最大长度进行初始化。
顺序表插入函数：
头插
头插从第一个位置插入，其余函数按顺序向后移动一格，
- 既然有插入就一定会有空间不够用的问题，这里用到检查空间是否够用的一个函数
void CheckSL(SeqList* SL) { assert(SL); //assert防止传进来的指针为空，进行断言 if (SL->sz == SL->capable) //如果当前大小等于当前最大大小那么进行扩容 { int* ptr = NULL; ptr = (int*)realloc(SL->data, sizeof(int) * (SL->capable + DEFAULT_INC)); if (ptr == NULL) { perror("check:realloc:"); } SL->data = ptr; SL->capable += DEFAULT_INC; printf("扩容成功\n"); } }
头插函数
- 将所有数据向后移动，注意要从后面开始移动，不然数据会被覆盖掉
void SLPushFront(SeqList* SL, SLDataType x) { assert(SL); //assert防止传进来的指针为空，进行断言 CheckSL(SL); int end = SL->sz - 1; while (end >= 0) //将所有数据向后移动，注意要从后面开始移动，不然数据会被覆盖掉 { SL->data[end + 1] = SL->data[end]; end--; } SL->data[0] = x; //所有数据都向后移动之后进行头插 SL->sz++; //当前大小+1 }
尾插
从最后进行插入数据
- 尾插也会用到检查空间是否够用的函数，这里不重复了
void SLPushBack(SeqList* SL,SLDataType x) { assert(SL); //assert防止传进来的指针为空，进行断言 CheckSL(SL); //判断空间是否够用，够用直接将数据放在尾部即可 SL->data[SL->sz] = x; SL->sz++; //插入之后当前大小+1 }
指定位置插入
- 只要有插入，就要检查空间是否够用
void SLInsert(SeqList* SL,int pos,SLDataType x) { assert(SL); //assert防止传进来的指针为空，进行断言 assert(pos >= 0 && pos < SL->sz); CheckSL(SL); int end = SL->sz - 1; while (end >=pos-1) //讲数据从后向后移动，避免被覆盖 { SL->data[end + 1] = SL->data[end]; end--; } SL->data[pos-1] = x; SL->sz++; //插入之后当前大小+1 }
顺序表打印函数
写完插入立马写打印，方便进行调试
void SLprint(SeqList* SL) { assert(SL); //assert防止传进来的指针为空，进行断言 for (int i = 0; i < SL->sz; i++) { printf("%d ", SL->data[i]); } printf("\n"); }
查找顺序表数据
int SLFind(SeqList* SL, SLDataType x) { assert(SL); //assert防止传进来的指针为空，进行断言 for (int i = 0; i < SL->sz; i++) { if (SL->data[i] == x) { return i; } } return -1; }
顺序表删除函数
头删
从头部删除数据，删除之后后面的数据依次向前移动一位，要从前往后移动，不然会被覆盖（同头插）
void SLPopFront(SeqList* SL) { assert(SL); //assert防止传进来的指针为空，进行断言 if (SL->sz <= 0) { printf("表为空，无需删除"); return; } int start = 0; while (start < SL->sz - 1) { SL->data[start] = SL->data[start + 1]; start++; } SL->sz--; }
尾删
void SLPopBack(SeqList* SL) { assert(SL); //assert防止传进来的指针为空，进行断言 if (SL->sz <= 0) { printf("表为空，无需删除"); return; } SL->sz--; }
指定位置删除
后面的数据依次向前移动
void SLEarse(SeqList* SL,int pos) { assert(SL); //assert防止传进来的指针为空，进行断言 assert(pos >= 0 && pos < SL->sz); int start = pos-1; while (start < SL->sz - 1) { SL->data[start] = SL->data[start + 1]; start++; } SL->sz--; }
修改顺序表
void SLModify(SeqList* SL, int pos, SLDataType x) { assert(SL); //assert防止传进来的指针为空，进行断言 assert(pos >= 0 && pos < SL->sz); SL->data[pos - 1] = x; }
销毁顺序表
void SLDestroy(SeqList* SL) { assert(SL); //assert防止传进来的指针为空，进行断言 free(SL->data);//释放堆空间数据 SL->data = NULL;//将指针置空预防野指针 SL->sz = 0; SL->capable = 0; }
文件分类
🌞🌞为了使代码更有阅读性，我们不建议把所有函数写在一个文件里，所以这里分成三个文件，模块化管理
test.c
测试文件
#include "SeqList.h" void test(SeqList* SL) { SLPushBack(SL, 10); SLPushBack(SL, 11); SLPushBack(SL, 11); SLPushBack(SL, 11); SLPushBack(SL, 11); SLPushBack(SL, 11); SLPushBack(SL, 11); SLPushBack(SL, 11); SLPushBack(SL, 19); SLprint(SL); SLPushFront(SL, 12); SLPushFront(SL, 13); SLPushFront(SL, 14); SLprint(SL); SLPopBack(SL); SLprint(SL); SLPopFront(SL); SLprint(SL); SLInsert(SL, 5, 99); SLprint(SL); SLModify(SL, 5, 22); SLprint(SL); //SLEarse(SL, 5); //SLprint(SL); SLFind(SL,5); SLDestroy(SL); } int main() { SeqList SL; SLInit(&SL); test(&SL); }
SeqList.c
i将所有函数封装在此文件下
#include "SeqList.h" void SLInit(SeqList* SL) { assert(SL); SL->capable = DEFAULT_SZ; SL->sz = 0; int* ptr = malloc(sizeof(int) * DEFAULT_SZ); if (ptr == NULL) { perror("malloc:"); } SL->data = ptr; printf("初始化成功\n"); } void SLprint(SeqList* SL) { assert(SL); for (int i = 0; i < SL->sz; i++) { printf("%d ", SL->data[i]); } printf("\n"); } void CheckSL(SeqList* SL) { assert(SL); if (SL->sz == SL->capable) { int* ptr = NULL; ptr = (int*)realloc(SL->data, sizeof(int) * (SL->capable + DEFAULT_INC)); if (ptr == NULL) { perror("check:realloc:"); } SL->data = ptr; SL->capable += DEFAULT_INC; printf("扩容成功\n"); } } void SLPushBack(SeqList* SL,SLDataType x) { assert(SL); CheckSL(SL); SL->data[SL->sz] = x; SL->sz++; } void SLPushFront(SeqList* SL, SLDataType x) { assert(SL); CheckSL(SL); int end = SL->sz - 1; while (end >= 0) { SL->data[end + 1] = SL->data[end]; end--; } SL->data[0] = x; SL->sz++; } void SLPopBack(SeqList* SL) { assert(SL); if (SL->sz <= 0) { printf("表为空，无需删除"); return; } SL->sz--; } void SLPopFront(SeqList* SL) { assert(SL); if (SL->sz <= 0) { printf("表为空，无需删除"); return; } int start = 0; while (start < SL->sz - 1) { SL->data[start] = SL->data[start + 1]; start++; } SL->sz--; } void SLInsert(SeqList* SL,int pos,SLDataType x) { assert(SL); assert(pos >= 0 && pos < SL->sz); int end = SL->sz - 1; while (end >=pos-1) { SL->data[end + 1] = SL->data[end]; end--; } SL->data[pos-1] = x; SL->sz++; } void SLEarse(SeqList* SL,int pos) { assert(SL); assert(pos >= 0 && pos < SL->sz); int start = pos-1; while (start < SL->sz - 1) { SL->data[start] = SL->data[start + 1]; start++; } SL->sz--; } void SLDestroy(SeqList* SL) { assert(SL); free(SL->data); SL->data = NULL; SL->sz = 0; SL->capable = 0; } int SLFind(SeqList* SL, SLDataType x) { assert(SL); for (int i = 0; i < SL->sz; i++) { if (SL->data[i] == x) { return i; } } return -1; } void SLModify(SeqList* SL, int pos, SLDataType x) { assert(SL); assert(pos >= 0 && pos < SL->sz); SL->data[pos - 1] = x; }
SeqList.h
将主程序所需要的函数全部在头文件中声明，增加代码阅读性
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <assert.h> #include <stdlib.h> #define SLDataType int #define DEFAULT_SZ 5 #define DEFAULT_INC 3 typedef struct SeqList { SLDataType* data; int sz; int capable; }SeqList; void SLInit(SeqList* SL); void SLprint(SeqList* SL); void SLPushFront(SeqList* SL, SLDataType x); void SLPushBack(SeqList* SL, SLDataType x); void SLPopFront(SeqList* SL); void SLPopBack(SeqList* SL); void SLInsert(SeqList* SL, int pos, SLDataType x); void SLEarse(SeqList* SL, int pos); int SLFind(SeqList* SL, SLDataType x); void SLModify(SeqList* SL, int pos, SLDataType x); void SLDestroy(SeqList* SL);
撒花
这就是实现顺序表的全部内容了，创作不易，还请各位小伙伴多多点赞👍关注收藏⭐，以后也会更新各种关于c语言，数据结构的博客，撒花！
