C语言动态数组分配算法演示

C动态数组算法演示

摘要:数据结构和算法对于编程的意义不言而喻,具有指导意义的。无论从事算法优化方向研究,还是大数据处理,亦或者网站开发APP开发云云。在求职过程中数据结构必然也是笔试的重点,面试的常客。基于此,系统梳理复习下数据结构和算法相关知识,其实核心为链表操作,串的匹配,树的先序、中序、后序。排序的相关操作,查找相关操作,深度优先遍历、广度优先遍历、哈弗曼树、动态规划等。本节为开胃菜,数组的相关操作

1 数组动态分配思想

数组是最常用的数据结构,在内存中连续存储,可以静态初始化(int a[2]={1,2}),可以动态初始化 malloc()。难点就是数组在删除或者插入元素的时候,要移动元素的坐标不好确定。

规律:

1.如果要在数组中第pos个位置插入一个元素(应该从后面开始移动),此处的pos为第几位,说明pBase[0]为第一位,pos=1;

for( i=cnu;i>=pos;i--) //cnu表示当前数组的有效个数 pos表示要插入的位置
pBase[i]=pBase[i-1]; //存储指向数组的指针(结构体中的指针成员)(见下文完整程序声明)

2.删除数组第pos位置的元素,从pos位依次往后移动一位

for(i=pos+1;i<=cnu;i--) //同上
pBase[i-2]=pBase[i-1];

3.使用malloc动态分配内存并将返回值赋给整型指针

int pBase=(int *)malloc(sizeof(int)len);//分配4*len字节长度的内存,并且以int类型的字节为一组进行划分(int *)为地址强制类型转换

此时pBase若指向数组中的第一个元素,可以作为数组变量名称使用。

2 数组的优缺点

优点:

存取速度快 o(1) 可以直接根据下标找到内存位置

缺点:

  1. 事先必须知道数组的长度
  2. 插入删除元素很慢
  3. 空间通常是有限制的
  4. 需要大块连续的内存块
  5. 插入删除元素的效率很低

3 完整案例

#include<stdio.h> 
#include<malloc.h> // 包含malloc
#include<stdbool.h> //可以使用bool和true、false输出是1或者0

/* 定义结构体 */
struct Arr{
    int len;//数组能存取的最大元素个数
    int cnu;//数组中当前元素个数
    int *pBase;//存储指向数组的指针
};

/*初始化数组*/
void init_Arr(struct Arr *pArray,int len){
    pArray->pBase=(int*)malloc(sizeof(int)*len);//分配4*len字节长度的内存
    if(NULL== pArray->pBase){
        printf("动态分配内存失败\n");
    }else{
        pArray->len=len;
        pArray->cnu=0;
        printf("动态分配内存成功 %d \n",pArray->len);
    }
}


/*判断数组是否为空,传地址省内存4字节,传结构体变量需要进行拷贝,12字节*/
bool isempty(struct Arr *pArray){
    if(0==pArray->cnu) return true;
    else return false;
}

/*判断数组是否满了*/
bool isfull(struct Arr *pArray){
  if(pArray->len==pArray->cnu)    return true;
  else return false;
}
/*显示数组内容*/
void show_Arr(struct Arr *pArray){
    if(isempty(pArray))    printf("数组为空!\n");
    else{
    for(int i=0; i<pArray->cnu;i++){
        printf("%d \t\t %d \t\t %d \n",pArray->pBase[i],pArray->cnu,pArray->len);
    }
    printf("------------------------------------\n");
    }
}

/*向数组追加元素*/
bool append(struct Arr *pArray,int val){
    if(isfull(pArray)){
        printf("数组已经满了!\n");
        return false;
    }else{
            pArray->pBase[pArray->cnu]=val;
            pArray->cnu++;
    }
}

/*向数组中插入元素,pos为数组中第几个位置,pos=3就是向a[2]插入元素*/
bool insert(struct Arr *pArray,int pos,int val){
    if(pos<1||pos>pArray->len+1){
        printf("插入的位置输入的不合法\n");
        return false;
    }
    if(isfull(pArray)){
        printf("数组已经满了,插入失败!\n");
        return false;
    }
    else{
        //printf("数组 %d \n",pArray->cnu);
        for(int i=pArray->cnu;i>=pos;i--){//循环将pos位置开始的数组后移
            pArray->pBase[i]=pArray->pBase[i-1];
        }
        pArray->pBase[pos-1]=val;
        pArray->cnu++;
        pArray->len++;
        return true;
    }
}

