数据结构--线性表的顺序存储结构
admin
2023-07-26 03:20:10
0

一 线性表的本质和操作

线性表的表现形式主要有以下几个方面
1 零个或多个数据元素组成的集合
2 数据元素在位置上是有序排列的
3 数据元素的个数是有限的
4 数据元素的类型必须相同
线性表的抽象定义是具有相同的n(n>=0)个数据元素的优先序列(a0,a1......an)

二 线性表的性质

a0为线性表的i的一个元素,只有一个后继
an-1为线性表的最后一个元素,只有一个前驱
除去这两个元素外的其他元素ai既有前前驱,又有后继
直接支持逐项访问和顺序存取

三线性表的一些常用操作

1将元素插入线性表
2将元素从线性表中删除
3获取目标位置处元素的值
4设置目标位置处元素的值
5获取线性表的长度
6清空线性表

template 
class List :public Object
{//Object为顶层父类
  protected:
     List(const List&);
     List& operator=(const List&);//避免赋值操作
    public:
        List(){};
        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,const T&e)=0;//获取值
        virtual int length()const=0;//获取长度
        virtual void clear()=0;//清空操作
}

四 线性表的顺序存储结构的实现
思路:可以用一维数组来实现顺序存储结构
存储空间 *T array
当前的长度
int length**

a.顺序存储结构的元素插入操作
1.判断目位置是否合法
2.将目标位置之后的所有元素后移一个位置
3.将新元素插入目标位置
4.线性表的长度+1
简单的图示
数据结构--线性表的顺序存储结构
代码的实现部分

inset (int i,const T&e)
{
    bool ret=((0<=i)&&(ii;p--)
        {
            array[p+1]=arrray[p];//将目标位置后的元素后移一位
        }
        array[i]=e;//将元素插入
        length++;//线性表长度加1
    }
    return ret;
}

b.顺序存储结构的元素删除操作
1.对位置进行判断是否合法
2.将目标位置后的所有元素前移一个位置
3.线性表的长度减1
实现代码如下
简单的图示
数据结构--线性表的顺序存储结构

remove(int i,const T&e)
{
    bool ret=((o<=i)&&(i<=length));
    ret=ret&&((length+1)<=capacity());//对位置进行判断是否合法

    if(ret)
    {
        for(int p=i;p

c.元素的设置以及获取
1判断目标位置是否合法
2.将目标位置作为数组下标对元素进行操作
实现代码如下

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

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

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

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

d.其他的操作(清除及获取长度)
实现代码如下

        int length()const
        {
            return length;
        }

        void clear()
        {
            length=0;
        }

完整的代码如下

include "List"
include "Object"

namespace MyLib
{
    template
    class SeqList :public List
    {
        protected:
            T* array;
            int length;
        public:
            bool insert(int i,const T&e)
        {
            bool ret=((0<=i)&&(i<=m_length));

            ret=ret&&(m_length=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);
        }

        /*删除操作
         1.判断目标是否合法
         2.将目标位置后的所有元素前移一个位置
         3.线性表长度减1
        */
        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;//纯虚h函数,由子类重写
    };
}

相关内容

热门资讯

我在没有空调的巴黎,感受世纪热... 最近半个月,我几乎每天都能收到好友Capucine发来的吐槽信息。“床是烫的,风扇吹出来的风也是烫的...
千万粉MCN放“黑料”敲诈明星... 6月29日,记者从广东公安获悉,近日,在公安部网安局和广东省公安厅网安总队的直接指挥下,河源市公安局...
辽宁葫芦岛一居民楼突发爆炸,已... 警情通报2026年6月29日7时11分,葫芦岛市消防救援局指挥中心接到报警,位于葫芦岛市南票区九龙街...
商都十二载,一轮焕新彰 郑州... 时光荏苒,初心如磐。为庆祝郑州绿地JW万豪酒店入驻中原12周年,酒店于城市之巅的JW花园隆重举办“夏...
做完数学题,韩国队回家了 随着刚果(金)逆转乌兹别克斯坦晋级美加墨世界杯淘汰赛,韩国球员心里绷了好几天的那根弦,“啪”的一下断...
军队、公安、司法、消防类院校2... 6月29日,河南省教育考试院公布河南省2026年军队院校、公安院校、司法类院校、中国消防救援学院的招...
国家体育总局政策法规司原副司长... 2026年6月29日,北京市第一中级人民法院依法公开宣判国家体育总局政策法规司原副司长胡光宇贪污案,...
鹤壁市人大常委会任免名单发布 鹤壁市人民代表大会常务委员会任免名单(2026年6月26日鹤壁市第十二届人民代表大会常务委员会第三十...
自由职业者也能评职称了?郑州出... 无论你是短剧演员还是服装设计师,无论你从事工程系列工作还是新型职业农民,只要是符合条件的“自由职业者...
河南省“社保通”服务平台上线 ... 河南日报讯 (全媒体记者 郭兵)想知道自己的养老金账户有多少钱?想快捷打印参保凭证?有社保疑问不知道...