1. 顺序表概述

1.1 什么是顺序表

顺序表（Sequential List）是线性表的一种存储结构，它使用一组地址连续的存储单元依次存储线性表中的数据元素。顺序表的特点是逻辑上相邻的元素在物理存储位置上也相邻，这种特性使得顺序表具有随机访问的能力。

顺序表可以看作是线性表的数组实现，它通过数组来存储元素，并通过一个变量来记录当前表中元素的个数。顺序表的存储密度高，不需要额外的空间来存储元素之间的逻辑关系。

1.2 顺序表的基本特性

物理结构特性：

• 存储空间连续：所有元素存储在连续的内存空间中
• 随机访问：可以通过下标直接访问任何位置的元素
• 固定容量：需要预先分配固定大小的存储空间

逻辑结构特性：

• 元素类型一致：所有元素属于同一数据类型
• 有限序列：元素个数有限，存在第一个和最后一个元素
• 有序性：每个元素有确定的位置（序号）

1.3 顺序表的抽象数据类型定义

ADT SeqList {
    数据对象：D = {a_i | a_i ∈ ElemSet, i = 1,2,...,n, n ≥ 0}
    数据关系：R = {<a_{i-1}, a_i> | a_{i-1}, a_i ∈ D, i = 2,3,...,n}
    
    基本操作：
        InitList(&L): 初始化顺序表
        DestroyList(&L): 销毁顺序表
        ClearList(&L): 清空顺序表
        ListEmpty(L): 判断顺序表是否为空
        ListLength(L): 获取顺序表长度
        GetElem(L, i, &e): 按位置获取元素
        LocateElem(L, e): 按值查找位置
        PriorElem(L, cur_e, &pre_e): 获取前驱元素
        NextElem(L, cur_e, &next_e): 获取后继元素
        ListInsert(&L, i, e): 插入元素
        ListDelete(&L, i, &e): 删除元素
        ListTraverse(L, visit()): 遍历顺序表
}

2. 顺序表的实现方式

2.1 静态分配实现

静态分配的顺序表在编译时就已经确定了存储空间的大小，使用定长数组存储元素。

#include <iostream>
#include <cstdlib>
using namespace std;

#define MAXSIZE 100  // 顺序表的最大容量
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

/**
 * 顺序表的静态分配实现
 * 使用定长数组存储元素，容量在编译时确定
 */
typedef struct {
    ElemType data[MAXSIZE];  // 静态数组存储数据元素
    int length;              // 当前长度
} StaticSeqList;

// 初始化静态顺序表
Status InitList_Static(StaticSeqList &L) {
    L.length = 0;  // 空表长度为0
    cout << "静态顺序表初始化成功，最大容量为：" << MAXSIZE << endl;
    return OK;
}

// 判断静态顺序表是否为空
Status ListEmpty_Static(StaticSeqList L) {
    return L.length == 0;
}

// 获取静态顺序表长度
int ListLength_Static(StaticSeqList L) {
    return L.length;
}

// 在静态顺序表中插入元素
Status ListInsert_Static(StaticSeqList &L, int i, ElemType e) {
    // 参数校验
    if (i < 1 || i > L.length + 1) {
        cout << "插入位置不合法！" << endl;
        return ERROR;
    }
    
    // 检查表是否已满
    if (L.length >= MAXSIZE) {
        cout << "顺序表已满，无法插入！" << endl;
        return ERROR;
    }
    
    // 移动元素，为插入位置腾出空间
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    
    // 插入新元素
    L.data[i - 1] = e;
    L.length++;
    
    cout << "在位置 " << i << " 插入元素 " << e << " 成功" << endl;
    return OK;
}

// 从静态顺序表中删除元素
Status ListDelete_Static(StaticSeqList &L, int i, ElemType &e) {
    // 参数校验
    if (i < 1 || i > L.length) {
        cout << "删除位置不合法！" << endl;
        return ERROR;
    }
    
    // 检查表是否为空
    if (L.length == 0) {
        cout << "顺序表为空，无法删除！" << endl;
        return ERROR;
    }
    
    // 保存被删除的元素
    e = L.data[i - 1];
    
    // 移动元素，填补删除位置
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    
    L.length--;
    cout << "在位置 " << i << " 删除元素 " << e << " 成功" << endl;
    return OK;
}

// 按位置获取静态顺序表中的元素
Status GetElem_Static(StaticSeqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length) {
        cout << "位置不合法！" << endl;
        return ERROR;
    }
    
    e = L.data[i - 1];
    cout << "位置 " << i << " 的元素是：" << e << endl;
    return OK;
}

// 按值查找静态顺序表中的元素位置
int LocateElem_Static(StaticSeqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            cout << "元素 " << e << " 的位置是：" << i + 1 << endl;
            return i + 1;
        }
    }
    
    cout << "未找到元素 " << e << endl;
    return 0;
}

// 遍历静态顺序表
void ListTraverse_Static(StaticSeqList L) {
    if (L.length == 0) {
        cout << "顺序表为空！" << endl;
        return;
    }
    
    cout << "顺序表内容：";
    for (int i = 0; i < L.length; i++) {
        cout << L.data[i] << " ";
    }
    cout << endl;
    cout << "当前长度：" << L.length << "，剩余容量：" << MAXSIZE - L.length << endl;
}

// 静态顺序表操作示例
void StaticSequenceListDemo() {
    cout << "=== 静态顺序表操作演示 ===" << endl;
    
    StaticSeqList L;
    ElemType e;
    
    // 初始化顺序表
    InitList_Static(L);
    
    // 插入元素
    for (int i = 1; i <= 10; i++) {
        ListInsert_Static(L, i, i * 5);  // 插入5,10,15,...,50
    }
    ListTraverse_Static(L);
    
    // 获取元素
    GetElem_Static(L, 3, e);
    
    // 查找元素
    LocateElem_Static(L, 25);
    
    // 删除元素
    ListDelete_Static(L, 4, e);
    ListTraverse_Static(L);
    
    // 在中间位置插入元素
    ListInsert_Static(L, 5, 99);
    ListTraverse_Static(L);
    
    cout << endl;
}

2.2 动态分配实现

动态分配的顺序表在运行时动态分配存储空间，可以根据需要调整容量。

#include <iostream>
#include <cstdlib>
using namespace std;

#define INIT_SIZE 10   // 初始容量
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

/**
 * 顺序表的动态分配实现
 * 使用指针动态分配内存，可根据需要调整容量
 */
typedef struct {
    ElemType *data;    // 动态数组的指针
    int length;        // 当前长度
    int capacity;      // 当前容量
} DynamicSeqList;

