1. AI技术聚合首页
  2. IT

顺序表基本操作全面解析

社会演员多 • • IT • 阅读 54

文章目录

  • 1.线性表
  • 2.顺序表分类
    • 2.1 静态顺序表
    • 2.2 动态顺序表
  • 3. 顺序表各接口实现
    • 1. 定义结构体`(Seqlist)`
    • 2. 结构体初始化`(SLInit)`
    • 3.检查容量 `(SLCheckCapacity)`
    • 4.打印数据 `(SLPrintf)`
    • 5.插入操作
      • 5.1 从数据头部插入`(SLPushFront)`
      • 5.2 从数据尾部插入`(SLPushBack)`
      • 5.3 从任意下标位置的插入`(SLInsert)`
    • 6.删除操作
      • 6.1 从数据头部删除`(SLPopFront)`
      • 6.2 从数据尾部删除`(SLPopBack)`
      • 6.3 从任意下标位置的删除`(SLErase)`
    • 7 销毁操作 `(SLDestroy)`
  • 4.完整代码
    • 4.1 SeqList.h文件
    • 4.2 SeqList.c文件
    • 4.3 Test.c文件

1.线性表

1.线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串
2.线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的一类数据结构的集合

2.顺序表分类

顺序表和数组的区别：
顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

2.1 静态顺序表

静态顺序表概念：使用定长数组存储元素
缺点是定义空间小了不够用，定义大了浪费，不好把控。

2.2 动态顺序表

动态顺序表概念：使用动态开辟的数组存储。
动态顺序表 根据自己的需求调整大小，

3. 顺序表各接口实现

首先建立3个文件
1.SeqList.h头文件,用来声明函数
2.SeqList.c文件，用来定义函数
3.Test.c文件，用来测试函数

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

1. 定义结构体(Seqlist)

在SeqList.h头文件中

typedef int SLDataType;

typedef struct Seqlist
{
  SLDataType* a;
  int size;       // 有效数据
  int capacity;   // 空间容量
}SL;

2. 结构体初始化(SLInit)

注意下述代码皆是：
在SeqList.h头文件中定义函数
在SeqList.c文件中实现函数
在Test.c文件中测试函数

SeqList.h文件中
定义函数：

SeqList.c文件中
实现函数：

 void SLInit(SL *ps)     // 数据表初始化
{
  assert(ps);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}

Test.c文件中
测试函数：

int main()
{
  SL s1;
  SLInit(&s1);
  return 0;
}

调试结果：

3.检查容量 (SLCheckCapacity)

定义函数：

实现函数：

void SLCheckCapacity(SL* ps)  // 检查内存是否足够，不够就扩容。
{
	//一般情况为了避免频繁插入数据而增容，或者一下开辟很大的空间，我们一般是每次增容2倍
	assert(ps);
    if (ps->size == ps->capacity)
    {
      int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
      SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newCapacity);
      if (tmp == NULL)
      {
        perror("realloc fail");
        return;
      }
      ps->a = tmp;
      ps->capacity = newCapacity;
    }
}

测试函数：

int main()
{
  SL s1;
  SLInit(&s1);
  SLCheckCapacity(&s1);
  return 0;
}

调试结果：

4.打印数据 (SLPrintf)

定义函数：

实现函数：

void SLPrintf(SL* ps)   // 数据表打印
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}

5.插入操作

5.1 从数据头部插入(SLPushFront)

定义函数：

实现函数：

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++;
}

动图解析：

测试函数结果：

5.2 从数据尾部插入(SLPushBack)

定义函数：

实现函数：

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

动图解析：

测试函数结果：

5.3 从任意下标位置的插入(SLInsert)

定义函数：

实现函数：

void SLInsert(SL* ps, int pos, SLDataType x)  // 任意下标位置的插入
{
  assert(ps);
  assert(pos >= 0 && 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++;
}

动图解析：

测试函数结果：

6.删除操作

6.1 从数据头部删除(SLPopFront)

定义函数：

实现函数：

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--;
}

动图解析：

测试函数结果：

6.2 从数据尾部删除(SLPopBack)

定义函数：

实现函数：

