C++ 数据结构线性表-数组实现

什么是线性表

线性表，简单来说，就是一种有序的数据结构，数据元素起来往往构成一列，比如数组、链表等等。

数组实现线性表

数组是一种容器，它可以存储相同类型的数据元素。使用数组实现线性表，就是将数据元素按照一定的顺序依次存储在数组中。

数组实现线性表的基本思路

1. 定义一个数组，用来存储数据元素；
2. 定义一个变量，用来记录线性表中元素的个数；
3. 插入元素时，将数据元素插入到数组中，并更新计数器；
4. 删除元素时，将数组中的元素前移，并更新计数器；
5. 遍历元素时，依次输出数组中的元素。

数组实现线性表的基本代码

const int MAXSIZE = 100; // 线性表的最大长度
typedef int ElementType; // 定义元素类型
typedef struct {    
    ElementType data[MAXSIZE]; // 数据元素存储数组
    int length; // 线性表当前长度
} LinearList;

// 初始化线性表
void InitList(LinearList &L)
{
    L.length = 0;
}

// 插入元素
bool InsertList(LinearList &L, int i, ElementType x)
{
    if (i < 1 || i > L.length + 1 || L.length == MAXSIZE)
        return false;
    for (int j = L.length; j >= i; j--)
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = x;
    L.length++;
    return true;
}

// 删除元素
bool DelList(LinearList &L, int i)
{
    if (i < 1 || i > L.length)
        return false;
    for (int j = i; j < L.length; j++)
        L.data[j - 1] = L.data[j];
    L.length--;
    return true;
}

// 遍历线性表
void TraverseList(LinearList L)
{
    for (int i = 0; i < L.length; i++)
        cout << L.data[i] << " ";
    cout << endl;
}

数组实现线性表的示例1

#include <iostream>
#include "linearlist.h"
using namespace std;

int main()
{
    LinearList L;
    InitList(L);
    InsertList(L, 1, 1);
    InsertList(L, 2, 3);
    InsertList(L, 3, 5);
    cout << "插入元素后的线性表：" << endl;
    TraverseList(L);
    DelList(L, 2);
    cout << "删除元素后的线性表：" << endl;
    TraverseList(L);
    return 0;
}

代码的执行结果如下：

插入元素后的线性表：
1 3 5 
删除元素后的线性表：
1 5 

数组实现线性表的示例2

#include <iostream>
#include "linearlist.h"
using namespace std;

int main()
{
    LinearList L;
    InitList(L);
    for (int i = 0; i < MAXSIZE / 2; i++)
        InsertList(L, i + 1, i * 2);
    cout << "插入元素后的线性表：" << endl;
    TraverseList(L);
    cout << "删除元素后的线性表：" << endl;
    for (int i = 0; i < MAXSIZE / 4; i++)
        DelList(L, i + 1);
    TraverseList(L);
    return 0;
}

代码的执行结果如下：

插入元素后的线性表：
0 2 4 6 8 10 12 14 16 18 
删除元素后的线性表：
8 10 12 14 16 18 

总结

数组的优点是随机存取速度快、内存地址连续等，缺点是大小固定，不能动态扩展。使用数组实现线性表，可以使用简单的数组操作实现常见的插入、删除、遍历等操作。但是线性表长度有限，无法动态扩展，因此需要慎重选择。