🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬🍬

☆*: .｡. o(≧▽≦)o .｡.: ☆~~~///(v)\~~~<(￣︶￣)↗[GO! ] ( •̀ ω •́ )✧(～￣▽￣)～φ(゜▽゜)♪o(￣︶￣*)oヾ(＠⌒ー⌒＠)ノo((>ω< ))o

🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭

数据结构对内存的管理无外乎增删查改，本篇重点讲解顺序表中是如何实现增删查改已经相关操作的。

1.🌏线性表🌏

线性表*（linear list）*是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

本篇讲的就是顺序表。

2.🌎顺序表🌎

2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下，采用数组存储。在数组上网查数据的增删查改。

顺序表一般可以分为静态顺序表和动态顺序表。

2.2静态顺序表

使用定长数组来存储元素。

2.3动态顺序表

使用动态开辟的数组存储

3.🌏实现动态顺序表🌏

静态顺序表只适用于确定知道需要存多少数据的情景。静态顺序表的顶层数组导致N定大了，空间就会浪费，定少了，就会不够用，所以现实中我们基本使用的都是动态顺序表，根据需要来动态开辟空间，所以我们下面来实现动态顺序表。

而我们知道数据结构是什么？

就是对内存数据进行管理，怎么管理呢？在顺序表中对数据的管理总结为增删查改。

#define INIT_Capacity 4
typedef int SLData;//在顺序表中使用的数据不一定就是int类型，所以先重定义一下，等要使用其他类型的数据时，直接对int修改即可，而不需要整体修改。
typedef struct SLList
{
  SLData* a;//指向动态开辟的数组
  int size;//实际的数据个数
  int capacity;//一开始的容量大小，或者每次扩容的大小
}SL;//将顺序表重定义为SL

接下来我们就要实现：

顺序表的初始化，扩容，插入，删除，查找，修改，销毁，打印等等操作。

1.void SLInit(SL* ps);//顺序表初始化
2.void SLpushBack(SL*ps,SLData x);//顺序表尾插
3.void SLpushFront(SL* ps, SLData x);//顺序表头插
4.void SLpopBack(SL* ps);//顺序表尾删
5.void SlpopFrint(SL* ps);//顺序表头删
6.void SLPrint(SL* ps);//顺序表打印
7.void SLInsert(SL* ps, int pos,SLData x);//顺序表在pos位置上插入x
8.void SLErase(SL* ps,int pos);//顺序表删除pos位置上的值
9.void SLFind_check(SL* ps, SLData x);//顺序表查找修改
10.void SLDestroy(SL* ps);//顺序表销毁

3.1顺序表初始化

顺序表初始化，首先要给数组开辟空间，这样才可以存入数据，因为一开始并没有数据所以size大小为0，而数组容量的大小由自己定。

void SLInit(SL* ps)
{
  ps->a = (SLData*)malloc(sizeof(SLData) * INIT_Capacity);//首先为a指针指向的数组开辟空间
  //一开始先给数组开辟capicity个空间
  if (ps->a == NULL)//判断一下开辟是否成功
  {
    perror("malloc");
    return;
  }
  ps->size = 0;//一开始因为没有数据所以将size置0
  ps->capacity = INIT_Capacity;//容量自己定
}

3.2顺序表尾插

我们先假设数组里面有数据，如果我们要尾插，该怎么插呢？

尾插就是插入最后一个元素的后面，而最后一个元素的下标不就是size-1嘛，那下一个空间的下标就是size，所以将x插入ps->a[size]的地方即可。然后再让size++；

如果数组里没有数据，上面的方法照样可以因为如果没有数据那么size就为0

ps->a[size]就是第一个元素。

不过插入数据的时候我们也要想到一个问题，如果数组空间满了，没有多余的空间给新数据插入，那么新数据的插入就不合法了，所以在插入之前我们需要进行判断，看是否需要扩容。

而需要扩容的充分条件就是当实际数据的个数等于数组的容量时就需要扩容了，也就是ps->size==ps->capicity时。

void SLpushBack(SL* ps, SLData x)//尾插
{
    assert(ps)//断言判断一下不为NULL
  //要考虑原本容量大小，考虑越界---扩容
  if (ps->size == ps->capacity)
  {
    SLData* new = (SLData*)realloc(ps->a, sizeof(SLData) * ((ps->capacity) * 2));
    if (new == NULL)
    {
      perror("realloc");
       return;
    }
    ps->a = new;//要将realloc新开辟的空间再赋给a
    printf("扩容成功\n");
    ps->capacity *= 2;
  }
  ps->a[ps->size] = x;
  ps->size++;
}

