线性结构 -- 连续存储(数组), 1个简单的c语言代码实现.

素颜马尾好姑娘i 2022-03-19 13:28 178阅读 0赞

数据结构大体成上可以分成两种:  
  
1. 线性结构.  
2. 非线性结构( 树,图)  
  
**1. 什么是线性结构**  
       大概上可以这样定义: 加入所有的节点可以用一条直线连接起来. 就是线性结构...  
  
  
**2. 线性机构也可以分成两种:**  
       **1) 连续存储 (数组)**  
             也就是指每1个节点在物理内存上是相连的.  
  
     **  2) 离散存储(链表)**  
              节点在物理内存上并不一定相连, 而是利用指针来关联.  
  
       这篇文章主要讲的第一种.  
  
  
**3. 什么是数组**  
      数组就是在内存里物理连续的一段元素的集合  
         注意: 数组里面的元素不一定是数. 可以是任何类型, 但是每个元素的类型和大小必须相等.  
  
**         而且这里的数组并不是指C语言里的数组类型, 而是数据结构的一种.  
         通常在c语言会利用结构(struct) 来实现  
  
  
  
4. 数组的一些关键属性.  
       ** 其实这些属性一般都可以在java / .net 等高级语言里的容器里见到.  
         c语言里常用的有以下几个  
          1. 当前数组的最大元素个数  
**         ** 2. 当前数组的元素个数  
          3. 数组第1个元素的地址  
          **4. 自动增长因子**

**5. 这个结构体是否被初始化, 也就是说该结构体里面的指针地址数组是否被分配内存**.  
  
           前面3个都很容易理解. 关键第4个... 其实也不是必要的.   
           我们定义1个动态的数组肯定会利用malloc函数来动态分配内存.  
  
           假如我们动态分配了1个长度为10的数组a\[10\], 而且10个元素都占用了  
  
            加入我们又要往里面加1个数组, 这样数组长度不够, 就用利用realloc函数动态扩充..  
            而在内存里扩充1个连续的空间其实比较耗费时间成本(万一后面连续的空间被占用, 就要另外找1块连续空间.把原空间数据拷到新连续空间)  
           所以要避免增加1个元素就扩充1个内存, 所以我们一般定义1个自动增长因子. 例如10, 也就是每次扩充内存时就扩充10个元素的长度, 那么下次增加元素就时就不用再执行扩充动作.  
  
           这种优点就避免大量扩充内存所占用的时间成本,  缺点就必须占用一定量的空间成本

**             关于第5点就十分重要了,  它用于判断该结构体是否被初始化, 因为定义1个结构体时, 结构体里面的成员都是垃圾数据, 如果忘了进行初始化而执行其他函数时, 很可能发生各种后果, 所以定义1个成员专门来判断是否被初始化**.

关于初始化下面会再详细解析一次.

**5. 数组在c语言里的简单实现 (只是int 整形的数组)  
         ** 下面我们会利用c语言来实现1个容器类型, 类似java 或 .net 的arraylist  
            其实很多.net 程序员对arraylist 肯定很熟悉,  实际上它的底层就是利用线性存储来实现的.  
             对应地. 另1种容器 linkedlist, 就是用链表来实现的啊.  
  
            **5.1 定义1个数组复合类型**  
**        ** 我们知道要在c语言里定义1个复合类型是通过结构体实现的.  
        代码如下:  
   
**arrlist.h**

![复制代码][copycode.gif]

1  struct Arrlist{
    2         int * paddr;
    3         int len;
    4         int cur_len;
    5         int increment;
    6         BOOL is_inited;
    7     };

![复制代码][copycode.gif]

**      **  
        见上面的代码, 顶定义了1个 叫Arrlist的结构类型. 里面5个成员上面都解析过啦.  
         注意这段代码只是定义了1个类型, 并没初始化1个变量, 系统是不会为这段代码分配内存的.  
     **    而且我们写这个容器, 肯定是为了给其他人其他文件用的,  所以要吧结构体定义放在头文件内. 别的文件只需要引用这个头文件引用这个头文件就可以使用这个头文件内定义的结构体和函数了.  
  
         当然, 我在标题讲过了, 我要实现的只是1个int类型的数组, 如果取消这个限制, 在上面加多1个成员, 就用来判断这个数组的类型.     以后的函数操作时先检测一下这个类型, 然后区分操作.  
  
      **   
