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删除,顺序表中数据为012)在头文件中加入对尾删法的定义//尾删 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); }最后通过调试可以发现顺序表被销毁总结上述完整代码链接顺序表完整代码仓
数据结构顺序表
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删除,顺序表中数据为012)在头文件中加入对尾删法的定义//尾删 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); }最后通过调试可以发现顺序表被销毁总结上述完整代码链接顺序表完整代码仓
