07-数据结构_线性结构-连续存储-数组

红太狼 2021-12-17 03:17 179阅读 0赞

# 线性结构 #

1, 概念  
把所有的结点用一根直线串起来  
2, 分类

(1) 连续存储\[数组\]

优点: 存取快

缺点: 插删慢, 空间(元素个数)通常有限, 需要大块连续的内存

(2) 离散存储\[链表\]

优点: 插删快, 空间无限制

缺点: 存取慢(主要是定位元素慢)

# 数组 #

## 1, 什么叫做数组 ##

一组 相同数据类型变量 的集合.

## 2, 数组的优缺点 ##

参看 C语言部分

## 3, 实现Java中的ArrayList ##

04-array\_1.c

### 初始化 init ###

// 初始化
    void init(struct Array * pArr, int length)
    {
        pArr->pBase = (int *) malloc( sizeof(int) * length );
        // 内存分配失败, malloc 返回 NULL, 终止程序
        if ( NULL == pArr->pBase ) 
        {   
            printf("动态内存分配失败!!");                    
            exit( -1 );
        }
        pArr->len = length;
        pArr->count = 0;
    
        return;
    }

### 追加 append ###

// 追加(在末尾添加一个元素)
    bool append(struct Array * pArr, int value)
    {
        if ( isFull( pArr ) )
        {
            return false;
        }
        
        //pArr->pBase[pArr->count++] = value; 
        pArr->pBase[pArr->count] = value; // 末尾追加
        pArr->count++;  // 有效元素个数加一
    
        return true;
    }

### 插入 insert ###

// 插入, pos 从 0 开始
    bool insert(struct Array * pArr, int pos, int value)
    {
        if ( pos < 0 || pArr->len - 1 < pos )
        {
            printf("元素位置不合法!--%d not in [0, %d]     ", pos, pArr->len-1);
            return false;
        }
    
        if ( isFull( pArr ) )
        {
            return false;
        }        
        
        // 如果是在末尾插入
        if ( pos == (pArr->count-1) )
        {
            append(pArr, value);
        }
        else 
        {
            // 从下标 pos 开始, 所有的元素后移一位
            int end = pArr->count - 1;
            for ( ;end >= pos; --end)
            {
                pArr->pBase[end+1] = pArr->pBase[end];            
            }
        }
        
        // 在 指定下标 元素处 添加value
        pArr->pBase[pos] = value;
        pArr->count++;  // 元素有效个数加一
    
        return true;
    }

### 删除 delete ###

// 删除, 判断是否删除成功, 同时返回 删除的元素的值
    bool delete(struct Array * pArr, int pos, int * pValue)
    {
        if ( isEmpty( pArr ) )
        {
            printf("数组为空!!");
            return false;
        }
        
        if ( pos < 0 || pos > (pArr->count-1) )
        {
            printf("元素位置不合法!--%d not in [0, %d]     ", pos, pArr->count-1);
            return false;
        }
    
        // 如果是删除末尾元素
    
        *pValue = pArr->pBase[pos];
    
        // 所有元素前移一位, 从 pos+1 索引开始
        int start = pos + 1;
        for (; start < pArr->count; ++start)
        {
            pArr->pBase[start-1] = pArr->pBase[start];
        }
        pArr->count--;
    
        return true;
    }

### 是否为空数组 isEmpty ###

// 是否为空数组
    bool isEmpty(struct Array * pArr)
    {
        if ( 0 == pArr->count)
        {
            return true;
        }
        return false;
    }

### 是否已满 isFull ###

// 是否已满
    bool isFull(struct Array * pArr)
    {
        if ( pArr->len == pArr->count )
        {
            return true;
        }
        return false;
    }

### 排序 sort ###

// 排序, 冒泡
    void sort(struct Array * pArr)
    {
        int i, j;
        int len = pArr->count - 1;
        for (i = 0; i < len - 1; ++i)
        {
            for (j = 0; j < len - 1 - i; ++j)
            {
                if ( pArr->pBase[j] > pArr->pBase[j+1])
                {
                    int temp = pArr->pBase[j];
                    pArr->pBase[j] = pArr->pBase[j+1];
                    pArr->pBase[j+1] = temp;
                }
            }
        }
        return;
    }