void SLPopBack(SL* ps)  // 尾删
{
  assert(ps);
  assert(ps->size>0);
  ps->size--;
}

动图解析：

测试函数结果：

6.3 从任意下标位置的删除(SLErase)

定义函数：

实现函数：

void SLErase(SL* ps, int pos)    // 任意下标位置的删除
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);   
  // 这里删除不能用等于ps->size,ps->size看作下标的话相当于下标的最后一个位置+1
  
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}

动图解析：

测试函数结果：

7 销毁操作 (SLDestroy)

定义函数：

实现函数：

void SLDestroy(SL* ps)  // 数据表销毁
{
  assert(ps);
  if (ps->a != NULL)
  {
    free(ps->a);
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;
  }
}

4.完整代码

4.1 SeqList.h文件

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;

typedef struct Seqlist
{
  SLDataType* a;
  int size;       // 有效数据
  int capacity;   // 空间容量
}SL;

void SLInit(SL *ps);    // 数据表初始化
void SLDestroy(SL *ps); // 数据表销毁

void SLPushFront(SL* ps, SLDataType x); // 头插
void SLPushBack(SL *ps ,SLDataType x);  // 尾插

void SLPopFront(SL* ps);  // 头删
void SLPopBack(SL* ps);   // 尾删


void SLCheckCapacity(SL* ps); // 检查内存是否足够，不够就扩容。
void SLPrintf(SL* ps);  // 数据表打印

void SLInsert(SL* ps, int pos, SLDataType x);  //任意下标位置的插入
void SLErase(SL* ps, int pos);  //任意下标位置的删除

4.2 SeqList.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

void SLCheckCapacity(SL* ps)  // 检查内存是否足够，不够就扩容。
{
    assert(ps);
    if (ps->size == ps->capacity)
    {
      int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
      SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newCapacity);
      if (tmp == NULL)
      {
        perror("realloc fail");
        return;
      }
      ps->a = tmp;
      ps->capacity = newCapacity;
    }
}

void SLPrintf(SL* ps)   // 数据表打印
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}


void SLInit(SL *ps)     // 数据表初始化
{
  assert(ps);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}

void SLDestroy(SL* ps)  // 数据表销毁
{
  assert(ps);
  if (ps->a != NULL)
  {
    free(ps->a);
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;
  }
}

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++;
}

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



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--;
}

void SLPopBack(SL* ps)  // 尾删
{
  assert(ps);
  assert(ps->size>0);
  ps->size--;
}

// pos是下标
void SLInsert(SL* ps, int pos, SLDataType x)  // 任意下标位置的插入
{
  assert(ps);
  assert(pos >= 0 && 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++;
}

void SLErase(SL* ps, int pos)    // 任意下标位置的删除
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);   // 这里删除不能用等于ps->size,ps->size看作下标的话相当于下标的最后一个位置+1
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}

4.3 Test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

void TestSL1()  // 头插,尾插
{
  printf("TestSL1:\n");
  SL s1;
  SLInit(&s1);
  SLPushFront(&s1, 10);
  SLPushBack(&s1, 30);
  SLPrintf(&s1);  
}

void TestSL2()  // 头删,尾删
{
  printf("TestSL2:\n");
  SL s1;
  SLInit(&s1);
  SLPushFront(&s1, 10);
  SLPushBack(&s1, 30);
  SLPushFront(&s1, 10);
  SLPushBack(&s1, 30);
  SLPrintf(&s1);
  SLPopBack(&s1);
  SLPopFront(&s1);
  SLPrintf(&s1);
}

void TestSL3()//任意下标位置的插入,删除测试
{
  printf("TestSL3:\n");
  SL s1;
  SLInit(&s1);
  SLPushFront(&s1, 10);
  SLPushBack(&s1, 30);
  SLPrintf(&s1);
  SLInsert(&s1, 1, 520);
  SLPrintf(&s1);
  SLErase(&s1, 2);
  SLPrintf(&s1);
}

int main()
{
  TestSL1();
  TestSL2();
  TestSL3();
}

运行结果如下：

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
社会演员多的头像社会演员多普通用户
0
上一篇 2023年12月13日
下一篇 2023年12月13日

相关推荐