6️⃣头部插入:SLPushFront
void SLPushFront(SL* psl, SLDatatype x);//头部插入
这里要说明一下头插之后的原有数组的元素的移动情况:从后往前挪动
从后往前的意思:是从数组原本有的元素开始,从最后一个元素开始往后面的空间移动,这样整体看来,对于数组原有元素来说,相对位置上确实是后面元素先挪动到后面,前面元素紧跟着后面元素的步伐
void SLPushFront(SL* psl, SLDatatype x) { assert(psl);//应对可能传过来的NULL指针,而且好处是直接告诉你哪个文件的哪一行出问题 SLCheckCapacity(psl); //挪动数据 int end = psl->size-1; while (end >= 0) { psl->a[end + 1] = psl->a[end]; --end; } psl->a[0] = x; psl->size++; }
代码可以看这个图解:
顺序表无元素:
这个图是头插第一个元素(顺序表无元素时候)end数组下标的位置,先把a[0]赋值,然后size此时为0++,有效元素个数+1
顺序表有元素:
这图是先从数组最后一个元素(也就是6)开始挪动,先把元素6往后面的空间挪动,不够了再扩容,然后7把6覆盖,以此类推,接着,看x此时输入(1)的是什么元素,再把a[0]赋值,达到头插的效果
调用头部插入的测试代码:
void TestSeqList2() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushFront(&s, 5); SLPushFront(&s, 6); SLPrint(&s); SLDestroy(&s); }
执行:
7️⃣尾部删除:SLPopBack
void SLPopBack(SL* psl);//尾删
一开始的思路就是把顺序表最后一个元素变为0或者-1
void SLPopBack(SL* psl)
{
psl->a[psl->size - 1] = 0;这句话不好,为什么?
psl->size--;
}
原因有两个:
1. 要是这个位置本来就是0,或者-1,那就没有意义了。
所以这时候,我们直接改成这样,干脆利落:
void SLPopBack(SL* psl) { psl->size--; }这样就不会引起其它问题了吗?然后并不是。
这是关于测试尾部删除的越界问题,以及打印值问题的测试代码
void TestSeqList3()//测试尾部删除的越界问题,以及打印值问题 { SL s; SLInit(&s); SLPushBack(&s, 1);//插入 SLPushBack(&s, 2);//插入 SLPushBack(&s, 3);//插入 SLPushBack(&s, 4);//插入 SLPushFront(&s, 5);//头插入 SLPushFront(&s, 6);//头插入 SLPrint(&s);//整体呈现出来应该是 6 5 1 2 3 4 SLPopBack(&s);//尾删除 SLPopBack(&s);//尾删除 SLPrint(&s);//整体呈现出来应该是 6 5 1 2 SLPopBack(&s);//尾删除 SLPopBack(&s);//尾删除 SLPrint(&s);//整体呈现出来应该是 6 5 SLPopBack(&s);//尾删除 SLPopBack(&s);//尾删除 SLPopBack(&s);//尾删除-->此时顺序表已经没有元素了还要删一个 SLPrint(&s);//这时候size有效信息个数还"欠"一个 SLPushBack(&s, 1);//所以这个是被吃掉了~! SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPrint(&s);//整体呈现 2 3 4 SLDestroy(&s); }
执行:
调试一下寻找原因:
先大概率猜测没有问题,所以可以直接跳过打断点的过程
猜测一下,这个问题应该是删除产生的, 直接把断点打到尾删这个位置,这时候可以看到size=6,因为插入了6 5 1 2 3 4,中间扩了一次容,所以容量psl->capacity *= 2 -->为8,扩容得刚好是8
再按F10一步一步跳过函数的内容,接着发现了size--到了-1。因为有6个数据已经删除了6次,第7次删除至少不要把size搞成-1
那我们应该如何处理那个函数,使得它在即将删除元素越界的时候程序可以正常运行呢?
温柔的检查:
//尾删 void SLPopBack(SL* psl) { assert(psl);//应对可能传过来的NULL指针,而且好处是直接告诉你哪个文件的哪一行出问题 //温柔检查 if (psl->size == 0) { printf("顺序表为空,删除失败\n"); return;//不报错任何问题,直接回答主函数。 } psl->size--; }
如果这个printf信息不写,那将不会返回这个信息,直接返回主函数
暴力检查(推荐):
//尾删 void SLPopBack(SL* psl) { assert(psl); //暴力检查 assert(psl->size > 0); psl->size--; }
关于free报错的原因:
一般情况是内存越界了:申请的空间不够大,但是通过数组等方式遍历到并访问不是动态开辟的空间。还有就是看看指针有没有错, 以图上的(psl->a)为例子,释放的那个指针是不是指向动态内存开辟的空间,除此之外有没有指向错误。
要是头文件处,变为typedef double SLDatatype;
那要写成psl->a[psl->size - 1] = 0.0;吗?
以下是可能会引发的问题:
所以删除的意思不是把顺序表最后一个元素抹成0或1就行了。
8️⃣头部删除:SLPopFront
void SLPopFront(SL* psl, SLDatatype x);//顺序表头插
把顺序表第一个元素删除掉,接着从顺序表第二个元素开始往前移动(第2个挪动到第1个,第3个移动到第2个, 以此类推)。
void SLPopFront(SL* psl)//从后往前 { assert(psl);//应对可能传过来的NULL指针,而且好处是直接告诉你哪个文件的哪一行出问题 //暴力检查 assert(psl->size > 0); //温柔检查 if (psl->size == 0) return; /*int start = 0; while (start < psl->size - 1) { psl->a[start] = psl->a[start + 1]; start++; }*/ /*int start = 1; while (start < psl->size) { psl->a[start - 1] = psl->a[start]; start++; }*/ psl->size--; }
写法1:start从0下标开始,start<psl->size-1
写法2:start从1下标开始,start<psl->size
开一组测试看看效果:
void TestSeqList4()//头部删除越界 { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPrint(&s); SLPopFront(&s); SLPopFront(&s); SLPrint(&s); SLPopFront(&s); SLPopFront(&s); SLPrint(&s); //以下再删除就会越界 //SLPopFront(&s); //SLPopFront(&s); //SLPrint(&s); SLDestroy(&s); }
执行:最下面一行打印是因为assert。