5.C++顺序表

一，顺序表的概念

顺序表是一种线性的数据结构，其中数据元素按照特定的顺序依次存储在连续的内存空间中。它由一系列元素组成，每个元素都与唯一的索引（或者叫下标）相关联，索引从0开始递增。 元素可以是整数，可以是浮点数，可以是任意类型，包括结构体或者对象，等等。

二，顺序表的元素插入

顺序表的元素插入，就是指给定一个索引和一个元素，将这个元素插入到对应的索引位置上，这个位置以后的所有元素都要往后移动一个位置。

第1步、判断插入位置是否合法，如果不合法则抛出异常（比如：原本只有5个元素，给定的索引是100，那显然这个位置是不合法的）。

第2步、如果顺序表已满，则需要扩容顺序表，一般是把原有顺序表的容量进行倍增。

第3步、将插入位置之后的元素向后移动，为新元素腾出空间。

第4步、将新元素插入到指定位置。

第5步、更新顺序表的大小。

三，顺序表的元素删除

顺序表的元素删除，就是指给定一个索引，将这个索引上的元素删除，并且把这个索引位置以后的所有元素都往前移动一个位置。

第1步、判断删除位置是否合法，如果不合法则抛出异常。

第2步、如果删除位置为最后一个元素，直接将顺序表的大小减 1。

第3步、如果删除位置不是最后一个元素，将删除位置之后的元素向前移动，覆盖要删除的元素。

第4步、更新顺序表的大小。

四，顺序表的元素查找

顺序表的元素查找（也叫 “查找 / 检索”），是指在给定的顺序表中，根据指定的条件（比如 “查找值为 X 的元素” 或 “查找索引为 i 的元素”），确定目标元素是否存在、以及它在顺序表中的位置（索引）的操作。

第1步、遍历整个顺序表，对顺序表中的每个元素，和指定元素进行比较，如果相等则返回当前的索引；

第2步、如果遍历完所有的顺序表元素，都没有找到相等的元素，则返回 -1；

五，顺序表的元素索引

顺序表的元素索引，是指给定一个索引值，通过下标访问，直接在顺序表中获取元素的值，时间复杂度 O(1)。

直接通过索引，访问，获得对应元素的值即可。

六，顺序表的元素修改

将顺序表中指定的元素更新为新的值。

七，C嘎嘎实现

