数据结构之线性结构--数组
一、什么是线性表
线性表是种由零个或者多个元素组成的有限序列，线性表强调元素是有限的，就像一个班的人数也是有限的，一个线性表中只有一个头和一个尾，中间的元素有一个前驱和一个后记。
【数据结构之线性结构--数组】
文章图片
二、线性表的顺序储存方式 1、 顺序储存结构中使用一片连续的内存来储存线性表中的所有元素。在C++中使用数组来实现储存。
文章图片
2、顺序储存结构中的元素的插入方式 ：
文章图片
3、顺序储存结构中的元素的删除方式 ;
文章图片
4、顺序储存结构的访问
在顺序储存结构中通常使用数组来储存数据，我们在访问数据的时候只需要指定数据在数组中的位置的下标则可以了。
5、顺序储存结构的优缺点
文章图片
6、顺序储存结构的代码实现
//H文件
#ifndef _AL_LISTSEQ_INCLUDE
#define _AL_LISTSEQ_INCLUDE#include template
class AL_ListSeq
{
public:
//定义了一些基本的常量//默认的储存区域大小
static const DWORD LISTSEQ_DEFAULTSIZE= 100;
//表示最大储存内存
static const DWORD LISTSEQ_MAXSIZE= 0xffffffff;
//表示没有当前内存没有这个元素
static const DWORD LISTSEQ_POSITION_INVALID= 0xffffffff;
//初始化构造函数,为线性表分配内存
AL_ListSeq(DWORD dwSize = LISTSEQ_DEFAULTSIZE);
//析构函数，释放数组内存
~AL_ListSeq();
//获取当前已经储存的数据的长度
DWORD Length() const;
//根据内容查找元素在表中的位置
DWORD Find(const T& tData) const;
//判读查找的元素是否在表中存在
BOOL IsElement(const T& tData) const;
//随机插入元素
BOOL Insert(DWORD dwIndex,const T& tData);
//在表的开始位置插入元素
BOOL InsertBegin(const T& tData);
//在表的元素长度的尾部插入元素
BOOL InsertEnd(const T& tData);
//移除并获取表中的任意元素
BOOL Remove(const T& tData);
//移除表中的任意元素但不返回移除元素的值
BOOL RemoveAt(DWORD dwIndex);
//判读当前表中是否有元素存在
BOOL IsEmpty() const;
//获取表中的任意一个元素的值
BOOL Get(DWORD dwIndex, T& tTypeOut) const;
//修改表中的任意一个元素的值
BOOL Set(DWORD dwIndex, const T& tData, T& tTypeOut);
//将记录表中存储元素的值归零
VOID Clear();
//两个表相互赋值
AL_ListSeq& operator = (const AL_ListSeq& cAL_ListSeq);
private:
//为线性表分配内存或者扩展内存大小
VOID GetBuffer();
//判断当前表中存储元素长度是否大于最大长度
BOOL IsFull() const;
AL_ListSeq(const AL_ListSeq& cAL_ListSeq);
private: T*m_pElements;
//用于储存元素的数组
DWORDm_dwMaxSize;
//数组的最大长度
DWORDm_dwSize;
//记录当前数组中储存元素的个数
};
//CPP文件
template
AL_ListSeq::AL_ListSeq(DWORD dwSize):
m_pElements(NULL),
m_dwMaxSize(dwSize),
m_dwSize(0x00)
{
if (0x00 == m_dwMaxSize) {
//for memory deal
m_dwMaxSize = 1;
}
GetBuffer();
}template
AL_ListSeq::~AL_ListSeq()
{
if (NULL != m_pElements) {
delete[] m_pElements;
m_pElements = NULL;
}
}template DWORD
AL_ListSeq::Length() const
{
if (TRUE == IsEmpty()) {
return 0;
}return m_dwSize;
}template DWORD
AL_ListSeq::Find(const T& tData) const
{
if (TRUE == IsEmpty()) {
return LISTSEQ_POSITION_INVALID;
}for(DWORD dwCnt=0x00;
dwCnt BOOL
AL_ListSeq::IsElement(const T& tData) const
{
if (TRUE == IsEmpty()) {
return FALSE;
}if (LISTSEQ_POSITION_INVALID == Find(tData )) {
return FALSE;
}return TRUE;
}template BOOL
AL_ListSeq::Insert(DWORD dwIndex, const T& tData)
{
//判插入的位置是否超出内存长度位置
if (dwIndex > Length()) {
return FALSE;
}
//判读当前储存元素个数是否与最大内存长度相同
if (TRUE == IsFull()) {
//重新分配内存
GetBuffer();
}
//将元素向后移动
for(DWORD dwCnt=(Length()-1+1);
dwCnt>dwIndex;
dwCnt--) {
m_pElements[dwCnt] = m_pElements[dwCnt-1];
}
m_pElements[dwIndex] = tData ;
m_dwSize++;
return TRUE;
}template BOOL
AL_ListSeq::InsertBegin(const T& tData)
{
return Insert(0, tData);
}template BOOL
AL_ListSeq::InsertEnd(const T& tData)
{
return Insert(Length(), tData);
}template BOOL
AL_ListSeq::Remove(const T& tData)
{
if (TRUE == IsEmpty()) {
return FALSE;
}BOOL bRemove = FALSE;
for(DWORD dwCnt=0x00;
dwCnt BOOL
AL_ListSeq::RemoveAt(DWORD dwIndex)
{
if (dwIndex > Length()) {
//can not insert to this position
return FALSE;
}for(DWORD dwCnt=dwIndex;
dwCnt BOOL
AL_ListSeq::IsEmpty() const
{
return (0x00 == m_dwSize) ? TRUE:FALSE;
}template BOOL
AL_ListSeq::Get(DWORD dwIndex, T& tTypeOut) const
{
if (TRUE == IsEmpty()) {return FALSE;
}if (Length()-1 < dwIndex) {return FALSE;
}tTypeOut = m_pElements[dwIndex];
return TRUE;
}template BOOL
AL_ListSeq::Set(DWORD dwIndex, const T& tData, T& tTypeOut)
{
if (Length()-1 < dwIndex) {
return FALSE;
}tTypeOut = m_pElements[dwIndex];
m_pElements[dwIndex] = tData ;
return TRUE;
}template VOID
AL_ListSeq::Clear()
{
m_dwSize = 0x00;
}template VOID
AL_ListSeq::GetBuffer()
{
//当数组中储存的元素为最大长度并且数组非空时则结束函数调用
if ( (FALSE == IsFull()) && (NULL != m_pElements) ) {
return;
}//当还没有为数组分配内存时，则为数组分配一个最大内存
if (NULL == m_pElements) {
if(0 < m_dwMaxSize){
m_pElements = new T[m_dwMaxSize];
}
return;
}T* pLastTpye = NULL;
//设置线性表最大内存的一个长度，是否超过我们设置的常量值。
pLastTpye = m_pElements;
if (LISTSEQ_MAXSIZE == m_dwMaxSize) {return;
}
else if (LISTSEQ_MAXSIZE/2 < m_dwMaxSize) {
m_dwMaxSize = LISTSEQ_MAXSIZE;
}
else {
m_dwMaxSize *= 2;
}
//从新为线性表分配内存长度，并将数据拷贝到新的内存空间中
if(0 < m_dwMaxSize){m_pElements = new T[m_dwMaxSize];
}
for (DWORD dwCpy=0x00;
dwCpy BOOL
AL_ListSeq::IsFull() const
{
return (m_dwMaxSize <= Length()) ? TRUE:FALSE;
}template AL_ListSeq&
AL_ListSeq::operator = (const AL_ListSeq& cAL_ListSeq)
{
Clear();
T tData;
for (DWORD dwAssign=0x00;
dwAssign 测试代码
void ListSeqTest()
{
//为数组分配一个单位的内存
AL_ListSeq cListSeq(1);
BOOL bEmpty = cListSeq.IsEmpty();
std::cout< 运行结果：
文章图片
推荐阅读
- PMSJ寻平面设计师之现代(Hyundai）
- 太平之莲
- 闲杂“细雨”
- 七年之痒之后
- 深入理解Go之generate
- 由浅入深理解AOP
- 期刊|期刊 | 国内核心期刊之（北大核心）
- 生活随笔｜好天气下的意外之喜
- 感恩之旅第75天
- python学习之|python学习之 实现QQ自动发送消息