数据结构基础（1）--数组C语言实现--动态内存分配

时间：2021-12-16 17:25:22

基本思想：数组是最常用的数据结构，在内存中连续存储，可以静态初始化（int a[2]={1,2}），可以动态初始化 malloc（）。

难点就是数组在删除或者插入元素的时候，要移动元素的坐标不好确定。规律：

1.如果要在数组中第pos个位置插入一个元素（应该从后面开始移动）

for( i=cnu;i>=pos;i--)

pBase[i]=pBase[i-1];

2.删除数组第pos位置的元素

for(i=pos+1;i<=cnu;i--)

pBase[i-2]=pBase[i-1];

使用malloc动态分配内存并将返回值赋给整形指针

int *pBase=(int *)malloc(sizeof(int)*len);//分配4*len字节长度的内存

这是pBase可以指向数组中的第一个元素，可以作为数组变量名称使用。

数组的优缺点：

优点：

存取速度快 o(1) 可以直接根据下标找到内存位置

缺点：

事先必须知道数组的长度

插入删除元素很慢

空间通常是有限制的

需要大块连续的内存块

插入删除元素的效率很低

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<stdbool.h>
  4. struct Arr{
  5. int len;//数组能存取的最大元素个数
  6. int cnu;//数组中当前元素个数
  7. int * pBase;//存储指向数组的指针
  8. };
  9. /**
  10. *初始化数组
  11. */
  12. void init_array(struct Arr * pArray,int len){
  13. pArray->pBase=(int *)malloc(sizeof(int)*len);//分配4*len字节长度的内存
  14. if(NULL== pArray->pBase)//判断内存是否分配失败
  15. {
  16. printf("动态分配内存失败\n");
  17. // exit(-1);
  18. }else{
  19. pArray->len=len;
  20. pArray->cnu=0;
  21. }
  22. return ;
  23. }
  24. /**
  25. *判断数组是否为空，传地址省内存4字节，传结构体变量需要进行拷贝，12字节
  26. */
  27. bool isempty(struct Arr * pArray){
  28. if(0==pArray->cnu)
  29. {
  30. return true;
  31. }else{
  32. return false;
  33. }
  34. }
  35. /**
  36. **判断数组是否满了
  37. */
  38. bool isfull(struct Arr * pArray)
  39. {
  40. if(pArray->len==pArray->cnu)
  41. {
  42. return true;
  43. }else {
  44. return false;
  45. }
  46. }
  47. /**
  48. *显示数组内容
  49. */
  50. void show_array(struct Arr * pArray){
  51. if(isempty(pArray))
  52. printf("数组为空！\n");
  53. else{
  54. int i;
  55. for( i=0; i<pArray->cnu;i++)
  56. {
  57. printf("%d \n",pArray->pBase[i]);
  58. }
  59. printf("------------------------------------\n");
  60. }
  61. }
  62. /**
  63. **向数组追加元素
  64. */
  65. bool append(struct Arr * pArray,int val){
  66. if(isfull(pArray))
  67. {
  68. printf("数组已经满了！\n");
  69. return false;
  70. }else{
  71. pArray->pBase[pArray->cnu]=val;
  72. pArray->cnu++;
  73. }
  74. }
  75. /**
  76. **向数组中插入元素,pos为数组中第几个位置，pos=3就是向a[2]插入元素
  77. */
  78. bool insert(struct Arr * pArray,int pos,int val)
  79. {
  80. if(pos<1||pos>pArray->len+1)//插入的位置不能小于1，同时不能比最后一个元素大二
  81. {
  82. printf("插入的位置输入的不合法\n");
  83. return false;
  84. }
  85. if(isfull(pArray))
  86. {
  87. printf("数组已经满了,插入失败！\n");
  88. return false;
  89. }
  90. int i;
  91. //循环将pos位置开始的数组后移
  92. for(i=pArray->cnu;i>=pos;i--)
  93. //移动范围是从第pos个到底cnu个
  94. {
  95. pArray->pBase[i]=pArray->pBase[i-1];
  96. /**
  97. 若以i表示要移动元素的位置，从一开始的。右边都是i-1,若左移，左边是i-2,右移，左边是i
  98. */
  99. }
  100. pArray->pBase[pos-1]=val;
  101. pArray->cnu++;
  102. pArray->len++;
  103. return true;
  104. }
  105. /**
  106. **删除数组中的第pos个元素，同时返回删除的元素的值
  107. */
  108. bool delete(struct Arr * pArray,int pos,int * val)
  109. {
  110. if(pos<1||pos>pArray->cnu)
  111. {
  112. printf("删除失败，位置不合法\n");
  113. return false;
  114. }
  115. int i;
  116. *val=pArray->pBase[pos-1];
  117. for(i=pos+1;i<=pArray->cnu;i++)
  118. {
  119. //移动单位是从第pos+1个到cnu
  120. pArray->pBase[i-2]=pArray->pBase[i-1];
  121. }
  122. pArray->cnu--;
  123. return true;
  124. }
  125. /**
  126. **数组倒置
  127. */
  128. bool inverse(struct Arr * pArray)
  129. {
  130. if(isempty(pArray))
  131. {
  132. printf("倒置失败，因数组为空");
  133. return false;
  134. }
  135. int i=0;
  136. int j=pArray->cnu-1;
  137. int temp;
  138. while(i<j)
  139. {
  140. temp=pArray->pBase[i];
  141. pArray->pBase[i]= pArray->pBase[j];
  142. pArray->pBase[j]=temp;
  143. i++;
  144. j--;
  145. }
  146. return true;
  147. }
  148. int main()
  149. {
  150. struct Arr arr;
  151. init_array(&arr,6);//将结构体的地址作为实参，这样才能修改结构体中的值，如果传的是结构体变量，那么将进行拷贝，不会改变值
  152. append(&arr,1);
  153. append(&arr,2);
  154. append(&arr,3);
  155. append(&arr,4);
  156. show_array(&arr);
  157. insert(&arr,2,88);
  158. show_array(&arr);
  159. int val;
  160. delete(&arr,1,&val);
  161. show_array(&arr);
  162. printf("删除了 %d\n",val);
  163. inverse(&arr);
  164. show_array(&arr);
  165. return 0;
  166. }

相关文章