顺序表专题

一、顺序表定义顺序表示线性表的一种低层结构是数组。 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。二、顺序表分类顺序表和数组区别顺序表底层就是数组相较于数组仅支持下标访问、缺乏封装好的增删查改逻辑顺序表封装了完整的增、删、查、改操作还能实现动态扩容逻辑长度可变使用更灵活安全。1.静态顺序表定义多用于数据量固定、很小或嵌入式 / 内存受限场景追求极简和极致速度structSeqList{intarr[100];//定长数组intsize;//顺序表当前有效的数据个数}缺点空间给少了不够用给多了会造成浪费2.动态顺序表定义数据量未知、会变、很大或通用业务开发日常编程 90% 的情况都用它动态增容一般以二倍的形式增加structSeqList{int*arr[100];intsize;//有效数据个数intcapacity;//空间大小}动态顺序表的实现头文件.h中#includestdio.h#includestdlib.h#includeassert.h#defineINIT_CAPACITY4typedefintSLDataType;//便于后续改变数据类型// 动态顺序表 -- 按需申请typedefstructSeqList{SLDataType*a;intsize;// 有效数据个数intcapacity;// 空间容量}SL;//初始化和销毁voidSLInit(SL*ps);voidSLDestroy(SL*ps);voidSLPrint(SL*ps);//扩容voidSLCheckCapacity(SL*ps);//尾部插⼊删除 / 头部插⼊删除voidSLPushBack(SL*ps,SLDataType x);voidSLPopBack(SL*ps);voidSLPushFront(SL*ps,SLDataType x);voidSLPopFront(SL*ps);//指定位置之前插⼊/删除数据voidSLInsert(SL*ps,intpos,SLDataType x);voidSLErase(SL*ps,intpos);//查找intSLFind(SL*ps,SLDataType x);源文件.c中#includeSL.h//初始化voidSLInit(SL*ps){ps-aNULL;ps-sizeps-capacity0;}//销毁voidSLDestroy(SL*ps){if(ps-a){free(ps-a);}ps-aNULL;ps-sizeps-capacity0;}//扩容voidSLCheckCapacity(SL*ps){if(ps-capacityps-size){intnewCapacityps-capacity0?4:2*ps-capacity;//扩容SLDataType*tmp(SLDataType*)realloc(ps-a,newCapacity*sizeof(SLDataType));if(tmpNULL){perror(realloc fail!);return;}ps-atmp;ps-capacitynewCapacity;}}//尾插voidSLPushBack(SL*ps,SLDataType x){//温柔的方式(空指针检查//if (ps NULL) {// return;// }//暴力assert(ps);SLCheckCapacity(ps);ps-a[ps-size]x;ps-size;}//头插voidSLPopFront(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);for(intips-size;i0;i--){ps-a[i]ps-a[i-1];}ps-a[0]x;}//顺序表打印voidSLPrint(SL s){for(inti0;is.size;i){printf(%d ,s.a[i]);}printf(\n);}//尾删voidSLPopBack(SL*ps){assert(ps);assert(ps-size);--ps-size;}//头删voidSLPopFront(SL*ps){for(inti0;ips-size-1;i){ps-a[i]ps-a[i1];}ps-size--;}//指定位置之前插⼊数据voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos0posps-size);SLCheckCapacity(ps);for(intips-size;ipos;i--){ps-a[i]ps-a[i-1];}ps-a[pos]x;}//删除指定位置数据voidSLErase(SL*ps,intpos){assert(ps);assert(pos0posps-size);for(intipos;ips-size-1;i){ps-a[i]ps-a[i1];}--ps-size;}//查找intSLFind(SL*ps,SLDataType x){assert(ps);for(inti0;ips-size;i){returni;//找到了}//没有找到return-1;}测试文件——验证代码是否正确自行添加有需要的注释#includeSL.hvoidSLTest01(){SL s1;SLInit(s1);//测试尾插SLPushBack(s1,1);SLPushBack(s1,2);SLPushBack(s1,3);SLPushBack(s1,4);SLPritn(s1);//测试头插SLPushFront(s1,5);SLPushFront(s1,6);SLPritn(s1);//测试尾删SLPopBack(s1);//测试头删SLPopFront(s1);SLPritn(s1);//测试指定位置之前插⼊SLInsert(s1,0,99);SLPritn(s1);//测试删除指定位置数据SLErase(s1,0);SLPritn(s1);SLDestroy(s1);//查找数据intfindSLFind(s1,4);if(find0){printf(没有找到\n);}else{printf(找到了下标为%d\n,find);}SLDestroy(s1);}intmain(){SLTest01();return0;}