数据结构(一):顺序表详解

简介: 数据结构(一):顺序表详解

在正式介绍顺序表之前,我们有必要先了解一个名词:线性表。

线性表:

线性表是,具有n个相同特性的数据元素的有限序列。常见的线性表:顺序表、链表、栈、队列、数组、字符串...

线性表在逻辑上是线性结构,但在物理结构上并不一定是连续的。


1. 顺序表概念

顺序表是用一段物理地址连续的储存单元、依次存储数据元素的线性结构,一般情况下采用数组存储。

2. 顺序表定义

typedef int SLDataType;// 顺序表数据类型
typedef struct SeqList
{
  SLDataType* arr; // 指向动态开辟的数组
  int size;        // 有效数据个数
  int capacity;    // 容量
}SL;

3. 顺序表的初始化

顺序表的初始化,是使用 动态内存管理 开辟空间构造一个空的顺序表

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define DefaultCapacity 4 // 默认初始化空间大小
void SLInit(SL* ps)
{
  assert(ps);
  SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType) * DefaultCapacity);
  if (tmp == NULL)
  {
    perror("malloc");
    exit(-1);
  }
  ps->arr = tmp;
  ps->capacity = DefaultCapacity;
  ps->size = 0;
}

4. 在pos位置插入元素

在pos位置插入数据之前,要检查动态顺序表的容量是否足够 ,

不够则利用 realloc函数 开辟一块更大的空间给顺序表。

检查容量/扩容:
void SLCapacityCheck(SL* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
    SLDataType* tmp = (SLDataType*)realloc(ps->arr, ps->capacity * 2 * sizeof(SLDataType));
    if (tmp == NULL)
    {
      perror("realloc");
      exit(-1);
    }
    ps->capacity *= 2;
    ps->arr = tmp;
  }
}
插入:
void SLInsert(SL* ps, int pos, SLDataType x)
{
  assert(ps);
  SLCapacityCheck(ps);
  for (int i = ps->size - 1; i >= pos; i--)
  {
    ps->arr[i + 1] = ps->arr[i];
  }
  ps->arr[pos] = x;
    ps->size++;
}

5. 删除pos位置元素

void SLErase(SL* ps, int pos)
{
  assert(ps);
  for (int i = pos + 1; i < ps->size; i++)
  {
    ps->arr[i - 1] = ps->arr[i];
  }
  ps->size--;
}

6. 顺序表查找(按值查找)

int SLFind(SL* ps, SLDataType x)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    if (ps->arr[i] == x)
      return i;
  }
  // 找不到所查找的元素
  return -1;
}

在主函数中使用 SLFind函数 时,应检验 “返回值” 是否为非 -1,再使用

7. 顺序表的打印

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

8. 顺序表销毁

void SLDestroy(SL* ps)
{
  assert(ps);
  free(ps->arr);
  ps->capacity = 0;
  ps->size = 0;
}

销毁 arr 所指向的空间,将空间还给操作系统。

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

热门文章

最新文章