现在的位置: 首页 > 综合 > 正文

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

2013年10月05日 ⁄ 综合 ⁄ 共 5893字 ⁄ 字号 小 中 大 ⁄ 评论关闭

线性结构

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;
}

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