**          5.2 声明一些数据操作函数.  
          ** 只有1个结构体远远不够, 就如java / .net 中的类 arraylist 那样, 还需要很多的操作函数,  例如1个最重要的初始化1个容器, 嗨哟为这个容器添加数据/ 删除数据等, 都需要一些函数来实现.  
  
           在面向对象语言中, 这些函数就是这个类的成员了,  而在c语言中, 我们会在头文件中声明这些函数, 注意是声明. 而不是定义, 函数定义还是要在同名的c 文件中,  这样其他文件引用头文件就能使用容器及其对应的一些函数了.  
  
            代码如下:

**arrlist.h**

![复制代码][copycode.gif]

1 #include "bool_me.h"
     2 #ifndef __ARRLIST_H_
     3 #define __ARRLIST_H_
     4 
     5     struct Arrlist{
     6         int * paddr;
     7         int len;
     8         int cur_len;
     9         int increment;
    10         BOOL is_inited;
    11     };
    12 
    13     void Arr_init(struct Arrlist * pArr, int length);  //inital an arraylist
    14     BOOL Arr_add(struct Arrlist * pArr, int val);   // add an element to the end of array
    15         BOOL Arr_insert(struct Arrlist * pArr, int position, int val); // insert an element to any place
    16     BOOL Arr_delete(struct Arrlist * pArr, int index); // delete an element
    17     int Arr_get(struct Arrlist * pArr, int index);  //get the index of an element by value
    18     BOOL Arr_set(struct Arrlist * pArr, int index, int val);  //set the value to specified element in the array 
    19     BOOL Arr_is_empty(struct Arrlist * pArr); 
    20     BOOL Arr_is_full(struct Arrlist * pArr); 
    21     void Arr_invert(struct Arrlist * pArr); //invert the array
    22     void Arr_sort(struct Arrlist * pArr);
    23     void Arr_show(struct Arrlist * pArr); 
    24             
    25 #endif

![复制代码][copycode.gif]

当然这段代码只是打算实现一些最基本的功能,  
             所以声明了几个最基本的函数,  当然上面说过了, 在头文件内只是声明. 下面就介绍这些函数如何具体定义了.

还有可见到我使用了BOOL 类型, 其实这只是1个宏, 宏代码如下, 如果要使用真正的bool类型, 可以引用 stdbool.h文件,  不过不是所有机器都有... 我所在公司的服务器solaris 10就么有, 就只好使用宏了.

**bool\_me.h**

![复制代码][copycode.gif]

1 #ifndef __BOOL_ME_H_
     2 #define __BOOL_ME_H_
     3 
     4         #ifndef BOOL
     5         #define BOOL char
     6         #endif
     7             
     8         #ifndef TRUE
     9         #define TRUE '1'
    10         #endif
    11             
    12         #ifndef FALSE
    13         #define FALSE '0'
    14         #endif
    15 
    16 #endif

![复制代码][copycode.gif]

**5.3 错误处理函数 Arr\_error(char \* pstr);**

虽然只是1个简单的代码实现, 但我也稍稍写的完善一点:

这个函数专门用来打印错误信息并退出程序的

**arrlist.c**   //注意以下函数的定义代码都是写在.c 文件了.

![复制代码][copycode.gif]

1 static Arr_error(char * pstr){
    2     while (*pstr != '\0'){
    3         printf("%c",*pstr);    
    4         pstr++;
    5     }
    6     
    7     printf("\n");    
    8     exit (-1)
    9 }

![复制代码][copycode.gif]

注意两点:

1.  参数是1个字符串的头部指针,  实际实参是"abcewew" 这种形式传递的.

2.  我不希望这个函数被其他文件直接调用, 所以用了static 前序.

**5.4****初始化函数 Arr\_int(struct Arrlist \* pArr, int length);  
    ** 首先说明一下为什么要有这个1个初始化函数.  
     当我们定义1个 struct Arrlist时  
      **struct Arrlist arr1;**  
      不就己经给变量arr1 分配1块内存了吗?  
        
       的确, 上面说的没错, 但是虽然给这个结构体分配了内存, 但是内存里它的4个成员因为没有赋值,所以里面的都是一些垃圾数据, 关键的是第1个成员addr 可能随机指向1个地址.  
  
        所以初始化时我们就要完成下面动作:  
         **1.设定结构体成员的初始值.(第1个成员地址除外)  
         2. 在内存里划分1份内存空间.  
         3. 让结构体的第1个地址成员指向这个内存空间的头部地址.**

