【编织时空一：探究顺序表与链表的数据之旅】（上）

2024-01-22 29

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【编织时空一：探究顺序表与链表的数据之旅】

本章重点

线性表

顺序表

顺序表OJ题

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

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

2.顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表中的元素在内存中是相邻存储的，每个元素都有一个对应的索引来标识其在顺序表中的位置。顺序表支持随机访问，可以通过索引直接访问任意位置的元素。

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。

静态顺序表的缺点：

固定大小：静态顺序表的大小在创建时被固定下来，无法动态地扩展或缩小。这意味着一旦初始化了静态顺序表，其容量就无法改变。如果需要存储的元素数量超过初始分配的容量，可能需要重新分配更大的空间并手动进行数据迁移。

内存浪费：如果静态顺序表的容量设置过大，但实际存储的元素数量较少，会导致内存浪费。因为未使用的部分空间也会被保留，占用了额外的内存。

不灵活：由于容量固定，静态顺序表可能无法适应动态变化的数据需求。当需要的容量超过初始设置时，可能需要重新设计或重写代码。

初始化成本：静态顺序表在初始化时需要分配固定大小的内存空间，而如果无法预估元素的最终数量，就需要进行适当的空间规划，这可能增加设计和开发的成本。

2. 动态顺序表：使用动态开辟的数组存储。

3.顺序表接口实现

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
  SLDataType* a;  // 指向动态开辟的数组
  int size;       // 有效数据个数
  int capicity;   // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 
// 顺序表初始化
void SeqListInit(SeqList * s);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* s);
// 顺序表尾插
void SeqListPushBack(SeqList* s, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* s);
// 顺序表头插
void SeqListPushFront(SeqList* s, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* s);
// 顺序表查找
int SeqListFind(SeqList* s, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* s, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* s, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* s);
// 顺序表打印
void SeqListPrint(SeqList* s);

顺序表初始化：void SeqListInit(SeqList * s);

代码中存在一些问题，主要是关于C语言中函数参数传递方式的错误理解。C语言中的参数传递是值传递，意味着函数接收的是参数的副本，而不是原始的数据。因此，当你在 SeqListInit 函数中修改 s 的值时，实际上只是修改了传递进来的副本，而不会影响原始的 s。为了解决这个问题，需要通过指针传递来修改原始数据。

// 顺序表初始化
void SeqListInit(SeqList* s)
{
  s->a = NULL;
  s->size = 0;
  s->capicity = 0;
}

但是，我们需要在初始的时候就开辟一些空间，这样更方便数据存储，不用一上来就扩容。

// 顺序表初始化
void SeqListInit(SeqList* s)
{
  s->a = (SeqList*)malloc(sizeof(SLDataType) * 4);
  if (s->a == NULL)
  {
    perror("malloc");
    //return;只是该函数退出，程序依然运行
    exit(-1);//程序退出为-1
  }
  s->size = 0;
  s->capicity = 4;
}

malloc函数：malloc函数的返回值是void *，使用malloc函数要在返回的时候转化为我们需要的类型。malloc(sizeof(SLDataType) * 4)这代表的是申请了4个SLDataType类型大小的空间。

malloc函数的使用要引头文件#include。

分配成功则返回指向被分配内存的指针，分配失败则返回空指针NULL。

检查空间，如果满了，进行增容：void CheckCapacity(SeqList* s);

// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* s)
{
  //满了需要扩容
  if (s->size == s->capicity)
  {
    //realloc,第二个参数是新空间的大小，不是要扩多少
    SLDataType* temp = (SLDataType*)realloc(s->a, s->capicity * 2 * sizeof(SLDataType));//扩容2倍
    if (temp == NULL)
    {
      perror("realloc");
      exit(-1);
    }
    s->a = temp;
    s->capicity *= 2;
  }
}

realloc函数：realloc函数的返回值是void *，使用realloc函数要在返回的时候转化为我们需要的类型。realloc(s->a, s->capicity * 2 * sizeof(SLDataType))这代表的是申请了s->capicity * 2 个SLDataTypet型大小的空间。我这里是扩充2倍空间。同时realloc函数,第二个参数是新空间的大小，不是要扩多少。

realloc函数的使用要引头文件#include。

分配成功则返回指向被分配内存的指针，分配失败则返回空指针NULL。

顺序表尾插：void SeqListPushBack(SeqList* s, SLDataType x);

// 顺序表尾插
void SeqListPushBack(SeqList* s, SLDataType x)
{
  CheckCapacity(s);
  s->a[s->size] = x;//尾插数字
  s->size++;//尾插后有效数字+1
}

顺序表尾删：void SeqListPopBack(SeqList* s);

// 顺序表尾删
void SeqListPopBack(SeqList* s)
{
  s->a[s->size - 1] = 0;
  s->size--;
}

这样写有一个问题，万一要删除的数字就是0，你还把size-1的位置设置为0，就没有意义了，我们发现只用将size--就行，有效数字就会少一个，打印数据自然会少一个，下次再尾插原本的数据就会被覆盖，原数字也自然就被删除了。

// 顺序表尾删
void SeqListPopBack(SeqList* s)
{
  //s->a[s->size - 1] = 0;
  s->size--;
}

这样写是不是还有问题，假设删掉的数字比原本数字多怎么办？程序直接崩了，这样会出现越界访问的问题

// 顺序表尾删
void SeqListPopBack(SeqList* s)
{
  //方法一：
  if(s->size == 0)//保证不会被越界
  {
    return;
  }
  //s->a[s->size - 1] = 0;
  s->size--;
  //方法二：
  assert(s->size > 0);
  //s->a[s->size - 1] = 0;
  s->size--;
}

顺序表头插：void SeqListPushFront(SeqList* s, SLDataType x);

// 顺序表头插
void SeqListPushFront(SeqList* s, SLDataType x)
{
  CheckCapacity(s);
  //挪动数据
  int end = s->size - 1;//最后一个数据
  while (end >= 0)
  {
    s->a[end + 1] = s->a[end];
    end--;
  }
  s->a[0] = x;
  s->size++;
}

顺序表头删：void SeqListPopFront(SeqList* s);

// 顺序表头删
void SeqListPopFront(SeqList* s)
{
  assert(s->size > 0);//防止越界
  int begin = 0;
  while (begin < s->size - 1)
  {
    s->a[begin] = s->a[begin + 1];
    begin++;
  }
  s->size--;
}

【编织时空一：探究顺序表与链表的数据之旅】（下）：https://developer.aliyun.com/article/1424868