一、概述

在学习数据结构时，顺序表（Sequential List） 是我们接触到的第一个线性结构。
它是线性表的一种顺序存储形式——即：所有元素依次存放在一段连续的内存空间中。

通俗点说：

顺序表就像一排座位，座位一个挨着一个。
每个座位只能坐一个人（存放一个数据），
想插队（插入）或离开（删除）时，后面的人都得动一动！

二、顺序表的定义与特点

1.定义

顺序表是一种用数组实现的线性表。
它通过元素的下标（索引） 来快速访问任意位置的数据。

在C语言中可以用结构体来表示：

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE]; // 存放元素的数组
    int length;        // 当前表的长度（有效元素个数）
} SqList;

2.特点

三、顺序表的基本操作

1.初始化顺序表

void InitList(SqList *L) {
    L->length = 0;
}

初始化后，表为空，但数组空间已准备好。

2. 插入元素

int ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) return 0; // 位置非法
    if (L->length >= MAXSIZE) return 0;       // 空间已满

    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j - 1]; // 元素后移
    }
    L->data[i - 1] = e;
    L->length++;
    return 1;
}

例子：在 [10, 20, 30, 40] 的第3个位置插入 99
执行后变为 [10, 20, 99, 30, 40]

3.删除元素

int ListDelete(SqList *L, int i, int *e) {
    if (i < 1 || i > L->length) return 0; // 位置非法
    *e = L->data[i - 1];                  // 保存删除的元素
    for (int j = i; j < L->length; j++) {
        L->data[j - 1] = L->data[j];      // 元素前移
    }
    L->length--;
    return 1;
}

例子：删除 [10, 20, 99, 30, 40] 中第3个元素
输出 删除元素 = 99
结果 [10, 20, 30, 40]

4.查找元素

int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e)
            return i + 1; // 返回逻辑位置
    }
    return 0;
}

查找 30 → 返回位置 3

5.遍历顺序表

void PrintList(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
}

四、综合示例：学生成绩表

假设我们要管理一个班级的成绩，数据如下：

我们要实现：

• 初始化成绩表
• 插入新学生成绩
• 删除一名学生
• 查找特定学号
• 打印全部成绩

完整代码示例：

#include <stdio.h>

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

void InitList(SqList *L) {
    L->length = 0;
}

int ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) return 0;
    if (L->length >= MAXSIZE) return 0;
    for (int j = L->length; j >= i; j--)
        L->data[j] = L->data[j - 1];
    L->data[i - 1] = e;
    L->length++;
    return 1;
}

int ListDelete(SqList *L, int i, int *e) {
    if (i < 1 || i > L->length) return 0;
    *e = L->data[i - 1];
    for (int j = i; j < L->length; j++)
        L->data[j - 1] = L->data[j];
    L->length--;
    return 1;
}

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

void PrintList(SqList L) {
    for (int i = 0; i < L.length; i++)
        printf("%d ", L.data[i]);
    printf("\n");
}

int main() {
    SqList scoreList;
    InitList(&scoreList);

    // 初始化数据
    ListInsert(&scoreList, 1, 85);
    ListInsert(&scoreList, 2, 90);
    ListInsert(&scoreList, 3, 78);
    printf("初始成绩表：");
    PrintList(scoreList);

    // 插入新成绩
    ListInsert(&scoreList, 2, 95);
    printf("插入新成绩后：");
    PrintList(scoreList);

    // 删除成绩
    int deleted;
    ListDelete(&scoreList, 3, &deleted);
    printf("删除第3个成绩(%d)后：", deleted);
    PrintList(scoreList);

    // 查找成绩
    int pos = LocateElem(scoreList, 90);
    if (pos)
        printf("成绩90在第%d个位置\n", pos);
    else
        printf("未找到成绩90\n");

    return 0;
}

运行结果示例：

初始成绩表：85 90 78 
插入新成绩后：85 95 90 78 
删除第3个成绩(90)后：85 95 78 
成绩90在第0个位置

五、时间与空间复杂度分析

六、应用场景

顺序表常用于：

• 存储固定数量的数据（如成绩表、学生名单）
• 频繁访问、较少插入/删除的场景
• 简单结构、性能要求不高的系统

七、总结

八、附：封装好的C++数据结构代码

//#include <iostream.h>
//using namespace std;
#ifndef List2
#define List2
template<class ElemType>
class List{
public:
virtual int GetLen()=0;/*求线性表长度*/
virtual ElemType &GetElem(int i)=0;/*取第i个元素,i=1~n*/
ElemType &operator[](int i){return GetElem(i);}//下标重载
virtual int Locate(ElemType x)=0;
virtual int InsElem(int i,ElemType x)=0;
virtual int DelElem(int i)=0;
virtual void DispList(char c=',',char c2='\n')=0;
};
#endif

#ifndef sq_List2
#define sq_List2

template<typename ElemType>
class sqList:public List<ElemType>{
ElemType *data,X;   //定义存储表中元素的数组
int Length,MaxLen;  //线性表的实际长度
public://构造函数初始化顺序表
sqList(int n=100):MaxLen(n),Length(0),X(0){data=new ElemType[n];}
int GetLen(){return Length;}//求线性表长度

ElemType &GetElem(int i)//取第i个元素值,i=1~n
{if(i<1||i>Length)return X;//返回随机数
 return data[i-1];}
//ElemType &operator[](int i){return GetElem(i);}//下标重载

int Locate(ElemType x)//查找值为x元素的位置,没找到返回a0
{int i;
for(i=0;i<Length;i++)if(!(data[i]!=x))return i+1;
return 0;}

int InsElem(int i,ElemType x)//第i位置插入结点x,i=1~n
{int j;
 if(Length==MaxLen)return 0;//表已满 
 if(i<1||i>Length+1)return 0;//插入位置出错
 for(j=Length;j>=i;j--)data[j]=data[j-1];//数据元素后移 
 data[i-1]=x;Length++;  //插入x,表长度加1 
 return 1;}

int DelElem(int i)//删除线性表中第i个位置上的元素 
{int j;
 if(i<1||i>Length)return 0;//检查空表及删除位置的合法性
 for(j=i;j<=Length-1;j++)data[j-1]=data[j];//向前移动元素
 Length--;return 1;}

void DispList(char c=',',char c2='\n')//输出线性表中每个元素值
{int i;
if(Length==0){cout<<"空表";if(c2)if(c2=='\n')cout<<endl;else cout<<c2;return;}
for(i=0;i<Length;i++){cout<<data[i];if(c)cout<<c;}
if(c2)if(c2=='\n')cout<<endl;else cout<<c2;
}

};

#endif