**         4. 设置其他成员的值.  
  
        **  
代码如下:

![复制代码][copycode.gif]

1 void Arr_init(struct Arrlist * pArr, int length){
     2     pArr->paddr = (int *)malloc(sizeof(int) * length);
     3         
     4     if (NULL == pArr->paddr){
     5         Arr_error("fail to assign memory!!");
     6     }
     7 
     8     pArr->len = length;
     9     pArr->cur_len = 0;
    10     pArr->increment = 10;
    11 
    12     pArr->is_inited = TRUE;
    13 
    14     return;
    15 }

![复制代码][copycode.gif]

解析一下上面为什么要加1个NULL判断呢, 就是因为一块连续的内存有可能划分失败(没有足够大的连续内存空间), 万一失败, malloc 函数会返回1个空指针,  以后的操作都无意义了.       所以判断分配失败后直接 exit(-1) 退出整个程序.

**       **

5.5 判断数组是否为空(0个元素)  Arr_is_empty(struct Arrlist * pArr)

![复制代码][copycode.gif]

1 BOOL Arr_is_empty(struct Arrlist * pArr){
     2     if (TRUE != pArr->is_inited){
     3         Arr_error("Array is not inited yet!!");
     4     }
     5 
     6     if (0 == pArr->cur_len){
     7         return TRUE;
     8     }
     9     return FALSE;
    10 }

![复制代码][copycode.gif]

5.6 判断数组是否为满(len = cur_len)  Arr_is_full(struct Arrlist * pArr)
    这个函数跟上面那个基本写一样:

![复制代码][copycode.gif]

1 BOOL Arr_is_full(struct Arrlist * pArr){
     2     if (TRUE != pArr->is_inited){
     3         Arr_error("Array is not inited yet!!");
     4     }
     5 
     6     if (pArr->len == pArr->cur_len){
     7         return TRUE;
     8     }
     9     return FALSE;
    10 }

![复制代码][copycode.gif]

**5.7 打印元素函数**  Arr\_show(struct Arrlist \* pArr)

只所以把这个函数放在Arr_is_empty() 下是因为Arr_show开始最好判断一下元素个数, 如果是空函数就不要做任何动作了.
    代码如下:

![复制代码][copycode.gif]

1 void Arr_show(struct Arrlist * pArr){
     2     if (TRUE != pArr->is_inited){
     3         Arr_error("Array is not inited yet!!");
     4     }
     5 
     6     if (TRUE == Arr_is_empty(pArr)){
     7         printf("It's an empty Arrlist\n");
     8         return;
     9     }
    10     
    11     int i;
    12     for (i=0; i < (pArr->cur_len - 1); i++){
    13          printf("%d, ", pArr->paddr[i]);
    14     }        
    15 
    16     printf("%d\n", pArr->paddr[pArr->cur_len -1]);
    17     return;
    18 }

![复制代码][copycode.gif]

5.8 添加元素到数组尾部函数   Arr_add(struct Arrlist * pArr, int val) 好了, 这是一个相当重要的函数, 也是最常被执行的.
    我们写1这个函数时应该有1个思路, 就是执行这个函数时, 这个结构体内部到底需要做什么事情.
    
    1. 首先判断pArr 指向的数组是否满了(cur_len = len)
    2. 如果满了, 扩充(扩充个数取决于成员 increment, 同时len+=increment)
    3. 如果扩充失败, 则返回false 内存里面没有足够大的连续空间了
    4. 如果未满或扩充成功了, 则添加1个元素到pArr 指向的数组尾部
    5. cur_len+=1
    
    代码如下:

![复制代码][copycode.gif]

BOOL Arr_add(struct Arrlist * pArr, int val){
        if (TRUE != pArr->is_inited){
            Arr_error("Array is not inited yet!!");
        }
    
        if (TRUE == Arr_is_full(pArr)){
            if (FALSE == Arr_extend(pArr, pArr->increment)){ 
                return FALSE;
            }
        }
        
        pArr->paddr[pArr->cur_len] = val; // assign the value
        pArr->cur_len++;        
        return TRUE;
    }

