40_线性表、向量

线性表的定义

    1. 线性表的逻辑结构
    2. 由n(n>=0)个数据元素(a1,a2,…,an)构成的有限序列。记作L=(a1,a2,…an)A1—-首元素,An尾元素
    3. 表的长度
    4. 空表

线性表的特征

    1. 直接前驱(prev)
    2. 直接后继(next)
    3. 允许没有前驱与后继,仅限于头尾

抽象数据类型线性表的定义

  1. ADT list

{

//增删改查、清空、前驱、后继、线性表的长度、取元素、合并、复制

}

线性表的顺序表示(顺序存储结构)

  1. 顺序分配—将线性表中的数据元素依次存放到计算机存储器中一组地址连续的存储单元中,这种分配方式称为顺序分配或顺序映像。得到:顺序存储结构或向量(一维数组)。最大优点算位置可以用公式,下标寻址公式
  2. 静态数组,长度是固定的。在磁盘上是可以用的
  3. 动态数组(向量),一开始申请的大小不够用,当不够用的时候申请更大的空间
  4. 数据结构都是泛型编程

C语言:

Void init();

Void * elements;

Void insert(Void * elements, int pos, void *elment, int size);

Void erase(Void * elements);

Void modify(Void * elements);

Void search(Void * elements);

C++语言:

class CMyVector //向量

{

private:

enum CAPACITY

{

MIX_CAPACITY = 1 //最少1个

};

public:

CMyVector(unsigned initCapacity = 0);

~CMyVector();

void resize(unsigned newSize); //调整大小,占位==》int ary[3];

void reserve(unsigned newCapacity); //调至容量

unsigned size() const; //获取大小

unsigned capacity() const; //获取容量

void push_back(int& value); //插入元素到尾部

bool empty(); //是否为空

void clear(); //清空元素

void erese(int pos); //删除

void insert(int pos, int& elem); //插入

private:

int *objects_; //元素 //一开始先支持一种int类型,一开始写基本数据类型不好,得写类对象

unsigned size_; //大小

unsigned capacity_; //总容量,一开始可以给个默认的大小

};

  1. 数据结构操作中不能用memcpy,因为不能重载符号,导致重复释放
  2. Resize()占位,申请2倍空间为了下次操作不扩容。如果不占位导致时间复杂度上升,影响效率
  3. Reserver()是调整数据完之后再调用
  4. Resize() 和reserver()是空间管理
  5. Clear(); //把之前的空间利用上了,只是把大小改为了0

向量的时间复杂度

插入

插入非尾部部O(n)

插入尾部0(1)

空间不够:O(n)

删除

删除尾部O(1),其它位置0(n)

修改

O(n)

查询

O(n) 排序O(logon)

随机访问

O(1)

优点

随机访问快

实际应用场合

播放音乐(不适合)

随机访问:频繁

插入:不频繁

删除:不频繁

查询:不频繁

修改:不频繁 //一般不记录,和查询相关

31个球选号(合适)

存球:从尾部插入常量阶

开号:常量阶

总结

固有的数量下,少量的从尾部删除增加,使用随机访问的应用

数据结构三大境界

    1. 会分析场景使用
    2. 会根据已有的场景修改当前的数据结构
    3. 没有合适软件的数据结构,自己去创造合适的数据结构

作业

1.编写动态数组模板

 //Vector.h
#pragma once

template 
class CVector
{
public:

    CVector(const unsigned initCapacity = 1U)    //默认构造二个,其它构造为2倍
    {
        m_pElement = new T[initCapacity * 2];
        setSize(0U);
        setCapacity(initCapacity * 2);
    }

    CVector(const CVector& obj) //采用深拷贝,新的向量不会影响当前向量
    {
        m_pElement = new T[obj.getSize() * 2];

        for (unsigned i = 0; i < obj.getSize(); i++)
        {
            m_pElement[i] = obj.m_pElement[i];
        }

        setSize(obj.getSize());
        setCapacity(getSize() * 2);
    }

    ~CVector()
    {
        if (m_pElement != nullptr)
        {
            delete[] m_pElement;
        }
    }

    const bool isEmpty() const  //判断使用的空间是否为空,给用户提供判空方法
    {
        if (m_uSize != 0)
        {
            return false;
        }
        else
        {
            return true;
        }
    }

    CVector& push_back(const T& element)    //末尾添加元素
    {
        checkCapacity();
        //存放数据
        *(m_pElement + getSize()) = element;
        //设置使用的空间
        setSize(getSize() + 1U);
        return *this;
    }

