devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构 - C/C++ - 数组

作者：很楠不爱3 | 2024-04-29 13:34:54

赞

踩

数据结构 - C/C++ - 数组

目录

结构特性

内存布局

结构样式

结构拓展

数据初始

元素访问

插入元素

删除元素

查找元素

修改元素

结构设计

成员变量

构造函数

功能函数

示例代码

结构特性

  • 长度固定：数组的长度在创建时已经被确定，如果需要动态改变数组的长度，可以考虑使用动态数组。

  • 连续性：数组中的所有元素在内存中是连续存储的。数组可以快速访问任意元素，单插入和删除操作会影响效率。

  • 一致性：数组中的所有元素必须都是相同的类型。

  • 索引：索引从0开始，数组下标上限长度减去1。

内存布局

  • 数组在内存中占据一块连续的内存空间。

  • 数组起始地址是数组首个元素的地址(数组名即为首地址)。

  • 每个元素占据的内存空间是相同的，具体大小取决于与元素的类型。

  • 通过索引可以快速访问数组中的任意元素。

    1. #include <iostream>
    2.  
    3. int main()
    4. {
    5.     int Arr[10] = { 1,3,2,5,4 };
    6.  
    7.     printf("Arr.BaseAddr -> %p \r\n", Arr);
    8.     printf("Arr.BaseAddr -> %p \r\n", &Arr[0]);
    9.  
    10.     for (int Index = 0; Index < sizeof(Arr) / sizeof(Arr[0]); Index++)
    11.     {
    12.         printf("Arr[%d] -> %p -> %d \r\n", Index, &Arr[Index], Arr[Index]);
    13.     }
    14.  
    15.     return 0;
    16. }

 

结构样式

  • 静态数组：编译时确定数组长度，无法在运行期间修改其长度。

  • 动态数组：运行时动态分配内存，可以在运行期间修改其长度。(C++STD::VECTOR)

结构拓展

数据初始

  1. #include <iostream>
  2.  
  3. int main()
  4. {
  5.     //stack
  6.     int Arr1[5];
  7.     int Arr2[5] = { 0 };
  8.     int Arr3[] = { 1,2,3,4,5 };
  9.  
  10.     //heap
  11.     int* p1 = new int[5];
  12.     delete[] p1;
  13.     int* p2 = new int[5]{ 1,2,3,4,5 };
  14.     delete[] p2;
  15.  
  16.     return 0;
  17. }

元素访问

  • 内存图解
  • 实例代码 
      1. #include <iostream>
      2.  
      3. int main()
      4. {
      5. 	int Arr[5] = { 1,3,2,5,4 };
      6. 	
      7. 	Arr[0] = 1;
      8. 	Arr[1] = 2;
      9. 	Arr[2] = 3;
      10. 	Arr[3] = 4;
      11. 	Arr[4] = 5;
      12.  
      13. 	return 0;
      14. }
  • 汇编分析  
      1. 	int Arr[5] = { 1,3,2,5,4 };
      2. 00414635  mov         dword ptr [ebp-18h],1  
      3. 0041463C  mov         dword ptr [ebp-14h],3  
      4. 00414643  mov         dword ptr [ebp-10h],2  
      5. 0041464A  mov         dword ptr [ebp-0Ch],5  
      6. 00414651  mov         dword ptr [ebp-8],4  
      7. 	
      8. 	Arr[0] = 1;
      9. 00414658  mov         eax,4  
      10. 0041465D  imul        ecx,eax,0  
      11. 00414660  mov         dword ptr [ebp+ecx-18h],1  
      12. 	Arr[1] = 2;
      13. 00414668  mov         eax,4  
      14. 0041466D  shl         eax,0  
      15. 00414670  mov         dword ptr [ebp+eax-18h],2  
      16. 	Arr[2] = 3;
      17. 00414678  mov         eax,4  
      18. 0041467D  shl         eax,1  
      19. 0041467F  mov         dword ptr [ebp+eax-18h],3  
      20. 	Arr[3] = 4;
      21. 00414687  mov         eax,4  
      22. 0041468C  imul        ecx,eax,3  
      23. 0041468F  mov         dword ptr [ebp+ecx-18h],4  
      24. 	Arr[4] = 5;
      25. 00414697  mov         eax,4  
      26. 0041469C  shl         eax,2  
      27. 0041469F  mov         dword ptr [ebp+eax-18h],5

    • ebp-18h == 数组首地址

    • mov dword ptr [ebp+ecx-18h],1 == ebp-18h + 0 * 4

    • mov dword ptr [ebp+eax-18h],2 == ebp-18h + 1 * 4

    • mov dword ptr [ebp+eax-18h],3 == ebp-18h + 2 * 4

    • mov dword ptr [ebp+ecx-18h],4 == ebp-18h + 3 * 4

    • mov dword ptr [ebp+eax-18h],5 == ebp-18h + 4 * 4