![复制代码][copycode.gif]

其中第2段用到了判断是否是满的函数, 如果数组满了, 则执行扩充, 然后就添加元素到数组的尾部  扩充函数是Arr\_extend. 下面会讲到

**5.9 数组扩容函数** **  Arr\_extend(struct Arrlist \* pArr)**

一旦数组的元素占满了数组的长度, 如果再添加元素. 就有必要进行扩容了.

所谓扩容就是重新为数组分配1个更长的连续内存空间.

实现的函数就是realloc函数.

假如,之前数组初始化前利用malloc函数动态分配了40个字节的连续内存空间,  那么执行realloc函数时, 则会判断原来的空间的后面一块内存空间,是否被占用, 如果未被其他程序占用, 则把这块空间也划分给数组, 数组的头部地址不变.  如果被占用了, 则会在内存了另外找1个块更大的连续内存空间. 并把原来内存里的数据Copy过去, 但是数组的地址就变化了(这时要把原来的空间释放)

这个函数要做的事情.

1.为pArr->paddr 分配1个更长的连续内存空间.

2.  如果pArr->paddr 当前地址后面的内存没有被占用, 这样的话pArr->paddr地址不会变.

3.  如果当前地址后面的内存已经被占用, 就只能到内存的另1个地方找1个更大的连续内存空间,  这样地址就变了, 但是无需手动释放旧的内存, realloc会自动释放!

4. 如果内存实在没有足够大的连续空间,  realloc函数会返回1个空指针,  我们要把pArr->paddr 返回原来的地址,  就认为扩容失败

5. pArr->len 长度增加.

代码:

static BOOL Arr_extend(ARRINT * pArr, int increment){
       int * pold = pArr->paddr;
        pArr->paddr = (int *)realloc(pArr->paddr, sizeof(int) * (pArr->cur_len + increment));
    
        if (NULL == pArr->paddr){
            pArr->paddr = pold;
            return FALSE;
         }
    
        // realloc will auto free the old memory, it's not allow to free it again!!!!
    //    if (pold != pArr->paddr){
    //        free(pold);
    //     }
    
        pArr->len += increment;
        return TRUE;
    }

见到我用了static 前序, 是因为i我只希望这个函数被数组的内部函数使用, 并不希望它被其他的文件直接调用.

**5.10 赋值指定元素函数** **  Arr\_set(struct Arrlist \* pArr, int index, int val)**

也许有人问, 直接用pArr->paddr\[index\] = val 不就可以了吗? 为何要专门写1个函数.

实际上, 上面的写法有可能被通过编译. 但是十分不安全,  因为数组的长度是有限的,  如果index的值大于等于数组的长度就很有可能造成内存泄露了.

所以实在上我们要在赋值前判断一下要赋值的index 和 数据实际长度 cur\_len的关系.

1. 判断index 是否超出当前数组的实际长度cur\_len, 如果是, 则告诉用户, 数组内还没这个元素呢, 返回false

2. 设置对应元素的值, 并返回true.

![复制代码][copycode.gif]

1 BOOL Arr_set(struct Arrlist * pArr, int index, int val){
     2     if (TRUE != pArr->is_inited){
     3         Arr_error("Array is not inited yet!!");
     4     }
     5 
     6     if((index < 0) || (index >= pArr->cur_len)){
     7         printf("the element is not existed yet\n");
     8         return FALSE;
     9     }
    10 
    11     pArr->paddr[index] = val;    
    12     return TRUE;
    13 }

![复制代码][copycode.gif]

**5.11 取指定元素函数** **  Arr\_get(struct Arrlist \* pArr, int index)**

同样要判断index 和 cur\_len的关系, 如果index >= cur\_len, 要么就退出整个程序抛出error, 但我这里返回1个0算了.

![复制代码][copycode.gif]

1 int Arr_get(struct Arrlist * pArr, int  index){
     2     if (TRUE != pArr->is_inited){
     3         Arr_error("Array is not inited yet!!");
     4     }
     5 
     6     if((index < 0) || (index >= pArr->cur_len)){
     7         printf("the element is not existed yet\n");
     8         return 0;
     9     }
    10 
    11     return pArr->paddr[index];    
    12 }

