• 【数据结构】C++代码定义了一个动态数组(Vector)的数据结构,并实现了一些基本的操作,包括插入、删除、扩容和输出。


    1. // 引入输入输出流库,用于在程序中输入和输出数据
    2. #include
    3. // 引入标准库函数库,提供rand()函数和srand()函数,用于生成随机数
    4. #include
    5. // 引入随机数生成函数库,提供time()函数,用于获取当前时间
    6. #include
    7. // 使用标准命名空间,这样我们就可以直接使用cout和endl等标准库中的元素,而不用在每个地方都写std::cout和std::endl
    8. using namespace std;
    9. // 定义一个结构体vector,包含三个成员变量:size表示向量的大小,count表示向量的元素个数,data是一个指向int类型的动态数组
    10. struct vector {
    11. int size; // size表示向量的大小
    12. int count; // count表示向量的元素个数
    13. int *data; // data是一个指向int类型的动态数组
    14. };
    15. // 定义一个函数getNewVector,用于创建一个新的vector结构体,并初始化其成员变量
    16. vector* getNewVector(int n) {
    17. // 使用new运算符动态分配内存空间,创建一个vector结构体指针p
    18. vector *p = new vector;
    19. // 设置p的成员变量size为n,创建一个大小为n的动态数组
    20. p->size = n;
    21. // 设置p的成员变量count为0,初始化元素个数为0
    22. p->count = 0;
    23. // 使用new运算符动态分配内存空间,创建一个大小为n的动态数组,并赋值给p的成员变量data
    24. p->data = new int[n];
    25. // 返回p指针,即新创建的vector结构体
    26. return p;
    27. }
    28. // 定义一个函数expand,用于扩展vector的大小,将向量的大小扩大一倍
    29. int expand(vector *v) {
    30. // 如果v指针为空,则返回0表示扩展失败
    31. if (v == nullptr) return 0;
    32. // 输出扩展前的向量大小和扩展后的向量大小
    33. cout << "expand v from " << v->size << " to " << 2 * v->size << endl;
    34. // 使用realloc函数重新分配内存空间,将v的成员变量data指向的动态数组扩大一倍,并返回新的地址
    35. int *p = (int *)realloc(v->data, sizeof(int) * 2 * v->size);
    36. // 如果realloc函数返回的地址为空(表示扩展失败),则返回0表示扩展失败
    37. if (p == nullptr) return 0;
    38. // 将v的成员变量data指向新的动态数组
    39. v->data = p;
    40. // 将v的成员变量size扩大一倍,表示向量的大小已经扩展了一倍
    41. v->size *= 2;
    42. // 返回1表示扩展成功
    43. return 1;
    44. }
    45. // 定义一个函数insert,用于在vector中插入元素
    46. int insert(vector *v, int pos, int val) {
    47. // 如果pos小于0或大于等于v的元素个数,则返回0表示插入失败
    48. if (pos < 0 || pos > v->count) return 0;
    49. // 如果v的元素个数已经等于其大小(即已经没有空位可以插入新元素),则需要先调用expand函数扩展向量的大小
    50. if (v->size == v->count && !expand(v)) return 0;
    51. // 从向量的末尾开始向前遍历,将元素向后移动一位,为新插入的元素腾出位置
    52. for (int i = v->count - 1; i >= pos; i--) {
    53. v->data[i + 1] = v->data[i];
    54. }
    55. // 在指定的位置插入新元素val,元素个数加1,表示插入成功
    56. v->data[pos] = val;
    57. v->count += 1;
    58. return 1; // 返回1表示插入成功
    59. }
    60. // 定义一个函数erase,用于从vector中删除指定位置的元素
    61. int erase(vector *v, int pos) {
    62. // 如果pos小于0或者大于等于vector的元素个数,返回0表示删除失败
    63. if (pos < 0 || pos >= v->count) return 0;
    64. // 从要删除元素的位置pos+1开始,将后面的所有元素向前移动一位
    65. for (int i = pos + 1; i < v->count; i++) {
    66. v->data[i - 1] = v->data[i];
    67. }
    68. // 删除元素后,vector的元素个数减1
    69. v->count -= 1;
    70. // 返回1表示删除成功
    71. return 1;
    72. }
    73. // 定义一个函数output_vector,用于输出vector的内容
    74. void output_vector(vector *v) {
    75. // 初始化len为0,用于计算vector中所有元素位置的宽度
    76. int len = 0;
    77. // 遍历vector中的所有元素,计算每个元素位置的宽度并累加到len中
    78. for (int i = 0; i < v->size; i++) {
    79. len += printf("%3d", i);
    80. }
    81. // 输出一个换行符
    82. cout << endl;
    83. // 根据len的宽度输出相应数量的短横线
    84. for (int i = 0; i < len; i++) cout << "-";
    85. cout << endl;
    86. // 遍历vector中所有的元素,并输出它们的值
    87. for (int i = 0; i < v->count; i++) {
    88. cout << v->data[i] << " ";
    89. }
    90. // 再输出一个换行符,用于分隔不同的输出内容
    91. cout << endl << endl;
    92. // 返回,结束函数的执行
    93. return;
    94. }
    95. // 定义一个函数clear,用于释放vector所占用的内存空间
    96. void clear(vector *v) {
    97. // 如果v指针为空,直接返回,不执行任何操作
    98. if (v == nullptr) return;
    99. // 释放v->data指向的动态数组所占用的内存空间
    100. delete[] v->data;
    101. // 释放v结构体所占用的内存空间
    102. delete v;
    103. // 返回,结束函数的执行
    104. return;
    105. }
    106. // 程序的主入口
    107. int main() {
    108. // 使用当前时间作为随机数生成器的种子,这样每次运行程序时生成的随机数序列都会不同
    109. srand(time(0));
    110. // 定义常量MAX_OP为20,用于限制操作次数
    111. #define MAX_OP 20
    112. // 创建一个大小为2的动态数组,并将其指针赋值给v
    113. vector *v = getNewVector(2);
    114. // 循环执行MAX_OP次操作
    115. for (int i = 0; i < MAX_OP; i++) {
    116. // 随机生成一个操作码op(0, 1, 2, 3),一个位置pos,一个值val和一个返回值ret
    117. int op = rand() % 4, pos, val, ret;
    118. // 根据操作码执行不同的操作
    119. switch (op) {
    120. case 0:
    121. case 1:
    122. case 2:
    123. // 随机生成一个在v的长度范围内的位置pos
    124. pos = rand() % (v->count + 2);
    125. // 随机生成一个在0到100之间的值val
    126. val = rand() % 100;
    127. // 调用insert函数在v的pos位置插入val,并将返回值存储在ret中
    128. ret = insert(v, pos, val);
    129. // 输出插入操作的结果,包括插入的值、插入的位置和返回值
    130. cout << "insert " << val << " at " << pos << " to vector = " << ret << endl;
    131. break;
    132. case 3:
    133. // 随机生成一个在v的长度范围内的位置pos
    134. pos = rand() % (v->count + 2);
    135. // 调用erase函数删除v中pos位置的元素,并将返回值存储在ret中
    136. ret = erase(v, pos);
    137. // 输出删除操作的结果,包括删除的位置和返回值
    138. cout << "erase item at " << pos << " in vector = " << ret << endl;
    139. break;
    140. }
    141. // 调用output_vector函数输出当前v的内容
    142. output_vector(v);
    143. }
    144. // 调用clear函数释放v所占用的内存空间
    145. clear(v);
    146. // 返回0,表示程序正常退出
    147. return 0;
    148. }

    这段代码定义了一个动态数组(Vector)的数据结构,并实现了一些基本的操作,包括插入、删除、扩容和输出。

    代码中定义了一个结构体Vector,它包含三个成员变量:sizecountdatasize表示数组的容量大小,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的动态数组,并使用循环执行一系列随机操作,包括插入、删除、扩容和输出操作。每次操作根据随机数生成器生成的操作类型和位置进行相应的操作,并输出相关信息。最后调用清空函数清空动态数组并释放内存空间。

  • 相关阅读:
    2024.3.11 C++作业
    安装使用TinyCore Linux的一些收获
    【课程】SP Module2 辅音和元音的声学
    golang学习笔记系列之变量和常量
    使用 Allatori 进行 Jar 包混淆
    PHP 变动:PHP 8 版本下字符串与数值的弱比较
    spring源码篇(八)事务的原理
    像Django一样开发FastAPI之: AppBoot 入门指南
    【python】高斯日记
    线性表4 双向链表及基本操作实例
  • 原文地址:https://blog.csdn.net/dsafefvf/article/details/132740362