3.3顺序表扩容

上面的尾插入已经讲了什么时候该扩容，只要插入数据就要进行判断是否需要扩容。

然后扩容的操作也是需要分析一下。

扩容是因为原数组的空间不够使用而需要操作系统给它分配更多的空间。

而分配更多的空间的操作是有realloc这个函数来实现的。

realloc扩容会有两个特点：

1.原地扩容

当原来的空间后面还有内存可以使用时，操作系统就会将后面的内存分配给它，也就是在原地址的基础上又得到更多空间。

所以有时候不把realloc扩容得到的新空间赋值给原指向数组的指向时，不会出错，但这种做法是不对的，因为还会有另一种更为常见的情况会出现也就是异地扩容。

2.异地扩容

异地扩容就是原数组的空间后面没有多余的内存可以使用，操作系统就会找另一块空间给它，然后将源数据拷贝过来，将源空间释放掉，所以这时new指向这块新的空间，这时如果不把new赋值给ps->a，就会出错。

所以我们要记住realloc扩容的空间需要赋值给原指针这个操作。

到后面我们就把这个扩容操作直接分装成一个函数即可。

每次扩容多少以需要决定。

void CheckCapacity(SL* ps)//检查扩容
{
    assert(ps)//断言判断一下不为NULL
  //要考虑原本容量大小，考虑越界---扩容
  if (ps->size == ps->capacity)
  {
    SLData* new = (SLData*)realloc(ps->a, sizeof(SLData) * ((ps->capacity) * 2));
    if (new == NULL)
    {
      perror("realloc");
      return;
    }
    ps->a = new;//要将realloc新开辟的空间再赋给a//空间可能还是原先的地方只不过大小变大了。
    //或者变成另一个空间。
    //realloc可能原地扩容也可能异地扩容
    printf("扩容成功\n");
    ps->capacity *= 2;
  }
}

3.4顺序表尾删

尾删是什么意思呢？

就是将最后一个元素删掉。

该怎么删呢？

我们要注意到，顺序表是按照ps->size的实现数据的大小来决定打印多少数据的而不是空间的多少。

所以删除最后一个数据直接让实际数据减1即可也就是ps->size–；

也不用释放这个元素的空间，因为也释放不了，操作系统不允许这样。

空间的开辟，释放，要么整体释放，要么不释放，不能部分释放

还有删除元素就一定要想到一个问题，会不会删过头了？

没有数据还删，导致ps->size-- ,都减到负数了。

所以在删除数据之前我们也要进行判断。

判断ps->size的大小是否==0，如果等于就不要删了。

最好的方法就是用assert进行断言，简单粗暴。

当然也有温柔的做法，当ps->size= =0时，return ；

void SLpopBack(SL* ps)//尾删
{
//数组动态开辟的空间不能一个一个元素（部分）释放，数组空间在堆区上申请，只能一起释放不能单独释放。
  //暴力监测
  assert(ps->size > 0);
  //温和监测
  if (ps->size == 0)
  {
    return;
  }
  //ps->a[ps->size - 1] = 0;
  ps->size--;
}

3.5顺序表打印

顺序表怎么打印呢？

就是像数组一样循环打印就可以了，因为它是连续的，可以通过下标来找到。打印的次数由ps->size实际数据个数来决定.

void SLPrint(SL* ps)//顺序表的打印
{
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
}

3.6顺序表头插

头插就是把数据插入到第一个元素前面，这个就需要挪动数据了。

需要将整体数据往后挪一个位置。

该怎么挪动呢？是从后往前挪还是从前往后挪

应该是从最后一个元素开始往后挪动。当把最后一个元素挪动完就可以了

接着就可以将数据插入到第一个位置了。

还有插入数据之前我们应该干嘛呢？

需要检查是否需要扩容呀！

void SLpushFront(SL* ps, SLData x)//头插
{
  CheckCapacity(ps);//检查是否需要扩容
  assert(ps);//断言判断
  int end = ps->size - 1;//从最后一个元素开始挪
  while (end >= 0)//当把第一个元素挪动后就结束
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[0] = x;
  ps->size++;//插入一个数据size++
}