// 初始化动态顺序表
Status InitList_Dynamic(DynamicSeqList &L) {
    // 分配初始内存空间
    L.data = new ElemType[INIT_SIZE];
    if (!L.data) {
        exit(OVERFLOW);  // 存储分配失败
    }
    
    L.length = 0;
    L.capacity = INIT_SIZE;
    
    cout << "动态顺序表初始化成功，初始容量为：" << L.capacity << endl;
    return OK;
}

// 销毁动态顺序表
Status DestroyList_Dynamic(DynamicSeqList &L) {
    if (L.data) {
        delete[] L.data;  // 释放内存
        L.data = NULL;
    }
    L.length = 0;
    L.capacity = 0;
    
    cout << "动态顺序表已销毁" << endl;
    return OK;
}

// 调整动态顺序表容量
Status ResizeList(DynamicSeqList &L, int newCapacity) {
    if (newCapacity < L.length) {
        cout << "新容量不能小于当前长度！" << endl;
        return ERROR;
    }
    
    ElemType *newData = new ElemType[newCapacity];
    if (!newData) {
        exit(OVERFLOW);
    }
    
    // 复制数据
    for (int i = 0; i < L.length; i++) {
        newData[i] = L.data[i];
    }
    
    // 释放旧内存，更新指针和容量
    delete[] L.data;
    L.data = newData;
    L.capacity = newCapacity;
    
    cout << "顺序表容量已调整为：" << newCapacity << endl;
    return OK;
}

// 在动态顺序表中插入元素
Status ListInsert_Dynamic(DynamicSeqList &L, int i, ElemType e) {
    // 参数校验
    if (i < 1 || i > L.length + 1) {
        cout << "插入位置不合法！" << endl;
        return ERROR;
    }
    
    // 检查是否需要扩容
    if (L.length >= L.capacity) {
        int newCapacity = L.capacity * 2;  // 容量翻倍
        if (!ResizeList(L, newCapacity)) {
            return ERROR;
        }
    }
    
    // 移动元素
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    
    // 插入新元素
    L.data[i - 1] = e;
    L.length++;
    
    cout << "在位置 " << i << " 插入元素 " << e << " 成功" << endl;
    return OK;
}

// 从动态顺序表中删除元素
Status ListDelete_Dynamic(DynamicSeqList &L, int i, ElemType &e) {
    // 参数校验
    if (i < 1 || i > L.length) {
        cout << "删除位置不合法！" << endl;
        return ERROR;
    }
    
    if (L.length == 0) {
        cout << "顺序表为空，无法删除！" << endl;
        return ERROR;
    }
    
    // 保存被删除的元素
    e = L.data[i - 1];
    
    // 移动元素
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    
    L.length--;
    
    // 检查是否需要缩容（当长度小于容量的1/4时）
    if (L.length > 0 && L.length < L.capacity / 4) {
        int newCapacity = max(INIT_SIZE, L.capacity / 2);
        ResizeList(L, newCapacity);
    }
    
    cout << "在位置 " << i << " 删除元素 " << e << " 成功" << endl;
    return OK;
}

// 遍历动态顺序表
void ListTraverse_Dynamic(DynamicSeqList L) {
    if (L.length == 0) {
        cout << "顺序表为空！" << endl;
        return;
    }
    
    cout << "顺序表内容：";
    for (int i = 0; i < L.length; i++) {
        cout << L.data[i] << " ";
    }
    cout << endl;
    cout << "当前长度：" << L.length << "，当前容量：" << L.capacity << endl;
}

// 动态顺序表操作示例
void DynamicSequenceListDemo() {
    cout << "=== 动态顺序表操作演示 ===" << endl;
    
    DynamicSeqList L;
    ElemType e;
    
    // 初始化顺序表
    InitList_Dynamic(L);
    
    // 插入元素，测试自动扩容
    cout << "插入15个元素测试自动扩容：" << endl;
    for (int i = 1; i <= 15; i++) {
        ListInsert_Dynamic(L, i, i * 3);  // 插入3,6,9,...,45
    }
    ListTraverse_Dynamic(L);
    
    // 删除元素，测试自动缩容
    cout << "删除12个元素测试自动缩容：" << endl;
    for (int i = 1; i <= 12; i++) {
        ListDelete_Dynamic(L, 1, e);  // 从头部删除
    }
    ListTraverse_Dynamic(L);
    
    // 销毁顺序表
    DestroyList_Dynamic(L);
    
    cout << endl;
}

3. 顺序表的基本操作详解

3.1 初始化操作

顺序表的初始化是使用顺序表的第一步，主要包括分配存储空间和设置初始状态。

/**
 * 顺序表初始化操作的详细实现
 * 包含错误处理和状态验证
 */
class AdvancedSeqList {
private:
    ElemType *data;     // 存储空间基址
    int length;         // 当前长度
    int capacity;       // 当前容量
    bool initialized;   // 初始化标志
    
public:
    // 构造函数
    AdvancedSeqList() : data(nullptr), length(0), capacity(0), initialized(false) {}
    
    // 析构函数
    ~AdvancedSeqList() {
        if (data) {
            delete[] data;
        }
    }
    
    // 初始化顺序表
    Status InitList(int initCapacity = INIT_SIZE) {
        // 参数校验
        if (initCapacity <= 0) {
            cout << "错误：初始容量必须大于0！" << endl;
            return ERROR;
        }
        
        // 如果已经初始化，先释放原有内存
        if (initialized && data) {
            delete[] data;
        }
        
        // 分配内存
        data = new ElemType[initCapacity];
        if (!data) {
            cout << "错误：内存分配失败！" << endl;
            return OVERFLOW;
        }
        
        length = 0;
        capacity = initCapacity;
        initialized = true;
        
        cout << "顺序表初始化成功，容量：" << capacity << endl;
        return OK;
    }
    
    // 验证顺序表状态
    bool IsValid() const {
        return initialized && data != nullptr;
    }
    
    // 获取当前状态信息
    void GetStatus() const {
        if (!IsValid()) {
            cout << "顺序表未初始化或已损坏！" << endl;
            return;
        }
        
        cout << "顺序表状态：" << endl;
        cout << " - 当前长度：" << length << endl;
        cout << " - 当前容量：" << capacity << endl;
        cout << " - 空间利用率：" << (length * 100.0 / capacity) << "%" << endl;
        cout << " - 剩余空间：" << (capacity - length) << endl;
    }
};

3.2 插入操作

插入操作是顺序表的核心操作之一，需要考虑位置合法性、容量检查和元素移动。

/**
 * 顺序表插入操作的完整实现
 * 包含多种插入方式和边界处理
 */
class InsertOperation {
private:
    ElemType *data;
    int length;
    int capacity;
    
public:
    InsertOperation(ElemType *d, int &len, int cap) 
        : data(d), length(len), capacity(cap) {}
    