#include <iostream> using namespace std; //线性表元素的类型 #define eleType int //顺序表结构体定义 typedef struct SequentialList { eleType* elements; // 存储数据的数组 int size; // 当前元素个数 int capacity; // 数组容量 } SequentialList; // 初始化顺序表 void initializeList(SequentialList* list, int capacity) { //申请存储空间 list->elements = new eleType[capacity]; //初始化元素个数和容量 list->size = 0; list->capacity = capacity; } // 销毁顺序表 void destroyList(SequentialList* list) { delete[] list->elements; list->elements = nullptr; list->size = 0; list->capacity = 0; } // 判断顺序表是否为空 bool isEmpty(const SequentialList* list) { //判断数组是否为空 if (list->elements == nullptr) { cout << "顺序表未初始化" << endl; return true; } //判断元素个数是否为0 return list->size == 0; } // 判断顺序表是否已满 bool isFull(const SequentialList* list) { //判断数组是否为空 if (list->elements == nullptr) { cout << "顺序表未初始化" << endl; return true; } //判断数组是否已满 return list->size == list->capacity; } // 扩容顺序表（倍增策略） void expandList(SequentialList* list) { //判断数组是否为空 if (list->elements == nullptr) { cout << "顺序表未初始化" << endl; return; } int newCapacity = list->capacity * 2; eleType* newElements = new eleType[newCapacity]; for (int i = 0; i < list->size; i++) { newElements[i] = list->elements[i]; } delete[] list->elements; list->elements = newElements; list->capacity = newCapacity; cout << "扩容完成，新容量：" << newCapacity << endl; } // 插入元素到指定位置 bool insertElement(SequentialList* list, int index, eleType element) { //判断数组是否为空 if (list->elements == nullptr) { cout << "顺序表未初始化" << endl; return false; } //判断插入位置是否合法 if (index < 0 || index > list->size) { cout << "插入位置不合法" << endl; return false; } //判断是否已满 if (isFull(list)) { cout << "顺序表已满，正在扩容..." << endl; expandList(list); } // 后移元素 //从最后索引开始，将元素后移一位 for (int i = list->size; i > index; i--) { list->elements[i] = list->elements[i - 1]; } // 插入元素 list->elements[index] = element; //元素个数加1 list->size++; return true; } // 删除指定位置的元素 bool deleteElement(SequentialList* list, int index) { //判断数组是否为空 if (list->elements == nullptr) { cout << "顺序表未初始化" << endl; return false; } //范围检测 if (index < 0 || index >= list->size) { cout << "删除位置不合法" << endl; return false; } // 前移元素 //从索引开始，将元素前移一位 for (int i = index; i < list->size - 1; i++) { list->elements[i] = list->elements[i + 1]; } // 元素个数减1 list->size--; return true; } // 按值查找元素，返回索引，未找到返回-1 int findElement(const SequentialList* list, eleType target) { //判断数组是否为空 if (list->elements == nullptr) { cout << "顺序表未初始化" << endl; return -1; } //遍历查找 for (int i = 0; i < list->size; i++) { if (list->elements[i] == target) { return i; } } //未找到 return -1; } // 按索引获取元素 eleType getElement(const SequentialList* list, int index) { //判断数组是否为空 if (list->elements == nullptr) { cout << "顺序表未初始化" << endl; return -1; // 这里返回-1仅作示意，可根据实际需求调整 } //范围检测 if (index < 0 || index >= list->size) { cout << "索引不合法" << endl; return -1; // 这里返回-1仅作示意，可根据实际需求调整 } return list->elements[index]; } // 修改指定位置的元素 bool modifyElement(SequentialList* list, int index, eleType newElement) { //判断数组是否为空 if (list->elements == nullptr) { cout << "顺序表未初始化" << endl; return false; } // 检测索引是否合法（必须是已存在元素的索引） if (index < 0 || index >= list->size) { cout << "修改位置不合法" << endl; return false; } // 直接修改指定索引的元素值 list->elements[index] = newElement; return true; } // 打印顺序表 void printList(const SequentialList* list) { //判断数组是否为空 if (isEmpty(list)) { cout << "顺序表为空" << endl; return; } cout << "顺序表内容："; for (int i = 0; i < list->size; i++) { cout << list->elements[i] << " "; } cout << endl; } // 测试主函数 int main() { SequentialList list; cout << "初始化顺序表..." << endl; initializeList(&list, 5); // 初始化容量为5 insertElement(&list, 0, 10); insertElement(&list, 1, 20); insertElement(&list, 2, 30); insertElement(&list, 1, 15); // 在索引1处插入15 cout << "插入元素后："; printList(&list); // 输出: 顺序表内容：10 15 20 30 cout << "索引2处的元素：" << getElement(&list, 2) << endl; // 输出: 20 int target = 20; int pos = findElement(&list, target); if (pos != -1) { cout << "元素" << target << "的索引：" << pos << endl; // 输出: 2 } else { cout << "未找到元素" << target << endl; } deleteElement(&list, 1); // 删除索引1处的元素 cout << "删除后："; printList(&list); // 输出: 删除后：顺序表内容：10 20 30 // 测试修改功能 modifyElement(&list, 1, 200); // 将索引1的元素改为200 cout << "修改后："; printList(&list); // 输出: 修改后：顺序表内容：10 200 30 // 测试非法修改（索引越界） modifyElement(&list, 5, 999); // 输出: 修改位置不合法 destroyList(&list); return 0; }

运行：