1. 连续存储【数组】

1.1 什么叫做数组

元素类型相同，大小相等（数组传参，只要传进去首地址和长度就行）

1.2 数组的优缺点：

1.2.1 优点：

  1. 存取速度快

    1.2.2 缺点：

  2. 事先必须知道数组的长度

  3. 插入删除元素很慢
  4. 空间通常是有限制的
  5. 需要大块连续的内存块
  6. 插入删除元素的效率很低

    1.3 数组的实现-不可自动增长版code

    ```c /*
    • @Descripttion: 线性数据结构-数组-不可自动增长版
    • @version: Beta-v1.0.0
    • @Author: jhong.tao
    • @Date: 2020-11-28 16:38:42 */

include // 包含了printf()

include // 包含了bool

include // 包含了malloc()

include // 包含了exit()

// 定义 struct Arr 结构体数据类型 struct Arr{ int * pBase; // 存储数组第一个元素的地址 int len; // 数组元素的长度 int cnt; // 当前数组有效元素的个数 // int increment // 自动增长因子 allocate() };

void init_arr(struct Arr pArr, int lenght); // 初始化 bool append_arr(struct Arr pArr, int val); // 末尾追加数据 bool insert_arr(struct Arr pArr, int pos, int val); // 插入数据,在pos位置插入一个数据，pos计数从1开始 bool delete_arr(struct Arr pArr, int pos, int pVal); // 删除数据,pos从1开始 int get(); // 获取下标值 bool is_enpty(struct Arr pArr); // 判空 bool is_full(struct Arr pArr); // 判满 void sort_arr(struct Arr pArr); // 排序 void show_arr(struct Arr pArr); // 打印 void inversion_arr(struct Arr pArr); // 倒置

int main(void){ struct Arr arr; int val;

  1. init_arr(&arr, 3);
  2. append_arr(&arr,2);
  3. append_arr(&arr,1);
  4. insert_arr(&arr,3,5);
  6. //delete_arr(&arr, 3, &val);
  7. inversion_arr(&arr);
  8. sort_arr(&arr);
  10. show_arr(&arr);   
  11. // printf("%d",val);
  12. return 0;

}

/**

  • @name: sort_arr(struct Arr * pArr)
  • @brief: 直接插入排序
  • @param {struct Arr * pArr:结构体数组地址}
  • @return {无返回值} / void sort_arr(struct Arr pArr){ if(pArr->cnt <2 ||is_enpty(pArr)) // 单个元素或空不用排序
    1.  return;
    else{
    1.   int temp,j;    // temp哨兵和j前面拍好序的编辑
    2.  for (int i = 1; i < pArr->cnt; i++){    //后面乱序部分
    3.      temp = pArr->pBase[i];      // 取一个后面乱序的数与前面已经拍好序的比较
    4.      for(j = i-1;j>=0;j--){ 
    5.          if(temp>=pArr->pBase[j])    // 如果后面取出来的数比前面最大的都大则位置不变
    6.              break;
    7.          else{       
    8.              pArr->pBase[j+1]=pArr->pBase[j];    // 移位操作
    9.          }
    10.      }
    11.      pArr->pBase[j+1] = temp;        // 插入合适的位置
    12.  }
    }

}

/**

  • @name: inversion_arr(struct Arr * pArr)
  • @brief: 将数组元素反向
  • @param {struct Arr * pArr:结构体数组地址}
  • @return {无返回值} / void inversion_arr(struct Arr pArr){ int temp; for(int i = pArr->cnt-1;i>=pArr->cnt/2;i—){
    1.  temp = pArr->pBase[i];
    2.  pArr->pBase[i] = pArr->pBase[pArr->cnt-i-1];
    3.  pArr->pBase[pArr->cnt-i-1] = temp;
    } return; }

/**

  • @name: init_arr(struct Arr * pArr, int lenght)
  • @brief: 初始化结构体数组
  • @param {struct Arr * pArr:结构体数组地址}
  • @param {int lenght:数组初试长度}
  • @return {没有返回值} / void init_arr(struct Arr pArr, int lenght){ pArr->pBase = (int)malloc(sizeof(int)lenght); //pArr指针变量所指向的arr结构体变量中的pBase成员 if(NULL == pArr->pBase){
    1.  printf("动态内存分配失败");
    2.  exit(-1);       // 终止整个程序
    }else{
    1.  pArr->len = lenght;
    2.  pArr->cnt = 0;
    } return; }

/**

  • @name: is_enpty(struct Arr * pArr)
  • @brief: 判断结构体数组是否为空
  • @param {struct Arr * pArr:结构体数组地址}
  • @return {bool类型，数组为空返回true} / bool is_enpty(struct Arr pArr){ if(pArr->cnt == 0)
    1.  return true;
    else
    1.  return false;
    }

/**

  • @name: show_arr(struct Arr * pArr)
  • @brief: 打印结构体数组
  • @param {struct Arr * pArr:结构体数组地址}
  • @return {无返回值，直接打印数组元素} / void show_arr(struct Arr pArr){ if(is_enpty(pArr)){
    1.  printf("数组为空\n");
    }else{
    1.  for(int i=0; i<pArr->cnt;i++)
    2.      printf("%d  ",pArr->pBase[i]);
    3.  printf("\n");
    } }

/**

  • @name: is_full(struct Arr * pArr)
  • @brief: 判断数组元素是否满
  • @param {struct Arr * pArr:结构体数组地址}
  • @return {bool类型，true:表示数组已满} / bool is_full(struct Arr pArr){ if(pArr->cnt == pArr->len)
    1.  return true;
    else
    1.  return false;
    }

/**

  • @name: append_arr(struct Arr * pArr, int val)
  • @brief: 向数组末尾追加一个元素
  • @param {struct Arr * pArr:结构体数组地址}
  • @param {int val:需要追加的元素}
  • @return {bool类型值，判断数据追加是否成功} / bool append_arr(struct Arr pArr, int val){ if(is_full(pArr)){
    1.  printf("数组已满,追加数据失败\n");
    2.  return false;
    }else{// 不满追加数据
    1.  pArr->pBase[pArr->cnt] = val;
    2.  pArr->cnt++;
    3.  return true;
    } }

/**

  • @name: insert_arr(struct Arr * pArr, int pos, int val)
  • @brief: 在数组的第pos个位置上插入一个元素
  • @param {struct Arr * pArr：结构体数组变量}
  • @param {int pos：在数组中需要插入数据的位置，pos从1开始，数组元组下标从0开始}
  • @param {int val：被插入的数}
  • @return {bool类型值，判断插入成功与否} / bool insert_arr(struct Arr pArr, int pos, int val){ int i; if(is_full(pArr) ||(pos<1 || pos>pArr->len)){
    1.  printf("越界异常，插入数据失败\n");
    2.  return false;
    }else{ 
    1.  if(pos>pArr->cnt){      // pos位置落在数组真实元素个数之后，直接追加
    2.      append_arr(pArr,val);
    3.      return true;
    4.  }else{                  // pos位置落在数组真实元素之间
    5.      for(i=pArr->cnt;i>=pos;i--){    // 移位操作
    6.          pArr->pBase[i] = pArr->pBase[i-1];
    7.      }
    8.      pArr->pBase[i] = val;   // 插入pos位置元素val
    9.      pArr->cnt++;            // 数组长度加一
    10.      return true;
    11.  }
    }

}

/**

  • @name: delete_arr(struct Arr pArr, int pos, int pVal)
  • @brief: 删除数组中pos位置的元素
  • @param {struct Arr * pArr：结构体数组的地址}
  • @param {int pos：被删除元素在数组中的位置，pos计数从1开始，数组元素计数从0开始}
  • @param {int * pVal：返回被删除的数}
  • @return {bool 类型值，表示删除成功与否} / bool delete_arr(struct Arr pArr, int pos, int * pVal){ if(is_enpty(pArr) || (pos<1 || pos>pArr->len)){
    1.  printf("数组为空或越界异常,删除失败\n");
    2.  return false;
    }else{
    1.  if(pos >= pArr->cnt){   // 如果pos大于数组中实际元素的个数，小于数组长度，则删除最后一个元素
    2.      *pVal = pArr->pBase[pArr->cnt-1];       // 返回被删除的数
    3.      pArr->cnt--;    // 数组元素减一
    4.      return true;
    5.  }else{                  // pos落在数组实际元素中间
    6.      *pVal = pArr->pBase[pos-1];     // 返回被删除的数
    7.      for(int i = pos-1; i<pArr->cnt-1; i++){     // 移位操作
    8.          pArr->pBase[i] = pArr->pBase[i+1];
    9.      }
    10.      pArr->cnt--;    // 数组元素减一
    11.      return true;
    12.  }
    } return false; }
  1. <a name="PVetJ"></a>
  2. ## 1.4 数组的实现-可自动增长版code
  3. ```c
  4. /*
  5.  * @Descripttion: 线性数据结构-数组-可自动增长版
  6.  * @version: Beta-v1.0.0
  7.  * @Author: jhong.tao
  8.  * @Date: 2020-11-28 16:38:42
  9.  */
  11. # include <stdio.h>     // 包含了printf()
  12. # include <stdbool.h>   // 包含了bool
  13. # include <malloc.h>    // 包含了malloc()
  14. # include <stdlib.h>    // 包含了exit()
  16. /**
  17.  * @name: struct Arr
  18.  * @brief: 定义 struct Arr 结构体数据类型
  19.  * @param {int * pBase:数组第一个元素的地址}
  20.  * @param {int len:数组的长度，从一开始计数，数组下标从0开始}
  21.  * @param {int cnt:数组中实际元素的个数，从1开始计数，数组下标从0开始}
  22.  * @param {int increment:数组长度不够时，自动增长因子}
  23.  */
  24. struct Arr{
  25.     int * pBase;    // 存储数组第一个元素的地址
  26.     int len;        // 数组元素的长度
  27.     int cnt;        // 当前数组有效元素的个数
  28.     int increment;  // 自动增长因子 realloc() 
  29. };
  31. void init_arr(struct Arr * pArr, int lenght);        // 初始化
  32. bool append_arr(struct Arr * pArr, int val);      // 末尾追加数据
  33. bool insert_arr(struct Arr * pArr, int pos, int val);      // 插入数据,在pos位置插入一个数据，pos计数从1开始
  34. bool delete_arr(struct Arr * pArr, int pos, int * pVal);         // 删除数据,pos从1开始
  35. int get();              // 获取下标值
  36. bool is_enpty(struct Arr * pArr);        // 判空
  37. bool is_full(struct Arr * pArr);         // 判满
  38. void sort_arr(struct Arr * pArr);        // 排序
  39. void show_arr(struct Arr * pArr);        // 打印
  40. void inversion_arr(struct Arr * pArr);   // 倒置
  43. int main(void){
  44.     struct Arr arr;
  45.     int val;
  47.     init_arr(&arr, 2);
  48.     append_arr(&arr,2);
  49.     append_arr(&arr,1);
  50.     insert_arr(&arr,1,5);
  52.     //delete_arr(&arr, 3, &val);
  53.     inversion_arr(&arr);
  54.     sort_arr(&arr);
  56.     show_arr(&arr);   
  57.     // printf("%d",val);
  58.     return 0;
  59. }
  62. /**
  63.  * @name: sort_arr(struct Arr * pArr)
  64.  * @brief: 直接插入排序
  65.  * @param {struct Arr * pArr:结构体数组地址}
  66.  * @return {无返回值}
  67.  */
  68. void sort_arr(struct Arr * pArr){
  69.     if(pArr->cnt <2 ||is_enpty(pArr))   // 单个元素或空不用排序
  70.         return;
  71.     else{
  72.          int temp,j;    // temp哨兵和j前面拍好序的编辑
  73.         for (int i = 1; i < pArr->cnt; i++){    //后面乱序部分
  74.             temp = pArr->pBase[i];      // 取一个后面乱序的数与前面已经拍好序的比较
  75.             for(j = i-1;j>=0;j--){ 
  76.                 if(temp>=pArr->pBase[j])    // 如果后面取出来的数比前面最大的都大则位置不变
  77.                     break;
  78.                 else{       
  79.                     pArr->pBase[j+1]=pArr->pBase[j];    // 移位操作
  80.                 }
  81.             }
  82.             pArr->pBase[j+1] = temp;        // 插入合适的位置
  83.         }
  84.     }   
  85. }
  87. /**
  88.  * @name: inversion_arr(struct Arr * pArr)
  89.  * @brief: 将数组元素反向
  90.  * @param {struct Arr * pArr:结构体数组地址}
  91.  * @return {无返回值}
  92.  */
  93. void inversion_arr(struct Arr * pArr){
  94.     int temp;
  95.     for(int i = pArr->cnt-1;i>=pArr->cnt/2;i--){
  96.         temp = pArr->pBase[i];
  97.         pArr->pBase[i] = pArr->pBase[pArr->cnt-i-1];
  98.         pArr->pBase[pArr->cnt-i-1] = temp;
  99.     }
  100.     return;
  101. }
  103. /**
  104.  * @name: init_arr(struct Arr * pArr, int lenght)
  105.  * @brief: 初始化结构体数组
  106.  * @param {struct Arr * pArr:结构体数组地址}
  107.  * @param {int lenght:数组初试长度}
  108.  * @return {没有返回值}
  109.  */
  110. void init_arr(struct Arr * pArr, int lenght){
  111.     pArr->pBase = (int*)malloc(sizeof(int)*lenght);     //pArr指针变量所指向的arr结构体变量中的pBase成员
  112.     if(NULL == pArr->pBase){
  113.         printf("动态内存分配失败");
  114.         exit(-1);       // 终止整个程序
  115.     }else{
  116.         pArr->len = lenght;
  117.         pArr->cnt = 0;
  118.         pArr->increment = lenght;
  119.     }
  120.     return;
  121. } 
  123. /**
  124.  * @name: is_enpty(struct Arr * pArr)
  125.  * @brief: 判断结构体数组是否为空
  126.  * @param {struct Arr * pArr:结构体数组地址}
  127.  * @return {bool类型，数组为空返回true}
  128.  */
  129. bool is_enpty(struct Arr * pArr){
  130.     if(pArr->cnt == 0)
  131.         return true;
  132.     else
  133.         return false;
  134. }
  136. /**
  137.  * @name: show_arr(struct Arr * pArr)
  138.  * @brief: 打印结构体数组
  139.  * @param {struct Arr * pArr:结构体数组地址}
  140.  * @return {无返回值，直接打印数组元素}
  141.  */
  142. void show_arr(struct Arr * pArr){
  143.     if(is_enpty(pArr)){
  144.         printf("数组为空\n");
  145.     }else{
  146.         for(int i=0; i<pArr->cnt;i++)
  147.             printf("%d  ",pArr->pBase[i]);
  148.         printf("\n");
  149.     }
  150. }
  152. /**
  153.  * @name: is_full(struct Arr * pArr)
  154.  * @brief: 判断数组元素是否满
  155.  * @param {struct Arr * pArr:结构体数组地址}
  156.  * @return {bool类型，true:表示数组已满}
  157.  */
  158. bool is_full(struct Arr * pArr){
  159.     if(pArr->cnt == pArr->len)
  160.         return true;
  161.     else
  162.         return false;
  163. }
  165. /**
  166.  * @name: append_arr(struct Arr * pArr, int val)
  167.  * @brief: 向数组末尾追加一个元素，如果数组满了则自动增长长度
  168.  * @param {struct Arr * pArr:结构体数组地址}
  169.  * @param {int val:需要追加的元素}
  170.  * @return {bool类型值，判断数据追加是否成功}
  171.  */
  172. bool append_arr(struct Arr * pArr, int val){
  174.     if(is_full(pArr)){
  175.         // 数组满了则自动增加数组长度并追加数据
  176.         pArr->len = pArr->len+pArr->increment;
  177.         pArr->pBase = (int*)realloc(pArr->pBase,sizeof(int)*pArr->len);
  178.     }
  180.     // 不满追加数据
  181.     if(pArr->pBase == NULL){
  182.         printf("数组扩容失败，不能追加数据\n");
  183.         return false;
  184.     }else{
  185.         pArr->pBase[pArr->cnt] = val;
  186.         pArr->cnt++;
  187.         return true;
  188.     } 
  189. }  
  191. /**
  192.  * @name: insert_arr(struct Arr * pArr, int pos, int val)
  193.  * @brief: 在数组的第pos个位置上插入一个元素,pos计数从1开始，如果超过数组元素长度则添加在末尾
  194.  * @param {struct Arr * pArr：结构体数组变量}
  195.  * @param {int pos：在数组中需要插入数据的位置，pos从1开始，数组元组下标从0开始}
  196.  * @param {int val：被插入的数}
  197.  * @return {bool类型值，判断插入成功与否}
  198.  */
  199. bool insert_arr(struct Arr * pArr, int pos, int val){
  200.     int i;
  201.     if(is_full(pArr)){
  202.         // 数组满了则自动增加数组长度并追加数据
  203.         pArr->len = pArr->len+pArr->increment;
  204.         pArr->pBase = (int*)realloc(pArr->pBase,sizeof(int)*pArr->len);
  205.     }
  206.     if(pArr->pBase == NULL){
  207.         printf("数组扩容失败，插入数据失败\n");
  208.         return false;
  209.     }else{
  210.         if(pos<1){
  211.             printf("越界异常，插入数据失败\n");
  212.             return false;
  213.         }else{      
  214.             if(pos>pArr->cnt){      // pos位置落在数组真实元素个数之后，直接追加
  215.                 append_arr(pArr,val);
  216.                 return true;
  217.             }else{                  // pos位置落在数组真实元素之间
  218.                 for(i=pArr->cnt;i>=pos;i--){    // 移位操作
  219.                     pArr->pBase[i] = pArr->pBase[i-1];
  220.                 }
  221.                 pArr->pBase[i] = val;   // 插入pos位置元素val
  222.                 pArr->cnt++;            // 数组长度加一
  223.                 return true;
  224.             }
  225.         }
  226.     }        
  227. }
  230. /**
  231.  * @name: delete_arr(struct Arr * pArr, int pos, int * pVal)
  232.  * @brief: 删除数组中pos位置的元素
  233.  * @param {struct Arr * pArr：结构体数组的地址}
  234.  * @param {int pos：被删除元素在数组中的位置，pos计数从1开始，数组元素计数从0开始}
  235.  * @param {int * pVal：返回被删除的数}
  236.  * @return {bool 类型值，表示删除成功与否}
  237.  */
  238. bool delete_arr(struct Arr * pArr, int pos, int * pVal){
  239.     if(is_enpty(pArr) || (pos<1 || pos>pArr->len)){
  240.         printf("数组为空或越界异常,删除失败\n");
  241.         return false;
  242.     }else{
  243.         if(pos >= pArr->cnt){   // 如果pos大于数组中实际元素的个数，小于数组长度，则删除最后一个元素
  244.             *pVal = pArr->pBase[pArr->cnt-1];       // 返回被删除的数
  245.             pArr->cnt--;    // 数组元素减一
  246.             return true;
  247.         }else{                  // pos落在数组实际元素中间
  248.             *pVal = pArr->pBase[pos-1];     // 返回被删除的数
  249.             for(int i = pos-1; i<pArr->cnt-1; i++){     // 移位操作
  250.                 pArr->pBase[i] = pArr->pBase[i+1];
  251.             }
  252.             pArr->cnt--;    // 数组元素减一
  253.             return true;
  254.         }
  255.     }
  256.     return false;
  257. }