    // 在指定位置插入元素
    Status InsertAt(int position, ElemType element) {
        // 基础参数校验
        if (position < 1 || position > length + 1) {
            cout << "错误：插入位置 " << position << " 不合法！" << endl;
            return ERROR;
        }
        
        if (length >= capacity) {
            cout << "错误：顺序表已满，无法插入！" << endl;
            return ERROR;
        }
        
        // 记录移动次数（用于性能分析）
        int moveCount = 0;
        
        // 移动元素
        for (int i = length; i >= position; i--) {
            data[i] = data[i - 1];
            moveCount++;
        }
        
        // 插入新元素
        data[position - 1] = element;
        length++;
        
        cout << "插入成功：位置=" << position 
             << ", 元素=" << element 
             << ", 移动元素次数=" << moveCount << endl;
        
        return OK;
    }
    
    // 在表头插入元素
    Status InsertAtHead(ElemType element) {
        return InsertAt(1, element);
    }
    
    // 在表尾插入元素
    Status InsertAtTail(ElemType element) {
        return InsertAt(length + 1, element);
    }
    
    // 批量插入元素
    Status BatchInsert(int position, const ElemType elements[], int count) {
        if (position < 1 || position > length + 1) {
            cout << "错误：插入位置不合法！" << endl;
            return ERROR;
        }
        
        if (length + count > capacity) {
            cout << "错误：空间不足，需要 " << (length + count) 
                 << "，但容量只有 " << capacity << endl;
            return ERROR;
        }
        
        // 移动现有元素，为批量插入腾出空间
        for (int i = length - 1; i >= position - 1; i--) {
            data[i + count] = data[i];
        }
        
        // 插入新元素
        for (int i = 0; i < count; i++) {
            data[position - 1 + i] = elements[i];
        }
        
        length += count;
        
        cout << "批量插入成功：位置=" << position 
             << ", 元素数量=" << count 
             << ", 新长度=" << length << endl;
        
        return OK;
    }
    
    // 有序插入（假设顺序表已排序）
    Status OrderedInsert(ElemType element) {
        if (length >= capacity) {
            cout << "错误：顺序表已满！" << endl;
            return ERROR;
        }
        
        // 查找插入位置
        int pos = 1;
        while (pos <= length && data[pos - 1] < element) {
            pos++;
        }
        
        return InsertAt(pos, element);
    }
};

3.3 删除操作

删除操作同样需要处理位置检查、元素移动和边界情况。

/**
 * 顺序表删除操作的完整实现
 * 包含多种删除方式和优化策略
 */
class DeleteOperation {
private:
    ElemType *data;
    int length;
    int capacity;
    
public:
    DeleteOperation(ElemType *d, int &len, int cap) 
        : data(d), length(len), capacity(cap) {}
    
    // 删除指定位置的元素
    Status DeleteAt(int position, ElemType &deletedElement) {
        // 参数校验
        if (position < 1 || position > length) {
            cout << "错误：删除位置 " << position << " 不合法！" << endl;
            return ERROR;
        }
        
        if (length == 0) {
            cout << "错误：顺序表为空，无法删除！" << endl;
            return ERROR;
        }
        
        // 保存被删除的元素
        deletedElement = data[position - 1];
        int moveCount = 0;
        
        // 移动元素填补空位
        for (int i = position; i < length; i++) {
            data[i - 1] = data[i];
            moveCount++;
        }
        
        length--;
        
        cout << "删除成功：位置=" << position 
             << ", 元素=" << deletedElement 
             << ", 移动元素次数=" << moveCount << endl;
        
        return OK;
    }
    
    // 删除表头元素
    Status DeleteAtHead(ElemType &deletedElement) {
        return DeleteAt(1, deletedElement);
    }
    
    // 删除表尾元素
    Status DeleteAtTail(ElemType &deletedElement) {
        return DeleteAt(length, deletedElement);
    }
    
    // 按值删除元素（删除第一个匹配的元素）
    Status DeleteByValue(ElemType value) {
        for (int i = 0; i < length; i++) {
            if (data[i] == value) {
                ElemType deleted;
                return DeleteAt(i + 1, deleted);
            }
        }
        
        cout << "未找到元素 " << value << "，删除失败" << endl;
        return ERROR;
    }
    
    // 删除所有匹配的元素
    Status DeleteAllByValue(ElemType value) {
        int deletedCount = 0;
        int writeIndex = 0;
        
        // 使用双指针法，避免多次移动
        for (int readIndex = 0; readIndex < length; readIndex++) {
            if (data[readIndex] != value) {
                data[writeIndex] = data[readIndex];
                writeIndex++;
            } else {
                deletedCount++;
            }
        }
        
        length = writeIndex;
        
        cout << "删除了 " << deletedCount << " 个值为 " << value << " 的元素" << endl;
        return deletedCount > 0 ? OK : ERROR;
    }
    
    // 批量删除指定范围的元素
    Status BatchDelete(int startPos, int endPos) {
        if (startPos < 1 || endPos > length || startPos > endPos) {
            cout << "错误：删除范围不合法！" << endl;
            return ERROR;
        }
        
        int deleteCount = endPos - startPos + 1;
        
        // 移动元素
        for (int i = endPos; i < length; i++) {
            data[i - deleteCount] = data[i];
        }
        
        length -= deleteCount;
        
        cout << "批量删除成功：位置 " << startPos << " 到 " << endPos 
             << "，共删除 " << deleteCount << " 个元素" << endl;
        
        return OK;
    }
    
    // 清空顺序表
    Status ClearList() {
        int oldLength = length;
        length = 0;
        cout << "已清空顺序表，原长度：" << oldLength << endl;
        return OK;
    }
};

3.4 查找操作

查找操作包括按位置查找和按值查找，是顺序表的基础操作。

/**
 * 顺序表查找操作的完整实现
 * 包含多种查找算法和优化策略
 */
class SearchOperation {
private:
    ElemType *data;
    int length;
    
public:
    SearchOperation(ElemType *d, int len) : data(d), length(len) {}
    
    // 按位置查找
    Status GetElement(int position, ElemType &element) {
        if (position < 1 || position > length) {
            cout << "错误：位置 " << position << " 不合法！" << endl;
            return ERROR;
        }
        
        element = data[position - 1];
        cout << "位置 " << position << " 的元素是：" << element << endl;
        return OK;
    }
    
    // 按值查找（顺序查找）
    int LocateElement(ElemType element) {
        for (int i = 0; i < length; i++) {
            if (data[i] == element) {
                cout << "元素 " << element << " 的位置是：" << i + 1 << endl;
                return i + 1;
            }
        }
        
        cout << "未找到元素 " << element << endl;
        return 0;
    }
    
