顺序表操作：初始化、尾部添加与插入

"线性表——数据机构.md" 线性表是一种基本的数据结构，它由n(n>=0)个相同类型元素构成的有限序列。在计算机科学中，线性表可以分为两种实现方式：顺序表和链表。本文主要讨论的是顺序表。 顺序表是线性表的一种静态存储结构，其中元素在内存中是连续存放的。这种结构使得我们可以直接通过下标访问任意位置的元素，但插入和删除操作可能涉及大量元素的移动。 1. **顺序表的结构定义** 顺序表通常用数组来实现。在C++中，可以定义一个结构体`sqlist`来表示顺序表，包含三个成员： - `int* head`：指向数组的首地址。 - `unsigned int rongliang`：线性表的容量，即数组能容纳的最大元素数量。 - `unsigned int shuliang`：已经储存的元素数量。 2. **初始化顺序表** 初始化一个顺序表需要设置其容量和存储空间。在示例代码中，`chushihua`函数用于初始化结构体，设定初始容量为5，并分配相应大小的内存。同时，设置存储数量为0，表示目前表中没有元素。 3. **在顺序表尾部添加元素** 添加元素到顺序表尾部是最常见的操作之一。在`add_end`函数中，首先检查当前表是否已满（即存储数量等于容量）。如果满了，需要进行扩容，通常是将容量增加10，然后重新分配内存，将旧数组中的元素复制到新数组，释放旧空间，最后将新数组的地址赋给`head`。如果还有剩余空间，可以直接在数组末尾添加元素并更新存储数量。 4. **在顺序表中插入元素** 插入操作可能会涉及到元素的移动。在`charu`函数中，首先检查传入的参数是否合法，然后判断插入位置是否正确。如果插入位置大于当前存储数量，说明插入位置超出范围，应给出错误提示。如果位置正确，需要从插入点开始，将所有元素向后移动一位，然后在插入点放入新元素。这会导致插入操作的时间复杂度较高，为O(n)，因为可能需要移动n个元素。 顺序表的优点在于访问速度快，可以通过下标直接访问元素，但插入和删除操作效率较低，特别是当需要在表中间插入或删除元素时。因此，在设计数据结构时，需要根据具体应用场景来选择合适的数据结构。