21ic电子技术开发论坛 › 单片机与嵌入式系统 › 嵌入式操作系统论坛 › 数据结构01：数组
返回列表 发新帖我要提问

[资料分享] 数据结构01：数组

[复制链接]
956|0
 楼主| seifguo 发表于 2016-3-20 22:32 | 显示全部楼层 |阅读模式
数据结构, se, TI, return, 函数
复制

  1. 


  2. 

  3.     /*
    

  4.      * 根据郝斌老师视频整理
    

  5.      * 编译环境：
    

  6.      * guo@linux:~$ gcc --version
    

  7.      * gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4
    

  8.      */
    

  9.     #include <stdio.h>
    

  10.     #include <malloc.h> /*malloc()*/
    

  11.     #include <stdlib.h> /*exit()*/
    


  12. 

  13.     #define FALSE 0
    

  14.     #define TRUE 1
    


  15. 

  16.     typedef struct Array
    

  17.     {
    

  18.         int *pBase;     /*存储数组第一个元素的地址*/
    

  19.         int len;         /*数组能容纳的有效元素的个数*/
    

  20.         int cnt;         /*当前数组有效元素的个数*/
    

  21.     // int increment; /*自动增长因子，需要allocate()函数*/
    

  22.     }ARRAY;
    


  23. 

  24.     /**************************声明*******************************/
    

  25.     /*初始化数组*/
    

  26.     void InitArray(ARRAY *, int );
    

  27.     /*数组追加元素*/
    

  28.     int AppendArray(ARRAY *, int );
    

  29.     /*数组插入元素*/
    

  30.     int InsertArray(ARRAY *, int , int );
    

  31.     /*数组删除元素*/
    

  32.     int DeleteArray(ARRAY *, int, int *);
    

  33.     /*获得元素*/
    

  34.     int get(ARRAY *,int , int *);
    

  35.     /*判断数组是否为空*/
    

  36.     int IsEmpty(ARRAY *);
    

  37.     /*判断数组是否已满*/
    

  38.     int IsFull(ARRAY *);
    

  39.     /*数组排序*/
    

  40.     void SortArray(ARRAY *);
    

  41.     /*显示数组*/
    

  42.     void ShowArray(ARRAY *);
    

  43.     /*倒置数组*/
    

  44.     void InversionArray(ARRAY *);
    


  45. 

  46.     /*
    

  47.      * 函数名称：InitArray。
    

  48.      * 函数说明：初始化数组，为数组分配内存，并确定长度。
    

  49.      * 输入参数：pArr数组首地址，length数组长度。
    

  50.      * 输出参数：无。
    

  51.      */
    

  52.     void InitArray(ARRAY *pArr, int length)
    

  53.     {
    

  54.         pArr->pBase = (int *)malloc(sizeof(int)*length);
    

  55.         if (NULL == pArr->pBase)
    

  56.         {
    

  57.             printf("动态分配内存失败！\n");
    

  58.             exit(-1);
    

  59.         }
    

  60.         else
    

  61.         {
    

  62.             pArr->len = length;
    

  63.             pArr->cnt = 0;
    

  64.         }
    


  65. 

  66.         return;
    

  67.     }
    


  68. 

  69.     /*
    

  70.      * 函数名称：IsEmpty。
    

  71.      * 函数说明：判断数组是否为空。
    

  72.      * 输入参数：pArr数组首地址。
    

  73.      * 输出参数：如果数组为空，返回TRUE；否则返回FALSE。
    

  74.      */
    

  75.     int IsEmpty(ARRAY *pArr)
    

  76.     {
    

  77.         if (0==pArr->cnt)
    

  78.             return TRUE;
    

  79.         else
    

  80.             return FALSE;
    

  81.     }
    


  82. 

  83.     /*
    

  84.      * 函数名称：IsFull。
    

  85.      * 函数说明：判断数组是否为满。
    

  86.      * 输入参数：pArr数组首地址。
    

  87.      * 输出参数：如果数组为满，返回TRUE；否则返回FALSE。
    

  88.      */
    

  89.     int IsFull(ARRAY *pArr)
    

  90.     {
    

  91.         if (pArr->len == pArr->cnt)
    

  92.             return TRUE;
    

  93.         else
    

  94.             return FALSE;
    

  95.     }
    


  96. 

  97.     /*
    

  98.      * 函数名称：AppendArray。
    

  99.      * 函数说明：数组追加元素。
    

  100.      * 输入参数：pArr数组首地址，val要追加的值。
    

  101.      * 输出参数：如果数组为满，返回FALSE；追加成功返回TRUE。
    

  102.      */
    

  103.     int AppendArray(ARRAY *pArr,int val)
    

  104.     {
    

  105.         if ( IsFull(pArr) )
    

  106.             return FALSE;
    


  107. 

  108.         pArr->pBase[pArr->cnt] = val;
    

  109.         pArr->cnt++;
    


  110. 

  111.         return TRUE;
    

  112.     }
    


  113. 

  114.     /*
    

  115.      * 函数名称：InsertArray。
    

  116.      * 函数说明：插入元素，如果数组只有3个元素，可以插入到第4个元素位置。
    

  117.      * 输入参数：pArr数组首地址；position要插入的位置，从1开始；val要插入的值。
    

  118.      * 输出参数：如果数组为满或下标越界或没有存储那么多元素，返回FALSE；插入成功返回TRUE。
    

  119.      */
    

  120.     int InsertArray(ARRAY *pArr, int position, int val)
    

  121.     {
    

  122.         int i;
    


  123. 

  124.         if ( IsFull(pArr) )
    

  125.             return FALSE;        /*数组已满*/
    

  126.         if (position<1 || position>pArr->len)
    

  127.             return FALSE;         /*下标越界*/
    

  128.         if (position>pArr->cnt+1)
    

  129.             return FALSE;         /*没存储那么多元素*/
    


  130. 

  131.         /*在位置position后的元素都向后移动一位*/
    

  132.         for (i=pArr->cnt;i>=position;--i)
    

  133.         {
    

  134.             pArr->pBase[i] = pArr->pBase[i-1];
    

  135.         }
    

  136.         
    

  137.         pArr->pBase[position-1] = val;
    

  138.         pArr->cnt++;
    


  139. 

  140.         return TRUE;
    

  141.     }
    


  142. 

  143.     /*
    

  144.      * 函数名称：DeleteArray。
    

  145.      * 函数说明：删除元素。
    

  146.      * 输入参数：pArr数组首地址；position要删除的位置；val存储要删除的值。
    

  147.      * 输出参数：如果数组为满或下标越界或没有存储那么多元素，返回FALSE；删除成功返回TRUE。
    

  148.      * 删除成功前，先存储要删除的元素。
    

  149.      */
    

  150.     int DeleteArray(ARRAY *pArr, int position, int *val)
    

  151.     {
    

  152.         int i;
    


  153. 

  154.         if ( IsEmpty(pArr) )
    

  155.             return FALSE;         /*数组为空*/
    

  156.         if (position<1 || position>pArr->len)
    

  157.             return FALSE;         /*下标越界*/
    

  158.         if (position > pArr->cnt)
    

  159.             return FALSE;         /*数组未存储那么多元素*/
    


  160. 

  161.         *val = pArr->pBase[position-1];
    

  162.         for (i=position-1;i<pArr->cnt;++i)
    

  163.         {
    

  164.             pArr->pBase[i] = pArr->pBase[i+1];
    

  165.         }
    

  166.         pArr->cnt--;
    


  167. 

  168.         return TRUE;
    

  169.     }
    


  170. 

  171.     /*
    

  172.      *
    

  173.      */
    

  174.     int get(ARRAY *pArr, int i, int *val)
    

  175.     {
    

  176.         if (i<1 || i>pArr->cnt)
    

  177.             return FALSE;
    

  178.         *val = pArr->pBase[i-1];
    

  179.         return TRUE;
    

  180.     }
    


  181. 

  182.     /*
    

  183.      * 函数名称：InversionArray。
    

  184.      * 函数说明：倒置数组。
    

  185.      * 输入参数：pArr数组首地址。
    

  186.      * 输出参数：无。
    

  187.      */
    

  188.     void InversionArray(ARRAY *pArr)
    

  189.     {
    

  190.         int i = 0;
    

  191.         int j = pArr->cnt - 1;
    

  192.         int temp;
    


  193. 

  194.         while (i<j)
    

  195.         {
    

  196.             temp = pArr->pBase[i];
    

  197.             pArr->pBase[i] = pArr->pBase[j];
    

  198.             pArr->pBase[j] = temp;
    

  199.             ++i;
    

  200.             --j;
    

  201.         }
    


  202. 

  203.         return;
    

  204.     }
    


  205. 

  206.     /*
    

  207.      * 函数名称：SortArray。
    

  208.      * 函数说明：选择排序
    

  209.      *              1. 先取数组第一个元素，跟其他所有元素比较，放最小值
    

  210.      *              2. 再取数组第二个元素，跟其他除了第一个元素外的所有元素比较，放最小值
    

  211.      *              3. 依次进行，直到比较完
    

  212.      * 输入参数：pArr数组首地址。
    

  213.      * 输出参数：无。
    

  214.      */
    

  215.     void SortArray(ARRAY *pArr)
    

  216.     {
    

  217.         int i, j, temp;
    

  218.         for (i=0;i<pArr->cnt-1;++i)
    

  219.         {
    

  220.             for (j=i+1;j<pArr->cnt;++j)
    

  221.             {
    

  222.                 if (pArr->pBase[i] > pArr->pBase[j])
    

  223.                 {
    

  224.                     temp = pArr->pBase[i];
    

  225.                     pArr->pBase[i] = pArr->pBase[j];
    

  226.                     pArr->pBase[j] = temp;
    

  227.                 }
    

  228.             }
    

  229.         }
    

  230.         return;
    

  231.     }
    


  232. 

  233.     /*
    

  234.      * 函数名称：ShowArray。
    

  235.      * 函数说明：显示数组元素。
    

  236.      * 输入参数：pArr数组首地址。
    

  237.      * 输出参数：无。
    

  238.      */
    

  239.     void ShowArray(ARRAY *pArr)
    

  240.     {
    

  241.         int i;
    


  242. 

  243.         if ( IsEmpty(pArr) )
    

  244.         {
    

  245.             printf("Array is empty!\n");
    

  246.         }
    

  247.         else
    

  248.         {
    

  249.             for (i=0;i<pArr->cnt;++i)
    

  250.             {
    

  251.                 printf("%d ",pArr->pBase[i]);
    

  252.             }
    

  253.             printf("\n");
    

  254.         }
    

  255.     }
    


  256. 


  257. 

  258.     int main(void)
    

  259.     {
    

  260.         int temp32;        
    

  261.         int val;         
    

  262.         ARRAY arr;
    


  263. 

  264.         InitArray(&arr, 6);
    

  265.         printf("新建数组：\n");
    

  266.         printf("len=%d cnt=%d\n", arr.len, arr.cnt);
    

  267.         ShowArray(&arr);
    

  268.         
    

  269.         printf("追加后，数组元素为:\n");
    

  270.         AppendArray(&arr,11);
    

  271.         AppendArray(&arr,22);
    

  272.         AppendArray(&arr,33);
    

  273.         AppendArray(&arr,44);
    

  274.     /*    AppendArray(&arr,55);
    

  275.         AppendArray(&arr,66);
    

  276.         AppendArray(&arr,77);
    

  277.         AppendArray(&arr,88); */
    

  278.         ShowArray(&arr);
    


  279. 

  280.         printf("插入后，数组元素为：\n");
    

  281.         temp32 = InsertArray(&arr,5,99);
    

  282.         if (TRUE == temp32)
    

  283.         {
    

  284.             ShowArray(&arr);
    

  285.         }
    

  286.         else
    

  287.         {
    

  288.             printf("插入错误！\n");
    

  289.         }
    


  290. 

  291.         printf("删除后，数组元素为：\n");
    

  292.         temp32 = DeleteArray(&arr, 3, &val);
    

  293.         if (TRUE == temp32)
    

  294.         {
    

  295.             ShowArray(&arr);
    

  296.             printf("删除的元素是%d\n", val);
    

  297.         }
    

  298.         else
    

  299.         {
    

  300.             printf("删除错误!\n");;
    

  301.         }
    


  302. 

  303.         temp32 = get(&arr, 5, &val);
    

  304.         if (temp32)
    

  305.         {
    

  306.             printf("第%d个元素是%d.\n", 5, val);
    

  307.         }
    

  308.         else
    

  309.         {
    

  310.             printf("获取元素错误！\n");
    

  311.         }
    


  312. 

  313.         printf("数组倒置后为：\n");
    

  314.         InversionArray(&arr);
    

  315.         ShowArray(&arr);
    

  316.         
    

  317.         printf("数组按升序排列后为：\n");
    

  318.         SortArray(&arr);
    

  319.         ShowArray(&arr);
    


  320. 

  321.         return 0;
    

  322.     }
    


  323.


回复

收藏1 举报

相关帖子
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

seifguo

6

主题

83

帖子

2

粉丝
快速回复 在线客服 返回列表 返回顶部