【数据结构】顺序表实现超详解(保姆级教程)

简介: 顺序表以及顺序表的接口实现注:保姆级教程,相信你一定会的~

前言



本章主要讲解:


顺序表以及顺序表的接口实现

注:保姆级教程,相信你一定会的~



顺序表


顺序表是线性标的一种


  • 概念:


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


  • 分类:


静态顺序表


使用定长数组存储元素


参考代码:

//静态循序表
#define CAPACITY 100
typedef struct SeqList
{
  SLDateType data[CAPACITY];//动态开辟指向其地址
  size_t size;//已经使用的数量
}SeqList;

图示:

0.png



动态顺序表:


使用动态开辟的数组存储


  • 参考代码:


//动态顺序表
typedef struct SeqList
{
  SLDateType* data;//动态开辟指向其地址
  size_t size;//已经使用的数量
  size_t capacity; //开辟空间的总大小(容量)
}SeqList;


1.png


接口实现



  • 静态顺序表

只适用于确定知道需要存多少数据的场景

局限:静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用


  • 动态顺序表:

现实使用时多采用动态顺序表

优势:需要多少用多少


注:下面我们着重实现动态顺序表(静态顺序表可以依法炮制~)


各项功能


顺序表的增删查改接口


//默认开辟大小
#define DEFAULT_SZ 4
//设定默认数据类型
typedef int SLDateType;
//动态顺序表
typedef struct SeqList
{
  SLDateType* data;//动态开辟指向其地址
  size_t size;//已经使用的数量
  size_t capacity; //开辟空间的总大小(容量)
}SeqList;
// 对数据的管理:增删查改 
//初始化
void SeqListInit(SeqList* ps);
//释放
void SeqListDestory(SeqList* ps);
//打印(展示)
void SeqListPrint(SeqList* ps);
//尾插
void SeqListPushBack(SeqList* ps, SLDateType x);
//头插
void SeqListPushFront(SeqList* ps, SLDateType x);
//前删
void SeqListPopFront(SeqList* ps);
//尾删
void SeqListPopBack(SeqList* ps);
// 顺序表查找x的位置
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos);


接口详解



顺序表初始化


比较简单


  • 参考代码:
//初始化顺序表
void SeqListInit(SeqList* ps)//传入链表地址便于修改
{
  ps->data = NULL;
  ps->capacity = 0;
  ps->size = 0;
  return;
}



顺序表释放


动态顺序表是动态开辟的空间,结束时需要进行释放,避免造成内存泄漏


  • 参考代码:
//摧毁释放顺序表
void SeqListDestory(SeqList* ps)
{
  free(ps->data);
//记得置空地址
  ps = NULL;
  return;
}


顺序表展示


  • 注意:
  1. 当顺序表为空时不打印


//展示顺序表
void SeqListPrint(SeqList* ps)
{
//暴力断言(ps不为空)
  assert(ps->data);
//使用指针打印结构体内保存的数据
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d\t", ps->data[i]);
  }
  return;
}


顺序表容量检查


  • 注意:
  1. 每当要增加数据时,都需要考虑空间是否使用完毕
  2. 如果使用完毕则需要考虑增容,增容为原来的两倍(避免频繁扩容)
  3. 增容后更新记录容量大小

注:这里我们考虑到有许多地方要检查是否增容,为了方便将它封装成一个函数


参考代码:

//顺序表容量判断
void SeqListCheak(SeqList* ps)
{
  int newcapacity;
//使用完毕时进行判断
  if (ps->size == ps->capacity)
  {
//如果为容量为0,则开辟默认大小的空间;否则扩容为原来的两倍空间
    newcapacity = ps->capacity == 0 ? DEFAULT_SZ : ps->capacity* 2;
//当data为NULL时,realloc的功能和malloc一致(申请开辟空间)
    ps->data = realloc(ps->data, newcapacity);
//判断是否扩容(开辟)空间成功
    if (ps == NULL)
    {
//为开辟(扩容)成功,则打印对应的错误原因,并结束进程
      perror("realloc:");
      exit(1);
    }
  }
//成功则更新记录容量的大小
  ps->capacity = newcapacity;
  return;
}


