- // 引入输入输出流库,用于在程序中输入和输出数据
- #include
-
- // 引入标准库函数库,提供rand()函数和srand()函数,用于生成随机数
- #include
-
- // 引入随机数生成函数库,提供time()函数,用于获取当前时间
- #include
-
- // 使用标准命名空间,这样我们就可以直接使用cout和endl等标准库中的元素,而不用在每个地方都写std::cout和std::endl
- using namespace std;
-
- // 定义一个结构体vector,包含三个成员变量:size表示向量的大小,count表示向量的元素个数,data是一个指向int类型的动态数组
- struct vector {
- int size; // size表示向量的大小
- int count; // count表示向量的元素个数
- int *data; // data是一个指向int类型的动态数组
- };
-
- // 定义一个函数getNewVector,用于创建一个新的vector结构体,并初始化其成员变量
- vector* getNewVector(int n) {
- // 使用new运算符动态分配内存空间,创建一个vector结构体指针p
- vector *p = new vector;
-
- // 设置p的成员变量size为n,创建一个大小为n的动态数组
- p->size = n;
-
- // 设置p的成员变量count为0,初始化元素个数为0
- p->count = 0;
-
- // 使用new运算符动态分配内存空间,创建一个大小为n的动态数组,并赋值给p的成员变量data
- p->data = new int[n];
-
- // 返回p指针,即新创建的vector结构体
- return p;
- }
-
- // 定义一个函数expand,用于扩展vector的大小,将向量的大小扩大一倍
- int expand(vector *v) {
- // 如果v指针为空,则返回0表示扩展失败
- if (v == nullptr) return 0;
-
- // 输出扩展前的向量大小和扩展后的向量大小
- cout << "expand v from " << v->size << " to " << 2 * v->size << endl;
-
- // 使用realloc函数重新分配内存空间,将v的成员变量data指向的动态数组扩大一倍,并返回新的地址
- int *p = (int *)realloc(v->data, sizeof(int) * 2 * v->size);
-
- // 如果realloc函数返回的地址为空(表示扩展失败),则返回0表示扩展失败
- if (p == nullptr) return 0;
-
- // 将v的成员变量data指向新的动态数组
- v->data = p;
-
- // 将v的成员变量size扩大一倍,表示向量的大小已经扩展了一倍
- v->size *= 2;
-
- // 返回1表示扩展成功
- return 1;
- }
-
- // 定义一个函数insert,用于在vector中插入元素
- int insert(vector *v, int pos, int val) {
- // 如果pos小于0或大于等于v的元素个数,则返回0表示插入失败
- if (pos < 0 || pos > v->count) return 0;
-
- // 如果v的元素个数已经等于其大小(即已经没有空位可以插入新元素),则需要先调用expand函数扩展向量的大小
- if (v->size == v->count && !expand(v)) return 0;
-
- // 从向量的末尾开始向前遍历,将元素向后移动一位,为新插入的元素腾出位置
- for (int i = v->count - 1; i >= pos; i--) {
- v->data[i + 1] = v->data[i];
- }
-
- // 在指定的位置插入新元素val,元素个数加1,表示插入成功
- v->data[pos] = val;
- v->count += 1;
- return 1; // 返回1表示插入成功
- }
- // 定义一个函数erase,用于从vector中删除指定位置的元素
- int erase(vector *v, int pos) {
- // 如果pos小于0或者大于等于vector的元素个数,返回0表示删除失败
- if (pos < 0 || pos >= v->count) return 0;
-
- // 从要删除元素的位置pos+1开始,将后面的所有元素向前移动一位
- for (int i = pos + 1; i < v->count; i++) {
- v->data[i - 1] = v->data[i];
- }
-
- // 删除元素后,vector的元素个数减1
- v->count -= 1;
-
- // 返回1表示删除成功
- return 1;
- }
-
- // 定义一个函数output_vector,用于输出vector的内容
- void output_vector(vector *v) {
- // 初始化len为0,用于计算vector中所有元素位置的宽度
- int len = 0;
-
- // 遍历vector中的所有元素,计算每个元素位置的宽度并累加到len中
- for (int i = 0; i < v->size; i++) {
- len += printf("%3d", i);
- }
-
- // 输出一个换行符
- cout << endl;
-
- // 根据len的宽度输出相应数量的短横线
- for (int i = 0; i < len; i++) cout << "-";
- cout << endl;
-
- // 遍历vector中所有的元素,并输出它们的值
- for (int i = 0; i < v->count; i++) {
- cout << v->data[i] << " ";
- }
-
- // 再输出一个换行符,用于分隔不同的输出内容
- cout << endl << endl;
-
- // 返回,结束函数的执行
- return;
- }
-
- // 定义一个函数clear,用于释放vector所占用的内存空间
- void clear(vector *v) {
- // 如果v指针为空,直接返回,不执行任何操作
- if (v == nullptr) return;
-
- // 释放v->data指向的动态数组所占用的内存空间
- delete[] v->data;
-
- // 释放v结构体所占用的内存空间
- delete v;
-
- // 返回,结束函数的执行
- return;
- }
- // 程序的主入口
- int main() {
-
- // 使用当前时间作为随机数生成器的种子,这样每次运行程序时生成的随机数序列都会不同
- srand(time(0));
-
- // 定义常量MAX_OP为20,用于限制操作次数
- #define MAX_OP 20
-
- // 创建一个大小为2的动态数组,并将其指针赋值给v
- vector *v = getNewVector(2);
-
- // 循环执行MAX_OP次操作
- for (int i = 0; i < MAX_OP; i++) {
-
- // 随机生成一个操作码op(0, 1, 2, 3),一个位置pos,一个值val和一个返回值ret
- int op = rand() % 4, pos, val, ret;
-
- // 根据操作码执行不同的操作
- switch (op) {
- case 0:
- case 1:
- case 2:
- // 随机生成一个在v的长度范围内的位置pos
- pos = rand() % (v->count + 2);
- // 随机生成一个在0到100之间的值val
- val = rand() % 100;
- // 调用insert函数在v的pos位置插入val,并将返回值存储在ret中
- ret = insert(v, pos, val);
- // 输出插入操作的结果,包括插入的值、插入的位置和返回值
- cout << "insert " << val << " at " << pos << " to vector = " << ret << endl;
- break;
- case 3:
- // 随机生成一个在v的长度范围内的位置pos
- pos = rand() % (v->count + 2);
- // 调用erase函数删除v中pos位置的元素,并将返回值存储在ret中
- ret = erase(v, pos);
- // 输出删除操作的结果,包括删除的位置和返回值
- cout << "erase item at " << pos << " in vector = " << ret << endl;
- break;
- }
-
- // 调用output_vector函数输出当前v的内容
- output_vector(v);
- }
-
- // 调用clear函数释放v所占用的内存空间
- clear(v);
-
- // 返回0,表示程序正常退出
- return 0;
- }
这段代码定义了一个动态数组(Vector)的数据结构,并实现了一些基本的操作,包括插入、删除、扩容和输出。
代码中定义了一个结构体Vector
,它包含三个成员变量:size
、count
和data
。size
表示数组的容量大小,count
表示数组中实际元素的数量,data
是一个指向整数数组的指针。
函数getNewVector(int n)
用于创建一个新的动态数组,并返回指向它的指针。该函数接受一个整数参数n
,表示数组的初始容量大小。在函数中,首先使用new
运算符动态分配了一个Vector
结构体的内存空间,然后设置了该结构体的成员变量,包括容量大小、计数和数据指针。最后返回指向该结构体的指针。
函数expand(Vector *v)
用于扩容动态数组。该函数接受一个指向Vector
结构体的指针v
作为参数。首先检查指针是否为空,如果为空则返回0。然后输出扩容前的容量大小,使用new
运算符动态分配两倍于原容量的新数组,将原数组的数据复制到新数组中,删除原数组的数据指针,将新数组的指针赋值给原数组的数据指针,最后将原数组的容量大小更新为新容量大小的两倍,并返回1表示扩容成功。
函数insert(Vector *v, int pos, int val)
用于在动态数组中插入一个元素。该函数接受三个参数:指向Vector
结构体的指针v
、要插入的位置pos
和要插入的元素值val
。首先检查位置是否合法和是否需要扩容,如果需要则调用expand(v)
函数进行扩容。然后从数组的末尾开始遍历,将数组中的元素向后移动一位,为要插入的元素腾出位置。最后将要插入的元素插入到指定位置,增加计数,并返回1表示插入成功。
函数erase(Vector *v, int pos)
用于从动态数组中删除一个元素。该函数接受两个参数:指向Vector
结构体的指针v
和要删除的位置pos
。首先检查位置是否合法,如果非法则返回0。然后从要删除的位置开始遍历,将后面的元素向前移动一位,减少计数。最后返回1表示删除成功。
函数outputVector(Vector *v)
用于输出动态数组的内容。该函数接受一个指向Vector
结构体的指针v
作为参数。首先计算数组中的所有位置的总长度,并输出一个表格的横线。然后遍历数组中的所有元素,并输出每个元素及其位置信息。最后输出一个空行作为分隔符。
函数clear(Vector *v)
用于清空动态数组,并释放内存空间。该函数接受一个指向Vector
结构体的指针v
作为参数。首先检查指针是否为空,如果为空则直接返回。然后删除原数组的数据指针,并释放其内存空间。最后删除指向Vector
结构体的指针。
在主函数中,首先使用当前时间作为随机数生成器的种子,并定义了一个常量MAX_OP
表示要执行的最大操作次数。然后创建一个初始容量为2的动态数组,并使用循环执行一系列随机操作,包括插入、删除、扩容和输出操作。每次操作根据随机数生成器生成的操作类型和位置进行相应的操作,并输出相关信息。最后调用清空函数清空动态数组并释放内存空间。