    // 按值查找（带比较函数）
    int LocateElement(ElemType element, bool (*compare)(ElemType, ElemType)) {
        for (int i = 0; i < length; i++) {
            if (compare(data[i], element)) {
                cout << "找到匹配元素，位置：" << i + 1 << endl;
                return i + 1;
            }
        }
        
        cout << "未找到匹配元素" << endl;
        return 0;
    }
    
    // 二分查找（要求顺序表有序）
    int BinarySearch(ElemType element) {
        int left = 0;
        int right = length - 1;
        int comparisons = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            comparisons++;
            
            cout << "二分查找第 " << comparisons << " 次比较："
                 << "left=" << left + 1 << ", mid=" << mid + 1 
                 << ", right=" << right + 1 << endl;
            
            if (data[mid] == element) {
                cout << "找到元素 " << element << "，位置：" << mid + 1 
                     << "，比较次数：" << comparisons << endl;
                return mid + 1;
            } else if (data[mid] < element) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        cout << "未找到元素 " << element << "，比较次数：" << comparisons << endl;
        return 0;
    }
    
    // 查找最大值和最小值
    Status FindMinMax(ElemType &minValue, ElemType &maxValue) {
        if (length == 0) {
            cout << "错误：顺序表为空！" << endl;
            return ERROR;
        }
        
        minValue = maxValue = data[0];
        
        for (int i = 1; i < length; i++) {
            if (data[i] < minValue) {
                minValue = data[i];
            }
            if (data[i] > maxValue) {
                maxValue = data[i];
            }
        }
        
        cout << "最小值：" << minValue << "，最大值：" << maxValue << endl;
        return OK;
    }
    
    // 统计元素出现次数
    int CountElement(ElemType element) {
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (data[i] == element) {
                count++;
            }
        }
        
        cout << "元素 " << element << " 出现了 " << count << " 次" << endl;
        return count;
    }
};

4. 顺序表的高级操作

4.1 排序操作

顺序表的排序操作可以利用其随机访问的特性，实现各种高效的排序算法。

/**
 * 顺序表排序操作的实现
 * 包含多种排序算法和性能比较
 */
class SortOperation {
private:
    ElemType *data;
    int length;
    
    // 交换两个元素
    void Swap(ElemType &a, ElemType &b) {
        ElemType temp = a;
        a = b;
        b = temp;
    }
    
public:
    SortOperation(ElemType *d, int len) : data(d), length(len) {}
    
    // 冒泡排序
    void BubbleSort() {
        int comparisons = 0;
        int swaps = 0;
        
        cout << "开始冒泡排序..." << endl;
        
        for (int i = 0; i < length - 1; i++) {
            bool swapped = false;
            
            for (int j = 0; j < length - 1 - i; j++) {
                comparisons++;
                if (data[j] > data[j + 1]) {
                    Swap(data[j], data[j + 1]);
                    swaps++;
                    swapped = true;
                }
            }
            
            // 如果没有发生交换，说明已经有序
            if (!swapped) {
                break;
            }
        }
        
        cout << "冒泡排序完成：比较次数=" << comparisons 
             << "，交换次数=" << swaps << endl;
    }
    
    // 选择排序
    void SelectionSort() {
        int comparisons = 0;
        int swaps = 0;
        
        cout << "开始选择排序..." << endl;
        
        for (int i = 0; i < length - 1; i++) {
            int minIndex = i;
            
            for (int j = i + 1; j < length; j++) {
                comparisons++;
                if (data[j] < data[minIndex]) {
                    minIndex = j;
                }
            }
            
            if (minIndex != i) {
                Swap(data[i], data[minIndex]);
                swaps++;
            }
        }
        
        cout << "选择排序完成：比较次数=" << comparisons 
             << "，交换次数=" << swaps << endl;
    }
    
    // 插入排序
    void InsertionSort() {
        int comparisons = 0;
        int moves = 0;
        
        cout << "开始插入排序..." << endl;
        
        for (int i = 1; i < length; i++) {
            ElemType key = data[i];
            int j = i - 1;
            
            while (j >= 0) {
                comparisons++;
                if (data[j] > key) {
                    data[j + 1] = data[j];
                    moves++;
                    j--;
                } else {
                    break;
                }
            }
            
            data[j + 1] = key;
        }
        
        cout << "插入排序完成：比较次数=" << comparisons 
             << "，移动次数=" << moves << endl;
    }
    
    // 快速排序的递归部分
    void QuickSortRecursive(int low, int high, int &comparisons, int &swaps) {
        if (low < high) {
            int pivotIndex = Partition(low, high, comparisons, swaps);
            QuickSortRecursive(low, pivotIndex - 1, comparisons, swaps);
            QuickSortRecursive(pivotIndex + 1, high, comparisons, swaps);
        }
    }
    
    // 快速排序的分区函数
    int Partition(int low, int high, int &comparisons, int &swaps) {
        ElemType pivot = data[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            comparisons++;
            if (data[j] <= pivot) {
                i++;
                if (i != j) {
                    Swap(data[i], data[j]);
                    swaps++;
                }
            }
        }
        
        Swap(data[i + 1], data[high]);
        swaps++;
        
        return i + 1;
    }
    
    // 快速排序
    void QuickSort() {
        int comparisons = 0;
        int swaps = 0;
        
        cout << "开始快速排序..." << endl;
        
        QuickSortRecursive(0, length - 1, comparisons, swaps);
        
        cout << "快速排序完成：比较次数=" << comparisons 
             << "，交换次数=" << swaps << endl;
    }
    
    // 检查顺序表是否有序
    bool IsSorted() {
        for (int i = 0; i < length - 1; i++) {
            if (data[i] > data[i + 1]) {
                return false;
            }
        }
        return true;
    }
    
    // 性能测试：比较各种排序算法
    void PerformanceTest() {
        // 保存原始数据
        ElemType *originalData = new ElemType[length];
        for (int i = 0; i < length; i++) {
            originalData[i] = data[i];
        }
        
        cout << "\n=== 排序算法性能比较 ===" << endl;
        cout << "数据量：" << length << endl;
        
        // 测试各种排序算法
        TestSortAlgorithm("冒泡排序", &SortOperation::BubbleSort);
        TestSortAlgorithm("选择排序", &SortOperation::SelectionSort);
        TestSortAlgorithm("插入排序", &SortOperation::InsertionSort);
        TestSortAlgorithm("快速排序", &SortOperation::QuickSort);
        
        // 恢复原始数据
        for (int i = 0; i < length; i++) {
            data[i] = originalData[i];
        }
        
        delete[] originalData;
    }
    
private:
    // 测试单个排序算法的性能
    void TestSortAlgorithm(const string &name, void (SortOperation::*sortFunc)()) {
        // 复制数据用于测试
        ElemType *testData = new ElemType[length];
        for (int i = 0; i < length; i++) {
            testData[i] = data[i];
        }
        
        // 执行排序
        auto start = chrono::high_resolution_clock::now();
        (this->*sortFunc)();
        auto end = chrono::high_resolution_clock::now();
        
        // 验证排序结果
        bool sorted = IsSorted();
        
        // 计算耗时
        auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
        
        cout << name << "：耗时=" << duration.count() << "微秒，"
             << "结果=" << (sorted ? "正确" : "错误") << endl;
        
        // 恢复测试前的数据
        for (int i = 0; i < length; i++) {
            data[i] = testData[i];
        }
        
        delete[] testData;
    }
};