/*删除数组中的第pos个元素,同时返回删除的元素的值*/
bool delete(struct Arr *pArray,int pos,int *val){
    if(pos<1||pos>pArray->cnu){
        printf("删除失败,位置不合法\n");
        return false;
    }
    if(isempty(pArray)){
        printf("数组已经空,删除失败!\n");
        return false;
    }
    else{
        *val=pArray->pBase[pos-1];
        for(int i=pos+1;i<=pArray->cnu;i++){
            pArray->pBase[i-2]=pArray->pBase[i-1];
        }
        pArray->cnu--;
        return true;
    }
}
/*数组倒置*/
bool inverse(struct Arr *pArray){
    if(isempty(pArray)){
        printf("倒置失败,因数组为空");
        return false;
    }
    else{
        int i=0,j=pArray->cnu-1,temp;
        while(i<j){
            temp=pArray->pBase[i];
            pArray->pBase[i]=pArray->pBase[j];
            pArray->pBase[j]=temp;
            i++;
            j--;
        }
    }
    return true;
}

int main(){
    struct Arr arr;
    init_Arr(&arr,20);
    append(&arr,1);
    append(&arr,2);
    append(&arr,3);
    append(&arr,4);
    append(&arr,5);
    show_Arr(&arr);
    insert(&arr,2,88);
    show_Arr(&arr);
    int val;
    delete(&arr,1,&val);
    show_Arr(&arr);
    printf("删除了 %d\n",val);
    inverse(&arr);
    show_Arr(&arr);
    return 0;
}

4 运行结果

Success time: 0 memory: 2300 signal:0

动态分配内存成功 20 
1          5          20 
2          5          20 
3          5          20 
4          5          20 
5          5          20 
------------------------------------
1          6          21 
88          6          21 
2          6          21 
3          6          21 
4          6          21 
5          6          21 
------------------------------------
88          5          21 
2          5          21 
3          5          21 
4          5          21 
5          5          21 
------------------------------------
删除了 1
5          5          21 
4          5          21 
3          5          21 
2          5          21 
88          5          21 
------------------------------------

5 实例解析

5.1 结构体说明:

结构体(struct)指的是一种数据结构,是C语言中聚合数据类型的一类。 结构体可以被声明为变量指针数组等,用以实现较复杂的数据结构。结构体的定义如下所示:

struct tag { member-list } variable-list ;

struct为结构体关键字,tag为结构体的标志,member-list为结构体成员列表,其必须列出其所有成员;variable-list为此结构体声明的变量。

5.2 初始化数组:

