【数据结构】顺序表的增删查改 (C语言实现)(1)

简介: 【数据结构】顺序表的增删查改 (C语言实现)(1)

一、线性表

是什么线性表

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

线性表的结构

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

2020062310470442.png

二、顺序表

1、什么是顺序表

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

简单来说,顺序表就是数组,只是要求数组里面的元素必须连续存储而已。

2、顺序表的分类

顺序一般分为两类:静态顺序表和动态顺序表。

静态顺序表:采用定长数组来存储元素。

#define MAX 1000  //数组的最大长度
typedef int SLDtataType;  //重命名数据类型
typedef struct SeqList
{
  SLDtataType data[MAX];  //使用定长数组来存储数据
  size_t size;  //有效数据的个数
}SL;

动态顺序表:使用动态开辟的数据来存储元素。

typedef int SLDataType;  //将数据类型重命名为SLDataType
typedef struct SeqList
{
  SLDataType* data;     //对应数据类型的指针,用来指向动态开辟的空间
  size_t size;          //记录当前有效数据的个数
  size_t capacity;      //记录当前容量,不够就增容
}SL;

两种顺序表的对比:相较于动态顺序表,静态顺序表存在很大的缺陷,那就是空间问题:当我们数据量很大时给定的空间可能不够用,但我们数据量比较小时,给定的空间又可能过大,造成空间浪费,即静态顺序表只适用于确定知道需要存多少数据的场景;所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,而静态顺序表很少使用。下面我们用C语言来模拟实现一个动态的顺序表。

三、动态顺序表的实现

1、结构的定义

#define DEF_SIZE 5       //初始容量
#define CRE_SIZE 2       //一次扩容的倍数
typedef int SLDataType;  //将数据类型重命名为SLDataType
typedef struct SeqList
{
  SLDataType* data;  //对应数据类型的指针,用来指向动态开辟的空间
  size_t size;          //记录当前有效数据的个数
  size_t capacity;      //记录当前容量,不够就增容
}SL;

如上:我们将要管理的数据类型重命名为SLDateType,这样以后当我们要用此顺序表管理其他数据类型时,我们就只需要改动这一个地方。


其次,相较于静态顺序表,我们的结构体多了一个参数 – capacity,我们用它来记录顺序表当前的容量,当当前的有效数据个数size与它相等时,我们就进行扩容;由于数据个数和顺序表的容量都不可能小于0,所以我们将其定义为size_t的。


最后就是关于初始容量和每次扩增倍数的问题,这里把初始容量设定为5,然后把扩增倍数设定为2,即我们的顺序表每次扩容两倍。

2、顺序表的初始化

在初始化函数中,我们把size和capacity都置为相应大小,并且为data指针动态开辟一块空间,用于存储数据。

//初始化顺序表
void SeqListInit(SL* psl)
{
  assert(psl);  //断言:防止psl为空
  psl->data = (SLDataType*)calloc(DEF_SIZE, sizeof(SLDataType));  //开辟默认大小的空间并初始化
  if (psl == NULL)  //判空
  {
    perror("calloc fail");  //打印错误信息
    return;
  }
  psl->size = 0;
  psl->capacity = DEF_SIZE;
}

3、检查容量

在检查容量的函数中,当我们结构体中的size和capacity相等时,我们就扩容,在扩容时我们要注意不要直接用data指针来接收realloc函数的返回值,避免扩容失败导致data指针找不到之前管理的空间,从而造成内存泄漏。

//检查容量(增容)
void CheckCapacity(SL* psl)
{
  assert(psl);  //断言:防止psl为空
  if (psl->size == psl->capacity)  //当数据个数和容量相等时扩容
  {
    //将realloc的返回值交由一个临时变量保存,防止扩容失败丢失原来空间的地址
    SLDataType* ptr = (SLDataType*)realloc(psl->data, psl->capacity * CRE_SIZE * sizeof(SLDataType));
    if (ptr == NULL)  //判空
    {
      perror("realloc fail");
      return;
    }
    psl->data = ptr;
    psl->capacity *= CRE_SIZE;  //增加容量
  }
}