4.2 合并操作

顺序表的合并操作在数据处理中非常常见，特别是处理有序数据时。

/**
 * 顺序表合并操作的实现
 * 包含有序合并和无序合并等多种方式
 */
class MergeOperation {
private:
    ElemType *data;
    int length;
    int capacity;
    
public:
    MergeOperation(ElemType *d, int &len, int cap) 
        : data(d), length(len), capacity(cap) {}
    
    // 合并两个有序顺序表
    Status MergeOrderedLists(const ElemType listA[], int lenA,
                           const ElemType listB[], int lenB) {
        // 检查容量是否足够
        if (lenA + lenB > capacity) {
            cout << "错误：容量不足，无法合并！" << endl;
            return ERROR;
        }
        
        int i = 0, j = 0, k = 0;
        
        // 归并过程
        while (i < lenA && j < lenB) {
            if (listA[i] <= listB[j]) {
                data[k++] = listA[i++];
            } else {
                data[k++] = listB[j++];
            }
        }
        
        // 处理剩余元素
        while (i < lenA) {
            data[k++] = listA[i++];
        }
        
        while (j < lenB) {
            data[k++] = listB[j++];
        }
        
        length = lenA + lenB;
        
        cout << "有序合并完成：长度A=" << lenA << "，长度B=" << lenB 
             << "，合并后长度=" << length << endl;
        
        return OK;
    }
    
    // 合并两个无序顺序表（去重）
    Status MergeUniqueLists(const ElemType listA[], int lenA,
                          const ElemType listB[], int lenB) {
        if (lenA + lenB > capacity) {
            cout << "错误：容量不足！" << endl;
            return ERROR;
        }
        
        // 先复制第一个表
        for (int i = 0; i < lenA; i++) {
            data[i] = listA[i];
        }
        length = lenA;
        
        // 添加第二个表中不重复的元素
        for (int i = 0; i < lenB; i++) {
            bool exists = false;
            
            // 检查是否已存在
            for (int j = 0; j < length; j++) {
                if (data[j] == listB[i]) {
                    exists = true;
                    break;
                }
            }
            
            if (!exists) {
                if (length >= capacity) {
                    cout << "错误：容量不足！" << endl;
                    return ERROR;
                }
                data[length++] = listB[i];
            }
        }
        
        cout << "无序合并（去重）完成：原始长度A=" << lenA 
             << "，原始长度B=" << lenB << "，合并后长度=" << length << endl;
        
        return OK;
    }
    
    // 求两个顺序表的交集
    Status Intersection(const ElemType listA[], int lenA,
                       const ElemType listB[], int lenB) {
        length = 0;
        
        for (int i = 0; i < lenA; i++) {
            // 检查listA[i]是否在listB中
            for (int j = 0; j < lenB; j++) {
                if (listA[i] == listB[j]) {
                    // 检查是否已经在结果中（避免重复）
                    bool exists = false;
                    for (int k = 0; k < length; k++) {
                        if (data[k] == listA[i]) {
                            exists = true;
                            break;
                        }
                    }
                    
                    if (!exists) {
                        if (length >= capacity) {
                            cout << "错误：容量不足！" << endl;
                            return ERROR;
                        }
                        data[length++] = listA[i];
                    }
                    break;
                }
            }
        }
        
        cout << "求交集完成：长度A=" << lenA << "，长度B=" << lenB 
             << "，交集大小=" << length << endl;
        
        return OK;
    }
    
    // 求两个顺序表的并集
    Status Union(const ElemType listA[], int lenA,
                const ElemType listB[], int lenB) {
        return MergeUniqueLists(listA, lenA, listB, lenB);
    }
    
    // 求两个顺序表的差集（A - B）
    Status Difference(const ElemType listA[], int lenA,
                     const ElemType listB[], int lenB) {
        length = 0;
        
        for (int i = 0; i < lenA; i++) {
            bool inB = false;
            
            // 检查listA[i]是否在listB中
            for (int j = 0; j < lenB; j++) {
                if (listA[i] == listB[j]) {
                    inB = true;
                    break;
                }
            }
            
            // 如果不在B中，则加入结果
            if (!inB) {
                if (length >= capacity) {
                    cout << "错误：容量不足！" << endl;
                    return ERROR;
                }
                data[length++] = listA[i];
            }
        }
        
        cout << "求差集完成：A长度=" << lenA << "，B长度=" << lenB 
             << "，差集大小=" << length << endl;
        
        return OK;
    }
};

5. 顺序表的应用实例

5.1 学生成绩管理系统

/**
 * 基于顺序表的学生成绩管理系统
 * 演示顺序表在实际应用中的使用
 */
#include <string>
#include <iomanip>

struct Student {
    int id;           // 学号
    string name;      // 姓名
    float score;      // 成绩
    string major;     // 专业
    
    // 重载运算符，便于比较和输出
    bool operator==(const Student &other) const {
        return id == other.id;
    }
    
    bool operator<(const Student &other) const {
        return score < other.score;
    }
    
    friend ostream& operator<<(ostream &os, const Student &stu) {
        os << setw(8) << stu.id << setw(10) << stu.name 
           << setw(8) << fixed << setprecision(1) << stu.score 
           << setw(12) << stu.major;
        return os;
    }
};

class StudentManagementSystem {
private:
    Student *students;   // 学生数组
    int count;          // 当前学生数
    int capacity;       // 系统容量
    
public:
    // 构造函数
    StudentManagementSystem(int initCapacity = 100) {
        capacity = initCapacity;
        students = new Student[capacity];
        count = 0;
        cout << "学生成绩管理系统初始化成功，容量：" << capacity << endl;
    }
    
    // 析构函数
    ~StudentManagementSystem() {
        delete[] students;
        cout << "学生成绩管理系统已销毁" << endl;
    }
    
