数据结构入门-线性结构

把所有的节点用一根直线串起来

连续存储[数组]

什么叫做数组：元素类型相同，大小相等

重点看代码吧，需要注意的都在注释里，多敲几遍，当然了，有些功能还没有实现，以后再实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定义了一个数据类型，这个数据类型的名字叫做struct Arr，有三个成员
struct Arr
{
    int * pBase;  // 存储的是数组第一个元素的地址
    int len;  // 数组所能容纳的最大元素的个数
    int cnt; // 当前元素有效元素的个数
};


void init_arr(struct Arr * pArr , int length);
bool append_arr(struct Arr * pArr  , int val); 
bool insert_arr(struct Arr * pArr , int pos , int val); //pos值从1开始
bool delete_arr(struct Arr * pArr , int pos , int *pval); // 这个指针用来接收删除的那个值
bool is_empty(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;

    // 这里要传入地址
    init_arr(&arr , 6);
    append_arr(&arr,2);
    append_arr(&arr,18);
    append_arr(&arr,55);
    append_arr(&arr,99);
    append_arr(&arr,6);
    inversion_arr(&arr);
    // insert_arr(&arr,1,100);
    // show_arr(&arr);
    // if(delete_arr(&arr, 6 , &val))
    //  printf("删除的元素为：%d\n", val);
    sort_arr(&arr);
    show_arr(&arr);


    

    return 0;
}

// 用于初始化,自己指定长度
void init_arr(struct Arr * pArr , int length)
{
    // 指针变量pArr指向结构体中的pBase成员
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    if (NULL == pArr->pBase)
    {
        printf("动态内存分配失败\n");
        exit(-1);  // 终止整个程序
    }
    else
    {
        pArr->len = length;
        pArr->cnt = 0;
        printf("初始化成功\n");
    }
    return;

}

// 输出数组
void show_arr(struct Arr * pArr )
{
    if (is_empty(pArr))
    {
        printf("数组为空！\n");
    }
    else
    {
        int i;
        printf("数组中的元素为：\n");
        for (i = 0; i < pArr->cnt; i++)
        {
            // 这里需要注意，输出的时候是这样，根据元素地址来
            printf("%d\n", pArr->pBase[i]);
        }
    }
}

// 判断数组是否为空
bool is_empty(struct Arr * pArr )
{
    if (pArr->cnt == 0)
        return true;
    else
        return false;
}


// 判断数组是否满了
bool is_full(struct Arr * pArr )
{
    if (pArr->cnt == pArr->len) 
        return true;
    else
        return false;
}


// 末尾添加元素
bool append_arr(struct Arr * pArr  , int val)
{

    if (is_full(pArr))
    {
        printf("数组已经满了\n");
        return false;
    }
    else
    {
        // 这里需要注意，把用户传入的值添加到当前对应的数组有效个数的后面，
        // 由于是数组，这里直接写cnt就可以了，完事之后有效个数加1
        pArr->pBase[pArr->cnt] = val;
        (pArr->cnt)++;
        printf("添加成功\n");
        return true;

    }
}



// 指定位置插入指定的元素
bool insert_arr(struct Arr * pArr , int pos , int val)
{

    int i;

    if (is_full(pArr))
        return false;
    if (pos < 1 || pos > pArr->cnt+1)
        return false;

    // 这里需要注意，画图很直接就出来了
    for (i = pArr->cnt - 1; i >= pos-1; i--)
    {
        // 把前面的值往后面移
        pArr->pBase[i+1] = pArr->pBase[i];
    }
    // 把指定元素插入到指定位置就可以了,然后个数加1
    pArr->pBase[pos-1] = val;
    pArr->cnt++;
    printf("插入成功\n");

    return true;
}


// 删除指定位置的值，并返回删除的值，用指针
bool delete_arr(struct Arr * pArr , int pos , int *pval)
{
    int i;

    if (is_empty(pArr))
    {
        return false;
    }
    if (pos < 1 || pos > pArr->cnt)
    {
        return false;
    }

    // 把要删除的那个值先赋值
    *pval = pArr->pBase[pos-1];

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

    pArr->cnt--;
    printf("删除成功\n");
    return true;

}


// 进行倒置
void inversion_arr(struct Arr * pArr)
{
    int i = 0;
    int j = pArr->cnt - 1;
    int t;
    while(i < j)
    {
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
        ++i;
        --j;
    }
    return;
}


// 排序
void sort_arr(struct Arr * pArr )
{
    int i , j , t;

    for (i = 0; i < pArr->cnt; ++i)
    {
        for (j = i+1; j < pArr->cnt; ++j)
        {
            if (pArr->pBase[i] > pArr->pBase[j])
            {
                t = pArr->pBase[i];
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = t;
            }
        }
    }
}