线性表的本质、操作及顺序存储结构(六)

发布时间:2020-10-09 16:33:06 作者:上帝之子521
来源:网络 阅读:911

        我们说到线性表,可能好多人还不太理解。那么我们举个例子来说,在幼儿园中,老师们总会让小朋友以同样的派对秩序出行,这个例子的本质就是线性表。

        那么线性表(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<T>
{
protected:
    T* m_array;
    int m_length;
    ////
}

        那么顺序存储结构的元素获取操作怎样来实现呢?一是判断目标位置是否合法,二是将目标位置作为数组下标获取元素。定义如下

bool SeqList<T>::get(int i, T& e) const    
{
    bool ret = ((0 <= i) && (i < m_length));

    if( ret )
    {
        e = m_array[i];
    }

    return ret;
}

        顺序存储结构的元素插入示例如下

bool SeqList<T>::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<T>::remove(int i)
{
    bool ret = ((0 <= i) && (i < m_length));

    if( ret )
    {
        for(int p=i; p<m_length-1; p++)
        {
            m_array[p] = m_array[p+1];
        }

        m_length--;
    }

    return ret;
}

        我们完成了以上的几个重要操作之后,我们来看看 SeqList 处于一个什么样的位置,如下图所示

线性表的本质、操作及顺序存储结构(六)

        那么这便是一个顺序存储结构线性表的抽象实现了。在 SeqList 设计时,我们要只有以下几点:1、抽象类模板,存储空间的位置和大小由子类完成;2、实现顺序存储结构线性表的关键操作(增、删、查等);3、提供数组操作符,方便快速获取元素。那么它的抽象定义如下:

template < typename T >
class SeqList : public List<T>
{
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<T>
{
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<m_length-1; p++)
            {
                m_array[p] = m_array[p+1];
            }

            m_length--;
        }

        return ret;
    }

    bool set(int i, const T& e)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if( ret )
        {
            m_array[i] = e;
        }

        return ret;
    }

    bool get(int i, T& e) const
    {
        bool ret = ((0 <= i) && (i < m_length));

        if( ret )
        {
            e = m_array[i];
        }

        return ret;
    }

    int length() const
    {
        return m_length;
    }

    void clear()
    {
        m_length = 0;
    }

    T& operator[] (int i)
    {
        if( (0 <= i) && (i < m_length) )
        {
            return m_array[i];
        }
        else
        {
            THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid ...");
        }
    }
    T operator[] (int i) const
    {
        return (const_cast<SeqList<T>&>(*this))[i];
    }

    virtual int capacity() const = 0;
};

}

#endif // SEQLIST_H

 

main.cpp 源码

#include <iostream>
#include "Seqlist.h"

using namespace std;
using namespace DTLib;

int main()
{
    SeqList<int>* l;

    return 0;
}

        经过编译,编译时通过的,说明我们已经完成了 SeqList 抽象类的实现了。接下来我们思考下,在前面的 SeqList 的实现中,我们在它的下面还有 StaticListDynamicList 的两个子类,那么我们该如何去实现它们呢?StaticListDynamicList 的差异在哪里?是否可以将 DynamicList 作为 StaticList 的子类实现呢?通过对线性表的学习,总结如下:1、线性表是数据元素的有序并且有限的集合,并且线性表中的数据元素必须是类型相同的;2、线性表可用于描述派对关系的一系列问题;3、线性表在程序中表现为一种特殊的数据类型;4、线性表在 C++ 中表现为一个抽象类。

推荐阅读:
  1. 线性表(1):线性表顺序存储结构的php实现
  2. 数据结构--线性表的顺序存储结构

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

线性表 顺序存储结构

上一篇:php初始化方法怎么实现

下一篇:虚拟主机怎样安装.net

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》