数据结构入门-----顺序表

1.什么是顺序表顺序表是指用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。顺序表在逻辑结构上是线性的在物理结构上也是线性的就像数组一样。顺序表的底层结构是数组所以顺序表是用数组来实现的可以说顺序表是数组ProMax版数组增加数据删除数据修改数据查找数据…2.顺序表的分类顺序表分为静态数据表和动态数据表静态数据表使用定长数组存储元素数组大小有限因此静态顺序表的缺陷就是空间给少了不够用给多了造成空间浪费所以说在已知数据大小具体是多少时可以使用静态数据表在大多数情况下我们使用动态数据表动态数据表按需申请内存空间它底层的数组空间在不断变化3.顺序表的实现1.创建顺序表在这里我们采用创建结构体的方法来创建顺序表#includestdio.htypedefstructSqList{int*arr;//这里可以通过typedef定义int 通过改变来进行类别转换intsize;//有效数据intcapacity;//空间大小}SL;2.顺序表的初始化void SLInit(SL* s){ s-arrNULL; s-sizes-capacity0; } void test01(){//进行初始化 SL s1; SLInit(*sl); }3.检查数据空间大小为了防止数据溢出我们将检查数据的大小boolSLCapaciteCheck(SL*ps){returnps-sizeps-capacite;}//如果顺序表空间满了我们将空间大小进行扩容如果是静态顺序表可以通过改变数组大小进行扩容voidSLExpansion(SL*ps){if(SLCapaciteCheck(ps)){//检查空间大小如果空间大小为0则给空间4个字节大小否则将当前空间扩大一倍intnewcapacityps-capacity0?4:ps-capacity*2;int*tmp(int*)realloc(ps-arr,newcapacity*sizeof(int));//为了防止扩容失败创建临时变量进行存储if(tmpNULL){perror(realloc failed);exit(1);}ps-arrtmp;ps-capacitynewcapacity;}}}4.数据插入//首先我们先进行数据尾部插入voidSLPushBack(SL*ps,intx){//检查空间是否足够SLExpansion(ps);//在空间足够情况下ps-arr[ps-size]x;}//接下来我们进行数据头部插入voidSLPushFront(SL*ps,intx){SLExpansion(SL*sl);//移动数据使数据头部空出来for(intips-size,i--,i0){ps-arr[ps-i]ps-arr[ps-i-1];}ps-arr[0]x;ps-size;}5.数据删除//我们首先对数据的尾部进行删除voidSLPopBack(SL*ps){//检查顺序表是否为空if(ps-size0){return0;}--ps-size;}//这里是进行数据头部删除voidSLPopFront(SL*ps){for(inti0;isize-1;i){ps-arr[i]ps-arr[i1];}--ps-size;}6.查找数据voidSLFind(SL*ps,intx){for(inti0;ips-size;i){//查找顺序表中元素为x如果找到则返回下标if(ps-arr[i]x){returni;}}printf(没找到);return-1;}7.顺序表的销毁voidSLDestroy(SL*ps){if(ps-arr){free(ps-arr);}ps-arrNULL;ps-sizeps-capacite0;}##### 以上就是顺序表的基础结构如果有需要可以增添一些功能如指定数据的删除/插入。总结顺序表具有一定的优缺点优点是数据存储密度大能够完成一部分功能缺点是增容需要申请新空间拷贝数据释放旧空间。会有不⼩的消耗。还会造成空间的浪费。