顺序表数据尾插


  • 注意:
  1. 插入数据考虑扩容
  2. 尾插后更新记录使用数量


  • 参考代码:
//顺序表数据尾插
void SeqListPushBack(SeqList* ps, SLDateType x)
{
//容量检查
  SeqListCheak(ps);
  ps->data[ps->size]=x;
//更新使用数量
  ps->size++;
  printf("顺序表尾插数据成功!\n");
  return;
}


顺序表数据头插

  • 注意:
  1. 插入数据考虑扩容
  2. 头插从后开始移动数据(避免数据覆盖)
  3. 尾插后更新记录使用数量
  • 参考代码:
//顺序表头插数据
void SeqListPushFront(SeqList* ps, SLDateType x)
{
  //插入数据考虑扩容
  SeqListCheak(ps);
  for (int i = ps->size - 1; i >= 0; i--)
  {
    //头插从后开始移动数据(避免数据覆盖)
    ps->data[i + 1] = ps->data[i];
  }
  ps->data[0]=x;
  //尾插后更新记录使用数量
  ps->size++;
  printf("顺序表头插数据成功!\n");
  return;
}


顺序表数据前删


  • 注意:


  1. 没有数据或者顺序表为空无法删除
  2. 前删后从前往后移动数据(避免覆盖)
  3. 更新记录使用的数量


参考代码:

//顺序表数据前删
void SeqListPopFront(SeqList* ps)
{
  //暴力断言(也可以选择if判断语句)
  assert(ps->data||ps->size);
  //从前往后移动数据(避免覆盖)
  for (int i = 0; i+1<ps->size; i++)
  {
    ps->data[i] = ps->data[i+1];
  }
  //更新记录使用的数量
  ps->size--;
  printf("顺序表前删数据成功!\n");
  return;
}


顺序表数据尾删


  • 注意:
  1. 没有数据或者顺序表为空无法删除
  2. 尾删数据只要记录使用数量的变量自减就行了


参考代码:

//顺序表尾删数据
void SeqListPopBack(SeqList* ps)
{
  assert(ps->data||ps->size);
  ps->size--;
  printf("顺序表尾删数据成功!\n");
  return;
}


顺序表数据查找


  • 注意:
  1. 没有数据或者顺序表为空无法查找
  2. 遍历查找,找到则返回下标,否则返回-1


  • 参考代码:


// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{
//没有数据或者顺序表为空无法查找
  assert(ps->data||ps->size);
//遍历查找,找到则返回下标,否则返回-1
  int pos=-1;
  for (int i = 0; i < ps->size; i++)
  {
    if (ps->data[i] == x)
    {
            pos=i;
      printf("数据查到了,下标是:%d\n", pos);
      return pos;
    }
  }
  printf("链表数据未查到!\n");
  return pos;
}

顺序表指定位置插入数据


  • 注意:
  1. 检查是否扩容
  2. 插入前先移动数据
  3. 插入后更新记录使用数量的大小
  • 参考代码:
//顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
  SeqListCheak(ps);
  for (int i = ps->size; i >= pos; i++)
  {
    ps->data[i] = ps->data[i - 1];
  }
  printf("请输入要插入的数:");
  scanf("%d", &ps->data[pos]);
  ps->size++;
  printf("链表插入数据成功!\n");
  return;
}


以上基本上就已经讲解顺序表完毕了,别忘了留个三连再走~~

相关文章
|
3月前
|
存储 编译器 C语言
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
数据结构-顺序表详解(看这篇就足够了,哈哈哈)
74 2
|
10天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
26 5
|
24天前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
2月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
2月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
97 3
|
2月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
3月前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
55 6
|
3月前
|
存储
数据结构(顺序表)
数据结构(顺序表)
34 0
|
3月前
|
存储 算法
【数据结构】新篇章 -- 顺序表
【数据结构】新篇章 -- 顺序表
26 0
|
3月前
|
存储 测试技术
探索数据结构:顺序表的实现与应用
探索数据结构:顺序表的实现与应用

热门文章

最新文章