![复制代码][copycode.gif]

**5.12 插入1元素到指定位置函数** **  Arr\_insert(struct Arrlist \* pArr, int position, int val)**

首先要理解insert 和 set的区别,  上面的Arr\_set所赋值的元素必须是数组已经存在的, 并且该元素的值将会变化.

而insert 则不一样, 似乎插入1个新的元素到数组到position元素的**前1个位置**,该新元素后面的其他元素的值不变化, 但是位置可能会被退后1位.

所以Insert动作后, cur\_len的值会加1, 因为多了1个元素嘛, 既然cur\_len会增加, 就要判断当前数组是否满了, 而且可能要用到扩容.

1.判断position是否在cur\_len的范围之内, 如果否就提醒用户, 让他用Arr\_add吧. 返回false

2.判断数组是否满了, 是则扩容

3.position和到后面所有元素,从最后1个元素开始, 复制到后1个位置.

4. 把要插入的值写入到index的位置上.

5. cur\_len +1

代码如下:

![复制代码][copycode.gif]

BOOL Arr_insert(struct Arrlist * pArr, int position, int val){
        if (TRUE != pArr->is_inited){
            Arr_error("Array is not inited yet!!");
        }
    
    
        if((position < 0) || (position >= pArr->cur_len)){
            printf("the position is over the length of array, please use Arr_add instead\n");
            return FALSE;
        }
        
        if(TRUE == Arr_is_full(pArr)){
            if (FALSE == Arr_extend(pArr, pArr->increment)){ 
                return FALSE;
            }
        }
    
        int i;
        for (i=(pArr->cur_len -1); i>= position; i--){
            pArr->paddr[i+1] = pArr->paddr[i];
        }
    
        pArr->paddr[position] = val;
        pArr->cur_len++;
            return TRUE;
    
    }

![复制代码][copycode.gif]

**5.13 删除1个指定位置的元素函数****  Arr\_delete(struct Arrlist \* pArr, int index)**

这个函数跟上面那个逻辑是对应关系,

1, 判断index 是否在cur\_len的范围内, 否则返回false

2, 从index 位置开始,   到最后1个位置的前1个元素, 每个元素的值设成后1个元素的值.

3, 把最后1个元素的值清空(设成0)  , 这一步不做也可以, 就当里面是垃圾数据.

4, cur\_len 的值减1 ,  这一步很重要.

代码如下:

![复制代码][copycode.gif]

1 BOOL Arr_delete(struct Arrlist * pArr, int index){
     2     if (TRUE != pArr->is_inited){
     3         Arr_error("Array is not inited yet!!");
     4     }
     5 
     6 
     7     if((index < 0) || (index >= pArr->cur_len)) {
     8         printf("the element is not existed yet\n");
     9         return FALSE;
    10     }
    11 
    12     int i;
    13     for(i = (index + 1); i <= (pArr->cur_len -1); i++){
    14         pArr->paddr[i-1]=pArr->paddr[i];    
    15     }    
    16     
    17     pArr->paddr[pArr->cur_len-1]=0;
    18     pArr->cur_len--;
    19     return TRUE;
    20 
    21 }

![复制代码][copycode.gif]

**5.14 倒置数组函数** **  Arr\_invert(struct Arrlist \* pArr)**

所谓倒置就是把数组前面元素放到后面, 后面的放到前面.

实现的算法其实不复杂,  就是最前的与最后互换,  第个元素与倒数第2个元素互换.....

代码如下:

![复制代码][copycode.gif]

1 void Arr_invert(struct Arrlist * pArr){
     2     if (TRUE != pArr->is_inited){
     3         Arr_error("Array is not inited yet!!");
     4     }
     5 
     6     if (TRUE == Arr_is_empty(pArr)){
     7         return;
     8     }
     9 
    10     int i = 0;
    11     int j = pArr->cur_len -1;
    12     int m;    
    13     
    14     while(i<j){
    15         m = pArr->paddr[i];
    16         pArr->paddr[i] = pArr->paddr[j];
    17         pArr->paddr[j] = m;
    18         i++;
    19         j--;
    20     }
    21 }

![复制代码][copycode.gif]

