重庆转店铺哪个网站平台好,官方查企业信息的网站,休闲度假村网站建设方案,html 如何嵌入网站页面文章目录 前言一、目标二、SeqList实现要点三、SeqList函数实现3.1 get函数3.2 set函数3.3 insert函数带2个参数的insert带一个参数的insert 3.4 remove函数3.5 clear函数3.6 下标运算符重载函数无const版本const版本 3.7 length函数 总结 前言
当谈到C数据结构时#xff0c;… 文章目录 前言一、目标二、SeqList实现要点三、SeqList函数实现3.1 get函数3.2 set函数3.3 insert函数带2个参数的insert带一个参数的insert 3.4 remove函数3.5 clear函数3.6 下标运算符重载函数无const版本const版本 3.7 length函数 总结 前言
当谈到C数据结构时顺序存储结构是一个重要的概念。它是一种将数据元素按照其逻辑顺序依次存储在内存中的方式。这种存储方式使得元素在内存中是连续存储的这有助于快速访问和操作数据。在本文中我们将讨论顺序存储结构的抽象实现以帮助您更好地理解它的原理和应用。
顺序存储结构是一种基本的数据结构通常用于线性表如数组的表示。它有助于我们在计算机程序中存储和操作一系列数据元素例如整数、字符、对象等。在顺序存储结构中元素按照它们的逻辑顺序在内存中依次排列这种存储方式使得元素的访问非常高效因为我们可以通过索引快速定位任何元素。 一、目标
本节课要实现承上启下的一个非常重要的类SeqList当我们实现了他我们才会去实现我们具体的StaticList和DynamicList所以他是非常重要的。那么我们上节课也已经介绍了实现流程如果不会的同学可以去看看上节课
二、SeqList实现要点
SedList 设计要点
抽象类模板存储空间的位置和大小由子类完成实现顺序存储结构线性表的关键操作 (增,删,查,等)提供数组操作符方便快速获取元素 那么我们可以抽象出下面这个类
template typename T
class SeqList :public ListT
{T* m_array;//存储位置由子类申请int m_length;//数组长度public:bool insert(const T e);bool insert(int i, const T e);bool remove(int i);bool set(int i, const T e);bool get(int i, T e) const;int length() const;void clear();T operator[](int i);T operator[](int i)const;virtual int capacity() const 0;
};三、SeqList函数实现
3.1 get函数
顺序存储结构的元素获取操作
判断目标位置是否合法
bool ret ((0 i) (i m_length));让我们来解释一下
(0 i) 意味着 i 必须大于或等于0因为在大多数编程中位置通常从0开始编号所以不能小于0。
(i m_length) 意味着 i 必须小于线性表的长度 m_length。这是因为线性表中的位置索引不能超过线性表的总元素个数。
这两个条件一起的意思是我们需要确保 i 不仅大于等于0还要小于线性表的长度这样我们才能访问线性表中有效的位置。如果 i 不满足这两个条件那么访问它可能导致越界错误这是一种非常常见的编程错误因此需要进行这样的合法性检查以防止程序出现问题。
将目标位置作为数组下标获取元素 因为我们这是原生数组所以直接使用下标操作即可
e m_array[i];总体代码如下
bool get(int i, T e) const
{bool ret ((0 i) (i m_length));if (ret){e m_array[i];}return ret;
}3.2 set函数
顺序存储结构的元素设置操作
判断目标位置是否合法
bool ret ((0 i) (i m_length));让我们来解释一下
(0 i) 意味着 i 必须大于或等于0因为在大多数编程中位置通常从0开始编号所以不能小于0。
(i m_length) 意味着 i 必须小于线性表的长度 m_length。这是因为线性表中的位置索引不能超过线性表的总元素个数。
这两个条件一起的意思是我们需要确保 i 不仅大于等于0还要小于线性表的长度这样我们才能访问线性表中有效的位置。如果 i 不满足这两个条件那么访问它可能导致越界错误这是一种非常常见的编程错误因此需要进行这样的合法性检查以防止程序出现问题。
将目标位置作为数组下标把参数设置进去 因为我们这是原生数组所以直接使用下标操作即可
m_array[i] e;总体代码如下
bool set(int i, const T e)
{bool ret ((0 i) (i m_length));if (ret){m_array[i] e;}return ret;
}3.3 insert函数
带2个参数的insert
顺序存储结构的元素插入操作 1.判断目标位置是否合法
bool ret ((0 i) (i m_length)); // 1ret ret (m_length capacity()); // 10 i 确保目标位置 i 不小于0因为位置通常是从0开始计数的。 i m_length 保证目标位置 i 不超过线性表的当前长度以免越界。 m_length capacity() 确保线性表的长度没有超过它的容量以防止插入元素导致溢出。 这两个步骤合在一起就是在确认插入的位置 i 是一个有效、合法的位置不会导致数组越界或者超过线性表的容量限制。
为什么是i m_length呢 拿出你的手是不是一般有5个手指那现在有一支笔要放到你手指中间有几种方式 有6种所以需要im_length
2.将目标位置之后的所有元素后移一个位置
for(int pm_length-1; pi; p--) // n, 0
{m_array[p 1] m_array[p];
}循环从线性表的最后一个元素开始一直到目标位置 i。 m_array[p 1] m_array[p] 将每个元素向后移动一个位置给插入的元素腾出空间。 这个步骤是为了给新元素腾出位置确保插入操作不会覆盖掉原有的元素。通过将目标位置之后的元素都向后移动一个位置为新元素腾出了插入的空间。这是线性表顺序存储结构中插入操作的一部分确保插入后的线性表仍然是有序、没有元素遗漏的。
3.将新元素插入目标位置 4…线性表长度加 1
总体代码如下
bool insert(int i, const T e)
{bool ret ((0 i) (i m_length));ret ret (m_length capacity());if (ret){for (int p m_length - 1; p i; p--){m_array[p 1] m_array[p];}m_array[i] e;m_length;}return ret;
}带一个参数的insert
那么这个函数设计出来干什么的呢 其实就是方便我们尾插入的。
所以我们怎么实现他呢 我们直接调用我们实现的2个参数的insert且在位置的参数写上m_length其意义就为尾插入
总体代码如下
bool insert(const T e)
{insert(m_length, e);
}3.4 remove函数
顺序存储结构的元素删除操作 1判断目标位置是否合法
bool ret ((0 i) (i m_length));0 i 确保目标位置 i 不小于0因为位置通常是从0开始计数的。 i m_length 保证目标位置 i 不超过线性表的当前长度以确保删除的位置是有效的。 这个步骤用于检查删除操作是否在合法的范围内进行以防止删除不存在的元素或者越界。
2将目标位置后的所有元素前移一个位置
for(int pi; pm_length-1; p) // n - 1{m_array[p] m_array[p1];}循环从目标位置 i 开始一直到线性表的倒数第二个元素m_length-1位置。 m_array[p] m_array[p1] 将每个元素向前移动一个位置覆盖掉目标位置上的元素。 这个步骤是为了删除操作。通过将目标位置之后的元素都向前移动一个位置可以覆盖掉要删除的元素相当于将它从线性表中删除掉。删除后线性表中的元素仍然是连续的没有间隙而且长度减少了一个元素。
3线性表长度减 1
总体代码如下
bool remove(int i)
{bool ret ((0 i) (i m_length));if (ret){for (int p i 1; p m_length-1; p){m_array[p] m_array[p 1];}m_length--;}return ret;
}3.5 clear函数
那么我们的clear操作是干什么的呢 就是清空所有元素。
那么怎么实现呢 可能有人知道调用remove函数一个一个去删除。 那么这样的时间就会消耗更多。
我们不妨回到insert函数里面看看
在insert的实现中有这样一行代码我们可以找到insert判断的条件的小技巧直接把m_length设置0 那么我们是不是就变成初始状态了所以就可以这样实现
bool ret ((0 i) (i m_length));总体代码如下
void clear()
{m_length 0;
}3.6 下标运算符重载函数
无const版本
我们的实现非常简单和我们的get函数类似只不过是我们需要在参数范围错误的时候抛出相应的异常即可
T operator[](int i)
{if ((0 i) (i m_length)){return m_array[i];}elseTHROW_EXCEPTION(IndexOutOfBoundsException, Parameter i is invalid...);
}const版本
其实我们的const和非const是一样的代码我们完全可以直接复制过来但是为了代码的复用性我们可以这样写
T operator[](int i)const
{return const_castSeqListT(*this)[i];
}我们使用了const_cast去除本类的const属性使他变成了一个普通的对象然后我们使用[]运算就会调用我们没有const的下标重载运算符了
3.7 length函数
int length() const
{return m_length;
}总结
顺序存储结构是一种在计算机编程中常见的数据结构它允许我们有效地存储和操作一系列数据元素。通过使用数组或向量等数据结构我们可以实现顺序存储结构的基本操作如插入、删除、查找和遍历。这种存储方式在许多应用中都非常有用例如列表、栈、队列等。了解顺序存储结构的抽象实现有助于我们更好地理解和应用数据结构的概念。希望本文能够帮助您更好地理解顺序存储结构的基本原理和应用。