### 打印 showArray ###

// 打印数组
    void showArray(struct Array * pArr)
    {
        printf("pBase = %p, len = %d, count = %d\n", pArr->pBase, pArr->len, pArr->count);
        // 数组为空
        if ( isEmpty(pArr) )
        {
            printf("[]\n");
            return;
        }
    
        printf("[");
        int i;
        for (i = 0; i < pArr->count; ++i)
        {
            if ( i < pArr->count - 1 )
            {
                printf( "%d, ", *(pArr->pBase + i) );
            }
            else 
            {
                printf( "%d]\n", pArr->pBase[i] );
            }
            
        }
    
        return;
    }

### 反转 inverse ###

// 反转
    void inverse(struct Array * pArr)
    {
        if ( isEmpty(pArr) )
        {
            printf("数组为空");
            return;
        }
    
        int start = 0;
        int end = pArr->count - 1;
        
        for (; start < end; ++start, --end)
        {
            int temp = pArr->pBase[start];
            pArr->pBase[start] = pArr->pBase[end];
            pArr->pBase[end] = temp;
        }
    
        return;
    }

### 完整代码 ###

#include <stdio.h>
    #include <stdbool.h>// bool    
    #include <malloc.h> // malloc
    #include <stdlib.h> // exit, 该头文件可省.
    
    // 定义数组
    struct Array
    {
        int * pBase;    // 存储数组第一个元素的地址
        int len;        // 数组长度
        int count;      // 当前数组有效元素的个数
        //int increment;  // 自动增长因子
    } ;
    
    // 初始化,
    void init(struct Array * pArr, int length);
    // 追加(在末尾添加一个元素)
    bool append(struct Array * pArr, int value);
    // 插入, pos 从 0 开始
    bool insert(struct Array * pArr, int pos, int value);
    // 删除, 判断是否删除成功, 同时返回 删除的元素的值
    bool delete(struct Array * pArr, int pos, int * pValue);
    // 获取指定下标的元素
    int get();
    // 是否为空数组
    bool isEmpty(struct Array * pArr);
    // 是否已满
    bool isFull(struct Array * pArr);
    // 排序
    void sort(struct Array * pArr);
    // 打印
    void showArray(struct Array * pArr);
    // 反转
    void inverse(struct Array * pArr);
    // find
    // deleteAll
    
    int main(void)
    {
        struct Array arr;
    
        init( &arr, 6 );
        
        printf("%d\n", append( &arr, 5 ));
        printf("%d\n", append( &arr, 7 ));
        printf("%d\n", append( &arr, 2 ));
        printf("%d\n", append( &arr, 4 ));
    //    printf("%d\n", append( &arr, 9 ));
    //    printf("%d\n", append( &arr, 1 ));
    //    printf("%d\n", append( &arr, 3 ));  // 追加失败
    
        printf("%d\n", insert( &arr, -2, 1 ));
        printf("%d\n", insert( &arr, 15, 8 ));
        printf("%d\n", insert( &arr, 2, 1 ));
        printf("%d\n", insert( &arr, 5, 8 ));
    //    printf("%d\n", insert( &arr, 5, -8 )); // 已满, 插入失败
    
        showArray( &arr );    
    
        int deletedValue;
        printf("delete %d -->%d\n", deletedValue, delete( &arr, 5, &deletedValue));
        printf("delete %d -->%d\n", deletedValue, delete( &arr, 0, &deletedValue));
        showArray( &arr );   
        
        inverse(&arr);
        showArray( &arr );
        
        sort(&arr);
        showArray( &arr );
    
        return 0;
    }
    
    // 初始化
    void init(struct Array * pArr, int length)
    {
        pArr->pBase = (int *) malloc( sizeof(int) * length );
        // 内存分配失败, malloc 返回 NULL, 终止程序
        if ( NULL == pArr->pBase ) 
        {   
            printf("动态内存分配失败!!");                    
            exit( -1 );
        }
        pArr->len = length;
        pArr->count = 0;
    
        return;
    }
    // 打印数组
    void showArray(struct Array * pArr)
    {
        printf("pBase = %p, len = %d, count = %d\n", pArr->pBase, pArr->len, pArr->count);
        // 数组为空
        if ( isEmpty(pArr) )
        {
            printf("[]\n");
            return;
        }
    
        printf("[");
        int i;
        for (i = 0; i < pArr->count; ++i)
        {
            if ( i < pArr->count - 1 )
            {
                printf( "%d, ", *(pArr->pBase + i) );
            }
            else 
            {
                printf( "%d]\n", pArr->pBase[i] );
            }
            
        }
    
        return;
    }
    
    // 是否为空数组
    bool isEmpty(struct Array * pArr)
    {
        if ( 0 == pArr->count)
        {
            return true;
        }
        return false;
    }
    
    // 追加(在末尾添加一个元素)
    bool append(struct Array * pArr, int value)
    {
        if ( isFull( pArr ) )
        {
            return false;
        }
        
        //pArr->pBase[pArr->count++] = value; 
        pArr->pBase[pArr->count] = value; // 末尾追加
        pArr->count++;  // 有效元素个数加一
    
        return true;
    }
    
    // 是否已满
    bool isFull(struct Array * pArr)
    {
        if ( pArr->len == pArr->count )
        {
            return true;
        }
        return false;
    }
    
    // 插入, pos 从 0 开始
    bool insert(struct Array * pArr, int pos, int value)
    {
        if ( pos < 0 || pArr->len - 1 < pos )
        {
            printf("元素位置不合法!--%d not in [0, %d]     ", pos, pArr->len-1);
            return false;
        }
    
        if ( isFull( pArr ) )
        {
            return false;
        }        
        
        // 如果是在末尾插入
        if ( pos == (pArr->count-1) )
        {
            append(pArr, value);
        }
        else 
        {
            // 从下标 pos 开始, 所有的元素后移一位
            int end = pArr->count - 1;
            for ( ;end >= pos; --end)
            {
                pArr->pBase[end+1] = pArr->pBase[end];            
            }
        }
        
        // 在 指定下标 元素处 添加value
        pArr->pBase[pos] = value;
        pArr->count++;  // 元素有效个数加一
    
        return true;
    }
    
    // 删除, 判断是否删除成功, 同时返回 删除的元素的值
    bool delete(struct Array * pArr, int pos, int * pValue)
    {
        if ( isEmpty( pArr ) )
        {
            printf("数组为空!!");
            return false;
        }
        
        if ( pos < 0 || pos > (pArr->count-1) )
        {
            printf("元素位置不合法!--%d not in [0, %d]     ", pos, pArr->count-1);
            return false;
        }
    
        // 如果是删除末尾元素
    
        *pValue = pArr->pBase[pos];
    
        // 所有元素前移一位, 从 pos+1 索引开始
        int start = pos + 1;
        for (; start < pArr->count; ++start)
        {
            pArr->pBase[start-1] = pArr->pBase[start];
        }
        pArr->count--;
    
        return true;
    }
    
    // 反转
    void inverse(struct Array * pArr)
    {
        if ( isEmpty(pArr) )
        {
            printf("数组为空");
            return;
        }
    
        int start = 0;
        int end = pArr->count - 1;
        
        for (; start < end; ++start, --end)
        {
            int temp = pArr->pBase[start];
            pArr->pBase[start] = pArr->pBase[end];
            pArr->pBase[end] = temp;
        }
    
        return;
    }
    
    // 排序, 冒泡
    void sort(struct Array * pArr)
    {
        int i, j;
        int len = pArr->count - 1;
        for (i = 0; i < len - 1; ++i)
        {
            for (j = 0; j < len - 1 - i; ++j)
            {
                if ( pArr->pBase[j] > pArr->pBase[j+1])
                {
                    int temp = pArr->pBase[j];
                    pArr->pBase[j] = pArr->pBase[j+1];
                    pArr->pBase[j+1] = temp;
                }
            }
        }
        return;
    }