数据结构：第八节-线性表的顺序存储（上）

Cpp入门到精通 2024-05-11

323

点击蓝字

山月

关注我们

第八节线性表的顺序存储（上）

我们上一节介绍了线性表的基本概念以及线性表有两种存储结构，分别是顺序存储结构和链式存储结构，这节我们先来具体分析线性表的顺序存储结构。线性表的顺序存储是指使用数组或类似数组的方式来存储线性表中的元素，使得元素在内存中是连续存储的。顺序存储适用于需要随机访问和知道元素位置的场景。

在C++中，我们通常使用内置数组(arr),vector容器或array容器来作为顺序存储结构的线性表容器。顺序存储的线性表又称为顺序表。

#include<iostream>
using namespace std;
#include<vector>
#include<array>
int main() {
  //1.用vector容器表示顺序表
  vector<int>v1 = { 1,2,3,4 };
  //2.用array容器表示顺序表
  array<int,4>arr1 = { 1,2,3,4 };
  //3.用内置数组表示顺序表
  int arr[4] = {1,2,3,4};
  return 0;
}

我们最常用且推荐的顺序存储容器是vector，它提供了高效的动态数组实现，适用于大多数线性表的顺序存储需求。

那么我们如何去计算顺序表中元素的存储位置?

在顺序表中，元素不仅在逻辑上相邻，也在物理上相邻，所以元素的存储位置可以通过索引来计算。

假设顺序表中的元素按照索引从 0 开始递增，存储在数组 v1 中，存储位置的计算公式如下：

对于顺序表中的第i 个元素（i 从 0 开始计数），其存储位置（即在数组中的索引）可以通过以下公式计算：

存储位置=基地址+i×单个元素大小存储位置=基地址+i×单个元素大小其中：

基地址是顺序表的起始地址（即数组的指针或首地址）。

单个元素大小是顺序表中每个元素的存储空间大小（通常是元素类型的大小，如 sizeof(int)）。

i 是元素在顺序表中的索引，从 0 开始计数。

我们下面以vector容器为例，求几个元素的存储位置：

#include<iostream>
using namespace std;
#include<vector>
int main() {  
  vector<int>v1 = { 1,2,3,4 };
  for (int i = 0; i < 4; i++) {
    cout << "下标为" << i << "的元素的地址为：" << &v1[i] << endl;
  }
  return 0;
}

我们使用循环遍历，分别打印出v1中四个元素的物理位置，结果如下：

下标为0的元素的地址为：0000027F17813210
下标为1的元素的地址为：0000027F17813214
下标为2的元素的地址为：0000027F17813218
下标为3的元素的地址为：0000027F1781321C

我们可以看出，四个元素的物理位置是连续的，下标为0的元素的地址即为基地址，如果我们要求下标为2的元素地址，因为我们这里定义的是int类型的元素，单个元素大小为4个字节，我们用上述方法可得下标为2的元素地址为0000027F17813210+2*4=0000027F17813218。以此类推，我们可以根据基地址求出所有下标元素的实际物理位置。

下面我们具体来看顺序表的类型定义：

const int MAX_SIZE = 100; // 假设顺序表的最大容量为 100


template <typename T>
class SeqList {
private:
    T data[MAX_SIZE]; // 用数组存储顺序表的元素
    int length; // 当前顺序表的长度
    }

在上面的代码中，我们定义了一个模板类 SeqList<T>
，用于表示存储类型为 T
的元素的顺序表。顺序表的元素存储在 data
数组中，最大容量为 MAX_SIZE
。顺序表的长度由 length
成员变量记录。

我们拓展该类，使该类提供常用的操作，包括插入元素、删除元素、获取指定位置的元素、获取顺序表的长度以及打印顺序表中的所有元素。这些操作能够对顺序表进行基本的增删改查操作。

#include <iostream>
#include <cassert>
using namespace std;
const int MAX_SIZE = 100; // 假设顺序表的最大容量为 100


template <typename T>
class SeqList {
private:
    T data[MAX_SIZE]; // 用数组存储顺序表的元素
    int length; // 当前顺序表的长度


public:
    // 构造函数，初始化顺序表为空表
    SeqList() : length(0) {}


    // 插入元素
    bool insert(int pos, const T& value) {
        if (pos < 0 || pos > length || length >= MAX_SIZE) {
            cout << "顺序表空间已满或不可插入" << endl;
            return false;
        }


        // 将 pos 位置后的元素依次向后移动一位
        for (int i = length; i > pos; --i) {
            data[i] = data[i - 1];
        }


        // 在 pos 位置插入新元素
        data[pos] = value;
        ++length; // 长度加一
        return true;
    }


    // 删除元素
    bool remove(int pos) {
        if (pos < 0 || pos >= length) {
            cout << "无效操作"<<endl;
            return false;
        }


        // 将 pos 位置后的元素依次向前移动一位
        for (int i = pos; i < length - 1; ++i) {
            data[i] = data[i + 1];
        }


        --length; // 长度减一
        return true;
    }


    // 获取指定位置的元素
    T& get(int pos) {
        assert(pos >= 0 && pos < length);
        return data[pos];
    }


    // 获取顺序表的长度
    int size() const {
        return length;
    }


    // 打印顺序表中的所有元素
    void print() const {
        cout << "SeqList: ";
        for (int i = 0; i < length; ++i) {
            cout << data[i] << " ";
        }
        cout << endl;
    }
};