【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)(中)

简介: 【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)(中)

6️⃣头部插入:SLPushFront

void SLPushFront(SL* psl, SLDatatype x);//头部插入

这里要说明一下头插之后的原有数组的元素的移动情况:从后往前挪动

从后往前的意思:是从数组原本有的元素开始,从最后一个元素开始往后面的空间移动,这样整体看来,对于数组原有元素来说,相对位置上确实是后面元素先挪动到后面,前面元素紧跟着后面元素的步伐

cf87df321d4b4b8eb0342ae10e6c86d0.png

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++;
}

代码可以看这个图解:

顺序表无元素:

ad4d137679e34e9fbbf0f1e9e4602aa6.png

这个图是头插第一个元素(顺序表无元素时候)end数组下标的位置,先把a[0]赋值,然后size此时为0++,有效元素个数+1

顺序表有元素:

67d190c38b77480ab16770d2b6cca361.png

这图是先从数组最后一个元素(也就是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);
}


执行:

11ced5a53fe9432794b7671df0f06c3d.png

7️⃣尾部删除:SLPopBack

void SLPopBack(SL* psl);//尾删


一开始的思路就是把顺序表最后一个元素变为0或者-1

void SLPopBack(SL* psl)

{

   psl->a[psl->size - 1] = 0;这句话不好,为什么?

   psl->size--;

}

原因有两个:

1.   要是这个位置本来就是0,或者-1,那就没有意义了。

8030d9bbebb545d5a60c202a31cb1864.png

所以这时候,我们直接改成这样,干脆利落:

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);
}


执行:

81a3a248b0904f348ee1e7b6c006a4d0.png

调试一下寻找原因:

先大概率猜测没有问题,所以可以直接跳过打断点的过程

9ebe5afc1e8242c997c67055b04a9f6d.png

猜测一下,这个问题应该是删除产生的, 直接把断点打到尾删这个位置,这时候可以看到size=6,因为插入了6 5 1 2 3 4,中间扩了一次容,所以容量psl->capacity *= 2 -->为8,扩容得刚好是8

9bb3b976907745e2957e9f75e3e66b6f.png

再按F10一步一步跳过函数的内容,接着发现了size--到了-1。因为有6个数据已经删除了6次,第7次删除至少不要把size搞成-1

c73acbf1b03a45c1978589b469dcdbf9.png

那我们应该如何处理那个函数,使得它在即将删除元素越界的时候程序可以正常运行呢?

温柔的检查:

//尾删
void SLPopBack(SL* psl)
{
  assert(psl);//应对可能传过来的NULL指针,而且好处是直接告诉你哪个文件的哪一行出问题
  //温柔检查
  if (psl->size == 0)
  {
    printf("顺序表为空,删除失败\n");
    return;//不报错任何问题,直接回答主函数。
  }
  psl->size--;
}

如果这个printf信息不写,那将不会返回这个信息,直接返回主函数

c70fc12eced440259a8731a430051677.png

暴力检查(推荐):

//尾删
void SLPopBack(SL* psl)
{
  assert(psl);
  //暴力检查
  assert(psl->size > 0);
  psl->size--;
}

b7175a4f40b44546bbdc87be3429cde5.png

关于free报错的原因:

636cf0fb8cf445b59da6c8cff10d6ea3.png

一般情况是内存越界了:申请的空间不够大,但是通过数组等方式遍历到并访问不是动态开辟的空间。还有就是看看指针有没有错, 以图上的(psl->a)为例子,释放的那个指针是不是指向动态内存开辟的空间,除此之外有没有指向错误。

要是头文件处,变为typedef double SLDatatype;

8ea172a97e384018b8ec20cf5a67d3ed.png

那要写成psl->a[psl->size - 1] = 0.0;吗?

以下是可能会引发的问题:

ca53092ceab14223ae58a41fa9f53950.png

所以删除的意思不是把顺序表最后一个元素抹成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

641861d5852c43e28278c67d92468e1e.png

 写法2:start从1下标开始,start<psl->size

574cec8f8a8b49e7bc20fe1394c29a03.png

开一组测试看看效果:

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。

c5646db153704c619fecbd2970355366.png

相关文章
|
20天前
|
存储 编译器 C语言
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
46 2
|
1天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
10 3
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
21天前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
27 6
|
21天前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
20 3
|
21天前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
18 2
|
24天前
|
存储 算法 索引
【数据结构】——顺序表
【数据结构】——顺序表
|
24天前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
20 1
|
26天前
|
存储
数据结构1——顺序表
数据结构1——顺序表
17 1

相关实验场景

更多