1、线性表
线性表(linearlist):是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表:顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2、顺序表
2.1、概念与结构
概念:顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采用数组存储。
结构:
2.2、分类
2.2.1静态顺序表
概念:使用定长数组存储元素
2.2.2动态顺序表
概念:可以按需申请空间，减少空间浪费
2.3、动态顺序表的实现
动态顺序表实现所用到的4种方法(尾插、头插、尾删、头删)
2.3.1尾插法
结构理解图：
在VIsual Studio 2022中进行代码编写
先定义一个头文件SeqList.h 在头文件内进行初始化、以及尾插的定义
//尾插 void SLPushBack(SL* ps, SLDatatype x);再创建一个源文件SeqList.c 在源文件内进行尾插的编写
//尾插 void SLPushBack(SL* ps, SLDatatype x) { assert(ps); //判断空间是否足够 SLCheckCapacity(ps); //空间足够的情况下 ps->arr[ps->size++] = x; }最后创建一个测试文件test.c 让编写的代码在test.c中实现编译
void test01() { SL s1; SLInit(&s1); SLPushBack(&s1, 1); SLPushBack(&s1, 2); SLPushBack(&s1, 3); SLPushBack(&s1, 4); SLPrint(&s1); }2.3.2头插法
结构理解图：
在头文件中加入对头插法的定义
//头插 void SLPushFront(SL* ps, SLDatatype x);在源文件SeqList.c内进行头插的编写
//头插 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++; }最后创建一个测试文件test.c 让编写的代码在test.c中实现编译
void test01() { SL s1; SLInit(&s1); SLPushFront(&s1, 1); SLPushFront(&s1, 2); SLPushFront(&s1, 3); SLPushFront(&s1, 4); SLPrint(&s1); }2.3.3尾删法
结构理解图:(将3删除,顺序表中数据为0，1，2)
在头文件中加入对尾删法的定义
//尾删 void SLPopBack(SL* ps);在源文件SeqList.c内进行尾删的编写
//尾删 void SLPopBack(SL* ps) { //在此处断言:ps不能为NULL ps->size为NULL(顺序表为空不能实现尾删) assert(ps && ps->size); ps->size--; }最后创建一个测试文件test.c 让编写的代码在test.c中实现编译
void test01() { SL s1; SLInit(&s1); SLPushBack(&s1, 1); SLPushBack(&s1, 2); SLPushBack(&s1, 3); SLPushBack(&s1, 4); SLPrint(&s1); SLPopBack(&s1); SLPrint(&s1); SLPopBack(&s1); SLPrint(&s1); SLPopBack(&s1); SLPrint(&s1); SLPopBack(&s1); SLPrint(&s1); }2.3.4头删法
结构理解图:
在头文件中加入对头删法的定义
//头删 void SLPopFront(SL* ps);在源文件SeqList.c内进行头删的编写
//头删 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--; }最后创建一个测试文件test.c 让编写的代码在test.c中实现编译
void test01() { SL s1; SLInit(&s1); SLPushBack(&s1, 1); SLPushBack(&s1, 2); SLPushBack(&s1, 3); SLPushBack(&s1, 4); SLPrint(&s1); SLPopFront(&s1); SLPrint(&s1); SLPopFront(&s1); SLPrint(&s1); SLPopFront(&s1); SLPrint(&s1); }2.3.5在指定位置之前插入数据
结构理解图:
在头文件中加入对指定位置插入的定义
//在指定位置之前插入数据 void SLInsert(SL* ps, int pos, SLDatatype x);在源文件SeqList.c内进行对指定位置插入的编写
//在指定位置之前插入 void SLInsert(SL* ps, int pos, SLDatatype x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); for (int i = ps->size; i > pos; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[pos] = x; ps->size++; }最后创建一个测试文件test.c 让编写的代码在test.c中实现编译
void test01() { SL s1; SLInit(&s1); SLPushBack(&s1, 1); SLPushBack(&s1, 2); SLPushBack(&s1, 3); SLPushBack(&s1, 4); SLPrint(&s1); SLInsert(&s1, 4, 100); SLPrint(&s1); }2.3.6删除指定位置数据
在头文件中加入对删除指定位置的定义
//删除插入位置数据 void SLErase(SL* ps, int pos);在源文件SeqList.c内进行删除指定位置数据的编写
//删除指定位置数据 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; }最后创建一个测试文件test.c 让编写的代码在test.c中实现编译
void test01() { SL s1; SLInit(&s1); SLPushBack(&s1, 1); SLPushBack(&s1, 2); SLPushBack(&s1, 3); SLPushBack(&s1, 4); SLPrint(&s1); SLErase(&s1, 3); SLPrint(&s1); }2.3.7查找数据
在头文件中加入对查找数据的定义
//查找数据 int SLFind(SL* ps, SLDatatype x);在源文件SeqList.c内进行查找数据的编写
//查找数据 int SLFind(SL* ps, SLDatatype x) { for(int i = 0; i < ps->size; i++ ) { if (ps->arr[i] = x) { return i; } } return -1; }最后创建一个测试文件test.c 让编写的代码在test.c中实现编译
void test01() { SL s1; SLInit(&s1); SLPushBack(&s1, 1); SLPushBack(&s1, 2); SLPushBack(&s1, 3); SLPushBack(&s1, 4); SLPrint(&s1); int find = SLFind(&s1, 2); if (find != -1) { printf("找到了 \n"); } else { printf("未找到 \n"); } SLDestroy(&s1); }2.3.8销毁顺序表
在头文件中加入对销毁数据表的定义
//销毁顺序表 void SLDestroy(SL* ps);在源文件SeqList.c内进行销毁数据表的编写
//销毁顺序表 void SLDestroy(SL* ps) { assert(ps); if (ps->arr) free(ps->arr); ps->arr = NULL; ps->size = ps->capacity = 0; }最后创建一个测试文件test.c 让编写的代码在test.c中实现编译
void test01() { SL s1; SLInit(&s1); SLPushBack(&s1, 1); SLPushBack(&s1, 2); SLPushBack(&s1, 3); SLPushBack(&s1, 4); SLPrint(&s1); SLDestroy(&s1); }最后通过调试可以发现顺序表被销毁
总结：上述完整代码链接
顺序表完整代码仓