**5.15 排序函数 Arr\_sort(****struct Arrlist \* pArr)**

排序是一个很有深度的课题, 我这里只用了最简单实现的冒泡排序法, 当然性能也几乎最渣了, 不过应付一般长度的数组还是可以的..

![复制代码][copycode.gif]

1 void Arr_sort(struct Arrlist * pArr){
     2     if (TRUE != pArr->is_inited){
     3         Arr_error("Array is not inited yet!!");
     4     }
     5 
     6     if (TRUE == Arr_is_empty(pArr)){
     7         return;
     8     }
     9     
    10     Arr_sort_dtlmaopao(pArr->paddr, pArr->cur_len);
    11 
    12 }
    13 
    14 
    15 static void Arr_sort_dtlmaopao(int * piar, int len){
    16     int i, j, m;
    17     for (i=0; i< len; i++){
    18         //printf("\n");
    19         //printf("i is %d\n",i);
    20         //Arr_p_array(piar,len);
    21 
    22         for (j=i+1; j< len; j++){
    23             //printf("mv is %d\n",piar[i]);
    24             //Arr_p_array(piar,len);
    25             if (piar[i] > piar[j]){
    26                 m =piar[i];    
    27                 piar[i] = piar[j];
    28                 piar[j] = m;
    29                     
    30             }
    31             //Arr_p_array(piar,len);
    32         }
    33     }    
    34 }

![复制代码][copycode.gif]

**6.最后写个小程序测试一下**

最基本的几个函数我都写出来, 但是还是要测试一下啦:

写个小程序:

![复制代码][copycode.gif]

1 int array1_1(){
     2 
     3     struct Arrlist arr1;
     4     struct Arrlist * parr1;
     5 
     6     parr1 = &arr1;
     7     
     8     Arr_init(parr1,10);
     9     char empty =Arr_is_empty(parr1);
    10 
    11 
    12     printf("len is %d\n",parr1->len);
    13     printf("is empty is %c\n",empty);
    14     printf("\n");
    15 
    16     int i;
    17     for (i=0;i<parr1->len;i++){
    18         Arr_add(parr1,(i+1) * 3);
    19     }
    20 
    21     printf("cur_len is %d\n",parr1->cur_len);
    22     printf("\n");
    23 
    24     Arr_set(parr1, 9,Arr_get(parr1,8));
    25     Arr_set(parr1, 10,100);
    26 
    27     Arr_insert(parr1, 10,11111);
    28     Arr_insert(parr1, 3,11111);
    29     Arr_insert(parr1, 3,22222);
    30     Arr_delete(parr1, 4);
    31     
    32     Arr_show(parr1);
    33 
    34     for (i=0; i<20; i++){
    35         Arr_add(parr1,(i+1)*4);
    36     
    37     }
    38     
    39         printf("cur_len is %d\n",parr1->cur_len);
    40     printf("len is %d\n",parr1->len);
    41     printf("\n");
    42 
    43     Arr_show(parr1);
    44     printf("\n");
    45     
    46     Arr_invert(parr1);        
    47     Arr_show(parr1);
    48     printf("\n");
    49     
    50     Arr_sort(parr1);    
    51     Arr_show(parr1);
    52     printf("\n");
    53 
    54     return 0;
    55 }

![复制代码][copycode.gif]

输出:

![复制代码][copycode.gif]

len is 10
    is empty is 1
    
    cur_len is 10
    
    the element is not existed yet
    the position is over the length of array, please use Arr_add instead
    3, 6, 9, 22222, 12, 15, 18, 21, 24, 27, 27
    cur_len is 31
    len is 40
    
    3, 6, 9, 22222, 12, 15, 18, 21, 24, 27, 27, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80
    
    80, 76, 72, 68, 64, 60, 56, 52, 48, 44, 40, 36, 32, 28, 24, 20, 16, 12, 8, 4, 27, 27, 24, 21, 18, 15, 12, 22222, 9, 6, 3
    
    3, 4, 6, 8, 9, 12, 12, 15, 16, 18, 20, 21, 24, 24, 27, 27, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 22222
    
    array1_main done

![复制代码][copycode.gif]

[copycode.gif]: /images/20220319/0c2ca8ec4a824c8483265466ebcb6a78.png