    // 添加学生
    Status AddStudent(int id, const string &name, float score, const string &major) {
        if (count >= capacity) {
            cout << "错误：系统容量已满！" << endl;
            return ERROR;
        }
        
        // 检查学号是否重复
        for (int i = 0; i < count; i++) {
            if (students[i].id == id) {
                cout << "错误：学号 " << id << " 已存在！" << endl;
                return ERROR;
            }
        }
        
        // 添加新学生
        students[count].id = id;
        students[count].name = name;
        students[count].score = score;
        students[count].major = major;
        count++;
        
        cout << "添加学生成功：" << name << "（学号：" << id << "）" << endl;
        return OK;
    }
    
    // 按学号删除学生
    Status DeleteStudent(int id) {
        for (int i = 0; i < count; i++) {
            if (students[i].id == id) {
                // 移动后续元素
                for (int j = i; j < count - 1; j++) {
                    students[j] = students[j + 1];
                }
                count--;
                
                cout << "删除学生成功：学号 " << id << endl;
                return OK;
            }
        }
        
        cout << "错误：未找到学号为 " << id << " 的学生" << endl;
        return ERROR;
    }
    
    // 按学号查找学生
    Student* FindStudentById(int id) {
        for (int i = 0; i < count; i++) {
            if (students[i].id == id) {
                return &students[i];
            }
        }
        return nullptr;
    }
    
    // 按姓名查找学生（可能重名）
    void FindStudentsByName(const string &name) {
        cout << "查找姓名包含 '" << name << "' 的学生：" << endl;
        bool found = false;
        
        for (int i = 0; i < count; i++) {
            if (students[i].name.find(name) != string::npos) {
                cout << students[i] << endl;
                found = true;
            }
        }
        
        if (!found) {
            cout << "未找到相关学生" << endl;
        }
    }
    
    // 显示所有学生
    void DisplayAllStudents() {
        if (count == 0) {
            cout << "系统中暂无学生信息" << endl;
            return;
        }
        
        cout << "\n所有学生信息：" << endl;
        cout << "==========================================" << endl;
        cout << setw(8) << "学号" << setw(10) << "姓名" 
             << setw(8) << "成绩" << setw(12) << "专业" << endl;
        cout << "------------------------------------------" << endl;
        
        for (int i = 0; i < count; i++) {
            cout << students[i] << endl;
        }
        
        cout << "==========================================" << endl;
        cout << "总计：" << count << " 名学生" << endl;
    }
    
    // 按成绩排序
    void SortByScore(bool ascending = true) {
        for (int i = 0; i < count - 1; i++) {
            for (int j = 0; j < count - 1 - i; j++) {
                bool shouldSwap = ascending ? 
                    students[j].score > students[j + 1].score :
                    students[j].score < students[j + 1].score;
                
                if (shouldSwap) {
                    Student temp = students[j];
                    students[j] = students[j + 1];
                    students[j + 1] = temp;
                }
            }
        }
        
        cout << "按成绩" << (ascending ? "升序" : "降序") << "排序完成" << endl;
    }
    
    // 统计成绩分布
    void ScoreStatistics() {
        if (count == 0) {
            cout << "暂无学生数据" << endl;
            return;
        }
        
        int excellent = 0, good = 0, medium = 0, pass = 0, fail = 0;
        float totalScore = 0;
        float maxScore = students[0].score, minScore = students[0].score;
        
        for (int i = 0; i < count; i++) {
            float score = students[i].score;
            totalScore += score;
            
            if (score > maxScore) maxScore = score;
            if (score < minScore) minScore = score;
            
            if (score >= 90) excellent++;
            else if (score >= 80) good++;
            else if (score >= 70) medium++;
            else if (score >= 60) pass++;
            else fail++;
        }
        
        cout << "\n成绩统计报告：" << endl;
        cout << "------------------------------------------" << endl;
        cout << "学生总数：" << count << endl;
        cout << "平均成绩：" << fixed << setprecision(2) << totalScore / count << endl;
        cout << "最高成绩：" << maxScore << endl;
        cout << "最低成绩：" << minScore << endl;
        cout << "优秀(90-100)：" << excellent << "人" << endl;
        cout << "良好(80-89)：" << good << "人" << endl;
        cout << "中等(70-79)：" << medium << "人" << endl;
        cout << "及格(60-69)：" << pass << "人" << endl;
        cout << "不及格(0-59)：" << fail << "人" << endl;
        cout << "------------------------------------------" << endl;
    }
    
    // 按专业统计
    void StatisticsByMajor() {
        if (count == 0) return;
        
        // 简单的专业统计（实际应用中可能需要更复杂的数据结构）
        cout << "\n按专业统计：" << endl;
        cout << "------------------------------------------" << endl;
        
        for (int i = 0; i < count; i++) {
            string major = students[i].major;
            int majorCount = 0;
            float majorTotalScore = 0;
            
            // 如果这个专业已经统计过，跳过
            bool counted = false;
            for (int j = 0; j < i; j++) {
                if (students[j].major == major) {
                    counted = true;
                    break;
                }
            }
            if (counted) continue;
            
            // 统计该专业
            for (int j = 0; j < count; j++) {
                if (students[j].major == major) {
                    majorCount++;
                    majorTotalScore += students[j].score;
                }
            }
            
            cout << major << "： " << majorCount << "人，平均分：" 
                 << fixed << setprecision(2) << majorTotalScore / majorCount << endl;
        }
        cout << "------------------------------------------" << endl;
    }
};

// 学生管理系统演示
void StudentSystemDemo() {
    cout << "=== 学生成绩管理系统演示 ===" << endl;
    
    StudentManagementSystem sys(50);
    
    // 添加测试数据
    sys.AddStudent(1001, "张三", 85.5, "计算机科学");
    sys.AddStudent(1002, "李四", 92.0, "软件工程");
    sys.AddStudent(1003, "王五", 78.5, "计算机科学");
    sys.AddStudent(1004, "赵六", 88.0, "人工智能");
    sys.AddStudent(1005, "钱七", 95.5, "软件工程");
    sys.AddStudent(1006, "孙八", 62.0, "网络工程");
    
    // 显示所有学生
    sys.DisplayAllStudents();
    
    // 成绩统计
    sys.ScoreStatistics();
    
    // 按专业统计
    sys.StatisticsByMajor();
    
    // 查找学生
    cout << "\n查找学号1003的学生：" << endl;
    Student* stu = sys.FindStudentById(1003);
    if (stu) {
        cout << *stu << endl;
    }
    
    // 按姓名查找
    sys.FindStudentsByName("张");
    
    // 按成绩排序
    sys.SortByScore(false); // 降序
    sys.DisplayAllStudents();
    
    cout << endl;
}

5.2 多项式运算系统

/**
 * 基于顺序表的多项式运算系统
 * 演示顺序表在数学计算中的应用
 */
#include <cmath>

struct PolynomialTerm {
    float coefficient;  // 系数
    int exponent;       // 指数
    