4、在头部插入数据

在头部插入数据时,我们需要先将顺序表中的数据整体向后挪动一位,然后在顺序表的开头插入;在插入完成后记得要让size++。

//在头部插入数据
void SeqListPushFront(SL* psl, SLDataType x)
{
  assert(psl);  //判空
  CheckCapacity(psl);  //检查容量
  int i = 0;
  for (i = psl->size - 1; i >= 0; i--)
  {
    psl->data[i + 1] = psl->data[i];  //将数据整体向后移
  }
  psl->data[0] = x;  //插入数据
  psl->size++;
}

5、在尾部插入数据

在尾部插入数据很简单,直接插入就行。

//在尾部插入数据
void SeqListPushBack(SL* psl, SLDataType x)
{
  assert(psl);  //判空
  CheckCapacity(psl);  //检查容量
  psl->data[psl->size] = x;  //插入数据
  psl->size++;
}

6、在指定位置插入数据

在此函数中,我们需要先将pos及其之后的元素整体向后挪动一位,然后再在pos处插入数据。

//在任意位置插入数据
void SeqListInsert(SL* psl, size_t pos, SLDataType x)
{
  assert(psl);
  assert(pos <= psl->size);  //断言 因为可能会在尾部插入数据,所以pos可以等于size
  CheckCapacity(psl);  //检查容量
  size_t end = psl->size;
  while (end > pos)  //把pos及以后的数据向后挪动一位
  {
    psl->data[end] = psl->data[end - 1];
    --end;
  }
  psl->data[pos] = x;  //插入数据
  ++psl->size;
}

由于尾插和头插也可以通过调用 SeqListInsret 函数实现,所以我们可以对头插和尾插函数进行改造,以此来简化代码:

在头部插入数据

//在头部插入数据
void SeqListPushFront(SL* psl, SLDataType x)
{
  assert(psl);
  SeqListInsert(psl, 0, x);  //相当于在0位置处插入数据
}

在尾部插入数据

//在尾部删除数据
void SeqListPopBack(SL* psl)
{
  assert(psl);
  SeqListErase(psl, psl->size - 1);  //相当于在size-1处插入数据(数组下标从0开始)
}

7、在尾部删除数据

删除尾部的数据很简单,我们只需要将size–即可,并不需要对其进行改动,因为我们下一次插入数据时会直接将原来空间中的数据覆盖掉。

//在尾部删除数据
void SeqListPopBack(SL* psl)
{
  assert(psl);
  assert(psl->size);
  psl->size--;  //如果尾部有数据,直接让size--即可
}

8、在头部删除数据

在头部删除数据,我们只需要将顺序表中的数据整体向前挪动一位,然后将size–即可。

//在头部删除数据
void SeqListPopFront(SL* psl)
{
  assert(psl);
  assert(psl->size);
  size_t i = 0;
  for (i = 0; i < psl->size - 1; i++)
  {
    psl->data[i] = psl->data[i + 1];  //让表中的数据依次往前移
  }
  psl->size--;
}

9、删除指定位置的数据

删除指定位置数据,我们需要将pos后面的数据整体向前挪动一位,然后让size–。

//删除指定位置的数据
void SeqListErase(SL* psl, size_t pos)
{
  assert(psl);
  assert(pos < psl->size);
  size_t i = 0;
  for (i = pos; i < psl->size - 1; i++)
  {
    psl->data[i] = psl->data[i + 1];
  }
  psl->size--;
}

和上面的插入数据一样,我们也可以通过调用 SeqListErase 函数来实现数据的头删和尾删。

在头部删除数据

