首页 > 其他分享 >数据结构之数组

数据结构之数组

时间:2022-12-12 22:46:36浏览次数:45  
标签:int void mpArr 数组 Array 数据结构 mCur

1.数组实现

数组的特点:内存是连续的,即物理地址是连续的。

优点

  • 随机访问的时间复杂度为 O(1);
  • 末尾位置增加元素的时间复杂度为 O(1);
  • 访问元素前后相邻位置的元素非常方便;

缺点

  • 非末尾位置增加元素需要进行大量的数据移动,时间复杂度为 O(n);
  • 搜索的时间复杂度:
    • 无序数组采用线性搜索,时间复杂度为 O(n);
    • 有序数组采用二分搜索,时间复杂度为 O(logn);
  • 数组扩容时的消耗比较大;

如下为动态数组的实现:

class Array {
public:
    Array(int size = 10);
    ~Array();

public:
    // 返回第i个位置的值
    int at(int idx) const { return mpArr_[idx]; }
    // 返回数组大小
    int size() const { return mCur_; }
    // 在末尾增加元素
    void push_back(int val);
    // 删除末尾元素
    void pop_back();
    // 按位置增加元素
    void insert(int pos, int val);
    // 按位置删除
    void erase(int pos);
    // 元素查询
    int find(int val);
    // 数组扩容
    void expand(int size);

private:
    int* mpArr_; // 指向可扩容数组的内存
    int  mCap_;  // 数组的容量
    int  mCur_;  // 数组有效元素的个数
};

Array::Array(int size)
    : mCur_(0)
    , mCap_(size) {
    mpArr_ = new int[mCap_];
}

Array::~Array() {
    delete[] mpArr_;
    mpArr_ = nullptr;
}

void Array::push_back(int val) {
    if (mCur_ == mCap_) {
        expand(2 * mCap_);
    }
    mpArr_[mCur_++] = val;
}

void Array::pop_back() {
    if (mCur_ != 0)
        mCur_--;
}

void Array::insert(int pos, int val) {
    if (pos < 0 || pos >= mCap_)
        return;

    if (mCur_ == mCap_) {
        expand(2 * mCap_);
    }

    for (int i = mCur_ - 1; i >= pos; i--) {
        mpArr_[i + 1] = mpArr_[i];
    }
    mpArr_[pos] = val;
    mCur_++;
}

void Array::erase(int pos) {
    if (pos < 0 || pos >= mCap_)
        return;
    for (int i = pos + 1; i < mCur_; i++) {
        mpArr_[i - 1] = mpArr_[i];
    }
    mCur_--;
}

int Array::find(int val) {
    for (int i = 0; i < mCur_; i++) {
        if (mpArr_[i] == val)
            return i;
    }
    return -1;
}

void Array::expand(int size) {
    int* ptr = new int[size];
    memcpy(ptr, mpArr_, sizeof(int) * mCap_);
    delete[] mpArr_;

    mpArr_ = ptr;
    mCap_  = size;
}

2.常见的算法问题

2.1 双指针

应用场景:数组逆序

算法过程:定义两个指针,分别指向数组头部和数组尾部,每次交换两个指针所指向的内容,然后左指针往左走,右指针往右走,直到左指针跨过右指针。

void reverse(int arr[], int size) {
	int* left = arr;
	int* right = arr + size - 1;
	while (left < right) {
		int tmp = *left;
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}

3.STL实现

在 STL 标准库中,数组数据结构的对应实现是 vector,即动态数组。

vector 采用的数据结构为:线性连续空间。它以两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已经被使用的范围,并以迭代器 end_of_storage 指向整块连续空间的尾端。

当增加新元素时,如果超过当前的容量,则容量会扩充到 2倍。如果两倍容量仍不足,就扩张至足够大的容量。所谓动态增加大小,并不是在原空间之后接续新空间,而是以原大小的两倍另外配置一块较大空间,然后将原内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。因此,对vector的任何操作,一旦引起空间重新配置,指向原 vector 的所有迭代器就都失效了

vector的大小为 3 个指针的大小,且它以普通指针作为迭代器,如下:

template<class T, class Alloc = alloc>
class vector {
    typedef T  value_type;
    typedef T* iterator;
    iterator start;
	iterator finish;
	iterator end_of_storage;
};

标签:int,void,mpArr,数组,Array,数据结构,mCur
From: https://www.cnblogs.com/tuilk/p/16977330.html

相关文章

  • 我花了一夜用数据结构给女朋友写个H5走迷宫游戏
    文章目录​​起因​​​​分析​​​​画线(棋盘)​​​​画迷宫​​​​方块移动​​​​结语​​先看效果图(在线电脑尝试地址http://biggsai.com/maze.html):起因又到深......
  • 【LeetCode】二分法--剑指 Offer 53 - I. 在排序数组中查找数字 I
    点击直达题目内容统计一个数字在排序数组中出现的次数。示例示例1:输入:nums=[5,7,7,8,8,10],target=8输出:2示例2:输入:nums=[5,7,7,8,8,10],target......
  • 【数据结构-树】二叉树的相关算法
    目录1计算二叉树中双分支结点的个数2交换二叉树中所有左右子树3求先序遍历第k个元素4删去值为x的子树5计算二叉树的带权路径长度(WPL)6将表达式树转化为等价的中缀......
  • 数组的活学活用(一)
    概览数组我们知道,是一种有序连续的数据结构,随机访问的效率高。之所以随机访问的效率高,就是因为它的每个值都有下标,可以根据下标直接找到我们想要的值。 既然我们已经......
  • Shell数组基本概述
    1.数组基本概述01.什么是数组?数组其实也算是变量,传统的变量只能存储一个值,但数组可以存储多个值。02.数组的分类Shell数组分为普通数组和关联数组。普通数组:只能使......
  • 剑指 Offer 56 - II. 数组中数字出现的次数 II(状态转移 位运算)
      ​​剑指Offer56-II.数组中数字出现的次数II​​难度中等38在一个数组 ​​nums​​ 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次......
  • 剑指offer 数组中的逆序对(归并排序)
    ​​剑指Offer51.数组中的逆序对​​难度困难176在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的......
  • 原地合并两个排序数组 O(1)空间复杂度,O(n)时间复杂度
    问题:给你两个从小到大的数组a,b。在不申请额外空间下,往a填充a和b合并后的排序数组(假设a的空间是足够的)。第一种方法:很直觉的思路是,我们采取和归并排序时同样的策略,每次拿出最......
  • C语言 (数据结构)在顺序表中用二分查找和冒泡排序算法
    main.c:#include<stdio.h>#include<stdlib.h>#include"SequenceList.h"intmain(){//创建顺序表和指针SequenceListSL,*P_SL;intchoice=0;......
  • 算法与数据结构实验四
    实验项目名称:实验四       一、 实验目的1)掌握图的邻接矩阵、邻接表存储结构表示及其创建算法2)掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法;3)掌握图......