    PolynomialTerm(float coef = 0, int exp = 0) : coefficient(coef), exponent(exp) {}
    
    // 重载运算符
    bool operator==(const PolynomialTerm &other) const {
        return exponent == other.exponent;
    }
    
    bool operator<(const PolynomialTerm &other) const {
        return exponent < other.exponent;
    }
    
    friend ostream& operator<<(ostream &os, const PolynomialTerm &term) {
        if (term.coefficient == 0) return os;
        
        if (term.exponent == 0) {
            os << term.coefficient;
        } else {
            if (term.coefficient != 1 && term.coefficient != -1) {
                os << term.coefficient;
            } else if (term.coefficient == -1) {
                os << "-";
            }
            os << "x";
            if (term.exponent != 1) {
                os << "^" << term.exponent;
            }
        }
        return os;
    }
};

class Polynomial {
private:
    PolynomialTerm *terms;  // 多项式项数组
    int termCount;         // 项数
    int capacity;          // 容量
    
public:
    // 构造函数
    Polynomial(int initCapacity = 50) {
        capacity = initCapacity;
        terms = new PolynomialTerm[capacity];
        termCount = 0;
    }
    
    // 析构函数
    ~Polynomial() {
        delete[] terms;
    }
    
    // 添加项
    Status AddTerm(float coefficient, int exponent) {
        if (termCount >= capacity) {
            cout << "错误：多项式容量已满！" << endl;
            return ERROR;
        }
        
        // 查找是否已存在相同指数的项
        for (int i = 0; i < termCount; i++) {
            if (terms[i].exponent == exponent) {
                terms[i].coefficient += coefficient;
                // 如果系数变为0，删除该项
                if (terms[i].coefficient == 0) {
                    for (int j = i; j < termCount - 1; j++) {
                        terms[j] = terms[j + 1];
                    }
                    termCount--;
                }
                return OK;
            }
        }
        
        // 添加新项
        terms[termCount++] = PolynomialTerm(coefficient, exponent);
        
        // 按指数排序（降序）
        SortTerms();
        
        return OK;
    }
    
    // 按指数排序
    void SortTerms() {
        for (int i = 0; i < termCount - 1; i++) {
            for (int j = 0; j < termCount - 1 - i; j++) {
                if (terms[j].exponent < terms[j + 1].exponent) {
                    PolynomialTerm temp = terms[j];
                    terms[j] = terms[j + 1];
                    terms[j + 1] = temp;
                }
            }
        }
    }
    
    // 显示多项式
    void Display() {
        if (termCount == 0) {
            cout << "0";
            return;
        }
        
        for (int i = 0; i < termCount; i++) {
            if (i > 0 && terms[i].coefficient > 0) {
                cout << " + ";
            } else if (terms[i].coefficient < 0 && i > 0) {
                cout << " - ";
            } else if (terms[i].coefficient < 0) {
                cout << "-";
            }
            
            if (abs(terms[i].coefficient) != 1 || terms[i].exponent == 0) {
                if (i == 0 || terms[i].coefficient < 0) {
                    cout << abs(terms[i].coefficient);
                } else {
                    cout << terms[i].coefficient;
                }
            }
            
            if (terms[i].exponent > 0) {
                cout << "x";
                if (terms[i].exponent > 1) {
                    cout << "^" << terms[i].exponent;
                }
            }
        }
        cout << endl;
    }
    
    // 多项式求值
    float Evaluate(float x) {
        float result = 0;
        for (int i = 0; i < termCount; i++) {
            result += terms[i].coefficient * pow(x, terms[i].exponent);
        }
        return result;
    }
    
    // 多项式相加
    Polynomial Add(const Polynomial &other) {
        Polynomial result(capacity + other.capacity);
        
        // 复制当前多项式的所有项
        for (int i = 0; i < termCount; i++) {
            result.AddTerm(terms[i].coefficient, terms[i].exponent);
        }
        
        // 添加另一个多项式的所有项
        for (int i = 0; i < other.termCount; i++) {
            result.AddTerm(other.terms[i].coefficient, other.terms[i].exponent);
        }
        
        return result;
    }
    
    // 多项式相乘
    Polynomial Multiply(const Polynomial &other) {
        Polynomial result(capacity * other.capacity);
        
        for (int i = 0; i < termCount; i++) {
            for (int j = 0; j < other.termCount; j++) {
                float coef = terms[i].coefficient * other.terms[j].coefficient;
                int exp = terms[i].exponent + other.terms[j].exponent;
                result.AddTerm(coef, exp);
            }
        }
        
        return result;
    }
    
    // 求导数
    Polynomial Derivative() {
        Polynomial result(capacity);
        
        for (int i = 0; i < termCount; i++) {
            if (terms[i].exponent > 0) {
                float coef = terms[i].coefficient * terms[i].exponent;
                int exp = terms[i].exponent - 1;
                result.AddTerm(coef, exp);
            }
        }
        
        return result;
    }
};

// 多项式系统演示
void PolynomialDemo() {
    cout << "=== 多项式运算系统演示 ===" << endl;
    
    Polynomial poly1, poly2;
    
    // 创建第一个多项式：3x^3 + 2x^2 - 5x + 4
    poly1.AddTerm(3, 3);
    poly1.AddTerm(2, 2);
    poly1.AddTerm(-5, 1);
    poly1.AddTerm(4, 0);
    
    // 创建第二个多项式：2x^2 + x - 3
    poly2.AddTerm(2, 2);
    poly2.AddTerm(1, 1);
    poly2.AddTerm(-3, 0);
    
    cout << "多项式1: ";
    poly1.Display();
    
    cout << "多项式2: ";
    poly2.Display();
    
    // 多项式相加
    Polynomial sum = poly1.Add(poly2);
    cout << "多项式1 + 多项式2: ";
    sum.Display();
    
    // 多项式相乘
    Polynomial product = poly1.Multiply(poly2);
    cout << "多项式1 × 多项式2: ";
    product.Display();
    
    // 求导数
    Polynomial derivative = poly1.Derivative();
    cout << "多项式1的导数: ";
    derivative.Display();
    
    // 求值
    float x = 2.0;
    cout << "多项式1在x=" << x << "处的值: " << poly1.Evaluate(x) << endl;
    
    cout << endl;
}

6. 顺序表的性能分析与优化

6.1 时间复杂度分析

操作	最好情况	平均情况	最坏情况	说明
访问元素	O(1)	O(1)	O(1)	随机访问
插入元素	O(1)	O(n)	O(n)	在尾部插入为O(1)
删除元素	O(1)	O(n)	O(n)	在尾部删除为O(1)
查找元素	O(1)	O(n)	O(n)	按位置查找为O(1)
排序操作	O(n)	O(n²)	O(n²)	取决于排序算法

