C++ 线性表操作：求表长、定位和插入

线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中，数据元素之间具有一对一的关系，也就是首元素无前驱、尾元素无后继，其余都有具有一个前驱和一个后继。具体实现时，线性表可以采用不同的存储策略。面给出了一种基于顺序存储的线性表实现方案：方案将线性表存储在一片连续空间里，并通过'elem'、'length'和'listsize'三个属性元素。组织成为一个结构：

'elem': 给出线性表存储空间的起始地址 'length': 指明线性表存储空间最多可存储的数据元素个数 'listsize': 当前线性表里的数据元素个个数

为了讨论简化，我们假设每个数据元素是一个整数:

typedef int ElemType; // 数据元素的数据类型

该线性表的结构定义如下：

typedef struct SqList{
   ElemType * elem;   // 数据元素存储空间的首地址
   int length;     // 线性表的当前长度
   int listsize;    // 线性表的存储容量
}SqList;

下面是 C++ 代码实现：

#include <iostream>
using namespace std;

typedef int ElemType;

typedef struct SqList{
   ElemType * elem;
   int length;
   int listsize;
}SqList;

// 求线性表的长度
int ListLength(SqList L) {
    return L.length;
}

// 定位操作，返回指定位置上的元素值
ElemType GetElem(SqList L, int pos) {
    if (pos < 1 || pos > L.length) {
        cout << '位置不合法' << endl;
        return -1;
    }
    return L.elem[pos-1];
}

// 插入操作，在指定位置上插入元素
bool ListInsert(SqList &L, int pos, ElemType e) {
    if (pos < 1 || pos > L.length + 1) {
        cout << '位置不合法' << endl;
        return false;
    }
    if (L.length >= L.listsize) {
        cout << '线性表已满，无法插入' << endl;
        return false;
    }
    for (int i = L.length-1; i >= pos-1; i--) {
        L.elem[i+1] = L.elem[i];
    }
    L.elem[pos-1] = e;
    L.length++;
    return true;
}

int main() {
    SqList L;
    L.elem = new ElemType[100]; // 假设线性表最多存储100个元素
    L.length = 0;
    L.listsize = 100;

    // 插入元素
    ListInsert(L, 1, 10);
    ListInsert(L, 2, 20);
    ListInsert(L, 3, 30);

    // 输出线性表的长度
    cout << '线性表的长度为：' << ListLength(L) << endl;

    // 输出指定位置上的元素
    cout << '第2个位置上的元素为：' << GetElem(L, 2) << endl;

    delete[] L.elem;
    return 0;
}