3.7顺序表头删

头删就是将表头数据删除掉，也是需要挪动数据的，不过跟上面的挪动数据不一样，这次是从前面开始往后挪动，如果先挪动后面的数据就会造成数据丢失。

当把最后一个数据挪动完后结束。

还有删除数据我们需要注意什么呢？

不能删过头了！

所以我们需要进行判断是否ps->size==0;

void SLpopFront(SL* ps)//头删
{
  assert(ps->size > 0);//首先进行判断是否删过头
  int start = 0;//从前面开始往后挪动
  while (start < ps->size - 1)
  {
    ps->a[start] = ps->a[start + 1];
    start++;
  }
  ps->size--;//删除减1
}

3.8顺序表的插入

现在讲的是从中间开始插入一个数据，其实与头插类似，只不过循环起始地方不同罢了。

从pos位置插入，就要知道该位置的下标，然后将该位置以及后面的数据整体往后挪动，空出一个位置给插入的数据，跟头插的挪动方法一样，从最后面开始挪动，直到挪动pos位置.

插入之前需要进行扩容判断喔。

void SLInsert(SL* ps,int pos, SLData x)
{
  assert(ps);//断言判断
  assert(pos >= 0 && pos <= ps->size);//对pos位置进行判断
  CheckCapacity(ps);//检查是否需要扩容
  //要考虑边界---超过容量怎么办，扩容
  //可以从开头插 位置是0，也可以在最后一个元素的后面插，相当于尾插了位置是 ps->size
  //跟头插很像
  int end = ps->size - 1;//从最后一个元素开始挪动
  while (end >= pos)//当挪动完pos位置的数据后结束
  {
    //从后往前移动
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;//将数据插入
  ps->size++;//size++
}

其实该插入就可以替代头插和尾插了，只要将位置pos改为size就是尾插

改成0就是头插。

3.9顺序表的删除

前面讲的是头删和尾删，现在讲的是从中间删，删除一个元素也需要挪动数据，需要讲pos位置后面的数据往前挪动一位，将pos位置的数据覆盖。

而这种挪动方式是从前面开始挪动，直到挪动最后一个元素为止。

删除数据之前要进行判断是否删除过头喔。

void SLErase(SL* ps,int pos)
{
  assert(ps);//断言判断
  assert(pos >= 0 && pos < ps->size - 1);
  //对pos位置判断以及是否删除过头
  int begin = pos-1;//从前面开始挪动
  while (begin < ps->size)
  {
    ps->a[begin] = ps->a[begin + 1];
    begin++;//从前面开始移动
  }
  ps->size--;
}

3.10顺序表的查找与修改

查找数据就可以修改，这两个操作其实可以合起来写。

怎么查找呢？

给一个数我们在数组中查找这个数，一般使用循环来找，这个最容易想到，所以我们就直接与顺序表中的数据一个一个比较就能找到，找到之后我们就可以对它修改了。

void SLFind_check(SL* ps, SLData x)
{
  assert(ps);//断言判断
  for (int i = 0; i < ps->size; i++)
  {
    if (ps->a[i] == x)//查找
    {
      printf("你要将 %d 修改成什么？\n",x);
      SLData n;
      printf("修改成：");
      scanf("%d", &n);
      ps->a[i] = n;//修改
    }
  }
}

4.🌕相关面试题🌕

4.1移除元素

OJ链接

移除元素也就是删除元素，删除元素怎么删呢？我们想应该是挪动覆盖，把这个元素覆盖了就算删除了。

这个题目要是没有要求不能使用额外的数组我们有很多方法可以进行移除。

可以找一个数组，让nums数组每个元素都与val比较，如果不相同就放进新数组里，如果相同就不放进去，最后再将新数组里的数据拷贝过去就可以了。

不过这道题要求不能使用额外空间，所以这种方法不行，但这种想法是可取的。不过不是放在新的数组里，而是就在原数组的基础上进行比较，定两个指针或者下标，src用来追踪进行比较的元素，des用来追踪比较后不同的元素,src位置上的元素与val比较发现不同则将值赋给des位置上，然后src++，des++，如果相同，则src++，des不++。

int removeElement(int* nums, int numsSize, int val){
int des=0;
int src=0;
while(src<numsSize)
{
    if(nums[src]!=val)
    {
        nums[des++]=nums[src++];
    }
    else
    {
        src++;
    }
}
return des;
}

4.2删除排序数组中的重复项

OJ链接

要求将有序数组中重复项删除掉，我的第一想法还是进行覆盖，那该怎么覆盖呢？

还是使用双指针或者双下标，src，des

src用来追踪比较的元素，des用来追踪进行覆盖的元素。

第一个元素肯定已经在数组里面存着呢，不用移除，所以src指向的是第二个元素

des是指向第一个元素，当src指向的元素与des指向的元素相同时，src肯定需要继续走，当src指向的元素与des指向的元素不一样时，这时需要将新元素赋给des指向的数组，但des这时还是指向着一个元素所以需要des++一下，再将src指向的元素赋给des指向的地方。

所以方法就是当src指向的元素与des指向的元素相同时，src++，des不动

当src指向的元素与des指向的元素相同时，需要将des往后挪动一下，再将src指向的值赋给des。

int removeDuplicates(int* nums, int numsSize){
int des=0;
int src=1;
while(src<numsSize)
{
    if(nums[des]==nums[src])
    {
        src++;
    }
    else
    {
        nums[++des]=nums[src++];
    }
}
 return des+1;
}

4.3合并两个有序数组

OJ链接

合并有序数组我们常规的做法是找两个指针或下标，分别指向两个数组，两个数组进行比较，将比较后小的先放进新数组里，较大的后放进数组里，直到某个数组遍历完，直接将每遍历完的数组剩下的元素放进新数组的后面去。

但这题与常规的不一样，因为它要求在原数组之上进行合并，不能额外开辟一个新的数组，这时就不能按照上面的想法来了。

正确的做法是从有效数字最后后面进行比较，将比较后较大的先放进数组最后一位，较小的后放进去，如果按照实例1来看也就是

最后如果num2比较完了，num1中自然也就排序完了。

但是还有另一种情况在，就是num2中的元素很小，num1中最小的元素跟它比还不是比他大，这时还需要将num2中剩下的元素赋给num1.

5.🚀顺序表问题总结🚀

5.1挪动数据时间复杂度高

中间，头部的插入删除需要挪动数据，时间复杂度大。

5.2需要不断扩容

增容需要申请新空间，拷贝数据，释放旧空间，会有不少消耗。

5.3浪费空间

增容一般呈2倍的增长，肯定会造成空间浪费，比如当前100容量，扩容到200，只使用了150，还剩50浪费掉了。

如何解决以上问题呢？

以上问题都将会在链表中得到解决，想要了解更多那就学习起来吧！

——----------————------_______________ ____________---------

【数据结构】顺序表的实现

数据结构对内存的管理无外乎增删查改，本篇重点讲解顺序表中是如何实现增删查改已经相关操作的。

1.🌏线性表🌏

2.🌎顺序表🌎

2.1概念及结构

2.2静态顺序表

2.3动态顺序表

3.🌏实现动态顺序表🌏

3.1顺序表初始化

3.2顺序表尾插

3.3顺序表扩容

3.4顺序表尾删

3.5顺序表打印

3.6顺序表头插

3.7顺序表头删

3.8顺序表的插入

3.9顺序表的删除

3.10顺序表的查找与修改

4.🌕相关面试题🌕

4.1移除元素

4.2删除排序数组中的重复项

4.3合并两个有序数组

5.🚀顺序表问题总结🚀

5.1挪动数据时间复杂度高

5.2需要不断扩容

5.3浪费空间

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】顺序表的实现

数据结构对内存的管理无外乎增删查改，本篇重点讲解顺序表中是如何实现增删查改已经相关操作的。

1.🌏线性表🌏

2.🌎顺序表🌎

2.1概念及结构

2.2静态顺序表

2.3动态顺序表

3.🌏实现动态顺序表🌏

3.1顺序表初始化

3.2顺序表尾插

3.3顺序表扩容

3.4顺序表尾删

3.5顺序表打印

3.6顺序表头插

3.7顺序表头删

3.8顺序表的插入

3.9顺序表的删除

3.10顺序表的查找与修改

4.🌕相关面试题🌕

4.1移除元素

4.2删除排序数组中的重复项

4.3合并两个有序数组

5.🚀顺序表问题总结🚀

5.1挪动数据时间复杂度高

5.2需要不断扩容

5.3浪费空间

热门文章

最新文章

相关课程

相关电子书