数据结构——连续存储【数组】

1、什么叫做数组

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

2、数组的优缺点:

优点:

  • 存取速度快

缺点:

  • 事先必须知道数组的长度(最大长度)(之后无法更改)
  • 插入删除元素很慢,效率很低(后续所有元素均需移动)
  • 空间通常是有限制的
  • 需要大块连续的内存块

 

#include<iostream>
using namespace std;

//定义了一个数据类型,该数据类型的名字叫做struct Arr, 该数据类型含有三个成员,分别是pBase, len, cnt
struct Arr
{
    int len;//数组最大长度
    int cnt;//数组当前长度
    int* PBase;//数组首地址
};  

//数组初始化
void init_arr(struct Arr* pArr, int length);
//数组是否为空
bool is_full(struct Arr* pArr);
//数组是否满了
bool is_empty(struct Arr* pArr);
//打印指针所有元素
void show_arr(struct Arr* pArr);
//在数组末追加一个元素
void append_arr(struct Arr* pArr,int val);
//在数组某个位置插入一个元素
void insert_arr(struct Arr* pArr, int pos, int val);
//在数组某个位置删除一个元素 并输出被删除元素
void delete_arr(struct Arr* pArr, int pos, int* pval);
//冒泡排个序
void sort_arr(struct Arr* pArr);
//将数组每个元素打印输出
void show_arr(struct Arr* pArr);


int main()
{    
    struct Arr arr;//用数据类型 struct Arr 定义变量 arr
    int val;
    init_arr(&arr, 6);
    append_arr(&arr, 8);
    append_arr(&arr, 6);    
    append_arr(&arr, 1);    
    append_arr(&arr, 5);
    append_arr(&arr, 3);
    show_arr(&arr);
    insert_arr(&arr, 2, 100);
    show_arr(&arr);
    delete_arr(&arr, 3, &val);
    cout << val << endl;
    show_arr(&arr);
    sort_arr(&arr);
    show_arr(&arr);
    return 0;
}

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) // (*Parr).和Parr->用法一致
        return true;
    else
        return false;
}
void init_arr(struct Arr* pArr, int length)
{
    pArr->PBase = (int*)malloc(sizeof(int) * length);
    if (pArr->PBase == NULL)
    {    
        cout << "动态分配内存失败" <<endl;
        exit(-1);
    }
    else
    {
        pArr->len = length;
        pArr->cnt = 0;
    }
}
void append_arr(struct Arr* pArr, int val)
{
    if (is_full(pArr)) 
    {
        cout << "数组已满,追加失败" << endl;
    }
    else
    {
        pArr->PBase[pArr->cnt] = val;
        pArr->cnt++;
    }
}
void insert_arr(struct Arr* pArr, int pos, int val)
{
    if (is_full(pArr))
    {
        cout << "数组已满,插入失败" << endl;
    }
    if (pos<1 || pos>pArr->cnt + 1)
    {
        cout << "输入数据有误" << endl;
    }
    else
    {
        for (int i = pArr->cnt-1;i >= pos-1;i--)
        {
            pArr->PBase[i + 1] = pArr->PBase[i];
        }
    }
    pArr->PBase[pos-1] = val;
    pArr->cnt++;
}
void delete_arr(struct Arr* pArr, int pos, int *val)
{
    *val = pArr->PBase[pos - 1]; 
    for (int i = pos - 1;i <= pArr->cnt - 2;i++)
    {
        pArr->PBase[i] = pArr->PBase[i + 1];
    }
    pArr->cnt--;
}
void show_arr(struct Arr* pArr)
{
    for (int i = 0;i <= pArr->cnt - 1;i++)
    {
        cout << pArr->PBase[i] << ' ';
    }
    cout << endl;
}
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;
            }
        }
    }
}

话说这个代码怎么进行修改 我怎么粘贴出来就不能回到上一步了

不管了 先这样吧..

 

上一篇:动态构建一维数组


下一篇:2、指针和数组