动态顺序表(C语言实现)

简介: 动态顺序表(C语言实现)

1.顺序表的概念

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

2.顺序表一般可以分为静态顺序表(使用定长数组存储元素)和动态顺序表(使用动态开辟的数组存储)

2.静态顺序表的缺点

静态顺序表只适用于确定知道需要存多少数据的场景 , 静态顺序表的定长数组导致空间开多了浪费,开少了不够用的弊端,所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,下面也会详细讲解动态顺序表的实现,不过掌握了动态顺序表相信静态的对你来说也是小菜一碟的

3.动态顺序表

3.1结构

typedef int SLDataType;//数据类型
typedef struct SeqList
{
  SLDataType* a;//指向动态开辟的数组
  int size;//记录储存多少个有效数据
  int capacity;//记录空间容量大小
}SL;

图解:

f35d157e008734fdbc5154ebac00dd69.png

3.2接口实现

3.2.1初始化顺序表

将有效数据个数和容量都初始化为0,并将指针指空

void SLInit(SL* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}

3.2.2打印顺序表

遍历打印数组中的内容

void SLprint(SL* ps)
{
  assert(ps);
  for (int i = 0; i < ps->size; ++i)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}

3.2.3 尾插

在数组尾部插入数据,首先要考虑扩容问题,再插入数据,同时元素个数增加

void SLPushBack(SL* ps, SLDataType x)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    //初始状态size=capacity=0的情况下先对容量开4个空间,后面就二倍开辟空间
    SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newCapacity);
    //先用一个指针tmp接收,防止扩容失败,成功扩容的话再将地址给到a
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    else
    {
      ps->a = tmp;//如果空间开辟成功,将地址给到a
      ps->capacity = newCapacity;//容量调整为新的容量大小
    }
  }
  ps->a[ps->size] = x;//尾部插入数据
  ps->size++;//元素个数增加
}

3.2.4尾删

删除数组尾部的数据,同时元素个数减小,要考虑数组为空不能删的情况

void SLPopBack(SL* ps)
{
  assert(ps);
  //断言数组为空的情况
  assert(ps->size > 0);
  ps->size--;
}

3.2.5扩容

由于多个接口需要检查数组容量,我们可以直接将判断扩容这一步骤封装成一个函数

void SLCheckCapacity(SL* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    //初始状态size=capacity=0的情况下先对容量开4个空间,后面就二倍开辟空间
    SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
    //先用一个指针tmp接收,防止扩容失败,成功扩容的话再将地址给到a
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    else
    {
      ps->a = tmp;//如果空间开辟成功,将地址给到a
      ps->capacity = newCapacity;//容量调整为新的容量大小
    }
  }
}

这样子我们就可以对上面的尾插接口进行简化了:

void SLPushBack(SL* ps, SLDataType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;
}

3.2.6头插

在数组尾部插入数据,首先要考虑扩容问题,再将数组的每个元素依次向后移动一位,再在第一个位置插入数据即可,同时元素个数增加

void SLPushFront(SL* ps, SLDataType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  //从最后一个数据开始依次向后挪动一位数据进行覆盖
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[0] = x;//头部插入数据
  ps->size++;//元素个数增加
}

3.2.7头删

从第二个数据开始将后面的数据依次向前移动一位进行覆盖即可达到头删的效果

void SLPopFront(SL* ps)
{
  assert(ps);
  assert(ps->size > 0);
  int begin = 1;
  //从第二个数据开始将后面的数据依次向前移动一位进行覆盖
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}

3.2.8任意位置插入数据

首先检查容量,再将目标位置之后的数据依次向后移动一位,再在此位置插入数据

void SLInsert(SL* ps, int pos, SLDataType x)
{
  assert(ps);
  assert(pos >= 0);
  assert(pos <= ps->size);
  SLCheckCapacity(ps);//检查容量
  //从最后一个数据到目标位置结束开始依次向后挪动一位数据覆盖
  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;
}

3.2.9 任意位置删除数据

将目标位置之后的数据依次向前移动一位进行覆盖即可达到删除效果

void SLErase(SL* ps, int pos)
{
  assert(ps);
  assert(pos >= 0);
  assert(pos < ps->size);
  //将目标位置之后的数据依次向前移动一位进行覆盖
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}

3.2.10查找数据位置

从该位置向后遍历数组,找到该数据就返回其下标,没找到就返回-1

int SLFind(SL* ps, SLDataType x, int begin)
{
  assert(ps);
  //从begin开始,找到返回下标,没找到返回-1
  for (int i = begin; i < ps->size; ++i)
  {
    if (ps->a[i] == x)
    {
      return i;
    }
  }
  return -1;
}

3.2.11销毁顺序表

释放顺序表的空间,并将指针指空,容量和数据个数置0 (只有在数组不为空的情况下才会销毁)

void SLDestroy(SL* ps)
{
  if (ps->a != NULL)
  {
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
  }
}

4.复用优化

既然我们写了任意位置插入删除的接口,那么我们是否可以将其复用给头插尾插,头删尾删呢?答案是可以的,下面我们就来对代码进行优化

4.1头插尾插优化

头插:

void SLPushFront(SL* ps, SLDataType x)
{
  //在下标为0的位置插入数据(首元素)
  SLInsert(ps, 0, x);
}

尾插:

void SLPushBack(SL* ps,SLDataType x)
{
  //在下标为size的位置插入数据(末尾元素的下一个)
  SLInsert(ps, ps->size, x);
}

4.2头删尾删优化

头删

void SLPopFront(SL* ps)
{
  //删除下标为0的数据(首元素)
  SLErase(ps, 0);
}

尾删

void SLPopBack(SL* ps)
{
  //删除下标为size-1的数据(末尾元素)
  SLErase(ps, ps->size - 1);
}

动态顺序表到这里就介绍结束了,期待大佬们的三连!

文章有写的不足或是错误的地方,欢迎评论或私信指出,我会在第一时间改正

目录
相关文章
|
10月前
|
存储 算法 程序员
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
210 0
|
10月前
|
C语言
C语言顺序表
C语言顺序表
67 0
|
4月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
116 3
|
5月前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
61 2
|
5月前
|
C语言
链式顺序表实现(C语言描述)
本文介绍了如何在C语言中实现链式顺序表,包括数据结构的定义、节点的创建、数据的插入和删除以及链表的打印和销毁。
66 2
|
5月前
|
C语言
顺序表数组法构建(C语言描述)
如何使用C语言通过数组方法构建有序顺序表,包括顺序表的创建、插入、删除和打印等。
42 2
|
6月前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表:顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表,使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作,并提供了具体代码示例。静态分配方式下顺序表的长度固定,而动态分配则可根据需求调整大小。此外,还总结了顺序表的优点,如随机访问效率高、存储密度大,以及缺点,如扩展不便和插入删除操作成本高等特点。
282 5
|
6月前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
9月前
|
存储 C语言
数据结构——顺序表(C语言版)
数据结构——顺序表(C语言版)
82 5
|
10月前
|
存储 C语言
C语言实验-动态顺序表实现简易通讯录(二)
在这个C语言实验中,你将实现一个简单的通讯录,它使用动态顺序表来存储联系人信息。
77 2