思路:

  1. 创建初始化函数,给数组分配长度malloc(sizeof(int)*len
  2. 指针地址为空,分配内存失败
  3. 反之,数组长度为当前内存长度,数组当前位置为0

例如:

/*初始化数组*/
void init_Arr(struct Arr *pArray,int len){
    pArray->pBase=(int*)malloc(sizeof(int)*len);//分配4*len字节长度的内存
    if(NULL== pArray->pBase){
        printf("动态分配内存失败\n");
    }else{
        pArray->len=len;
        pArray->cnu=0;
        printf("动态分配内存成功 %d \n",pArray->len);
    }
}

5.3 判断数组是否为空:

  1. 创建判空函数,结构体参数数组
  2. 判断当前元素个数是否为空
/*判断数组是否为空,传地址省内存4字节,传结构体变量需要进行拷贝,12字节*/
bool isempty(struct Arr *pArray){
    if(0==pArray->cnu) return true;
    else return false;
}

5.4 判断数组是否为满:

  1. 创建判满函数,结构体参数数组
  2. 判断数组长度是否为当前元素长度

例如:

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

5.5 向数组追加元素:

  1. 创建追加函数,结构体数组参数,元素值
  2. 注意判满情况,反之循环输入
  3. 数组当前指针地址赋值
  4. 数组指向下一个位置,自加

例如:

/*向数组追加元素*/
bool append(struct Arr *pArray,int val){
    if(isfull(pArray)){
        printf("数组已经满了!\n");
        return false;
    }else{
        pArray->pBase[pArray->cnu]=val;
        pArray->cnu++;
    }
}

5.5 显示数组内容

  1. 创建显示函数,结构体数组参数
  2. 注意判空情况,反之循环输入
  3. 遍历数组输出

例如:

/*显示数组内容*/
void show_Arr(struct Arr *pArray){
    if(isempty(pArray))    printf("数组为空!\n");
    else{
    for(int i=0; i<pArray->cnu;i++){
        printf("%d \t\t %d \t\t %d \n",pArray->pBase[i],pArray->cnu,pArray->len);
    }
    printf("------------------------------------\n");
    }
}

5.6 向数组中插入元素

pos为数组中第几个位置,pos=3就是向a[2]插入元素

  1. 创建插入函数,结构体数组参数,位置参数,插入值参数
  2. 判断插入位置是否越界,判断数组是否满
  3. 循环将pos位置开始的数组后移,移动范围是从第pos个到第cnu个
  4. 循环将pos位置开始的数组后移,将值插入pos处
  5. 指向下一位且长度加1

例如:

/*向数组中插入元素,pos为数组中第几个位置,pos=3就是向a[2]插入元素*/
bool insert(struct Arr *pArray,int pos,int val){
    if(pos<1||pos>pArray->len+1){
        printf("插入的位置输入的不合法\n");
        return false;
    }
    if(isfull(pArray)){
        printf("数组已经满了,插入失败!\n");
        return false;
    }
    else{
        //printf("数组 %d \n",pArray->cnu);
        for(int i=pArray->cnu;i>=pos;i--){//循环将pos位置开始的数组后移
            pArray->pBase[i]=pArray->pBase[i-1];
        }
        pArray->pBase[pos-1]=val;
        pArray->cnu++;
        pArray->len++;
        return true;
    }
}

5.7 删除数组中的第pos个元素

同时返回删除的元素的值

  1. 创建插入函数,结构体数组参数,位置参数,插入值参数
  2. 判断插入位置是否越界合法
  3. 获取删除的元素值
  4. 移动单位是从第pos+1个到cnu
  5. 指针向前指向,自减

例如:

/*删除数组中的第pos个元素,同时返回删除的元素的值*/
bool delete(struct Arr *pArray,int pos,int *val){
    if(pos<1||pos>pArray->cnu){
        printf("删除失败,位置不合法\n");
        return false;
    }
    if(isempty(pArray)){
        printf("数组已经空,删除失败!\n");
        return false;
    }
    else{
        *val=pArray->pBase[pos-1];
        for(int i=pos+1;i<=pArray->cnu;i++){
            pArray->pBase[i-2]=pArray->pBase[i-1];
        }
        pArray->cnu--;
        return true;
    }
}

5.8 数组倒置

  1. 创建倒置函数,判断数组是否为空
  2. 三个变量进行交换,其中temp中间变量,ij分别指向数组首尾索引
  3. 循环数组,使前后索引交换位置
  4. 每一遍循环,ij索引分别前进一步,直到跳出循环,程序结束

例如:

/*数组倒置*/
bool inverse(struct Arr *pArray){
    if(isempty(pArray)){
        printf("倒置失败,因数组为空");
        return false;
    }
    else{
        int i=0,j=pArray->cnu-1,temp;
        while(i<j){
            temp=pArray->pBase[i];
            pArray->pBase[i]=pArray->pBase[j];
            pArray->pBase[j]=temp;
            i++;
            j--;
        }
    }
    return true;
}

上一篇
C语言链表算法演示 C语言链表算法演示
C语言链表算法演示 摘要: 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针)(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(
2018-11-03
下一篇
幸福的获得 幸福的获得
幸福的获得​ 一只兔子要比黄热病菌大得多,然而,一个拥有知识的人却会从与后者的搏斗中获得乐趣。就情感内容而言,那些受到高等教育的人所得到的快乐,与我的花匠所体验到的是完全相同的,教育所造成的差异仅在于产生这种快乐的活动形式不同而已。
2018-11-01