插入元素

  • 插入步骤
  • 代码实现 
      1. void Insert(int* p, int nLength, int nIndex, int nVar)
      2. {
      3. 	for (int i = nLength - 1; i > nIndex; i--)
      4. 	{
      5. 		p[i] = p[i - 1];
      6. 	}
      7.  
      8. 	p[nIndex] = nVar;
      9. }

删除元素

  • 删除步骤
  • 代码实现 
      1. void Remove(int* p, int nLength, int nIndex)
      2. {
      3. 	for (int i = nIndex; i < nLength - 1; i++)
      4. 	{
      5. 		p[i] = p[i + 1];
      6. 	}
      7. }

查找元素

    1. int Find(int* p, int nLength, int nVar)
    2. {
    3. 	for (int i = 0; i < nLength; i++)
    4. 	{
    5. 		if (p[i] == nVar)
    6. 		{
    7. 			return i;
    8. 		}
    9. 	}
    10. 	return -1;
    11. }

修改元素

    1. 	int Arr[6] = { 1,2,3,4,5 };
    2. 	Arr[0] = 11;
    3. 	*(Arr + 1) = 22;

结构设计

成员变量

  1. 	T*	data;		//动态数组指针
  2. 	int size;		//数组元素个数
  3. 	int capacity;	//数组容量大小

构造函数

  • 默认构造函数
  • 有参构造函数
  • 拷贝构造函数
  • 移动构造函数
  • 列表构造函数

功能函数

  • 元素个数
  • 数组容量
  • 是否为空
  • 下标访问
  • 插入元素
  • 删除元素
  • 查找元素

