【数据结构】顺序表

其他篇章【Linux专栏】其他篇章 【C语言专栏】上期回顾 【Linux】网络基础2—Socket编程预备文章目录前言1.顺序表的概念及结构常⻅的线性表1.1线性表2.顺序表分类3.动态顺序表的实现前言在此之前我们先来了解一下什么是数据结构?数据结构是由“数据”和“结构”两词组合⽽来。什么是数据常⻅的数值1、2、3、4…、教务系统⾥保存的⽤⼾信息姓名、性别、年龄、学历等等、⽹⻚⾥⾁眼可以看到的信息⽂字、图⽚、视频等等这些都是数据.什么是结构当我们想要使⽤⼤量使⽤同⼀类型的数据时通过⼿动定义⼤量的独⽴的变量对于程序来说可读性⾮常差我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起结构也可以理解为组织数据的⽅式。概念数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成即数据由那部分构成以什么⽅式构成以及数据元素之间呈现的结构数组是最基础的数据结构1.顺序表的概念及结构在了解顺序表之前我们先来了解一下线性表线性表linear list是n个具有相同特性的数据元素的有限序列。常⻅的线性表顺序表、链表、栈、队列、字符串... 线性表顺序表逻辑结构连续顺序表物理结构不一定连续1.1线性表顺序表和数组的区别顺序表的底层结构是数组对数组的封装实现了常⽤的·增删改查·等接⼝2.顺序表分类静态顺序表使⽤定⻓数组存储元素缺陷空间给少了不够用给多了浪费动态顺序表3.动态顺序表的实现SeqList.h#pragmaonce#includestdio.h#includestdlib.h#includeassert.htypedefintSLdatatype;typedefstructSeqList{SLdatatype*arr;intsize;intcapacity;//空间容量}SL;//SL是对结构体SeqList的重命名//顺序表初始化voidSLInit(SL*ps);//打印顺序表voidSLPrint(SL*ps);//尾插voidSLPushBack(SL*ps,SLdatatype x);//头插voidSLPushFront(SL*ps,SLdatatype x);//尾删voidSLPopBack(SL*ps);//头删voidSLPopFront(SL*ps);SeqList.c#define_CRT_SECURE_NO_WARNINGS1#includeSeqList.h//初始化voidSLInit(SL*ps){ps-arrNULL;ps-size0;ps-capacity0;//空间容量}//打印// size是有效的数据个数voidSLPrint(SL*ps){for(inti0;ips-size;i){printf(%d ,ps-arr[i]);}printf(\n);}voidSLCheckCapacity(SL*ps){//检查顺序表容量是否已满intnewcapacityps-capacity0?4:2*ps-capacity;//为真-则为四个字节的容量int类型为假-则扩容原容量的2倍//用tmp接收realloc返回值避免直接覆盖ps-arr,防止扩容失败丢失原地址SLdatatype*tmp(SLdatatype*)realloc(ps-arr,newcapacity*sizeof(SLdatatype));if(tmpNULL){perror(realloc);exit(1);//非0表示程序异常终止}ps-arrtmp;ps-capacitynewcapacity;}//尾插voidSLPushBack(SL*ps,SLdatatype x){assert(ps);//检查空间是否足够SLCheckCapacity(ps);//空间足够ps-arr[ps-size]x;}//头插voidSLPushFront(SL*ps,SLdatatype x){assert(ps);//检查空间是否足够SLCheckCapacity(ps);//空间足够for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];//for循环原数据全部向后移动一位}ps-arr[0]x;//将要头插的数据插入到数组首位ps-size;}//尾删voidSLPopBack(SL*ps){assert(psps-size);ps-size--;}//头删voidSLPopFront(SL*ps){assert(psps-size);for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];//将所有元素向后移动一位}ps-size--;}test.c#define_CRT_SECURE_NO_WARNINGS1#includeSeqList.hvoidtest(){SL s;//s-结构体变量SLInit(s);//只能传地址//尾插SLPushBack(s,5);SLPushBack(s,2);SLPushBack(s,0);SLPushBack(s,4);//打印SLPrint(s);//5 2 0 4//头插SLPushFront(s,8);SLPrint(s);// 8 5 2 0 4//尾删SLPopBack(s);SLPopBack(s);SLPrint(s);// 8 5 2//头删SLPopFront(s);SLPrint(s);//5 2}intmain(){test();}运行结果注意为什么只能传地址呢?1.传值时,ps是临时值的拷贝,SLInit 的参数是 SL* ps 指针如果传值比如传 s1而不是 s1会出现两个错误编译报错 SLInit(s) 中 s 是 SL 类型而 SLInit 需要 SL* 类型指针类型不匹配直接编译失败退一步说即使强行传值比如错误写 SLInit((SL*)s1) ps 会变成一个指向随机内存的野指针执行 ps-arr NULL 时会触发内存访问违规程序直接崩溃。2.调用时,实参s的整个结构体内容(包括垃圾值的arr/size/capacity)会被拷贝一份 ,赋值给形参ps,而在函数void SLPrint(SL* ps)内修改的是赋值后的形参ps,和实参无关系,在函数执行完之后,形参ps被销毁,实参依然是未初始化的垃圾值核心问题:形参是独立的副本,修改形参≠修改实参