顺序表的插入

文章目录代码为什么插入必须“从后往前”移动如果写反方向从前往后)会怎样边界条件分析重点插入位置表尾追加插入位置表头插入空间已满更新长度代码#includestdio.h#defineMaxSize10// 定义最大长度typedefstruct{intdata[MaxSize];// 静态数组存放数据元素intlength;// 顺序表当前有效长度}SqList;// 顺序表类型定义// 初始化顺序表voidInitList(SqListL){for(inti0;iMaxSize;i){L.data[i]0;// 数组全部置0清除垃圾值}L.length0;// 有效元素个数置 0代表空表}// 位序 i 处插入元素 e 位序 i 从 1 开始boolListInsert(SqListL,inti,inte){// 1. 健壮性检查 边界判断if(i1||iL.length1)returnfalse;// 2. 存储空间检查 数组存满无法插入if(L.lengthMaxSize)returnfalse;// 3. 核心移动逻辑从最后一个元素开始依次向后挪一格for(intjL.length;ji;j--)L.data[j]L.data[j-1];// 4. 插入新元素L.data[i-1]e;// 位序 i 转换为数组下标 i-1// 5. 有效长度1L.length;// 更新有效元素计数告诉程序现在表里有效元素数量 1。// 新增一个有效元素计数器必须 1删除一个计数器必须 - 1。returntrue;}intmain(){SqList L;InitList(L);ListInsert(L,3,3);// 第 3 个位置插入数字 3return0;}为什么插入必须“从后往前”移动假设当前顺序表里有数据[1, 2, 4, 5]length 4即有效元素个数为4。我们现将在位序 3即第3个位置数组下标为2插入元素 3。循环轮次j 的值执行语句物理动作内存视角数组变化下标0~4初始状态---[1, 2, 4, 5, ?]第1轮j4L.data[4]L.data[3]把下标3的5复制到下标4向后腾挪[1, 2, 4, 5, 5]第2轮j3L.data[3]L.data[2]把下标2的4复制到下标3向后腾挪[1, 2, 4, 4, 5]结束循环j2条件 ji (23) 为假退出下标2即位序3的位置空出来了[1, 2, 4, 4, 5]最后执行L.data[2] 3数组变为[1, 2, 3, 4, 5]。如果写反方向从前往后)会怎样如果写反方向从前往后 for(ji; jL.length; j)会怎样第1轮L.data[2] L.data[1]把2复制到下标2→ 数组变成 [1, 2, 2, 4, 5]。下标2的原值 4 被覆盖丢失了。后面无论怎么挪4 和 5 都再也找不回来数据彻底损坏。结论必须倒着移动保证每个元素在被覆盖前已经先被复制到后面的安全位置了。边界条件分析重点插入位置表尾追加插入位置i L.length 1表尾追加当前有 length 个元素元素之间、头尾一共会多出length 1个空位 用来插入新元素。i 1表头空位i length1表尾空位插入位置表头插入插入位置 i 1表头插入j 从 length 一直减到 1所有元素整体后移一位。执行 L.data[0] e;插入到表头。空间已满空间已满L.length MaxSize直接return false防止数组越界写入保护内存安全。更新长度数组只是存数据的容器length 是记录有效元素的计数器新增一个有效元素计数器必须 1删除一个计数器必须 - 1。L.length;更新有效元素计数告诉程序现在表里有效元素数量 1。如果插入后不更新 length后续所有代码全部逻辑错乱出现越界、读取不到元素等 bug。