数据结构：顺序表

文章目录1.线性表2.顺序表2.1 概念2.2 分类2.2.1 静态顺序表2.2.2 动态顺序表2.3 动态顺序表的实现1.定义动态顺序表的结构2.初始化3.销毁4.动态申请内存5.顺序表的打印6.尾插7.头插8.尾删9.头删10.查找11.在指定位置之前插入数据12.删除指定位置的数据3.顺序表的应用场景4.总结1.线性表2.顺序表2.1 概念因为数组也是一段连续的存储单位由此可知顺序表的底层逻辑就是数组。它与数组的区别就是顺序表对数组的封装处理即增加了对数组的增删查改等操作。2.2 分类2.2.1 静态顺序表概念使用定长数组存储数据缺点空间大小是确定的不可改变给多了怕浪费给少了怕不够用。2.2.2 动态顺序表2.3 动态顺序表的实现1.定义动态顺序表的结构typedefintSLDataType;typedefstructSeqList{SLDataType*arr;intsize;//记录使用的空间的大小intcapacity;//记录申请空间的大小}SL;2.初始化voidSLInit(SL*ps){ps-arrNULL;ps-size0;ps-capacity0;}3.销毁voidSLDestroy(SL*ps){if(ps-arr){free(ps-arr);}ps-arrNULL;ps-sizeps-capacity0;}4.动态申请内存voidSLCheckCapacity(SL*ps){if(ps-capacityps-size){//申请空间, 创建新的变量避免空间申请失败导致数据消失intnewCapacityps-capacity0?4:2*ps-capacity;// 三目运算符避免初始空间为空而且扩容一般为2~3倍SLDataType*tmp(SLDataType*)realloc(ps-arr,newCapacity*sizeof(SLDataType));if(tmpNULL){perror(realloc fail!);exit(1);//退出程序}ps-arrtmp;//将申请的空间地址给回数组ps-capacitynewCapacity;}}5.顺序表的打印voidSLPrintf(SL s){for(inti0;is.size;i){printf(%d ,s.arr[i]);}printf(\n);}注打印不需要传指针不需要改变数据6.尾插voidSLPushBack(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);//判断空间是否足够不够就增容ps-arr[ps-size]x;ps-size;}7.头插voidSLPushFront(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);//判断空间是否足够不够就增容//先向后移一位for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];}ps-arr[0]x;//赋值ps-size;//空间增大size}8.尾删voidSLPopBack(SL*ps){assert(ps);assert(ps-size);//判断数组是否为空--ps-size;//不删掉数据改变size的范围}9.头删voidSLPopFront(SL*ps){assert(ps);assert(ps-size);//数据整体往前移一位for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}10.查找intSLFind(SL*ps,SLDataType x){assert(ps);for(inti0;ips-size;i){if(ps-arr[i]x){returni;}}return-1;}11.在指定位置之前插入数据voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos0posps-size);SLCheckCapacity(ps);//pos之后的位置整体往后移一位for(intips-size;ipos;i--){ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;ps-size;}12.删除指定位置的数据voidSLErase(SL*ps,intpos){assert(ps);assert(pos0posps-size);for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}3.顺序表的应用场景数据量固定或变化较小且需要频繁随机访问。作为其他复杂数据结构如堆、哈希表的基础实现。4.总结优点随机访问高效通过下标可在O ( 1 ) O(1)O(1)时间内访问任意元素。存储密度高仅存储数据元素无需额外空间维护逻辑关系。缺点插入/删除效率低平均时间复杂度为O ( n ) O(n)O(n)需移动后续元素。容量固定静态分配需预先确定大小动态分配虽可扩容但涉及数据迁移。