C++顺序表实现指南：数据结构与核心操作详解

结果或目标

在C++中建立一个顺序表，本质上是在内存中开辟一块连续的数组空间来存储数据元素。为了便于后续的操作与维护，我们需要明确以下几个核心要素：

• 容器定义：确定最大容量限制，防止内存越界。
• 数据载体：定义用于存储具体信息的结构体（如学生记录）。
• 状态追踪：记录当前已存入的有效元素个数，以便控制访问范围。
• 操作逻辑：实现初始化、插入、删除、查找和遍历等标准接口。

准备条件

在使用顺序表之前，首先需要定义其底层的数据结构。我们将顺序表视为一个班级的学生记录表，包含学号（key）、姓名（name）和年龄（age）三项属性。由于C++的数组默认从下标0开始计数，但在教学演示中，为了方便对应“第几个”这一自然语言概念，本例采用下标1至N的逻辑，将下标0留作备用或不使用。

第1步：定义数据元素类型

创建一个名为DATA的结构体，用来保存每一个具体的节点信息。

#define MAXLEN 100 // 定义顺序表的最大长度
struct DATA {
    string key;   // 结点的关键字 (如学号)
    string name;  // 结点名称 (如学生姓名)
    int age;      // 结点年龄
};

第2步：定义顺序表整体结构

创建名为SLType的结构体，包含保存数据的结构数组和当前长度的计数器。

struct SLType { 
    DATA ListData[MAXLEN+1]; // 保存顺序表的结构数组
    int ListLen;             // 顺序表已存结点的数量
};

真实操作顺序

第1步：初始化顺序表

在使用顺序表进行任何操作前，必须先将其状态重置为空。这可以通过将内部计数器ListLen设为0来实现，此时数组虽然分配了内存，但在逻辑上被视为空表。

关键参数：指向顺序表的指针。完成状态：ListLen为0。

void SLInit(SLType * SL) // 初始化顺序表
{
    SL->ListLen = 0;
}

第2步：计算线性表的长度

获取当前顺序表中有效数据的个数。因为我们在结构中专门维护了ListLen变量，所以直接返回该值即可，时间复杂度为O(1)。

入口：调用SLLenght函数。动作：返回SL->ListLen。结果：返回整型数值。

int SLLenght(SLType *SL)
{
    return (SL->ListLen); // 返回顺序表的元素数量 
}

第3步：向指定位置插入节点

插入是顺序表最核心的操作之一。它要求在第n个位置插入一个新节点，并使原+1及之后的所有节点依次后移一位，以腾出空间。

目的：维护节点的连续性并更新内容。重要参数：插入位置n和新数据data。

1. 合法性检查：
   • 若ListLen >= MAXLEN，说明表已满，拒绝插入。
   • 若插入位置n小于1或大于当前长度SL->ListLen + 1，属于非法位置，拒绝插入。
2. 数据迁移：从最后一个元素开始（i = ListLen），逐个将数据复制到后一个位置（ListData[i+1] = ListData[i]），直到移动到第n个位置之前。
3. 填入新数据：将新数据放入ListData[n]。
4. 更新状态：将ListLen加1。

注意：C++字符串比较需包含头文件。

int SLInsert(SLType *SL, int n, DATA data)
{
    int i;
    if(SL->ListLen >= MAXLEN) // 顺序表结点数量已超过最大数量
    {
        cout << "顺序表已满，不能插入结点！" << endl;
        return 0; // 返回0表示插入不成功 
    }
    if(n < 1 || n > SL->ListLen + 1) // 插入结点的序号不合法 
    {
        cout << "插入序号错误！" << endl;
        return 0;
    }
    for(i = SL->ListLen; i >= n; i--) // 将顺序表中的数据向后移动
    {
        SL->ListData[i+1] = SL->ListData[i];
    }
    SL->ListData[n] = data;
    SL->ListLen++;
    return 1; 
}

第4步：追加节点到尾部

这是一种特殊的插入操作，即在顺序表的最后添加新元素。由于不需要移动其他节点，其效率优于普通插入。

动作：首先检查容量，然后直接将data放入ListData[++SL->ListLen]的位置。

int SLAdd(SLType * SL, DATA data)
{
    if(SL->ListLen >= MAXLEN)
    {
        cout << "顺序表已满，不能再添加结点了！" << endl;
        return 0;
    } 
    SL->ListData[++SL->ListLen] = data;
    return 1;
}

第5步：删除指定位置的节点

删除第n个节点后，为了保持物理存储的连续性，需要将该位置之后的所有节点依次向前移动一位。

步骤：

1. 校验删除位置n是否合法（1 <= n <= ListLen）。
2. 从i = n开始循环，执行ListData[i] = ListData[i+1]，直至最后一个元素被覆盖掉。
3. 将ListLen减1。

int SLDelete(SLType *SL, int n) // 删除顺序表中的数据元素
{
    int i;
    if(n < 1 || n > SL->ListLen) // 删除结点的序号不合法 
    {
        cout << "删除序号错误！" << endl;
        return 0;
    }
    for(i = n; i < SL->ListLen; i++) // 将顺序表中的数据向前移动 
    {
        SL->ListData[i] = SL->ListData[i+1]; 
    } 
    SL->ListLen--;     // 顺序表元素数量减1 
    return 1;          // 成功删除返回1 
}

第6步：查找节点

查找分为两种常见场景：通过序号定位和通过关键字检索。

1. 按照序号查找节点： 这是最直接的方式，时间复杂度O(1)。只要判断序号n是否在[1, ListLen]范围内，满足则返回该元素的地址指针。

DATA * SLFindByNum(SLType *SL, int n) // 根据序号返回数据元素
{
    if(n < 1 || n > SL->ListLen)   
    {
        cout << "查询序号错误！" << endl;
        return 0;
    }
    return &(SL->ListData[n]); 
}

2. 按照关键字查找节点： 例如查找特定姓名的学生。需要遍历整个列表，逐一比对string name字段。

DATA * SLFindByCont(SLType * SL, string name) // 按关键字查询结点 
{
    int i;
    for(i = 1; i <= SL->ListLen; i++)
    {
        if(SL->ListData[i].name == name) // 如果找到结点 
        {
            return &(SL->ListData[i]);
        }
    }
    return 0;      // 在整个表中都没有找到，返回0 
}

第7步：显示所有节点

遍历数组并打印每个节点的详细信息。

void SLALL(SLType *SL)
{
    int i;
    for(i = 1; i <= SL->ListLen; i++)
    {
        cout << "key:" << SL->ListData[i].key << ",name:" << SL->ListData[i].name << ",age:" << SL->ListData[i].age << endl;
    }
}

简要总结

上述各函数构成了C++顺序表的完整工具箱。实际应用中，可以将它们组合成一个带有交互菜单的主程序，让用户动态输入数据并进行增删查改测试。以下是该顺序表的主要特点：

• 优势：支持随机访问（通过序号快速查找），存储密度高，无需额外的指针域开销。
• 劣势：插入和删除操作涉及大量数据搬移，平均时间复杂度为O(N)；且由于定义了静态数组MAXLEN，存在固定容量的限制。

以上就是C++建立顺序表的详细内容，更多关于C++数据结构与算法的资料请关注本站其它相关文章！