线性表的本质、操作及顺序存储结构(六)-创新互联
我们说到线性表,可能好多人还不太理解。那么我们举个例子来说,在幼儿园中,老师们总会让小朋友以同样的派对秩序出行,这个例子的本质就是线性表。
10年积累的网站设计制作、成都网站设计经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先做网站后付款的网站建设流程,更有夏河免费网站建设让你可以放心的选择与我们合作。那么线性表(List)的表现形式是怎样的呢?符合以下几个特征:1、零个或多个数据元素组成的集合;2、数据元素在位置上是有序排列的;3、数据元素的个数是有限的;4、数据元素的类型必须是相同的。那么线性表的抽象定义是怎么定义的呢?线性表是具有相同类型的 n( ≥ 0 ) 个数据元素的有限序列。如下
下来我们来看看 List 的本质:1、a0为线性表的第一个元素,只有一个后继;2、an-1为线性表的最后一个元素,只有一个前驱;3、除 a0和 an-1外的其他元素 ai,既有前驱又有后继;4、直接支持逐项访问和顺序存取。下面我们来看看线性表一些常用操作:a> 将元素插入线性表;b> 将元素从线性表中删除;c>获取目标位置处元素的值;d>设置目标位置处元素的值;d> 获取线性表的长度;e>清空线性表。
线性表在程序中表现为一种特殊的数据类型。定义如下
#ifndef LIST_H #define LIST_H #include "Object.h" namespace DTLib { template < typename T > class List : public Object { public: List() {} virtual bool insert(const T& e) = 0; virtual bool insert(int i, const T& e) = 0; virtual bool remove(int i) = 0; virtual bool set(int i, const T& e) = 0; virtual bool get(int i, T& e) const = 0; virtual int length() const = 0; virtual void clear() = 0; }; } #endif // LIST_H
下面我们来看看顺序存储的定义:线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表中的数据元素。如下
那么我们该如何设计呢?可以使用一维数组来实现顺序存储结构,存储空间:T* m_array;当前长度: int m_length;定义如下
template < typename T > class SeqList : public List{ protected: T* m_array; int m_length; //// }
那么顺序存储结构的元素获取操作怎样来实现呢?一是判断目标位置是否合法,二是将目标位置作为数组下标获取元素。定义如下
bool SeqList::get(int i, T& e) const { bool ret = ((0 <= i) && (i < m_length)); if( ret ) { e = m_array[i]; } return ret; }
顺序存储结构的元素插入示例如下
bool SeqList::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; }
顺序存储结构的元素删除操作:1、判断目标位置是否合法;2、将目标位置后的所有元素前移一个位置;3、线性表长度减一。删除示例如下
bool SeqList::remove(int i) { bool ret = ((0 <= i) && (i < m_length)); if( ret ) { for(int p=i; p 我们完成了以上的几个重要操作之后,我们来看看 SeqList 处于一个什么样的位置,如下图所示
那么这便是一个顺序存储结构线性表的抽象实现了。在 SeqList 设计时,我们要只有以下几点:1、抽象类模板,存储空间的位置和大小由子类完成;2、实现顺序存储结构线性表的关键操作(增、删、查等);3、提供数组操作符,方便快速获取元素。那么它的抽象定义如下:
template < typename T > class SeqList : public List{ protected: T* m_array; // 顺序存储空间 int m_length; // 当前线性表长度 public: 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 是怎么写的
SeqList.h 源码
#ifndef SEQLIST_H #define SEQLIST_H #include "List.h" #include "Exception.h" namespace DTLib { template < typename T > class SeqList : public List{ protected: T* m_array; int m_length; public: 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; } bool insert(const T& e) { return insert(m_length, e); } bool remove(int i) { bool ret = ((0 <= i) && (i < m_length)); if( ret ) { for(int p=i; p &>(*this))[i]; } virtual int capacity() const = 0; }; } #endif // SEQLIST_H main.cpp 源码
#include#include "Seqlist.h" using namespace std; using namespace DTLib; int main() { SeqList * l; return 0; } 经过编译,编译时通过的,说明我们已经完成了 SeqList 抽象类的实现了。接下来我们思考下,在前面的 SeqList 的实现中,我们在它的下面还有 StaticList 和 DynamicList 的两个子类,那么我们该如何去实现它们呢?StaticList 和 DynamicList 的差异在哪里?是否可以将 DynamicList 作为 StaticList 的子类实现呢?通过对线性表的学习,总结如下:1、线性表是数据元素的有序并且有限的集合,并且线性表中的数据元素必须是类型相同的;2、线性表可用于描述派对关系的一系列问题;3、线性表在程序中表现为一种特殊的数据类型;4、线性表在 C++ 中表现为一个抽象类。
标题名称:线性表的本质、操作及顺序存储结构(六)-创新互联
URL标题:http://myzitong.com/article/eohsg.html