6.2 空间复杂度分析

• 静态顺序表：O(n)，固定大小的存储空间
• 动态顺序表：O(n)，可动态调整的存储空间
• 存储密度：100%，不需要额外存储关系信息

6.3 性能优化策略

/**
 * 顺序表性能优化实现
 * 包含多种优化技术和策略
 */
class OptimizedSeqList {
private:
    ElemType *data;
    int length;
    int capacity;
    float loadFactor;  // 扩容因子
    float shrinkFactor; // 缩容因子
    
public:
    OptimizedSeqList(int initCapacity = 10, float load = 0.75, float shrink = 0.25) 
        : loadFactor(load), shrinkFactor(shrink) {
        capacity = initCapacity;
        data = new ElemType[capacity];
        length = 0;
    }
    
    ~OptimizedSeqList() {
        delete[] data;
    }
    
    // 智能扩容策略
    void SmartResize() {
        int newCapacity;
        
        if (length >= capacity * loadFactor) {
            // 扩容：选择1.5倍或2倍，取最大值
            newCapacity = max(capacity * 2, (int)(capacity * 1.5));
            cout << "触发扩容：" << capacity << " -> " << newCapacity << endl;
        } else if (length <= capacity * shrinkFactor && capacity > 10) {
            // 缩容：减少到当前长度的1.5倍，但不小于初始容量
            newCapacity = max(10, (int)(length * 1.5));
            cout << "触发缩容：" << capacity << " -> " << newCapacity << endl;
        } else {
            return; // 不需要调整
        }
        
        // 执行调整
        ElemType *newData = new ElemType[newCapacity];
        for (int i = 0; i < length; i++) {
            newData[i] = data[i];
        }
        
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }
    
    // 批量插入优化
    Status BatchInsertOptimized(int position, const ElemType elements[], int count) {
        if (position < 1 || position > length + 1) {
            return ERROR;
        }
        
        // 预检查容量
        while (length + count > capacity) {
            SmartResize();
        }
        
        // 一次性移动元素
        for (int i = length - 1; i >= position - 1; i--) {
            data[i + count] = data[i];
        }
        
        // 批量插入
        for (int i = 0; i < count; i++) {
            data[position - 1 + i] = elements[i];
        }
        
        length += count;
        return OK;
    }
    
    // 内存池技术（简化版）
    class MemoryPool {
    private:
        vector<ElemType*> blocks;
        int blockSize;
        int currentBlock;
        int currentIndex;
        
    public:
        MemoryPool(int size = 1000) : blockSize(size), currentBlock(0), currentIndex(0) {
            blocks.push_back(new ElemType[blockSize]);
        }
        
        ~MemoryPool() {
            for (auto block : blocks) {
                delete[] block;
            }
        }
        
        ElemType* Allocate(int count) {
            if (currentIndex + count > blockSize) {
                blocks.push_back(new ElemType[blockSize]);
                currentBlock++;
                currentIndex = 0;
            }
            
            ElemType *ptr = &blocks[currentBlock][currentIndex];
            currentIndex += count;
            return ptr;
        }
    };
    
    // 缓存友好的遍历
    void CacheFriendlyTraverse() {
        // 顺序访问，充分利用CPU缓存
        for (int i = 0; i < length; i += 8) {
            // 一次处理多个元素，减少缓存失效
            for (int j = i; j < min(i + 8, length); j++) {
                // 处理data[j]
                data[j] = data[j]; // 示例操作
            }
        }
    }
    
    // 预分配策略
    void PreAllocate(int expectedSize) {
        if (expectedSize > capacity) {
            int newCapacity = expectedSize * 1.2; // 多分配20%
            ElemType *newData = new ElemType[newCapacity];
            
            for (int i = 0; i < length; i++) {
                newData[i] = data[i];
            }
            
            delete[] data;
            data = newData;
            capacity = newCapacity;
            
            cout << "预分配完成：新容量=" << capacity << endl;
        }
    }
};

7. 顺序表与链表的比较

7.1 性能比较

特性	顺序表	链表
存储结构	连续存储	离散存储
访问方式	随机访问	顺序访问
访问时间复杂度	O(1)	O(n)
插入删除时间复杂度	O(n)	O(1)
存储密度	高（100%）	低（需要额外指针）
内存分配	一次性分配	动态分配
缓存友好性	好	差

7.2 适用场景比较

顺序表适用场景：

1. 需要频繁随机访问元素
2. 数据量相对稳定，变化不大
3. 对内存使用效率要求高
4. 元素体积较小，移动成本低
5. 需要高效的缓存利用率

链表适用场景：

1. 需要频繁插入删除操作
2. 数据量变化较大，无法预估大小
3. 元素体积较大，移动成本高
4. 内存空间碎片化严重
5. 需要实现栈、队列等数据结构

7.3 选择建议

/**
 * 数据结构选择指导
 * 根据具体需求选择顺序表或链表
 */
class DataStructureSelector {
public:
    static void RecommendStructure(const string &scenario, 
                                 bool needRandomAccess,
                                 bool needFrequentInsertDelete,
                                 int dataSize,
                                 int elementSize) {
        cout << "\n应用场景: " << scenario << endl;
        cout << "需求分析:" << endl;
        cout << "  - 随机访问需求: " << (needRandomAccess ? "高" : "低") << endl;
        cout << "  - 插入删除频率: " << (needFrequentInsertDelete ? "高" : "低") << endl;
        cout << "  - 数据规模: " << dataSize << endl;
        cout << "  - 元素大小: " << elementSize << " bytes" << endl;
        
        if (needRandomAccess && !needFrequentInsertDelete) {
            cout << "推荐使用: 顺序表" << endl;
            cout << "理由: 顺序表提供O(1)的随机访问，且存储密度高" << endl;
        } else if (!needRandomAccess && needFrequentInsertDelete) {
            cout << "推荐使用: 链表" << endl;
            cout << "理由: 链表在插入删除方面性能更优" << endl;
        } else if (elementSize > 100) {
            cout << "推荐使用: 链表" << endl;
            cout << "理由: 大元素移动成本高，链表更合适" << endl;
        } else {
            cout << "推荐使用: 顺序表" << endl;
            cout << "理由: 综合性能更优，缓存友好" << endl;
        }
    }
};

// 使用示例
void StructureSelectionDemo() {
    cout << "=== 数据结构选择演示 ===" << endl;
    
    DataStructureSelector::RecommendStructure(
        "学生成绩查询系统", true, false, 1000, 4);
    
    DataStructureSelector::RecommendStructure(
        "文本编辑器缓冲区", false, true, 5000, 1);
    
    DataStructureSelector::RecommendStructure(