打印
[资料分享]

数据结构01:数组

[复制链接]
847|0
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
seifguo|  楼主 | 2016-3-20 22:32 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式


    /*
     * 根据郝斌老师视频整理
     * 编译环境:
     * guo@linux:~$ gcc --version
     * gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4
     */
    #include <stdio.h>
    #include <malloc.h> /*malloc()*/
    #include <stdlib.h> /*exit()*/

    #define FALSE 0
    #define TRUE 1

    typedef struct Array
    {
        int *pBase;     /*存储数组第一个元素的地址*/
        int len;         /*数组能容纳的有效元素的个数*/
        int cnt;         /*当前数组有效元素的个数*/
    // int increment; /*自动增长因子,需要allocate()函数*/
    }ARRAY;

    /**************************声明*******************************/
    /*初始化数组*/
    void InitArray(ARRAY *, int );
    /*数组追加元素*/
    int AppendArray(ARRAY *, int );
    /*数组插入元素*/
    int InsertArray(ARRAY *, int , int );
    /*数组删除元素*/
    int DeleteArray(ARRAY *, int, int *);
    /*获得元素*/
    int get(ARRAY *,int , int *);
    /*判断数组是否为空*/
    int IsEmpty(ARRAY *);
    /*判断数组是否已满*/
    int IsFull(ARRAY *);
    /*数组排序*/
    void SortArray(ARRAY *);
    /*显示数组*/
    void ShowArray(ARRAY *);
    /*倒置数组*/
    void InversionArray(ARRAY *);

    /*
     * 函数名称:InitArray。
     * 函数说明:初始化数组,为数组分配内存,并确定长度。
     * 输入参数:pArr数组首地址,length数组长度。
     * 输出参数:无。
     */
    void InitArray(ARRAY *pArr, int length)
    {
        pArr->pBase = (int *)malloc(sizeof(int)*length);
        if (NULL == pArr->pBase)
        {
            printf("动态分配内存失败!\n");
            exit(-1);
        }
        else
        {
            pArr->len = length;
            pArr->cnt = 0;
        }

        return;
    }

    /*
     * 函数名称:IsEmpty。
     * 函数说明:判断数组是否为空。
     * 输入参数:pArr数组首地址。
     * 输出参数:如果数组为空,返回TRUE;否则返回FALSE。
     */
    int IsEmpty(ARRAY *pArr)
    {
        if (0==pArr->cnt)
            return TRUE;
        else
            return FALSE;
    }

    /*
     * 函数名称:IsFull。
     * 函数说明:判断数组是否为满。
     * 输入参数:pArr数组首地址。
     * 输出参数:如果数组为满,返回TRUE;否则返回FALSE。
     */
    int IsFull(ARRAY *pArr)
    {
        if (pArr->len == pArr->cnt)
            return TRUE;
        else
            return FALSE;
    }

    /*
     * 函数名称:AppendArray。
     * 函数说明:数组追加元素。
     * 输入参数:pArr数组首地址,val要追加的值。
     * 输出参数:如果数组为满,返回FALSE;追加成功返回TRUE。
     */
    int AppendArray(ARRAY *pArr,int val)
    {
        if ( IsFull(pArr) )
            return FALSE;

        pArr->pBase[pArr->cnt] = val;
        pArr->cnt++;

        return TRUE;
    }

    /*
     * 函数名称:InsertArray。
     * 函数说明:插入元素,如果数组只有3个元素,可以插入到第4个元素位置。
     * 输入参数:pArr数组首地址;position要插入的位置,从1开始;val要插入的值。
     * 输出参数:如果数组为满或下标越界或没有存储那么多元素,返回FALSE;插入成功返回TRUE。
     */
    int InsertArray(ARRAY *pArr, int position, int val)
    {
        int i;

        if ( IsFull(pArr) )
            return FALSE;        /*数组已满*/
        if (position<1 || position>pArr->len)
            return FALSE;         /*下标越界*/
        if (position>pArr->cnt+1)
            return FALSE;         /*没存储那么多元素*/

        /*在位置position后的元素都向后移动一位*/
        for (i=pArr->cnt;i>=position;--i)
        {
            pArr->pBase[i] = pArr->pBase[i-1];
        }
        
        pArr->pBase[position-1] = val;
        pArr->cnt++;

        return TRUE;
    }

    /*
     * 函数名称:DeleteArray。
     * 函数说明:删除元素。
     * 输入参数:pArr数组首地址;position要删除的位置;val存储要删除的值。
     * 输出参数:如果数组为满或下标越界或没有存储那么多元素,返回FALSE;删除成功返回TRUE。
     * 删除成功前,先存储要删除的元素。
     */
    int DeleteArray(ARRAY *pArr, int position, int *val)
    {
        int i;

        if ( IsEmpty(pArr) )
            return FALSE;         /*数组为空*/
        if (position<1 || position>pArr->len)
            return FALSE;         /*下标越界*/
        if (position > pArr->cnt)
            return FALSE;         /*数组未存储那么多元素*/

        *val = pArr->pBase[position-1];
        for (i=position-1;i<pArr->cnt;++i)
        {
            pArr->pBase[i] = pArr->pBase[i+1];
        }
        pArr->cnt--;

        return TRUE;
    }

    /*
     *
     */
    int get(ARRAY *pArr, int i, int *val)
    {
        if (i<1 || i>pArr->cnt)
            return FALSE;
        *val = pArr->pBase[i-1];
        return TRUE;
    }

    /*
     * 函数名称:InversionArray。
     * 函数说明:倒置数组。
     * 输入参数:pArr数组首地址。
     * 输出参数:无。
     */
    void InversionArray(ARRAY *pArr)
    {
        int i = 0;
        int j = pArr->cnt - 1;
        int temp;

        while (i<j)
        {
            temp = pArr->pBase[i];
            pArr->pBase[i] = pArr->pBase[j];
            pArr->pBase[j] = temp;
            ++i;
            --j;
        }

        return;
    }

    /*
     * 函数名称:SortArray。
     * 函数说明:选择排序
     *              1. 先取数组第一个元素,跟其他所有元素比较,放最小值
     *              2. 再取数组第二个元素,跟其他除了第一个元素外的所有元素比较,放最小值
     *              3. 依次进行,直到比较完
     * 输入参数:pArr数组首地址。
     * 输出参数:无。
     */
    void SortArray(ARRAY *pArr)
    {
        int i, j, temp;
        for (i=0;i<pArr->cnt-1;++i)
        {
            for (j=i+1;j<pArr->cnt;++j)
            {
                if (pArr->pBase[i] > pArr->pBase[j])
                {
                    temp = pArr->pBase[i];
                    pArr->pBase[i] = pArr->pBase[j];
                    pArr->pBase[j] = temp;
                }
            }
        }
        return;
    }

    /*
     * 函数名称:ShowArray。
     * 函数说明:显示数组元素。
     * 输入参数:pArr数组首地址。
     * 输出参数:无。
     */
    void ShowArray(ARRAY *pArr)
    {
        int i;

        if ( IsEmpty(pArr) )
        {
            printf("Array is empty!\n");
        }
        else
        {
            for (i=0;i<pArr->cnt;++i)
            {
                printf("%d ",pArr->pBase[i]);
            }
            printf("\n");
        }
    }


    int main(void)
    {
        int temp32;        
        int val;         
        ARRAY arr;

        InitArray(&arr, 6);
        printf("新建数组:\n");
        printf("len=%d cnt=%d\n", arr.len, arr.cnt);
        ShowArray(&arr);
        
        printf("追加后,数组元素为:\n");
        AppendArray(&arr,11);
        AppendArray(&arr,22);
        AppendArray(&arr,33);
        AppendArray(&arr,44);
    /*    AppendArray(&arr,55);
        AppendArray(&arr,66);
        AppendArray(&arr,77);
        AppendArray(&arr,88); */
        ShowArray(&arr);

        printf("插入后,数组元素为:\n");
        temp32 = InsertArray(&arr,5,99);
        if (TRUE == temp32)
        {
            ShowArray(&arr);
        }
        else
        {
            printf("插入错误!\n");
        }

        printf("删除后,数组元素为:\n");
        temp32 = DeleteArray(&arr, 3, &val);
        if (TRUE == temp32)
        {
            ShowArray(&arr);
            printf("删除的元素是%d\n", val);
        }
        else
        {
            printf("删除错误!\n");;
        }

        temp32 = get(&arr, 5, &val);
        if (temp32)
        {
            printf("第%d个元素是%d.\n", 5, val);
        }
        else
        {
            printf("获取元素错误!\n");
        }

        printf("数组倒置后为:\n");
        InversionArray(&arr);
        ShowArray(&arr);
        
        printf("数组按升序排列后为:\n");
        SortArray(&arr);
        ShowArray(&arr);

        return 0;
    }



相关帖子

发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

6

主题

83

帖子

2

粉丝