数据结构--顺序表

目录一、顺序表的定义1、顺序表的概念及结构1.1线性表2、顺序表概念和分类2.1 静态顺序表2.2 动态顺序表二、动态顺序表的实现1、创建文件2、顺序表的实现2.1、创建顺序表2.2、实现接口里面的功能2.2.1、SLInit(SL* ps) 接口的实现细节2.2.2、SLDestroy(SL* ps)接口的实现细节2.2.3、SLPrint(SL* ps) 接口的实现细节2.2.4、SLCheckCapacity(SL* ps) 接口的实现细节2.2.5、SLInsert(SL* ps, int pos, SLDataType num) 接口的实现细节2.2.6、SLErase(SL* ps, int pos) 接口的实现细节2.2.7、SLFind(SL* ps, SLDataType x) 接口的实现细节三、测试和总结1、测试1.1、添加数据1.2、删除数据1.3、查找数据2、总结一、顺序表的定义1、顺序表的概念及结构1.1线性表线性表linear list是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结 构常见的线性表顺序表、链表、栈、队列、字符串等。线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物 理上存储时通常以数组和链式结构的形式存储。2、顺序表概念和分类顺序表的概念顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组 上完成数据的增删查改。2.1 静态顺序表概念使用定长数组存储元素。静态顺序表缺陷空间给少了不够用给多了就会造成空间浪费的现象。静态顺序表代码如下//静态顺序表代码 //这里将存储的类型变为 SLDataType 是为了方便以后修改使用不同的数据类型 typedef int SLDataType; #define N 100;//这里将数组存储的数据容量设置为 N 是为了方便以后修改容量 typedef struct SeqList { SLDatatype arr[N]; int size;//size是有效数据的个数 }SL;2.2 动态顺序表概念使用动态开辟的数组存储。接下来我们以动态顺序表代码为例来进行讲解。二、动态顺序表的实现1、创建文件按照图中的样式来创建文件解释一下创建这三个文件的作用 1、头文件SeqList.h是用来声明接口函数定义顺序表将几个公共用到的库函数集合起来 2、源文件SeqList.c是用来完善接口里面的细节 3、源文件test.c是用于接口的测试工作 即具体的使用场景2、顺序表的实现2.1、创建顺序表首先在SeqList.h里定义顺序表的结构和功能#pragma once #includestdio.h #includestdlib.h #includeassert.h typedef int SLDataType; typedef struct Seqlist { SLDataType* a; int size; //有效数据个数 int capacity; //空间容量 }SL; //增删查改 void SLInit(SL* ps);//初始化顺表表里面的数据 void SLDestroy(SL* ps);//销毁顺序表 void SLPrint(SL* ps);//打印存储在顺序表里面的数据 void SLCheckCapacity(SL* ps);//检查当前容量是否满了满了的话就进行扩容 void SLInsert(SL* ps, int pos, SLDataType num);//往顺寻表里面某一位置插入数据 void SLErase(SL* ps, int pos);//删除顺序表里面某一位置的数据 int SLFind(SL* ps, SLDataType x);//查找顺寻表里面某一个数据的下标2.2、实现接口里面的功能2.2.1、SLInit(SL* ps)接口的实现细节//初始化里面的数据 void SLInit(SL* ps) { ps-a NULL; // 刚初始化时不分配内存指向空 ps-size 0; // 有效数据个数为0 ps-capacity 0; // 容量为0 }2.2.2、SLDestroy(SL* ps)接口的实现细节//销毁顺序表 void SLDestroy(SL* ps) { //判断当前传的值是否为空指针 assert(ps); //释放申请的空间 free(ps-a); //将指针初始化为空指针防止变为“野指针”。 ps-a NULL; ps-capacity ps-size 0; }2.2.3、SLPrint(SL* ps)接口的实现细节//打印存储在顺序表里面的数据 void SLPrint(SL* ps) { for (int i 0; i ps-size; i) { printf(%d , ps-a[i]); } printf(\n); }2.2.4、SLCheckCapacity(SL* ps)接口的实现细节//检查当前容量是否满了满了的话就进行扩容 void SLCheckCapacity(SL* ps) { if (ps-size ps-capacity) { //sizeof(SLDataType) * ps-capacity * 2 意思是将目前的容量扩大2倍 //sizeof(SLDataType) 判断当前类型是多少字节 //ps-capacity 当前的容量是多少 SLDataType* tmp (SLDataType*)realloc(ps-a, sizeof(SLDataType) * ps-capacity * 2); if (tmp NULL) { perror(realloc); return; } //指向新开辟的内存空间 ps-a tmp; //因为改变的内存的值不会影响到这里容量的值所以需要我们手动改为原来的2倍 ps-capacity * 2; } }2.2.5、SLInsert(SL* ps, int pos, SLDataType num)接口的实现细节//往顺寻表里面某一位置插入数据 void SLInsert(SL* ps, int pos, SLDataType num) { //判断传来的数据是否合理 assert(ps); assert(pos 0 pos ps-size); //检查当前的容量是否足够 SLCheckCapacity(ps); //插入数据将具体的值放入对应的下标那里。 //插入数据逻辑是需要将 插入数据 位置后面的数据往后面移动那我们只需要定位到 //顺序表最后一个位置就好了(指的是ps-size当前的长度)然后从后面一个个进行移动所以检查容量的这个过程。 //必须在移动数据这个操作前进行。 for (int i ps-size; i pos; i--) { ps-a[i] ps-a[i - 1]; } //移动完毕之后将这个下标对应的值赋值给要插入的数据的值 ps-a[pos] num; //有效数据 1; (这里面的有效数据指当前有多少值放在这个顺序表里面) ps-size; }2.2.6、SLErase(SL* ps, int pos)接口的实现细节//删除顺序表里面某一位置的数据 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-a[i] ps-a[i 1]; } //之后有效数据 -1(这里面的有效数据指当前有多少值放在这个顺序表里面) ps-size--; }2.2.7、SLFind(SL* ps, SLDataType x)接口的实现细节//查找顺寻表里面某一个数据的下标 int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i 0; i ps-size; i) { if (ps-a[i] x) { //找到了就返回它的下标 return i; } } //没找到就返回 -1 return -1; }三、测试和总结1、测试1.1、添加数据测试代码#includeseqList.h int main() { //创建变量 SL s; //先初始化数据 SLInit(s); //警告插入数据的时候必须要连续存储不能跳着插入不然引发报错 //因为顺序表要求数据从下标0开始连续存储所以插入位置只能是 [0, size] 闭区间 //不能跳着插入这就是为什么在 SLInsert 函数中必须加 assert(pos 0 pos ps-size) //来防止这种错误操作。 SLInsert(s, 0, 1); SLInsert(s, 1, 2); SLInsert(s, 2, 3); SLInsert(s, 3, 4); SLInsert(s, 4, 5); SLInsert(s, 5, 6); SLPrint(s); return 0; }测试结果1.2、删除数据测试代码#includeseqList.h int main() { //创建变量 SL s; //先初始化数据 SLInit(s); //添加数据 SLInsert(s, 0, 1); SLInsert(s, 1, 2); SLInsert(s, 2, 3); SLInsert(s, 3, 4); SLInsert(s, 4, 5); SLInsert(s, 5, 6); SLPrint(s); //删除数据 SLErase(s, 4); SLErase(s, 0); SLPrint(s); return 0; }测试结果1.3、查找数据测试代码#includeseqList.h int main() { //创建变量 SL s; //先初始化数据 SLInit(s); SLInsert(s, 0, 1); SLInsert(s, 1, 2); SLInsert(s, 2, 3); SLInsert(s, 3, 4); SLInsert(s, 4, 5); SLInsert(s, 5, 6); SLPrint(s); SLErase(s, 4); SLErase(s, 0); SLPrint(s); //查找值对应的下标 int res SLFind(s, 4); printf(对应的下标值为%d, res); return 0; }测试结果2、总结以上便是我对顺序表部分的全部理解了。有啥不好的地方也欢迎大家积极指出建议大家理解这部分内容的时候可以多多画图方便理解。希望大家早日被自己喜欢的offer录取。那我们就下一个博客见。