入门数据结构：顺序表（SqList）完整实现

米罗篮

436人浏览 · 2026-03-17 17:36:11

米罗篮 · 2026-03-17 17:36:11 发布

作为数据结构入门的第一个线性结构，顺序表（基于静态数组实现）是理解“线性存储”“元素操作”的基础。最近从零实现了顺序表的完整功能，过程中踩了几个典型新手坑，今天整理成一篇复盘博客，适合和我一样刚入门数据结构的小伙伴参考，附上完整可运行代码和问题解析，新手也能直接上手。

一、顺序表核心概念

顺序表是用一段连续的内存空间存储数据元素的线性结构，简单说就是“用数组存数据，再用一个变量记录有效元素个数”。它的核心特点是：

随机访问快：通过下标能直接定位元素，时间复杂度O(1)
插入/删除慢：需要移动元素腾出位置或填补空缺，时间复杂度O(n)
静态顺序表：用固定大小的数组实现（本文采用这种，适合入门理解）

本文实现的顺序表，覆盖所有基础操作：初始化、创建、销毁、判空、获取长度、遍历、取值、查找、插入、删除，一站式搞定新手入门需求。

二、完整可运行代码

//2026 03 17

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define ElemType ll
#define MaxSize 50

struct SqList{
    ElemType data[MaxSize];
    int length;
};
void InitList(SqList*&L){
    L=(SqList*)malloc(sizeof(SqList));
    L->length=0;
}
void CreateList(SqList*&L,ElemType a[],int n){
    int i=0;
    InitList(L);
    while(i<n){
        L->data[i]=a[i];
        i++;
    }
    L->length=i;
}
void DestroyList(SqList*&L){
    free(L);
}
bool Listempty(SqList*L){
    return(L->length==0);
}
int Listsize(SqList*L){
    return(L->length);
}
void DispList(SqList*L){
    for(int i=0;i<L->length;i++){
        cout<<L->data[i];
        if(i<L->length-1)cout<<' ';
    }
    cout<<'\n';
}
bool GetElem(SqList*L,int i,ElemType&e){
    if(i<1||i>L->length)return false;
    e=L->data[i-1];
    return true;
}
int LocateElem(SqList*L,ElemType e){
    int i=0;
    while(i<L->length&&L->data[i]!=e) i++;
    if(i>=L->length)return 0;else return i+1;
}
bool ListInsert(SqList*&L,int i,ElemType e){
    int j;
    if(i<1||i>L->length+1||L->length==MaxSize)return false;
    i--;
    for(j=L->length;j>i;j--)L->data[j]=L->data[j-1];
    L->data[i]=e;
    L->length++;
    return true;
}
bool ListDelete(SqList*&L,int i,ElemType&e){
    int j;
    if(i<1||i>L->length)return false;
    i--;
    e=L->data[i];
    for(j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];
    L->length--;
    return true;
}
int main(){
    SqList*L;
    ElemType a[]={13,56,89,78,45,89};
    CreateList(L,a,6);
    DispList(L);
    ListInsert(L,3,8);
    DispList(L);
    ElemType get1;
    GetElem(L,3,get1);
    cout<<get1<<'\n';
    cout<<LocateElem(L,78);
}

注释版本：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

// 宏定义：统一数据类型和顺序表最大容量，便于后续扩展
#define ElemType ll   // 数据元素类型，可按需修改（如int、double）
#define MaxSize 50    // 顺序表最大容量

// 顺序表结构体定义
struct SqList{
    ElemType data[MaxSize];  // 存储元素的静态数组
    int length;              // 顺序表当前有效元素个数
};

// 1. 初始化顺序表
// 核心：分配内存 + 初始化length为0（新手易漏）
void InitList(SqList*&L){
    // 分配内存（C风格malloc，新手可先掌握，后续可替换为C++的new）
    L=(SqList*)malloc(sizeof(SqList));
    L->length=0;  // 关键步骤：避免length为随机值导致逻辑错误
}

// 2. 根据数组创建顺序表（快速初始化）
void CreateList(SqList*&L,ElemType a[],int n){
    int i=0;
    InitList(L);  // 先初始化顺序表
    while(i<n){
        L->data[i]=a[i];  // 将数组元素赋值到顺序表
        i++;
    }
    L->length=i;  // 更新有效元素个数
}

// 3. 销毁顺序表（释放内存，避免泄漏）
void DestroyList(SqList*&L){
    free(L);      // 释放分配的内存
    L = nullptr;  // 关键：销毁后将指针置空，避免野指针
}

// 4. 判断顺序表是否为空
bool Listempty(SqList*L){
    return(L->length==0);  // 空表：有效元素个数为0
}

// 5. 获取顺序表有效长度
int Listsize(SqList*L){
    return(L->length);
}

// 6. 遍历输出顺序表
void DispList(SqList*L){
    // 优化：空表时给出提示，避免输出空行
    if(Listempty(L)){
        cout << "顺序表为空！" << '\n';
        return;
    }
    for(int i=0;i<L->length;i++){
        cout<<L->data[i];
        if(i<L->length-1)cout<<' ';  // 元素间加空格，最后一个元素不空格
    }
    cout<<'\n';
}

// 7. 获取指定位置的元素（位序从1开始，新手易混淆下标）
bool GetElem(SqList*L,int i,ElemType&e){
    // 边界检查：位置i必须在[1, length]之间
    if(i<1||i>L->length)return false;
    e = L->data[i-1];  // 位序转数组下标（数组从0开始）
    return true;
}

// 8. 查找元素的位序（返回从1开始的位序，未找到返回0）
int LocateElem(SqList*L,ElemType e){
    int i=0;
    // 遍历查找，找到则返回位序，未找到返回0
    while(i<L->length&&L->data[i]!=e) i++;
    if(i>=L->length)return 0;
    else return i+1;  // 关键：数组下标转位序（新手易漏+1）
}

// 9. 插入元素到指定位置（位序从1开始）
bool ListInsert(SqList*&L,int i,ElemType e){
    int j;
    // 边界检查：插入位置合法 + 顺序表未满
    if(i<1||i>L->length+1||L->length==MaxSize)return false;
    i--;  // 位序转数组下标
    // 元素后移，腾出插入位置（从最后一个元素开始移）
    for(j=L->length;j>i;j--)L->data[j]=L->data[j-1];
    L->data[i]=e;  // 插入元素
    L->length++;   // 更新有效元素个数
    return true;
}

// 10. 删除指定位置的元素（位序从1开始）
bool ListDelete(SqList*&L,int i,ElemType&e){
    int j;
    // 边界检查：删除位置合法
    if(i<1||i>L->length)return false;
    i--;  // 位序转数组下标
    e = L->data[i];  // 保存被删除的元素
    // 元素前移，填补删除空缺（从删除位置开始移）
    for(j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];
    L->length--;  // 更新有效元素个数
    return true;
}

// 主函数：测试所有功能
int main(){
    SqList*L;
    ElemType a[]={13,56,89,78,45,89};  // 测试数组
    CreateList(L,a,6);                  // 创建顺序表
    
    cout << "1. 初始顺序表：";
    DispList(L);                        // 遍历输出
    
    ListInsert(L,3,8);                  // 第3位插入元素8
    cout << "2. 插入元素8后：";
    DispList(L);
    
    ElemType get1;
    GetElem(L,3,get1);                  // 获取第3位元素
    cout << "3. 第3位元素：" << get1 << '\n';
    
    cout << "4. 元素78的位序：" << LocateElem(L,78) << '\n';  // 查找元素
    
    DestroyList(L);                     // 销毁顺序表，避免内存泄漏
    return 0;
}