示例代码

  1. #include <iostream>
  2. #include <vector>
  3.  
  4. template <typename T>
  5. class Vector
  6. {
  7. private:			//成员变量
  8. 	T*	data;		//动态数组指针
  9. 	int size;		//数组元素个数
  10. 	int capacity;	//数组容量大小
  11.  
  12. public:				//构造析构
  13. 	//默认构造函数
  14. 	Vector() : data(nullptr), size(0), capacity(0)
  15. 	{
  16.  
  17. 	}
  18. 	
  19. 	//有参构造函数
  20. 	Vector(int size, const T& var) : size(size), capacity(size)
  21. 	{
  22. 		this->data = new T[capacity];
  23. 		for (size_t i = 0; i < capacity; i++)
  24. 		{
  25. 			data[i] = var;
  26. 		}
  27. 	}
  28.  
  29. 	//拷贝构造函数
  30. 	Vector(const Vector& ref) : size(ref.size), capacity(ref.capacity)
  31. 	{
  32. 		this->data = new T[capacity];
  33. 		for (size_t i = 0; i < capacity; i++)
  34. 		{
  35. 			this->data[i] = ref.data[i];
  36. 		}
  37. 	}
  38.  
  39. 	//移动构造函数
  40. 	Vector(Vector&& other)noexcept : data(other.data), size(other.size), capacity(other.capacity)
  41. 	{
  42. 		other.data = nullptr;
  43. 		other.size = 0;
  44. 		other.capacity = 0;
  45. 	}
  46.  
  47. 	//列表构造函数
  48. 	Vector(std::initializer_list<T> initlist) : size(initlist.size()), capacity(initlist.size())
  49. 	{
  50. 		this->data = new T[capacity];
  51. 		int i = 0;
  52. 		for (const auto& value: initlist)
  53. 		{
  54. 			data[i++] = value;
  55. 		}
  56. 	}
  57.  
  58. 	//默认析构函数
  59. 	~Vector()
  60. 	{
  61. 		if (this->data != NULL)
  62. 		{
  63. 			delete[] this->data;
  64. 		}
  65. 	}
  66.  
  67. 	
  68. public:				//成员函数
  69. 	//获取元素个数
  70. 	int Size() const
  71. 	{
  72. 		return this->size;
  73. 	}
  74.  
  75. 	//获取数组容量
  76. 	int Capacity() const
  77. 	{
  78. 		return this->capacity;
  79. 	}
  80.  
  81. 	//数组是否为空
  82. 	bool Empty()
  83. 	{
  84. 		return this->size == 0 ? true : false;
  85. 	}
  86.  
  87. 	//下标获取元素
  88. 	T& operator[](int nIndex)
  89. 	{
  90. 		return this->data[nIndex];
  91. 	}
  92.  
  93. 	//末尾追加元素
  94. 	void Push_Back(const T& value)
  95. 	{
  96. 		//判断容器容量
  97. 		if (this->size >= this->capacity)
  98. 		{
  99. 			//容量大小修正
  100. 			capacity = (capacity == 0) ? 1 : capacity * 2;
  101.  
  102. 			//申请扩容内存
  103. 			T* tempData = new T[capacity];
  104.  
  105. 			//拷贝默认数据
  106. 			for (int i = 0; i < size; i++)
  107. 			{
  108. 				tempData[i] = this->data[i];
  109. 			}
  110.  
  111. 			//释放默认内存
  112. 			delete[] this->data;
  113.  
  114. 			//修正数据指针
  115. 			this->data = tempData;
  116. 		}
  117.  
  118. 		this->data[size] = value;
  119. -		size++;
  120. 	}
  121.  
  122. 	//插入元素数据
  123. 	void Insert(int nIndex, const T& value)
  124. 	{
  125. 		//判断索引序号
  126. 		if (nIndex < 0 || nIndex > size)
  127. 		{
  128. 			throw std::out_of_range("Invalid Index");
  129. 		}
  130.  
  131. 		//判断容器容量
  132. 		if (this->size >= this->capacity)
  133. 		{
  134. 			//容量大小修正
  135. 			capacity = (capacity == 0) ? 1 : capacity * 2;
  136.  
  137. 			//申请扩容内存
  138. 			T* tempData = new T[capacity];
  139.  
  140. 			//拷贝默认数据
  141. 			for (int i = 0; i < size; i++)
  142. 			{
  143. 				tempData[i] = this->data[i];
  144. 			}
  145.  
  146. 			//释放默认内存
  147. 			delete[] this->data;
  148.  
  149. 			//修正数据指针
  150. 			this->data = tempData;
  151. 		}
  152.  
  153. 		//指定位置插入
  154. 		for (int i = size; i > nIndex; i--)
  155. 		{
  156. 			this->data[i] = this->data[i - 1];
  157. 		}
  158.  
  159. 		this->data[nIndex] = value;
  160. 		this->size++;
  161. 	}
  162.  
  163. 	//删除元素数据
  164. 	void erase(int nIndex)
  165. 	{
  166. 		//判断索引序号
  167. 		if (nIndex < 0 || nIndex > size)
  168. 		{
  169. 			throw std::out_of_range("Invalid Index");
  170. 		}
  171.  
  172. 		//删除指定元素
  173. 		for (int i = nIndex; i < this->size -1; i++)
  174. 		{
  175. 			this->data[i] = this->data[i + 1];
  176. 		}
  177.  
  178. 		//修正数组个数
  179. 		//this->data[this->size - 1] = 0;
  180. 		this->size--;
  181. 	}
  182.  
  183. 	//查找指定元素
  184. 	int Find(const T& valud) const
  185. 	{
  186. 		for (size_t i = 0; i < this->size; i++)
  187. 		{
  188. 			if (this->data[i] == valud)
  189. 			{
  190. 				return i;
  191. 			}
  192. 		}
  193.  
  194. 		return -1;
  195. 	}
  196.  
  197. };
  198.  
  199.  
  200. int main()
  201. {
  202. 	//默认构造函数
  203. 	Vector<int> vec1;
  204.  
  205. 	//有参构造函数
  206. 	Vector<int> vec2(3, 0xCC);
  207. 	
  208. 	//拷贝构造函数
  209. 	Vector<int> vec3(vec2);
  210.  
  211. 	//移动构造函数
  212. 	Vector<int> vec4(std::move(vec3));
  213.  
  214. 	//列表构造函数
  215. 	Vector<int> vec5 = { 1,2,3,4,5 };
  216.  
  217. 	return 0;
  218. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/508015
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号