C++实现顺序存储线性表的求长度、定位和插入操作

线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中，数据元素之间具有一对一的关系，也就是首元素无前驱、尾元素无后继，其余都有具有一个前驱和一个后继。具体实现时，线性表可以采用不同的存储策略。

本文给出了一种基于顺序存储的线性表实现方案：将线性表存储在一片连续空间里，并通过'elem'、'length'和'listsize'三个属性元素组织成为一个结构：

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

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

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

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

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

本题任务是将Seqlist.cpp中的'ListLength'、'LocateElem'和'ListInsert'函数实现，用以实现顺序表的求长度、定位和插入功能，函数接口再次说明如下：

函数接口定义：

 int ListLength(SqList L)  ;
 //返回顺序线性表长度；

 int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
 //返回L中第1个与e满足关系compare()的数据元素的位序。 若这样的数据元素不存在，则返回值为0。

Status ListInsert(SqList &L,int i,ElemType e) 
  //在L中第i个位置之前插入新的数据元素e，L的长度加1，并返回OK

以下是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;
}

int LocateElem(SqList L, ElemType e, bool (*compare)(ElemType, ElemType)) {
    for (int i = 0; i < L.length; i++) {
        if (compare(L.elem[i], e)) {
            return i + 1;
        }
    }
    return 0;
}

bool compare(ElemType a, ElemType b) {
    return a == b;
}

bool compare_greater(ElemType a, ElemType b) {
    return a > b;
}

bool compare_less(ElemType a, ElemType b) {
    return a < b;
}

void ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) {
        cout << "插入位置无效" << endl;
        return;
    }
    if (L.length == L.listsize) {
        cout << "线性表已满，无法插入" << endl;
        return;
    }
    for (int j = L.length - 1; j >= i - 1; j--) {
        L.elem[j + 1] = L.elem[j];
    }
    L.elem[i - 1] = e;
    L.length++;
}

int main() {
    SqList L;
    L.elem = new ElemType[10];
    L.length = 5;
    L.listsize = 10;
    for (int i = 0; i < L.length; i++) {
        L.elem[i] = i + 1;
    }
    cout << "线性表长度：" << ListLength(L) << endl;
    cout << "插入元素前的位置：" << LocateElem(L, 3, compare) << endl;
    ListInsert(L, 3, 10);
    cout << "插入元素后的位置：" << LocateElem(L, 3, compare) << endl;
    delete[] L.elem;

    return 0;
}

注意：

在本代码中，我们使用了一个辅助函数'compare'，用于比较两个元素是否相等。根据题目要求，我们假设每个数据元素是一个整数，因此比较函数的实现非常简单，只需要判断两个元素是否相等。如果数据元素的类型不是整数，可以根据实际情况修改比较函数的实现。

另外，为了演示插入操作，我们在'main'函数中初始化了一个线性表，并进行插入操作后输出插入元素的位置。你可以根据需要修改'main'函数中的代码进行测试。