//在头部删除数据
void SeqListPopFront(SL* psl)
{
  assert(psl);
  SeqListErase(psl, 0);  //相当于删除0下标处的数据
}

在尾部删除数据

//在尾部删除数据
void SeqListPopBack(SL* psl)
{
  assert(psl);
  SeqListErase(psl, psl->size - 1);  //相当于删除size-1下标处的数据
}

面试题:删除数据是否要缩容?

我们知道,插入数据空间不够时我们要增容,那么删除数据达到一定的数量后我们是否要缩容呢?答案是不用缩容。原因如下:


第一:我们缩容之后插入数据又需要重新增容,而增容是有代价的,会降低程序的效率。我们知道 realloc 函数扩容分为两种情况,一种是原地扩,即当原来的空间后面有足够的空闲空间时,操作系统会直接将那一块空间交由我们使用,这种情况对效率影响不大;另一种是异地扩,即当原来空间后面没有足够的的空间开辟时,操作系统会在另外空间足够的地方为我们开辟一块新的空间,这时操作系统需要先将我们原来空间中的数据拷贝到新空间中,再将原来的空间释放掉,这种情况对效率的影响就比较大了。


第二:缩容也是有代价的。其实缩容和扩容的过程是一样的,都分为原地和异地,会对程序效率造成影响。


第三:顺序表申请的是一块连续的空间,而free函数数并不能释放连续空间的一部分,只能全部一起释放,所以这里即使想释放也是做不到的。


所以综合前面三个因素考虑,顺序表删除数据不会缩容;这是我们典型的以空间换时间的做法。

10、查找数据

当我们找到该元素时,我们返回元素的下标;当该元素不存在时,我们返回一个无意义的值。(如-1)

//查找数据
int SeqListFind(const SL* psl, SLDataType x)
{
  assert(psl);
  int i = 0;
  for (i = 0; i < (int)psl->size; i++)
  {
    if (psl->data[i] == x)
      return i;  //找到元素所在返回下标
  }
  return -1;  //找不到返回-1(一个无效下标)
}

11、修改指定位置的数据

//修改指定位置的数据
void SeqListModify(SL* psl, size_t pos, SLDataType x)
{
  assert(psl);
  assert(pos < psl->size);  //断言
  psl->data[pos] = x;  //修改数据
}

12、打印顺序表中的数据

//打印顺序表中的数据
void SeqListPrint(const SL* psl)
{
  assert(psl);  //判空
  size_t i = 0;
  for (i = 0; i < psl->size; i++)
  {
    printf("%d ", psl->data[i]);
  }
  printf("\n");
}

13、顺序表的销毁

在销毁顺序表的时候我们一定要记得将前面动态开辟的空间释放掉,防止内存泄漏。

//销毁顺序表
void SeqListDestory(SL* psl)
{
  assert(psl);  //断言:防止psl为空
  free(psl->data);    //释放(避免内存泄漏)
  psl->data = NULL;   //置空(避免野指针)
  psl->size = 0;
  psl->capacity = 0;
}





相关文章
|
1天前
|
存储
数据结构1——顺序表
数据结构1——顺序表
7 1
|
24天前
|
存储 Java 程序员
【数据结构】初识集合&深入剖析顺序表(Arraylist)
Java集合框架主要由接口、实现类及迭代器组成,包括Collection和Map两大类。Collection涵盖List(有序、可重复)、Set(无序、不可重复),Map则由键值对构成。集合通过接口定义基本操作,具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复,Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现,各有适用场景。其中ArrayList实现了动态数组功能,可根据需求自动调整大小。
31 11
|
2天前
|
存储 C语言 索引
数据结构--顺序表
数据结构--顺序表
|
2天前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
6 0
|
1月前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
1月前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
3天前
|
存储 缓存
【初阶数据结构】深入解析顺序表:探索底层逻辑
【初阶数据结构】深入解析顺序表:探索底层逻辑
|
1月前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
2天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
77 64
|
11天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用