    CVector& pop_back() //末尾删除元素
    {
        //如果实际使用空间不为0
        if (getSize() != 0U)
        {
            setSize(getSize() - 1U);
        }

        return *this;
    }

    T& operator[](const int index)    //重载下标获得值
    {
        if (!isEmpty())
        {
            return *(m_pElement + index)->m_pInt;
        }
        else
        {
            return NULL;
        }
    }

    CVector& insert(const int pos, const T& obj)     //向指定位置增加元素
    {
        checkCapacity();
        //从后面元素移动到下一个元素移动以前的数据
        for (int i = (getSize() - 1);  i >= pos;  i--)
        {
            m_pElement[i + 1] = m_pElement[i];
        }
        //插入数据
        m_pElement[pos] = obj;
        //设置使用的空间
        setSize(getSize() + 1U);

        return *this;
    }

    CVector& earse(const int pos)  //删除指定位置元素
    {
        if (getSize() > 0)
        {
            //从后面元素移动到下一个元素移动以前的数据
            for (int i = pos; i < (int)getSize() - 1; i++)
            {
                m_pElement[i] = m_pElement[i + 1];
            }
            //设置使用的空间
            setSize(getSize() - 1U);
        }
        return *this;
    }

    void notChange()    //暂时不修改大小了,把实际占用空间和使用的空间设为一样
    {
        if (getSize() == 0U && getCapacity() != 0U)
        {
            delete[] m_pElement;
            setCapacity(0U);
            m_pElement = nullptr;
        }
        else if (getSize() != getCapacity())
        {
            T *pOldElement = m_pElement;
            m_pElement = new T[getSize()];
            for (unsigned i = 0; i < getSize(); i++)
            {
                m_pElement[i] = pOldElement[i];
            }
            delete[] pOldElement;

            setCapacity(getSize());
        }
    }

    void clear()    //清空元素
    {
        setSize(0U);
    }

    CVector& operator+(const CVector& obj)  //合并两个向量
    {
        //复制数据
        CVector *pVec = new CVector((this->getSize() + obj.getSize()) * 2);
        unsigned vec = 0;
        for (unsigned i = 0; i < this->getSize(); i++, vec++)
        {
            pVec->m_pElement[vec] = this->m_pElement[i];
        }
        for (unsigned i = 0; i < obj.getSize(); i++, vec++)
        {
            pVec->m_pElement[vec] = obj.m_pElement[i];
        }
        //设置空间
        pVec->setCapacity((vec - 1u) * 2);
        pVec->setSize(vec - 1u);
        return *pVec;
    }

    T& back()
    {
        return m_pElement[getSize() - 1U];
    }

    T& front()
    {
        return m_pElement[0];
    }

    CVector& operator+= (const CVector& vec)
    {
        for (unsigned i = 0; i < vec.getSize(); i++)
        {
            push_back(vec[i]);
        }
    }

private:
    unsigned getSize() const    //获取使用的空间
    {
        return m_uSize;
    }

    unsigned getCapacity() const    //获取实际占用空间
    {
        return m_uCapacity;
    }

    void setSize(const unsigned size)   //设置使用的空间
    {
        m_uSize = size;
    }

    void setCapacity(const unsigned capacity)   //设置实际占用空间
    {
        m_uCapacity = capacity;
    }

    void checkCapacity()    //判断空间能否增加元素
    {
        //如果空间不够增加
        if (getSize() == getCapacity())
        {
            //设置旧的元素指针
            T *pOldElement = m_pElement;
            //设置实际存储空间为当前值的两倍
            setCapacity(getCapacity() * 2U);
            //申请新的占用空间
            m_pElement = new T[getCapacity()];
            //拷贝旧数据
            for (unsigned i = 0; i < getSize(); i++)
            {
                m_pElement[i] = pOldElement[i];
            }
            //清理掉以前的元素类型
            delete[] pOldElement;
        }
    }
private:
    T *m_pElement;      //存储的元素
    unsigned m_uSize;       //使用的空间
    unsigned m_uCapacity;   //实际占用空间
};
 //test.cpp
#include "Vector.h"

void main()
{
    {
        CVector vec;
        vec.push_back(2);
        vec.push_back(3);
        vec.push_back(4);
        vec.push_back(5);
        vec.insert(0, 1);
        vec.insert(5, 6);

        for (int i = 0; i < 6; i++)
        {
            vec.earse(0);
        }

        vec.notChange();
    }
}
0 条评论
发表一条评论